技术摘要：对抗性核 Bandit 中的近最优遗憾

1. 问题表述

本文解决了对抗性核 Bandit问题，这是对抗性线性 Bandit 的推广，其中损失函数属于再生核希尔伯特空间（RKHS）。

• 设定：在每一轮 $t \in [T]$ 中，学习器从有限动作集 $\mathcal{X} \subset \mathbb{R}^d$ 中选择一个动作 $x_t$。同时，一个不可知（oblivious）对手在 RKHS $\mathcal{H}$ 中选择一个向量 $w_t$。
• 损失：学习器遭受损失 $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$，其中 $\Phi: \mathcal{X} \to \mathcal{H}$ 是与对称正定核 $K$ 相关的特征映射。
• 反馈：学习器仅观察到标量损失 $\ell_t(x_t)$，而非向量 $w_t$ 或完整的损失函数。
• 目标：最小化相对于事后最佳固定动作 $x^*$ 的期望遗憾 $R_T$：
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• 假设：对手是有界的（$\|w_t\|_{\mathcal{H}} \le B$），且核是有界的（$K(x,x) \le 1$）。关键在于，与 Chatterji 等人 [2019] 的先前工作不同，对手不被限制为秩一损失（即 $w_t$ 不必具有 $\Phi(z_t)$ 的形式）；$w_t$ 可以是 $\mathcal{H}$ 中任意范数有界的元素。

2. 方法论与算法

作者提出了一种基于**指数权重（Exp2）**的算法，并针对无限维特征空间进行了适配。核心挑战在于，当特征映射位于无限维 RKHS 中时，由于协方差算子的特征值趋于零，线性 Bandit 中标准的基于重要性加权的估计量会变得无界。

为克服这一困难，作者引入了两项关键改进：

1. 正则化重要性加权估计量：
   算法不使用经验协方差算子 $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$ 的逆，而是使用岭正则化版本 $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$。估计量定义为：
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   这种正则化确保了即使 $\Sigma_t$ 的特征值接近零，估计量仍保持有界。然而，这会引入系统性偏差：$\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$。

2. 显式偏差校正项：
   为了补偿正则化偏差，算法构建了一个校正后的损失代理 $\hat{\ell}_t(x)$：
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   其中校正项为 $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$。

   • 机制：该校正项直接源自闭式偏差表达式。它作为偏差的点态上界，确保损失代理的期望值对比较器（即最佳固定动作）而言低估了真实损失。这种结构选择保证了遗憾分解中比较器侧的残差为非正，仅留下可控制的学习器侧残差。

3. 探索策略：
   算法维护一个分布 $p_t$，它是当前指数权重分布 $q_t$ 与固定探索分布 $\nu_G$ 的混合。探索分布通过正则化 G-最优设计进行选择，以确保有效维度得到控制。

3. 主要贡献

• 算法设计：提出了一种原则性算法，将指数权重与正则化估计量及显式偏差校正项相结合。该方法避免了 Chatterji 等人 [2019] 所要求的限制性秩一对手假设。
• 基于有效维度的遗憾分析：作者推导出了依赖于核的有效维度 $d^*(\lambda)$ 的遗憾界，定义为：
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• 移除秩一假设：该框架允许任意有界的 RKHS 损失，与之前依赖需要秩一约束的基于投影估计量的工作相比，显著拓宽了适用范围。

4. 主要结果

本文建立了如下形式的遗憾界：
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
其中 $d^*(\lambda)$ 捕捉了核的复杂度。该速率与已知的随机核 Bandit 问题的最优速率相匹配（忽略对数因子）。

特定核速率：

• Matérn$(\nu, d)$ 核：对于 $\mathbb{R}^d$ 上具有平滑度 $\nu$ 的 Matérn 核，有效维度产生的遗憾界为：
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  这优于 Chatterji 等人 [2019] 之前的已知最佳速率 $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$，并与并行工作 [Iwazaki, 2026] 的下界相匹配（忽略对数因子）。值得注意的是，之前的速率在 $\nu < d/2$ 时甚至不是次线性的，而新界始终是次线性的。
• 平方指数（SE）核：该界恢复了近最优的 $\tilde{O}(\sqrt{T})$ 速率，与 Chatterji 等人 [2019] 的结果一致，但无需秩一限制。
• 一般特征值衰减：
  • 多项式衰减（$\mu_j \le C j^{-\beta}$）：实现 $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$。
  • 指数衰减（$\mu_j \le C e^{-\beta j}$）：实现 $R_T = \tilde{O}(\sqrt{T})$。

5. 意义与主张

本文声称缩小了对抗性与随机核 Bandit 性能之间的差距。具体而言：

• 最优性：推导出的速率与已知的随机核 Bandit 最优速率（例如通过 SupKernelUCB 或贝叶斯优化方法）相匹配（忽略对数因子）。
• 理论进展：通过移除秩一对手假设，结果适用于更广泛、更现实的对抗环境类，其中损失函数是 RKHS 中任意有界元素。
• 与先前工作的比较：该工作在 Matérn 核和一般多项式衰减方面改进了 Chatterji 等人 [2019] 的结果，提供了更紧的界，这些界在先前界不满足次线性条件的情况下是次线性的。
• 并行工作：作者承认 Iwazaki [2026] 的独立并行工作，该工作使用密切相关的方法（带有正则化估计量和偏差校正的指数权重）取得了类似结果。本文指出了问题设定上的细微差异（例如不可知对手与自适应对手、特定的复杂度度量），但断言核心算法和分析贡献本质上是等价的。

本文结论认为，所提出的方法为对抗性核 Bandit 问题提供了近最优解，通过正则化和显式偏差校正有效地处理了无限维特征空间的挑战。