Batched Kernelized Bandits: Refinements and Extensions

1. 问题背景 (Problem Setup)

本文研究的是**批处理核化多臂老虎机（Batched Kernelized Bandits）**问题，这是黑盒优化在噪声反馈和批处理约束下的一个变体。

• 核心设定：
  • 目标：优化一个未知的黑盒函数 $f(x)$，该函数定义在域 $\mathcal{X}$ 上，且属于一个再生核希尔伯特空间（RKHS），其范数有界（$\|f\|_k \le \Psi$）。
  • 反馈：观测值带有噪声（$y_t = f(x_t) + z_t$）。
  • 批处理约束：观测值不是即时反馈的，而是以**批次（Batches）**的形式揭示。算法将时间视界 $T$ 划分为 $B$ 个批次。在第 $i$ 个批次中，算法选择一组点 $N_i$ 进行查询，但只有在第 $i$ 个批次结束时才能观察到所有 $N_i$ 个点的反馈，并据此决定下一个批次的策略。
• 两种模式：
  1. 固定批次（Fixed Batches）：所有批次的大小 $N_i$ 和结束时间 $t_i$ 在开始前预先确定。
  2. 自适应批次（Adaptive Batches）：批次大小可以根据前一个批次的观测结果动态调整（即 $t_i$ 在 $t_{i-1}$ 结束后决定）。
• 目标：最小化累积遗憾（Cumulative Regret） $R_T = \sum_{t=1}^T (f(x^*) - f(x_t))$，其中 $x^*$ 是函数的全局最大值点。

2. 方法论 (Methodology)

本文主要基于 BPE (Batched Pure Exploration) 算法进行改进，并引入了新的理论分析框架。

2.1 算法改进：优化的 BPE

• 原算法 (Li and Scarlett, 2022)：使用特定的批次大小增长策略（$N_i \approx \sqrt{T N_{i-1}}$），证明了 $B = O(\log \log T)$ 个批次即可达到近最优遗憾。
• 本文改进：
  • 提出了更通用的批次大小定义：$N_i = \min \{ \lceil T^{1-a i} \rceil, \dots \}$，其中参数 $a \in (0, 1)$ 控制批次增长的速度。
  • 关键发现：通过调整 $a$，可以在批次数量 $B$ 和累积遗憾 $R_T$ 之间找到更优的平衡。特别是对于 Matérn 核，当 $a$ 接近 $\frac{\nu}{2\nu+d}$ 时，可以用更少的批次达到相同的遗憾界。
  • 消除冗余因子：移除了原分析中遗憾界里不必要的 $B$ 因子（即从 $O(B \cdot \sqrt{T\gamma_T})$ 优化为 $O(\sqrt{T\gamma_T})$ 量级，仅保留对数项）。

2.2 理论下界：自适应批次的分析

• 挑战：现有的下界分析通常假设批次大小是固定的。对于自适应批次，由于算法可以根据观测动态改变策略，传统的“坏批次”构造方法不再直接适用。
• 创新方法：
  • 引入了**测度变换（Change of Measure）**技术。
  • 构造了 $B$ 组“困难函数”集合 $\{ \mathcal{F}_i \}_{i=1}^B$，每组对应一种“第 $i$ 个批次是坏批次”的情况。
  • 利用全变差距离（Total Variation Distance）将不同函数分布下的概率联系起来，证明了即使算法可以自适应选择批次大小，其最小最大遗憾（Minimax Regret）的缩放阶数与固定批次基本一致。

2.3 扩展：鲁棒设置 (Robust Setting)

• 定义：考虑对抗性扰动。目标是找到一个点 $x$，使得在任意扰动 $\delta$（满足距离约束 $d(x, x+\delta) \le \xi$）下，函数值 $f(x+\delta)$ 依然尽可能高。
• 算法：提出了 Robust-BPE 算法。
  • 在每一批次中，不仅探索候选点 $x$，还探索其扰动邻域 $x + \Delta_\xi(x)$。
  • 消除规则基于扰动后的置信区间（UCB/LCB）：如果某点的扰动后 UCB 低于其他点的扰动后 LCB，则将其剔除。
• 结果：证明了鲁棒设置下的累积遗憾界与非鲁棒设置相同，且简单遗憾（Simple Regret）显著优于之前的工作（Bogunovic et al., 2018）。

3. 主要贡献与结果 (Key Contributions & Results)

3.1 算法上界 (Upper Bounds)

• 最优批次数量：不仅确定了 $B = O(\log \log T)$ 是充分的，还给出了包含常数因子的精确界限（在 $1+o(1)$ 意义下最优）。
• 遗憾界优化：
  • 对于高斯核（SE）和 Matérn 核，证明了使用优化的批次策略，累积遗憾为：
    $$R_T = O\left( (\Lambda + \sqrt{\log \log \log T}) \sqrt{T \gamma_T} \right)$$
    其中 $\Lambda$ 包含 RKHS 范数和置信度项，$\gamma_T$ 是最大信息增益。
  • 去除了 $B$ 因子：相比 Li and Scarlett (2022) 的结果，移除了遗憾界中显式的 $B$ 乘数项。
  • Matérn 核的适应性：对于 Matérn 核，当参数 $a$ 选择得当时，所需的批次数量 $B$ 可以更少，且随着问题难度增加（$\nu/d$ 变小），所需批次反而减少。

3.2 算法无关下界 (Lower Bounds)

• 自适应批次下界：首次为自适应批次大小的核化老虎机建立了下界。
• 结论：
  • 对于 SE 核：$E[R_T] = \Omega(B^{-2} T^{\frac{1-\eta}{1-\eta B}} (\log T)^{\dots})$
  • 对于 Matérn 核：$E[R_T] = \Omega(B^{-(2\eta+1)} T^{\frac{1-\eta}{1-\eta B}})$
  • 其中 $\eta$ 取决于核类型（SE 为 $1/2$，Matérn 为 $\frac{\nu}{2\nu+d}$）。
• 意义：证明了自适应批次虽然在概念上更灵活，但在最小最大遗憾的缩放阶数上，并没有比固定批次带来本质上的提升（只要 $B$ 在 $O(\log \log T)$ 范围内）。

3.3 鲁棒性扩展

• 鲁棒 BPE：提出了处理对抗扰动的算法。
• 性能：
  • 累积遗憾界与非鲁棒情况一致。
  • 简单遗憾：$r_\xi(x^{(T)}) = O^*(\sqrt{\gamma_T/T})$，去除了之前工作中 $\sqrt{\gamma_T}$ 的额外因子，达到了近最优界。

4. 实验验证 (Experiments)

• 在合成数据（2D 网格）上进行了实验，对比了原始 BPE 算法（固定批次策略）与本文提出的参数化批次策略（不同 $a$ 值）。
• 结果：
  • 对于 SE 核，调整 $a$ 接近 0.5 时表现与原始算法相当。
  • 对于 Matérn 核（$\nu=1.5, 2.5$），使用更小的 $a$ 值（如 0.4）可以在减少批次数量（例如从 4 批减至 3 批）的同时，获得更低的累积遗憾。这验证了理论中关于“更少的批次即可达到最优遗憾”的结论。

5. 意义与影响 (Significance)

1. 理论完善：填补了自适应批次下界分析的空白，证明了自适应性在核化老虎机问题中并不能突破最小最大遗憾的界限，为算法设计提供了理论边界。
2. 实践指导：通过精确化批次数量的常数因子和移除冗余的 $B$ 因子，为实际应用（如超参数调优、A/B 测试、临床试验）提供了更优的批次调度策略。特别是在并行计算资源受限（批次少）的场景下，本文提出的策略能以更少的批次达到更高的优化效率。
3. 鲁棒性扩展：将批处理优化扩展到了对抗性鲁棒场景，并给出了更紧的简单遗憾界，增强了算法在安全关键应用中的可靠性。

总结：这篇论文在理论深度（下界分析、常数优化）和应用广度（鲁棒性、自适应批次）上对批处理核化多臂老虎机问题做出了重要推进，确立了 $B = O(\log \log T)$ 批次下的近最优遗憾界，并证明了自适应策略在此类问题中的局限性。