技术摘要：用于具有遗憾保证的贝叶斯优化的最优点方差缩减法

问题陈述

贝叶斯优化（BO）是优化昂贵的待评估黑盒函数的一种框架。虽然单步前瞻（one-step lookahead）方法（如熵搜索 ES 和知识梯度 KG）通过考虑全局效用，已展示出卓越的经验性能，但它们面临两个主要局限性：

1. 计算不可行性： 这些方法通常依赖于复杂的、计算成本高昂的嵌套优化或启发式近似（例如，针对给定最优输入或最大值的条件分布）。
2. 缺乏理论保证： 尽管这些方法在实践中非常有效，但其理论特性仍不完善。具体而言，单步前瞻 BO 方法的有限样本遗憾保证在很大程度上仍是一个开放问题，且现有的分析往往依赖于并不普遍成立的假设（如后验方差的次模性）。

方法论

本文提出了**最优点方差缩减法（Optimal-Point Variance Reduction, OVR）**及其正则化变体 Regularized OVR (ROVR)。这些是旨在最小化最优输入 $x^*$ 处的后验方差（或标准差）的单步前瞻 BO 方法。

核心机制

与通过最大化互信息（需要对条件分布进行启发式近似）的 ES 类方法不同，OVR 直接针对最优点处的期望后验标准差。OVR 的采集函数（AF）定义为：
$$\alpha_t(x) = \mathbb{E}_{x^*} [\sigma_t(x^* | x) \mid D_{t-1}]$$
其中 $\sigma_t(x^* | x)$ 是给定在 $x$ 处的新观测后，最优点 $x^*$ 处的后验标准差。

关键技术特征：

• 解析变换： 作者表明，可以解析地消除对观测值 $y_x$ 的期望，从而将采集函数简化为仅对最优点 $x^*$ 的期望。
• 蒙特卡洛（MC）近似： 由于 $x^*$ 的分布难以处理，OVR 使用 MC 采样来近似该期望。它生成 $M_t$ 条后验样本路径 $g_t \sim p(f \mid D_{t-1})$，优化每条路径以找到样本最优值 $x^*_{t,m}$，并计算采集函数为：
  $$\hat{\alpha}_t(x) = \frac{1}{M_t} \sum_{m=1}^{M_t} \sigma_t(x^*_{t,m} \mid x)$$
• 正则化 (ROVR)： 为了确保探索并实现理论收敛，ROVR 引入了一个正则化项：
  $$\hat{\alpha}_t(x) = \frac{1}{M_t} \sum_{m=1}^{M_t} \sigma_t(x^*_{t,m} \mid x) - c_t \sigma_{t-1}(x)$$
  其中 $c_t \geq 0$ 是正则化参数。该项惩罚低不确定性，从而促进选择具有高不确定性的输入（探索）。

实现细节

• 后验采样： 该方法采用路径条件化（pathwise conditioning）和随机傅里叶特征近似（Wilson 等人，2020，2021）来高效生成近似后验样本路径。
• 无启发式： 与预测性 ES (PES)、最大值 ES (MES) 或联合 ES (JES) 不同，OVR 不需要针对给定最优输入或最大值的条件分布进行启发式近似。

核心贡献

本文做出了三个主要贡献：

1. 提出 OVR 和 ROVR： 作者引入了易于实现的单步前瞻 BO 方法，这些方法通过最小化最优输入处的后验方差来实现。这些方法仅依赖于后验采样和 MC 近似，避免了 PES、MES 和 JES 所需的启发式近似。
2. 一致的 MC 估计误差界限： 本文提供了输入域上 MC 采集函数估计的理论一致误差界限。
   • 对于离散域，误差界限为 $O(\sqrt{\log(|X|/\delta)/M_t})$。
   • 对于连续域，在核函数的 Lipschitz 连续性假设下，误差界限为 $O(\sqrt{d \log(M_t)/M_t})$。这确立了 $M_t = \Omega(\log(t/\epsilon)/\epsilon^2)$ 个样本足以达到 $\epsilon$ 精度。
3. 遗憾保证： 本文证明了 ROVR 实现了消失的贝叶斯期望简单遗憾（BSR）上界。该界限与现有其他 BO 方法的结果相当：
   $$\text{BSR}_T \leq \sqrt{\frac{C_1 \beta_T \gamma_T}{T}} + O\left(\frac{\beta_T^{1/2}}{T}\right) + O\left(\frac{1}{T c_T}\right) + O\left(\frac{1}{T} \sum_{t=1}^T \frac{\log M_t}{\sqrt{M_t} c_t}\right)$$
   其中 $\gamma_T$ 是最大信息增益，$\beta_T$ 取决于定义域大小和光滑度。

实验结果

作者在合成函数、基准函数（Ackley, Hartmann）以及来自 Olympus 框架的仿真器上评估了 OVR 和 ROVR。

• 性能： 在不同噪声水平（$\sigma^2 = 10^{-4}$ 和 $\sigma^2 = 1$）的合成实验中，OVR 和 ROVR 始终优于或等同于包括 EI、UCB、TS、PIMS、JES 和 MES 在内的最先进方法。
• 鲁棒性： 与 JES 和 MES 不同（由于启发式修改，随着样本数增加往往会陷入局部最优），OVR 和 ROVR 表现出鲁棒的性能，其性能会随着更多 MC 样本的使用而趋于稳定或提升。
• 对比： 这些方法在单步前瞻策略（MES, JES）中表现出更优越的性能，验证了无需启发式近似的方差缩减方法的有效性。

意义与主张

本文声称 OVR 和 ROVR 弥合了单步前瞻策略的实际效能与理论证明之间的鸿沟。

• 理论进展： 通过提供一个不依赖于次模性假设（这些假设经常被违反）的单步前瞻方法的消失遗憾界限，这项工作解决了 BO 理论文献中的一个重要空白。
• 实用价值： 这些方法在计算上是高效的，仅需要后验采样和 MC 近似，这使得它们比现有的单步前瞻方法（如 KG 或 ES 变体）更具可行性。
• 局限性： 作者承认，单步前瞻方法的累积遗憾分析仍然是一个开放问题，因为获得瞬时遗憾界限比基于多臂老虎机算法（如 UCB 或 TS）要困难。此外，目前的分析忽略了后验采样近似引入的误差，这将在未来工作中进行探讨。

总之，本文提出了一种具有理论依据、计算高效的单步前瞻 BO 方法，该方法在避免了困扰现有基于熵的方法的启发式近似的同时，实现了消失的简单遗憾。