面向上下文赌博机的图降维：近似平滑与噪声特征空间下的结构特定遗憾界

# 面向上下文老虎机的图降维：近似光滑性与含噪特征空间下的结构特定遗憾界  
来源：https://arxiv.org/html/2606.27917  

###### 摘要  
图结构臂的上下文老虎机出现在推荐、引文检索和社交广告中，其中图上相连的臂倾向于共享奖励信号。标准降维会忽略这种结构，导致探索代价增加d/k倍。我们提出GraphDR-LinUCB，该方法将臂特征投影到图的低频谱子空间，并在所得k维空间中运行线性UCB。我们首次证明了基于谱投影的上下文老虎机具有Õ(k√T)遗憾界，将维度依赖从d降至k；通过扰动分析将此结果扩展到噪声图情形，并给出显式的奖励-光滑性不匹配代价和图估计误差惩罚。我们的核心理论发现是：高频奖励成分不需要承担最坏情况下的线性T惩罚；其实际代价取决于其在已选路径上的实现影响，而非其总能量。子空间之间的简单谱比较（Γk）能预测在给定数据集上哪种降维器更优，无需任何拟合阈值即可正确预测六个真实数据集中的五个结果。在合成基准测试和六个真实数据集（MovieLens、Amazon、LastFM、ogbn-arxiv、MIND）上，GraphDR-LinUCB相较于全维度LinUCB将累积遗憾降低了15倍，并在六个数据集中有五个优于其他图感知方法；唯一失败的情况正是图的谱子空间与奖励未对齐的场景。

## 引言  
具有图结构臂的上下文老虎机广泛存在于部署系统中[25]：通过社交链接相连的用户、通过共同购买或类型组织的产品、以及通过引文链接的文档。在每种设置中，奖励函数通常在图上具有光滑性（邻近节点共享期望奖励），而图谱方法正是为捕捉这种结构而设计的。自然的问题是，将臂特征投影到低频拉普拉斯特征空间，将探索维度从d降至k≪d，是否能在全特征空间操作的基础上带来真正的遗憾改进。答案并不明显。标准误设线性老虎机理论[23,12]对任何奖励偏离投影子空间的行为收取一个最坏情况下的偏差惩罚，该偏差与νkT成正比，可以迅速压倒√T的探索增益。先前的图老虎机工作要么通过沿边传播信息[13,5]，要么通过图Laplacian软正则化[38]来回避此问题；两者都没有执行真正降低探索维度的硬投影。频谱老虎机[34]在图频率基下操作，但未分析含噪特征空间或量化不完美图光滑性的代价。硬图谱投影在老虎机中的理论可行性及其实际条件仍未得到刻画。此外，硬投影只有在奖励在图上是光滑的（这是数据的属性，而非算法的属性）时才有用，因此结构性证伪测试至关重要：投影到节点置换后的特征空间会保持维度不变但破坏图-奖励对齐，因此任何真正的增益都必然消失。

为解决这些挑战，我们研究GraphDR-LinUCB（图降维）：将每个臂的特征向量投影到底部k个拉普拉斯特征空间，并在所得k维空间中运行LinUCB[1,3]，每次实验均附带图洗牌对照作为结构性证伪测试。我们证明了精确子空间和Davis–Kahan鲁棒遗憾界，开发了用实现图量取代最坏情况误设惩罚的结构特异性残差分析，并引入了一种谱选择规则，用于在图降维器和竞争降维器之间进行选择，无需拟合任何阈值。

#### 贡献。
- •有限样本与鲁棒界。我们证明，在精确图光滑性下，GraphDR-LinUCB 实现 Õ(k√T) 遗憾，将维度依赖从 d 降至 k。通过 Davis–Kahan 论证，将其扩展到近似光滑性和噪声图观测，通过谱间隙 Δk 和光滑性尾部 ζk 显式给出特征空间估计误差的遗憾代价。
- •结构特异性残差定理。我们证明，高频残差不需要以最坏情况下的线性 T 速率支付。其代价由两个实现图量——残差杠杆 SRLT 和候选集残差宽度 CRWT——决定，当残差在图上是良性的时，这些量是次线性的。一种可实现的基于预实验的变体使得该界可从数据中计算。
- •谱选择规则。我们定义子空间捕获裕度 Γk = ‖Uk⊤θ‖₂² - ‖P⊤θ‖₂²，这是一个无参数谱统计量，无需任何拟合阈值即可预测哪种降维器更好地与奖励对齐。我们将其与理论推导的诊断量 Gk 和标量尾部 ζk 一起评估。
- •实证评估。我们在随机块模型和随机几何图合成数据上验证该方法，每次配置均附带图洗牌对照，并在六个真实图老虎机数据集（涵盖推荐、新闻和引文：MovieLens-100k/1M、Amazon、LastFM、MIND-small、ogbn-arxiv）上进行评估。

## 相关工作
#### 线性上下文老虎机。
LinUCB 框架[7,3,1]通过椭圆置信集和自归一化鞅浓度[24]实现 d 维线性奖励的 Õ(d√T) 遗憾，并由 Dani 等人[9]建立了匹配的 Ω(d√T) 下界。在 UCB 之外，汤普森采样[6,32]提供了一种贝叶斯替代探索策略。

#### 误设线性老虎机。
当奖励仅在所选特征上近似线性时，遗憾会引入额外的偏差项。最坏情况分析[23,12]支付一个关于时间范围线性且与误设水平成比例的包络，即使在温和误设下，该代价也会迅速主导 √T 探索项。KL 正则化上下文老虎机的尖锐时间范围依赖性分析[40]在正则化下强化了这些最坏情况包络，尽管残差的图结构性形式仍未得到检验。

#### 图老虎机。
老虎机的在线聚类[13]通过共享相邻臂之间的估计值，在用户图上传播奖励信息。Laplacian 正则化 LinUCB[38]在岭目标中加入图光滑性惩罚，使估计器偏向于在图上缓慢变化的函数。Mannor 和 Shamir[26]的图反馈老虎机设置将相邻臂的奖励作为侧信息观测；最近的工作将其扩展到相似臂图[30,17]和干扰结构[18]。Wang 等人[36]结合低秩结构和图 Laplacian 正则化，通过软惩罚处理矩阵上下文老虎机；本文则使用硬谱投影并推导出显式的谱间隙遗憾界。

#### 频谱老虎机。
频谱老虎机[34]为图上的光滑收益函数设计算法，其遗憾由反映收益在低频图坐标中集中度的谱有效维度所控制。该算法在全图频率基下操作，每个特征值赋予一个光滑性权重，而非在固定维度 k 处进行硬截断。

#### 图信号处理与谱嵌入。
作为低频图坐标的 Laplacian 特征向量源于图信号处理[33]，并支撑着 Laplacian 特征映射[4]和谱聚类[27,35]。我们的贡献不是一种新的嵌入方法，而是第一个将硬谱投影与探索代价联系起来的虎头机遗憾分析。

#### 模型选择与自适应 k。
套接方法[2]实现了与基学习器池中最佳算法竞争的遗憾，更广泛的上下文老虎机模型选择已通过平滑元算法[28]得到研究，为自适应 k 的 GraphDR 提供了可行路径；一个紧致的图特定定理留待未来工作。

#### 老虎机中的降维。
随机投影[39]在运行线性老虎机之前降低特征维度，遗憾依赖于投影后维度。双线性老虎机[20]通过两阶段子空间探索方法利用低秩奖励结构，实现 Õ((d1+d2)^{3/2}√(rT)) 遗憾，紧致的二到无穷子空间恢复方法[19]为矩阵老虎机改进了这些界。最近的工作处理非平稳子空间：Khosravi and Huo[21]证明了分段平稳低秩线性老虎机的 Õ(r√T) 动态遗憾，Dai 等人[8]在模型路由设置下为具有低秩专家的对抗性上下文老虎机获得了秩相关遗憾。在子空间方法之外，高维线性老虎机的矩阵草图[37]显示，在重谱尾部下需要自适应草图大小以避免线性遗憾。在多智能体和分布式设置中，通信图的谱间隙直接控制合作老虎机算法的遗憾[29,31]。上述工作均未使用图结构性子空间作为特征投影器，也未将虎头机遗憾与奖励-图谱间隙联系起来。本文提供了第一个这样的分析，刻画了何时将臂特征投影到 Laplacian 特征空间可以减少探索代价，以及何时不能。

## 设置与算法
#### 图与拉普拉斯矩阵。
设 G 是一个无向图，对称归一化 Laplacian 为 L = I - D^{-1/2} A D^{-1/2}，其特征值满足 0 = λ₁ ≤ λ₂ ≤ … ≤ λ_n ≤ 2。我们假设边权非负且无孤立节点，必要时添加自环以确保 D_ii > 0。我们进一步假设存在正的特征间隙 Δ_k = λ_{k+1} - λ_k > 0，使得底部 k 个特征空间定义良好。令 E_k ∈ ℝ^{d×k} 为特征空间低频子空间的一组标准正交基，投影算子 Π_k = E_k E_k^⊤。在节点臂、独热特征情况下，d = n 且 E_k = U_k，其中 U_k 收集了 k 个最低频拉普拉斯特征向量。在整个理论分析中，U_k *包含*常值特征向量 u₁（在连通图上 λ₁ = 0）；实验则转移到 u₂, …, u_{k+1} 并明确报告该约定。分析针对节点臂设置 d = n，x_{t,a} = e_a，E_k = U_k。

#### 老虎机交互。
在每个回合 t，学习器观察到有限臂集 A_t，其中臂 a ∈ A_t 具有特征 x_{t,a} ∈ ℝ^d。选择 a_t 后，获得奖励 y_t = x_{t,a_t}^⊤ θ^⋆ + η_t，其中 θ^⋆ ∈ ℝ^d 未知，η_t 是条件次高斯噪声。在实践中，干净的 Laplacian 可能不可用。我们令 L̂ 表示观测或估计的 Laplacian，Ê_k ∈ ℝ^{d×k} 为其底部 k 个特征空间的一组标准正交基，并设置 Π̂_k = Ê_k Ê_k^⊤ 和 P̂ = Ê_k^⊤。投影后的特征为 z_{t,a} = Ê_k^⊤ x_{t,a} ∈ ℝ^k。

算法 1 GraphDR-LinUCB
输入：观测 Laplacian L̂；臂特征 oracle x_{t,a}；维度 k；正则化参数 λ > 0；置信度序列 (β_t)_{t≥1}
输出：选取的臂 a₁, …, a_T
1: 计算 L̂ 的底部 k 个标准正交特征基 Ê_k ∈ ℝ^{d×k}
2: 初始化 V₁ ← λ I_k, b₁ ← 0 ∈ ℝ^k
3: for t = 1, 2, …, T do
4: 计算 α̂_t ← V_t^{-1} b_t
5: 观测候选集 A_t；投影每个臂：z_{t,a} ← Ê_k^⊤ x_{t,a}，对所有 a ∈ A_t
6: 选取 a_t ← arg max_{a∈A_t} [ z_{t,a}^⊤ α̂_t + β_t ‖z_{t,a}‖_{V_t^{-1}} ]
7: 观测奖励 y_t
8: V_{t+1} ← V_t + z_{t,a_t} z_{t,a_t}^⊤；b_{t+1} ← b_t + z_{t,a_t} y_t
9: end for

#### 算法。
GraphDR-LinUCB（算法1；流程见图1）在 k 维投影空间中运行普通的线性 UCB；投影 P̂ 是它与标准 LinUCB 的唯一区别。

图 G → Laplacian L → 基 Ê_k → 投影 z = Ê_k^⊤ x → 在 ℝ^k 中运行 LinUCB → 选取 a_t → 残差 r_{⟂,k} = (I - Π̂_k) θ^⋆