Spectral bandits for smooth graph functions with applications in recommender systems

技术摘要：平滑图函数的谱带体

问题表述
本文解决了一个多臂老虎机问题，其中臂对应于已知图 $G=(V, E)$ 的节点，而拉动一个臂的期望收益由定义在图上的平滑函数决定。在此设定下，奖励函数 $f$ 被假设为图拉普拉斯算子 $L$ 的特征向量的线性组合。具体而言，如果 $Q$ 包含 $L$ 的特征向量作为列，则节点 $v$ 的奖励为 $f_\alpha(v) = \langle x_v, \alpha^* \rangle$，其中 $x_v$ 是 $Q$ 的第 $v$ 行，$\alpha^*$ 是一个未知的权重向量。

核心挑战在于，当节点数量 $N$（因此特征空间的维度 $D=N$）非常大，甚至可能超过学习过程的时间范围 $T$（即 $T < N$）时，标准的线性老虎机算法通常使其遗憾值随环境维度 $D$ 或臂的数量 $K$ 缩放，在这种情形下表现会不佳。本文假设真实函数是“平滑的”，这意味着与较大特征值对应的特征向量所关联的系数 $\alpha^*$ 较小，而与较小特征值对应的系数则较大。

方法论
作者提出了两种算法，利用图的谱性质来实现随“有效维度” $d$ 而非全维度 $N$ 缩放的遗憾界。

1. 有效维度 ($d$)： 本文基于正则化拉普拉斯算子 $\Lambda = \Lambda_L + \lambda I$ 的特征值增长，提出了有效维度 $d$ 的形式化定义。$d$ 被定义为满足 $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$ 的最大整数。该指标捕捉了问题中“相关”维度的数量，在实际世界的图中，该数量通常远小于 $N$。

2. 谱 UCB (SpectralUCB)： 该算法是对 LinUCB 算法的改进。它利用谱基对 $\alpha^*$ 采用正则化最小二乘估计器。关键在于，它使用有效维度 $d$ 而非环境维度 $D$ 来构建预测奖励的置信界。该算法选择最大化上置信界的节点：$\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$，其中 $c_t$ 依赖于 $d$。

3. 谱汤普森采样 (SpectralTS)： 该算法利用贝叶斯方法。它维护关于 $\alpha^*$ 的后验分布，建模为高斯分布 $N(\hat{\alpha}_t, v^2 V_t^{-1})$。先验协方差被设定为正则化拉普拉斯算子 $\Lambda$，编码了平滑函数（低特征值分量）更可能的假设。在每一步，从后验分布中抽取一个样本 $\tilde{\alpha}$，并选择最大化 $x_v^T \tilde{\alpha}$ 的节点。

主要贡献与理论结果

• 新颖框架： 这是首个将收益为图上平滑函数的老虎机问题形式化的工作，架起了流形学习/半监督学习与在线学习之间的桥梁。
• 遗憾界： 本文证明了 SpectralUCB 和 SpectralTS 均实现了随有效维度 $d$ 缩放的累积遗憾界：
  • SpectralUCB： $O(d\sqrt{T \ln T})$。
  • SpectralTS： $O(d\sqrt{T \ln N})$。
    这些界具有重要意义，因为 $d$ 通常远小于 $N$，使得算法即使在 $T < N$ 时也能表现良好。
• 计算效率： 作者强调了 SpectralTS 的计算优势。虽然 SpectralUCB 需要计算所有 $N$ 个臂的置信界（在最坏情况下 $D=N$ 时，每步复杂度为 $O(N^3)$），但 SpectralTS 仅需采样一个参数向量并寻找最大值，这可以更高效地完成（每步 $O(N^2)$）。

实验结果
作者在合成数据集和真实世界数据集上评估了这些算法：

• 合成数据： 使用 Barabási-Albert 图（$N=250$），其中真实奖励函数是前 3 个最平滑特征向量的线性组合。在 $T < N$ 的情形下，SpectralUCB 和 SpectralTS 在累积遗憾方面显著优于其线性对应算法（LinUCB 和 LinearTS）。SpectralTS 还表现出更快的计算时间。
• 真实世界数据： 实验在 MovieLens 数据集（$N=2019$ 部电影）上进行，将用户偏好建模为基于电影评分构建的相似性图上的平滑函数。结果与合成发现一致：谱算法比线性老虎机基线实现了更低的累积遗憾。本文指出，对于数千种物品的用户偏好，仅需数十次节点评估即可学习到一个良好的估计器。

意义与主张
本文主张，通过谱分解利用图上函数的平滑性，可以在不使遗憾随节点数量表现不佳的情况下，解决具有大量臂的在线学习问题。有效维度 $d$ 的引入使得算法能够适应图结构的内在复杂性。该工作 motivated 于基于内容的推荐和社交网络中的定向广告应用，在这些场景中，用户偏好或兴趣倾向于在相连节点间平滑变化。作者强调，他们的方法特别适用于可用交互次数 ($T$) 远少于可用物品数量 ($N$) 的场景。