Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

技术摘要：具有恒定探索强度的时变高斯过程多臂老虎机更紧的遗憾界限

问题设定
本文研究了非平稳环境下贝叶斯优化的问题，其中未知奖励函数 $f_t: S \to \mathbb{R}$ 随时间演化。具体而言，作者考虑了由 Bogunovic 等人 [2016] 引入的时变高斯过程（TV-GP）模型。在此设定下，潜在函数根据由 GP 创新驱动的马尔可夫递归进行演化：
$$f_{t+1}(x) = \sqrt{1-\epsilon} f_t(x) + \sqrt{\epsilon} g_{t+1}(x)$$
其中 $g_t$ 是来自具有核函数 $k_S$ 的空间高斯过程的独立同分布抽样，$\epsilon \in (0, 1]$ 是控制变化速率的漂移参数。目标是最小化累积遗憾 $R_T = \sum_{t=1}^T (f_t(x_t^*) - f_t(x_t))$。与静态设定不同，在此类设定下通常无法实现亚线性累积遗憾；其目标是建立平均遗憾 $R_T/T$ 关于漂移率 $\epsilon$ 的界限。

方法论
作者重新审视了动态设定下的高斯过程上置信界（GP-UCB）算法。标准分析对于 TV-GP 老虎机通常要求探索参数 $\beta_t$ 随时间 $t$ 增长，以在整个时间范围内维持一致的置信界。本文提出了一种不同的分析方法：

1. 局部置信事件： 与依赖于在整个时间跨度内一致成立的单一全局置信事件（这需要随时间增加的 $\beta_t$）不同，该分析为每一轮构建了局部置信事件 $E_t$。
2. 恒定探索参数： 通过利用这些局部事件，作者证明了可以使用恒定的探索参数 $\beta_t \equiv \beta$ 来运行 GP-UCB。
3. 离散化与尾部界限： 证明结合了基于局部置信事件的单轮 UCB 遗憾界以及针对稀有补集事件的算法无关界。这涉及：
   • 大小为 $\tau^d$ 的空间网格离散化。
   • 用于控制离散化误差的导数尾部界限（假设 1）。
   • 函数跨度 $W_t = \sup f_t - \inf f_t$ 的亚高斯集中性。
4. 时间衰减的信息增益： 作者推导出了一个关于时变最大信息增益 $\tilde{\gamma}_T$ 更紧的界限，该增益控制着后验方差之和。他们利用块分解技术将 $\tilde{\gamma}_T$ 与静态信息增益 $\gamma_N$ 及漂移参数 $\epsilon$ 联系起来。

核心贡献与结果

• 恒定探索遗憾界限： 主要理论结果（定理 1）确立了恒定 $\beta$ 的 TV-GP-UCB 的期望累积遗憾界限：
  $$E[R_T] \le \sqrt{C_1 T \beta \tilde{\gamma}_T} + T C_2 + T \delta C_3$$
  该界限对于任何固定的漂移率 $\epsilon > 0$ 均成立，且不需要 $\beta$ 随 $T$ 缩放。
• 更紧的信息增益缩放： 文中推导了一个新的时变信息增益界限。如果静态信息增益满足 $\gamma_N = \tilde{O}(N^q)$，则在持续漂移机制下（即时间跨度 $T$ 超过有效块长度），平均信息增益缩放为：
  $$\frac{\tilde{\gamma}_T}{T} = \tilde{O}\left(\epsilon^{\frac{2(1-q)}{4-q}}\right)$$
  因此，期望平均遗憾缩放为：
  $$\frac{E[R_T]}{T} = \tilde{O}\left(\epsilon^{\frac{1-q}{4-q}}\right)$$
  对于平方指数核（$q=0$），这产生了 $\tilde{O}(\epsilon^{1/4})$ 的平均遗憾。
• 界限建议的探索参数： 分析表明，通过平衡遗憾界限各项所建议的最优恒定 $\beta$（记作 $\beta_{opt}$）与漂移率的反对数呈对数关系：
  $$\beta_{opt} \propto \log(1/\epsilon)$$
  这与以往 $\beta_t$ 独立于 $\epsilon$ 的调度方案形成对比。作者认为，随着漂移减慢（$\epsilon \to 0$），过去的观测值保持信息性的时间变长，从而降低了后验方差；较大的 $\beta$ 通过赋予剩余不确定性更高的权重来补偿这一点。
• 已实现遗憾保证： 本文提供了针对已实现遗憾的后验（post-hoc）和预设置信度保证。在预设置信度设定下，算法可以在使用恒定 $\beta$ 的同时，实现对失败概率 $\omega$ 具有对数依赖性的高概率遗憾界限。
• 采样频率自适应： 该框架提供了一个调整 $\beta$ 的启发式方法，当采样频率发生变化时，若每 $\Delta$ 个时间单位收集一次观测，则有效漂移变为 $\epsilon_\Delta = 1 - (1-\epsilon)^\Delta$，建议的 $\beta$ 随 $\log(1/\epsilon_\Delta)$ 缩放。

意义与主张
本文声称其分析解决了时变 GP 老虎机文献中一个反复出现的局限性：即需要随时间增长的探索调度，这会导致在长周期内性能恶化且难以调优。通过从全局置信事件转向局部置信事件，作者展示了可以利用恒定探索参数来维持严格的性能保证。

其意义在于：

1. 改进的长周期缩放： 移除了在领先遗憾项中通过对时间进行并集界限处理而经常引入的 $\sqrt{\log T}$ 因子。
2. 显式的漂移依赖性： 为探索参数如何随环境漂移率 $\epsilon$ 而缩放（而非仅仅随时间 $t$）提供了理论基础。
3. 更紧的界限： 与之前的工作（如 Bogunovic 等人 [2016], Imamura 等人 [2020]）相比，提供了更紧的时变信息增益速率。

实证验证
作者通过在 2D 域上使用平方指数核的模拟研究支持了其理论发现。他们使用卡尔曼滤波实现来高效处理时变后验，模拟了 $T=10,000$ 轮的过程。结果证实了：

• 广泛范围内的恒定 $\beta$ 值表现优于随时间增长的对数启发式方法。
• 经验最优常数 $\hat{\beta}_{opt}$ 随 $-\log(\epsilon)$ 线性增加，验证了理论预测 $\beta_{opt} \propto \log(1/\epsilon)$。

局限性与未来方向
作者指出，其分析依赖于由马尔可夫漂移模型诱导的特定几何时间核。将这些保证扩展到更一般的时间核仍是一个开放性问题。此外，目前的分析假设漂移参数 $\epsilon$ 是已知的；在 $\epsilon$ 未知时在线调整 $\beta$ 是一个建议的未来研究方向。论文还承认，恒定探索结果是一种“正向漂移”结果，在 $\epsilon=0$ 时无法恢复标准的静态亚线性遗憾保证，后者需要单独的分析。