🤖 machine learning

Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

本文通过提出一种带有标准当前最优解的变体，解决了噪声高斯过程 bandit 优化中期望改进收敛性的开放问题，该变体在无需先验知道再生核希尔伯特空间范数或噪声参数的情况下实现了 $\mathcal{O}(\gamma_T\sqrt{T})$ 的遗憾界，并进一步引入了一种比现有对应算法收敛更快的改进算法。

原作者： Hung Tran-The, Sunil Gupta, Santu Rana, Svetha Venkatesh

发布于 2026-04-28

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Hung Tran-The, Sunil Gupta, Santu Rana, Svetha Venkatesh

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一片广阔而雾气弥漫的山脉中找到最高的山峰。你无法看到整张地图，而且每当你迈一步去检查高度时，你的 altimeter（高度计）给出的读数都会略微颤抖、带有噪声。这就是高斯过程贝叶斯优化（Gaussian Process Bandit Optimization）所面临的问题：在只能获得带有噪声的局部信息时，寻找复杂问题的最佳解。

为了解决这个问题，你需要一种策略。最流行的策略被称为期望提升（Expected Improvement, EI）。将 EI 想象成一位徒步者，他会问：“如果我移动到这片新区域，与我迄今为止看到的最佳地点相比，我的视野会好多少？”

问题：那位“带噪声”的徒步者

长期以来，科学家们知道这种“期望提升”策略在实践中行之有效，但他们无法从数学上证明为什么它有效，尤其是在高度计读数带有噪声的情况下。

主要的障碍在于“当前最佳值”（incumbent）——即徒步者记忆中当前的最佳地点。

在一个完美的世界（无噪声）中，徒步者只需记住迄今为止找到的最高峰。这个数值只会上升，因此很容易追踪。
在充满噪声的世界里，“最佳”地点可能仅仅是测量中的一个幸运故障。如果徒步者将这个有故障的数值作为基准，数学推导就会变得混乱并失效。之前的尝试试图通过让徒步者知晓关于山脉的秘密隐藏数值（例如地形究竟有多平滑，或高度计有多不稳定）来解决这个问题。但在现实世界中，你通常并不知道这些秘密。

解决方案：一种新的行走方式

本文的作者 Hung Tran-The 及其团队提出了一种处理这种“带噪声徒步者”问题的新方法。

1. 标准修复方案（GP-EI）
他们证明，你可以使用一个标准的、简单的基准（即从地图中得出的最佳预测平均高度，而非带有噪声的原始读数），并仍能保证徒步者最终找到山峰。

结果：他们从数学上证明了该方法能够收敛（找到山峰），并提供了一个“遗憾界”（regret bound）。用徒步术语来说，“遗憾”是指你未能每一步都站在真正山峰上而错过的总高度。他们证明了该徒步者的遗憾增长得足够缓慢，因此是高效的。
额外优势：与之前的方法不同，他们的徒步者不需要知道山脉的秘密“平滑度”或高度计的“不稳定性”。他们只需开始行走即可。

2. 超快修复方案（Improved-GP-EI）
他们意识到，对于非常复杂的山脉（高维情况），第一种方法可能仍然耗时过长，因为徒步者会反复检查同一区域太多次。
因此，他们创造了Improved-GP-EI。

类比：想象徒步者将山脉划分为越来越小的网格盒子。他们不再一次性检查整座山脉，而是专注于一个盒子，绘制其地图；如果该盒子看起来有希望，他们就将该盒子分割成更小的盒子以进行更近距离的观察。如果某个盒子看起来无趣，他们就忽略它。
结果：这种“分而治之”的策略使徒步者速度快得多。他们证明了这种新方法比第一种方法更快地找到山峰，并且仍然不需要那些关于山脉的秘密参数。

证明：为何信任这位徒步者？

这篇论文充满了数学推导，但其核心逻辑如下：

他们将徒步者的错误（遗憾）分解为两部分：地图预测中的误差和噪声测量中的误差。
他们使用了一个涉及“方差”（即地图的不确定性程度）的巧妙技巧。他们表明，随着徒步者的探索，地图中的不确定性会以一种可预测的方式自然缩小。
通过证明这些不断缩小的不确定性之和保持在可控范围内，他们证明了徒步者不会永远漫无目的地游荡。

试驾

为了确保他们的理论不仅仅是一个漂亮的数学把戏，他们在计算机模拟中进行了测试：

合成山脉：他们创建了虚假的、复杂的数学景观（如 Hartmann 函数和 Ackley 函数），并让他们的算法去搜寻顶峰。
竞争：他们将他们的"Improved-GP-EI"徒步者与其他著名的徒步者（如 GP-UCB 和标准 GP-EI）进行了比较。
结果：他们的 Improved-GP-EI 徒步者比其他徒步者更快、更可靠地找到了山峰，特别是在“秘密参数”（如确切的噪声水平）未知的情况下。

总结

简而言之，这篇论文针对一种流行但在数学上尚不稳固的策略（期望提升）进行了修复，修补了其理论缺陷，并构建了一个更快、更稳健的版本，无需用户了解问题的隐藏细节。它证明了即使面对带有噪声的数据，一种聪明且贪婪的策略也能在不依赖水晶球的情况下，高效地找到最佳解。

以下是论文《高斯过程 Bandit 优化中期望改进算法的遗憾界》的详细技术总结。

1. 问题陈述

本文解决了高斯过程（GP）Bandit 优化问题，具体是在非贝叶斯设定下（即函数是固定但未知的，且位于再生核希尔伯特空间 RKHS 中）。目标是根据含噪观测值 $y_t = f(x_t) + \epsilon_t$ ，顺序选择点 $x_t$ 以最大化昂贵的黑盒函数 $f(x)$ 。

性能通过累积遗憾 $R_T = \sum_{t=1}^T (f(x^*) - f(x_t^+))$ 来衡量，其中 $x^*$ 是全局最优解， $x_t^+$ 是算法在第 $t$ 次迭代前报告的最佳点。

核心挑战：
尽管期望改进（EI）算法因其简单性而成为贝叶斯优化的流行启发式方法，但其在含噪设定下的理论收敛性质一直是一个未解之谜。

在无噪设定中，“当前最佳值”（incumbent） simply 是观测到的最大值，具有单调性。
在含噪设定中，当前最佳值通常定义为GP 预测均值（ $\mu_t^+$ ）的最大值，或含噪观测值（ $y_t^+$ ）的最大值。
与无噪情况不同，GP 预测均值 $\mu_t^+$ 随时间并非单调的。这种缺乏单调性的特点使得标准的理论分析（依赖于通过当前最佳值的单调性来界定遗憾）变得极其困难。以往的研究要么需要知道未知参数（如 RKHS 范数界 $B$ 和噪声次高斯性 $R$ ），要么使用需要昂贵全局优化步骤的非标准当前最佳值。

2. 方法论

作者提出了两种主要算法来解决这些理论和实践上的差距。

A. 使用标准当前最佳值的 GP-EI

第一项贡献是对标准 GP-EI 算法的严格分析，其中当前最佳值定义为观测点上 GP 预测均值的最大值：
$\xi_t = \mu_t^+ = \max_{x_i \in D_{t-1}} \mu_{t-1}(x_i)$

采集函数： 算法通过最大化期望改进来选择下一个点 $x_t$ ：
$\alpha_{EI}(x) = \mathbb{E}[\max\{0, f(x) - \mu_t^+\} | D_t]$
该值使用函数 $\rho(u, v) = u\Phi(u/v) + v\phi(u/v)$ 以闭式形式计算。
时变尺度： 为了处理噪声并确保在不了解 RKHS 范数（ $B$ ）或噪声参数（ $R$ ）的情况下收敛，算法使用时变尺度参数 $\omega_t = \sqrt{\gamma_{t-1} + 1 + \ln(1/\delta)}$ ，其中 $\gamma_t$ 是最大信息增益。
关键理论创新： 作者通过利用方差函数的单调性（ $\sigma_t(x)$ 随 $t$ 增加而减小）克服了 $\mu_t^+$ 的非单调性。他们分解了瞬时遗憾，并利用这一方差性质对“改进项”之和进行界定，这是一种此前未以这种方式应用于 GP Bandit 优化的技术。

B. Improved-GP-EI

为了解决标准 GP-EI 的局限性（具体而言，即遗憾界对于 Matérn 核并不总是次线性的，且尺度参数 $\omega_t$ 增长过快，导致不必要的探索），作者提出了Improved-GP-EI。

灵感来源： 改编自 $\pi$ -GP-UCB 算法（Janz 等人，2020）。
分区策略： 将搜索空间划分为超立方体（覆盖）。每个超立方体仅使用局部数据拟合一个独立的 GP。
全局尺度： 它不使用时变的 $\omega_t$ ，而是使用固定的全局尺度 $\omega_T = \sqrt{\ln(T)\ln\ln(T)}$ ，该尺度仅呈多对数增长。
机制： 在每一步，算法通过最大化特定超立方体（包含当前最佳候选者的那个）内的期望改进来选择点，从而有效地将优化局部化。

3. 主要贡献

标准 GP-EI 的首个理论保证：
本文首次证明了带有标准当前最佳值（ $\xi = \mu_t^+$ ）的 GP-EI 在含噪设定下是收敛的。
- 遗憾界： 累积遗憾被界定为 $O(\gamma_T \sqrt{T})$ 。
- 参数独立性： 关键在于，该算法不需要知道 RKHS 范数界（ $B$ ）或噪声的次高斯性参数（ $R$ ），而这些参数在现实世界应用中通常是未知的。
Improved-GP-EI 算法：
一种新变体，实现了针对 Matérn 核的更快收敛速率。
- 遗憾界： 对于平滑度 $\nu > 1$ 的 Matérn 核，遗憾为 $\tilde{O}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$ 。这对于所有 $\nu > 1$ 和 $d \geq 1$ 都是次线性的，改进了标准 GP-EI 的局限性。
- 效率： 通过使用分区策略和多对数尺度参数，它避免了以往方法中看到的方差尺度的快速增长，减少了不必要的探索。
新颖的证明技术：
作者引入了一种证明策略，通过利用 GP 方差函数的递减单调性来界定改进项之和，从而处理 GP 预测均值当前最佳值的非单调性。

4. 结果

理论结果

标准 GP-EI： 实现了 $O(\gamma_T \sqrt{T})$ 的遗憾。对于平方指数（SE）核，这是次线性的。对于 Matérn 核，需要 $2\nu > d$ 才能是次线性的。
Improved-GP-EI： 实现了更紧的遗憾界，对于所有 $\nu > 1$ 都是次线性的。它达到了与 $\pi$ -GP-UCB 相同的遗憾速率，但移除了对 $B$ 和 $R$ 的了解要求。

实证结果

作者在合成函数（Hartmann3, Shekel, Hartmann6, Ackley）和由 RKHS 空间生成的函数上测试了他们的算法。

性能： Improved-GP-EI 始终优于标准 GP-EI、Modified-GP-EI 和最先进的 $\pi$ -GP-UCB。
鲁棒性： 与需要启发式调整未知参数（ $B$ 和 $R$ ）且在这些参数猜测错误时表现不佳的 $\pi$ -GP-UCB 不同，Improved-GP-EI 关于这些界是无参数的，并显示出更优越的稳定性。
效率： Improved-GP-EI 中的分区策略降低了计算复杂度。例如，在 Hartmann3 上，Improved-GP-EI 每次迭代的平均运行时间为 1.21 分钟，而标准 GP-EI 为 1.37 分钟；随着视野（horizon）的扩大，由于核矩阵求逆规模的减小（逆的是较小的局部矩阵而不是一个全局矩阵），这一差距进一步拉大。

5. 意义

本文解决了高斯过程 Bandit 期望改进理论分析中长期存在的一个开放性问题。

弥合理论与实践： 它证明了最流行的启发式方法（EI）在含噪环境中在理论上是合理的，且不需要关于函数平滑度或噪声水平的“神谕”知识。
实际适用性： 通过消除对未知参数（ $B$ 和 $R$ ）的依赖，所提出的算法可立即应用于现实世界场景（如机器人技术、超参数调整），在这些场景中，这些值很难或无法在事前估计。
算法进步： Improved-GP-EI 提供了一种鲁棒的、无参数的 UCB 类方法替代方案，证明了基于 EI 的策略在实现最优遗憾速率的同时，对核选择和参数不确定性具有更强的鲁棒性。