Near-Optimal Regret in Adversarial Kernel Bandits¶

会议: NeurIPS 2026
arXiv: 2605.26585
领域: 优化/理论
关键词: 对抗核老虎机、指数权重算法、正则化重要性加权估计、偏差消除补偿项、有效维度

一句话总结¶

针对非线性、无穷维再生核希尔伯特空间（RKHS）下的对抗核老虎机问题，本文提出带有正规化损失估计器与显式偏差消除项的指数权重算法，在移除秩一对手假设的同时，首次达到了与随机核老虎机已知下界严格对齐的近最优遗憾界。

研究背景与动机¶

在线决策与老虎机反馈机制是现代强化学习与序贯推荐的核心范式，经典的对抗线性老虎机通过将每轮损失建模为决策向量的线性泛函，取得了成熟且深刻的理论进展。然而，实际应用中的损失表面往往高度复杂且具非线性结构，线性假设构成了严苛的技术瓶颈。为了打破维度与线性假设的束缚，对抗核老虎机框架将损失函数嵌入到再生核希尔伯特空间（RKHS）中，允许潜在无穷维的特征映射，成为建模非平稳与动态非线性在线决策的核心工具。

然而，将决策空间扩展到无穷维 RKHS 会遭遇根本性的估计失效：学习者在每一轮只能观察到所选动作的一个标量损失反馈，若沿用线性老虎机的标准重要性加权估计，无限维协方差算子在核空间中的谱可以任意接近于零，导致常规逆算子产生无界甚至不可逆的估计量方差。先前基准方法（如 Chatterji et al., 2019）通过将 Mercer 特征展开截断到前有限项来强行恢复可逆性，不仅分析中必须强加极不合理的“秩一对手”假设（即对手损失函数必须来自单样本核基），更在常见的多项式特征值衰减核（如高斯过程与贝叶斯优化中应用极广的 Matérn 核）上导致极其松弛的遗憾上界，在低平滑度时甚至无法保证次线性遗憾。

解决该瓶颈的核心矛盾在于：引入谱下界正则化虽然能够压制无穷维特征逆运算导致的方差爆炸，但在对抗非平稳损失环境下会引入结构未知的系统性估计偏差，传统的绝对值放缩会使比较子端产生无法被学习者控制的正累积误差。本文的核心 idea 是：构造带脊正则化的重要性加权核估计量以确保特征有界，并依据闭式正则化偏差设计显式加权补偿项直接抵消比较子端的偏差残差，将对抗核老虎机遗憾严格收敛到核的有效维度。

方法详解¶

整体框架¶

算法的整体运行机制遵循混合探索的指数权重框架（Exp2 范式）。在每轮决策前，学习者基于历史加权经验维持一个主动作分布，并与基于正则化 G-最优实验设计计算出的静态探索分布进行凸组合混合，生成当前轮的实际采样分布并抽取决策动作。在仅观测到单个标量损失后，算法并不直接在无穷维希尔伯特空间中实例化权重向量，而是通过核技巧隐式计算出岭正则化协方差算子下的重要性加权损失预测，并减去依据算子范数精确推导出的点向偏差补偿量。最后，利用该校正损失代理执行指数权重概率更新。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["初始化全局探索分布<br/>正则化 G-最优设计"] --> B["阶段 1：混合分布动作采样<br/>凸组合主分布与探索策略"]
    B --> C["阶段 2：岭正则化重要性加权估计<br/>RKHS 协方差谱下界约束"]
    C --> D["阶段 3：显式偏差抵消补偿项<br/>消除比较子端正向残差"]
    D --> E["阶段 4：隐式核评估与指数权重更新<br/>对偶核逆矩阵乘积迭代"]

关键设计¶

1. 岭正则化重要性加权估计：在无穷维核空间中强制逆协方差谱有界

经典对抗线性老虎机依赖协方差矩阵逆算子构建无偏重要性估计，但在无穷维 RKHS 中，协方差算子 \(\Sigma_t = \mathbb{E}_{\mathbf{x}\sim p_t}[\Phi(\mathbf{x})\Phi(\mathbf{x})^\top]\) 的特征值向零衰减，直接求逆会导致估计量范数剧烈发散。针对这一问题，本设计在协方差算子中引入显式岭参数 \(\lambda > 0\)，定义正则化协方差算子为 \(\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}\)，从而严格保证算子谱的下界不低于 \(\lambda\)。利用标量反馈 \(y_t = \langle \Phi(\mathbf{x}_t), \mathbf{w}_t\rangle_{\mathcal{H}}\)，构造重要性加权损失估计量：

\[\widehat{\mathbf{w}}_t = y_t \cdot (\Sigma_t^\lambda)^{-1}\Phi(\mathbf{x}_t)\]

该构造通过引入受控收缩，牺牲了完全无偏性，其条件期望满足 \(\mathbb{E}[\widehat{\mathbf{w}}_t \mid \mathcal{F}_{t-1}] = (I_{\mathcal{H}} - \lambda (\Sigma_t^\lambda)^{-1})\mathbf{w}_t\)，从而精确导出了闭式偏差算子 \(\lambda (\Sigma_t^\lambda)^{-1}\mathbf{w}_t\)。更重要的是，通过对偶核表示，所有逆算子内积计算均可通过核矩阵 \((K_t + \lambda I_{|\mathcal{X}|})^{-1}\) 封闭完成，彻底避免了在无限维空间中显式维护特征向量的难题。

2. 显式偏差消除补偿项：将比较子端对抗性偏差严格压制为非正残差

当估计量存在固有收缩偏差时，传统后悔界分解会将基准最优动作 \(\mathbf{x}_*\) 处的偏差项以绝对值形式放缩，导致累积项随步数线性发散。为了彻底消除这一隐患，本设计依据柯西-施瓦茨不等式与对手范数上界 \(\|\mathbf{w}_t\|_{\mathcal{H}} \le B\)，针对每个动作点向构建一个由局部马氏距离导出的显式惩罚补偿项：

\[c_t(\mathbf{x}) = B\sqrt{\lambda}\,\|\Phi(\mathbf{x})\|_{(\Sigma_t^\lambda)^{-1}}\]

将估计损失修正为下偏估计损失代理 \(\widehat{\ell}_t(\mathbf{x}) = \langle \widehat{\mathbf{w}}_t, \Phi(\mathbf{x})\rangle_{\mathcal{H}} - c_t(\mathbf{x})\)。在数学机制上，减去 \(c_t(\mathbf{x})\) 确保了该损失代理在条件期望下处处低估真实损失；当对最优比较子 \(\mathbf{x}_*\) 进行展开时，比较子侧的累积误差项 \(- (B_T^{\mathbf{x}_*} + C_T^{\mathbf{x}_*})\) 被该显式下界直接对冲为非正数（\(\le 0\)）。这一关键代数结构将原本不可控的双侧对抗偏差完全转化为学习者侧的单侧残差，为后续借助核有效维度建立界限扫清了障碍。

3. 正则化 G-最优混合探索：实现代理损失绝对有界与学习者方差控制

为了使指数权重算法的对数矩母函数展开成立，修正后的损失代理必须满足严格的有界性条件 \(|\eta \widehat{\ell}_t(\mathbf{x})| \le 1\)。然而纯利用历史分布 \(q_t\) 无法防止未探索方向的协方差逆范数爆炸。为此，本设计在算法初始化时借助凸优化求解正则化 G-最优实验设计分布：

\[\nu_G \in \arg\min_{\nu \in \Delta(\mathcal{X})} \max_{\mathbf{x}\in\mathcal{X}} \|\Phi(\mathbf{x})\|_{(\Sigma(\nu) + (\lambda/\gamma)I_{\mathcal{H}})^{-1}}^2\]

并将每轮抽样策略设定为 \(p_t = (1-\gamma)q_t + \gamma \nu_G\)。由于协方差算子满足 \(\Sigma_t^\lambda \succeq \gamma (\Sigma(\nu_G) + (\lambda/\gamma)I_{\mathcal{H}})\)，每个候选动作在正则化度量下的范数均一致受控于有效维度 \(d_{\mathrm{eff}}(\Sigma(\nu_D), \lambda/\gamma)\)。这一性质不仅保证了单步损失代理在全局范围内绝对值不大于 \(1/\eta\)，同时保证了学习者端累积方差和偏差残差能够以 \(\mathcal{O}(B\sqrt{T d_*(\lambda) \log |\mathcal{X}|})\) 的统一阶数闭合。

实验关键数据¶

主实验¶

论文重点从理论上严格证明了各种经典核在对抗环境下的遗憾上界，并将所得结果与先前对抗核老虎机 SOTA（Chatterji et al., 2019；Takemori & Sato, 2021）以及随机核老虎机的理论最优下界进行系统性对比。

核函数类别	谱衰减/特征假设	先前对抗基准界（Chatterji et al.）	先前无约束对手界（Takemori & Sato）	本文理论上界（Ours）	随机核老虎机已知匹配下界
Matérn(\(\nu, d\))	多项式衰减 \(\nu > 0\)	\(\widetilde{\mathcal{O}}(T^{\frac{2\nu+d}{4\nu}})\)（限秩一对手）	\(\widetilde{\mathcal{O}}(T^{\frac{\nu+d}{2\nu}})\)	\(\mathbf{\widetilde{\mathcal{O}}(T^{\frac{\nu+d}{2\nu+d}})}\)	\(\Omega(T^{\frac{\nu+d}{2\nu+d}})\)
Squared Exp (SE)	指数衰减 \(\mu_j \le C e^{-\beta j}\)	\(\widetilde{\mathcal{O}}(\sqrt{T})\)（限秩一对手）	\(\widetilde{\mathcal{O}}(T^{\frac{1}{2}+\epsilon})\)	\(\mathbf{\widetilde{\mathcal{O}}(\sqrt{T})}\)（无秩一约束）	\(\Omega(\sqrt{T})\)
通用多项式核	谱衰减 \(\mu_j \le C j^{-\beta}, \beta>1\)	\(\widetilde{\mathcal{O}}(T^{\frac{\beta}{2(\beta-1)}})\)（限秩一对手）	未显式给出紧界	\(\mathbf{\widetilde{\mathcal{O}}(T^{\frac{\beta+1}{2\beta}})}\)	\(\Omega(T^{\frac{\beta+1}{2\beta}})\)（不同设定）

消融实验¶

通过对遗憾分解公式中的核心理论组件及不同正则化/偏差消除机制进行消融分析，揭示各模块在控制无穷维遗憾增长时的必要作用。

| 理论构造变体 | 比较子侧偏差残差 | 损失代理有界性 \(|\eta\widehat{\ell}_t| \le 1\) | 遗憾增长阶数（Matérn 示例） | 理论机制失效说明 | |---|---|---|---|---| | 完整机制 (Full) | \(\le 0\)（精确非正抵消） | 满足（G-最优保证） | \(\widetilde{\mathcal{O}}(T^{\frac{\nu+d}{2\nu+d}})\) | 达到近最优，与随机环境匹配 | | 无偏差补偿项 (\(c_t = 0\)) | 无法保证符号，需绝对值放缩 | 满足 | \(\mathcal{O}(T)\)（线性发散） | 比较子累积正偏差破坏次线性收敛 | | 无岭正则化 (\(\lambda = 0\)) | 无偏差但协方差算子不可逆 | 破坏（逆范数在无穷维无界） | \(\infty\)（方差爆炸） | 损失估计器单步方差无界，Exp2 失效 | | 均匀探索代替 G-最优 | \(\le 0\) | 局部极值点可能破坏界限 | 次优或依赖 \(|\mathcal{X}|\) 几何常数 | 缺乏最坏情况杠杆控制，最坏样本点下界失效 |

关键发现¶

Matérn 核的突破性提升：先前技术 Chatterji et al. 在平滑度较小（\(\nu < d/2\)）时，指数 \(\frac{2\nu+d}{4\nu} > 1\)，上界完全丧失次线性保证；本文上界 \(\frac{\nu+d}{2\nu+d} < 1\) 恒成立，且严格对齐随机环境的 minimax 最优下界。
摆脱秩一限制的核心收益：不仅大幅推广了对抗对手的设定范畴（允许任意在 RKHS 范数球内的非线性时变函数），而且理论界没有任何常数恶化，表明正则化偏差控制比基底截断更加本质。

亮点与洞察¶

设计精巧的自对冲偏差消除项：构造的修正项 \(c_t(\mathbf{x})\) 既是马氏距离的对偶度量，又是单步期望偏差的一致上界，直接在指数加权更新内部将最棘手的比较子侧偏差抹平为非正数。
信息增益桥梁的严谨打通：通过贪心极大行列式构造（引理 8），将抽象算子迹定义的有效维度 \(d_*(\lambda)\) 严格连接到经典随机核老虎机中的最大信息增益 \(\bar{\gamma}_T\)，打通了对抗分析与贝叶斯优化文献的桥梁。
对偶核技巧计算落地：尽管形式上定义在无穷维特征空间，全算法的损失估计与 G-最优设计均可通过有限维核 Gram 矩阵逆运算实现，具备严格的代数闭式表达。

局限与展望¶

计算复杂度随动作集规模立方增长：每轮需对 \(|\mathcal{X}| \times |\mathcal{X}|\) 的核矩阵求逆，单步复杂度为 \(\mathcal{O}(|\mathcal{X}|^3)\)，当连续动作空间网格化使得 \(|\mathcal{X}| \approx T^{d/2}\) 时，计算负担极为沉重。
参数选择依赖时限先验：学习率 \(\eta\)、正则化参数 \(\lambda\) 与混合比 \(\gamma\) 的最优设定依赖总步数 \(T\) 和有效维度的先验上界，尚不具备自适应未知时限与未知光滑度的能力。
高概率遗憾界的缺失：当前主定理仅建立了期望遗憾界 \(\mathcal{R}_T\)，在强对抗环境下推导高概率有限时间遗憾保证仍是开放挑战。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次在无秩一限制的对抗核老虎机中设计出近最优算法并闭合了理论下界。
实验充分度: ⭐⭐⭐⭐ 理论分析严密自洽，完整给出了针对各类核谱与有效维度的转化推导，但缺少数值模拟验证。
写作质量: ⭐⭐⭐⭐⭐ 动机阐述深刻，从无穷维逆算子失效到偏差补偿设计的数学逻辑一气呵成。
价值: ⭐⭐⭐⭐⭐ 解决了对抗非线性决策领域多年的悬而未决难题，是核方法与在线学习交叉方向的标志性工作。