Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization¶

会议: NeurIPS 2026
arXiv: 2608.16492
OpenReview: https://openreview.net/forum?id=KXCNleX2pP
领域: 优化/理论
关键词: 高斯过程老虎机、并行贝叶斯优化、延迟反馈、汤普森采样、后悔界分析

一句话总结¶

针对并行与延迟反馈高斯过程老虎机优化，提出基于改进椭圆势计数的理论分析技术，证明批量汤普森采样（GP-BTS）无需经验上低效的初始不确定性采样阶段即可将批大小/延迟参数 $Q$ 从乘性因子降为加性常数项，并在无噪声场景下首次建立收敛速率显著更优的超低后悔界。

研究背景与动机¶

高斯过程（GP）老虎机优化作为黑盒昂贵函数全局极值寻优的核心框架，被广泛应用于材料合成、超参数微调及化学分子设计等科学与工程领域。然而在现代高通量筛选和分布式并行计算集群中，多次函数评估往往并发执行，导致算法必须在尚未获得最近 $Q$ 次查询结果的延迟反馈条件下决定下一步采样点，同时维持采样点之间的空间多样性以避免冗余探索。

面对这种并行与延迟挑战，现有代表性批处理算法（如 GP-BUCB 与 GP-BTS）的理论累积后悔界普遍遭受与批大小或延迟步数 $Q$ 相关的严重乘性恶化。例如经典 GP-BTS 的累积后悔界中包含因子 $\sqrt{Q \gamma_{T/Q} \gamma_T T \ln T}$，当进行大规模并行化（如并发工作节点数 $Q > 100$）时，理论上界会出现剧烈退化。过去为了消除这种乘性恶化，理论界通常需要强制算法在最开始执行多项式阶次数的不确定性采样（Uncertainty Sampling, US）作为预热探索阶段；但这种脱离目标函数优化的纯探索预热阶段在实际应用中极度浪费昂贵的评估预算，优化效率极低。

这种理论推导瓶颈的核心矛盾在于：过去的技术框架（如直接应用 Cauchy-Schwarz 不等式结合标准信息增益界）将滞后后验方差粗暴放大，迫使分析者在“承受乘性 $Q$ 惩罚”与“依赖实践低效的初始 US 阶段”之间二选一。本文旨在打破这一长达十年的分析困境。核心 idea：通过引入基于延迟后验方差阈值切分的扩展椭圆势计数引理，将整个优化时间步划分为至多包含 $O(Q \gamma_T)$ 步的高不确定性子集与占据主体的低不确定性互补子集，从而在无需任何初始不确定性采样预热的前提下，将延迟参数 $Q$ 完全解耦为加性项，并拓展至无噪声设定取得紧致的后悔收敛界。

方法详解¶

整体框架¶

本文针对 $Q$ 步延迟反馈的高斯过程老虎机优化问题，对标准的批量高斯过程汤普森采样（GP-BTS）算法建立全新的理论分析框架。在第 $t$ 步时，算法可用的历史观测数据集仅为 $\mathcal{D}_{t-Q-1} = \{(\boldsymbol{x}_i, y_i)\}_{i=1}^{t-Q-1}$，无法感知最近 $Q$ 步的反馈。算法基于滞后数据集计算后验均值 $\mu_{t-Q-1}(\boldsymbol{x})$ 和核后验协方差 $k_{t-Q-1}(\boldsymbol{x}, \boldsymbol{x}')$，并在离散化网格 $\mathcal{X}_t \subset \mathcal{X}$ 上抽取膨胀方差后的高斯过程样本路径 $g_t \sim \mathcal{G}\mathcal{P}(\mu_{t-Q-1}, \beta_t k_{t-Q-1})$，选取令其最大的点 $\boldsymbol{x}_t$ 作为当前评估输入。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["历史延迟数据集 D_{t-Q-1}<br/>未观测最近 Q 个并发查询结果"] --> B["滞后高斯过程后验构建<br/>计算后验均值与协方差"]
    B --> C["网格抽样与置信膨胀<br/>采样 g_t 选取最大化点 x_t"]
    C --> D["单步后悔与截断后验分解<br/>建立 min{2B, c_t * sigma} 紧致上界"]
    D --> E["时序索引集划分策略<br/>阈值 lambda^2 / Q 切分高低方差步"]
    E -->|高方差集合 T| F["势能计数基数界<br/>总步数严格受限在 O(Q * gamma_T)"]
    E -->|低方差互补集 T^c| G["后验方差比值展开与解耦<br/>紧致信息增益累积和上界 8*lambda^2*gamma_T"]
    F --> H["全局累积后悔收敛界<br/>噪声下 Q 项完全加性化 / 无噪声下超低后悔"]
    G --> H

关键设计¶

1. 单步瞬时后悔的期望截断分解

针对汤普森采样的随机探索特性，以往分析在处理单步瞬时后悔 $\mathbb{E}[f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)]$ 时通常直接放缩为 $\min\{2B, c_t \mathbb{E}[\sigma_{t-Q-1}(\boldsymbol{x}_t)]\}$，这种期望在里层的形式在子集求和时会导致上界乘上 $c_T |\mathcal{T}| = O(\sqrt{\gamma_T \ln T} |\mathcal{T}|)$ 的多余信息增益因子。本文将单步分析精细化，定义饱和集 $\mathcal{S}_t = \{\boldsymbol{x} \in \mathcal{X}_t \mid f([\boldsymbol{x}^*]_t) - f(\boldsymbol{x}) > \beta_t^{1/2}(p_t^{(f)}) (\zeta_t^{1/2}(p_t^{(g)}) + 1) \sigma_{t-Q-1}(\boldsymbol{x})\}$，利用高斯反集中不等式证明汤普森采样落入非饱和集的概率至少为常数 $p/2$（其中 $p = 1 / (4e\sqrt{\pi})$）。在此基础上，本文推导出期望在外层的截断瞬时后悔上界：

\[ \mathbb{E}[f(\boldsymbol{x}^*) - f(\boldsymbol{x}_t)] \leq \frac{2+p}{p} \mathbb{E}\left[\min\left\{2B, c_t \sigma_{t-Q-1}(\boldsymbol{x}_t)\right\}\right] + \frac{B}{N_t} + 2B p_t^{(f)} + 2B p_t^{(g)} \]

通过将离散化误差控制在 $B/N_t$、高置信失效概率控制在 $p_t^{(f)}$ 与 $p_t^{(g)}$（后续设为 $1/t^2$），使得后续在任意指标集 $\mathcal{T}$ 上的累积后悔可直接由有界范数常数截断为 $O(B |\mathcal{T}|)$，为彻底解耦 $Q$ 奠定了代数结构基础。

2. 延迟方差阈值切分与扩展势能计数技术

为了摆脱传统分析中导致 $\sqrt{Q}$ 乘性因子的 Cauchy-Schwarz 粗糙放缩，本文提出基于方差阈值 $\lambda^2 / Q$ 对优化时序 $[T]$ 进行两相划分。令高方差集合 $\mathcal{T} = \{t \in [T] \mid \sigma_{t-Q-1}^2(\boldsymbol{x}_t) \geq \lambda^2 / Q\}$，互补集合为 $\mathcal{T}^c$。对于高方差集合，定义平滑截断函数 $h(a) = \min\{1, a\}$，通过望远镜级数展开将滞后方差与逐项更新方差关联：

$$

|\widetilde{\mathcal{T}}| = \sum_{t \in \widetilde{\mathcal{T}}} h(Q \lambda^{-2} \sigma_{t-1}^2(\boldsymbol{x}t)) + \sum}}} \sum_{i=1}^Q \left{ h(Q \lambda^{-2} \sigma_{t-i-1}^2(\boldsymbol{xt)) - h(Q \lambda^{-2} \sigma_t)) \right} $$}^2(\boldsymbol{x

结合后验方差更新下界 $\sigma_{t-i}^2(\boldsymbol{x}_t) \geq \frac{\sigma_{t-i-1}^2(\boldsymbol{x}_t)}{\lambda^{-2} \sigma_{t-i-1}^2(\boldsymbol{x}_{t-i}) + 1}$ 与初等不等式，本文证明该集合的元素总数受到最大信息增益严格限制，满足 $|\mathcal{T}| \leq 6Q \gamma_{|\mathcal{T}|}(\lambda^2) + Q \leq 6Q \gamma_T(\lambda^2) + Q$。这意味着高不确定性探索的发生次数受限于系统总信息容量，不会无限制膨胀。

3. 滞后后验协方差比值控制与互补集无退化界

对于低方差互补时步 $t \in \mathcal{T}^c$，未观测到的中间样本方差均满足 $\sigma_{i-Q-1}^2(\boldsymbol{x}_i) \leq \lambda^2 / Q$。本文基于矩阵行列式引理扩展了高斯过程后验方差更新比值界，证明在加入任意延迟观测子集 $\mathcal{M}_t = \mathcal{T}^c \cap \{t-Q, \dots, t-1\}$ 时，后验方差比值满足：

\[ \frac{\sigma_{t-Q-1}^2(\boldsymbol{x}_t)}{\widetilde{\sigma}_{t-1}^2(\boldsymbol{x}_t)} \leq 1 + \lambda^{-2} \sum_{i \in \mathcal{M}_t} \sigma_{t-Q-1}^2(\boldsymbol{x}_i) \leq 1 + \lambda^{-2} \cdot Q \cdot \frac{\lambda^2}{Q} = 2 \]

由于后验方差最多仅被放大常数因子 2，互补集上滞后方差的平方和得以完全转化为标准序列化信息增益进行控制：$\sum_{t \in \mathcal{T}^c} \sigma_{t-Q-1}^2(\boldsymbol{x}_t) \leq 8 \lambda^2 \gamma_T$。通过 Cauchy-Schwarz 不等式，互补集上的累积后悔项直接收敛到标准的串行阶 $O(\gamma_T \sqrt{T \ln T})$，而高方差集合 $\mathcal{T}$ 上的累积后悔则直接上界为 $O(B |\mathcal{T}|) = O(B \overline{T}^{(Q)})$，其中 $\overline{T}^{(Q)} = \max\{t \in \mathbb{N} \mid t \leq 6Q \gamma_t + Q\}$。由此成功将 $Q$ 完全解耦为加性项。

4. 无噪声反馈下的次线性与多对数超低后悔分析

在无噪声设置下（即观测 $y_t = f(\boldsymbol{x}_t)$，$\lambda = 0$），传统的方差阈值切分法无法直接应用。本文借助模 $Q$ 的时间网格分解 $\mathcal{T}_q = \{t \in [T] \mid t \bmod Q = q\}$，构造辅助虚拟噪声参数序列 $\lambda_t$，建立关于后验标准差最小值的积分控制机制。对于平滑度极高的平方指数核（SE），滞后方差展现出超多项式极速衰减；对于 Matérn 核，证明了其衰减阶受指标 $(T/Q)^{-\nu/d} (\ln(T/Q))^{\nu/d}$ 控制。在对单步后悔求和积分后，首次在并行无噪声 GP 老虎机中证明了当 $\nu \geq d$ 时累积后悔达到关于时间 $T$ 的多对数阶甚至是 $O(Q \ln^{1/2} T)$ 的超强收敛上界。

损失函数 / 训练策略¶

作为免训练的黑盒贝叶斯优化算法，GP-BTS 在每轮迭代运行中按闭式后验表达式进行核矩阵更新。置信区间宽度理论设定参数为：在有噪声设定下，$\beta_t^{1/2}(\delta) = B + \frac{R}{\lambda} \sqrt{2(\gamma_t + \ln(1/\delta))}$；在无噪声设定下，$\beta_t^{1/2}(\delta) = B$。在第 $T$ 轮评估结束后，算法输出推荐最优解：在有噪声情况下输出下置信界（LCB）最大化点 $\hat{\boldsymbol{x}}_T = \arg\max_{\boldsymbol{x} \in \mathcal{X}} \{\mu_T(\boldsymbol{x}) - \beta_T^{1/2}(p_T^{(g)}) \sigma_T(\boldsymbol{x})\}$；在无噪声情况下直接输出历史最大采样点 $\hat{\boldsymbol{x}}_T = \arg\max_{\boldsymbol{x} \in \{\boldsymbol{x}_1, \dots, \boldsymbol{x}_T\}} f(\boldsymbol{x})$。

实验关键数据¶

主实验¶

论文在三维紧凑网格域 $\mathcal{X} = \{0, 0.1, \dots, 0.9\}^3$（输入维度 $d=3$）上开展了合成函数优化实验，通过真实高斯过程后验均值生成符合 RKHS 范数约束的目标函数，比较不同并发批大小 / 延迟步长 $Q \in \{0, 2, 4, 8, 16, 32\}$ 下的累积后悔。

下表系统对比了本文提出的 GP-BTS 理论累积后悔上界与现有代表性基线在噪声设定下的渐近阶（省略多对数因子 $\widetilde{O}$）：

算法 / 理论方法	核函数类型	理论累积后悔上界 $\mathbb{E}[R_T]$	延迟/批大小 $Q$ 的依赖模式	是否需初始 US 预热
GP-BTS（本文）	平方指数核 (SE)	$O(Q \ln^{d+1} Q + \sqrt{T \ln^{2d+3} T})$	加性项 (Additive)	否
GP-BTS（基于 Vakili 等 2021c）	平方指数核 (SE)	$O(\sqrt{Q T \ln^{d+1}(T/Q) \ln^{d+2} T})$	乘性因子 (Multiplicative)	否
串行 GP-TS（Chowdhury 等 2017）	平方指数核 (SE)	$O(\sqrt{T \ln^{2d+3} T})$	$Q=0$（理想基线）	否
GP-BTS（本文）	Matérn 核 ($\nu$)	$\widetilde{O}(Q^{\frac{2\nu+d}{2\nu}} + T^{\frac{2\nu+3d}{4\nu+2d}})$	加性项 (Additive)	否
GP-BTS（基于 Vakili 等 2021c）	Matérn 核 ($\nu$)	$\widetilde{O}(Q^{\frac{\nu}{2\nu+d}} T^{\frac{2\nu+3d}{4\nu+2d}})$	乘性因子 (Multiplicative)	否
串行 GP-TS（Chowdhury 等 2017）	Matérn 核 ($\nu$)	$\widetilde{O}(T^{\frac{2\nu+3d}{4\nu+2d}})$	$Q=0$（理想基线）	否

在无噪声设定下，累积后悔上界对比展现出更本质的跨越：

算法 / 理论方法	SE 核界	Matérn ($d > \nu$)	Matérn ($d = \nu$)	Matérn ($d < \nu$)
GP-BTS（本文）	$O(Q \ln^{\frac{1}{2}} T)$	$\widetilde{O}(Q + Q^{\frac{\nu}{d}} T^{\frac{d-\nu}{d}})$	$O(Q \ln^{\frac{5}{2}} T)$	$O(Q \ln^{\frac{1}{2}} T)$
GP-UCB-batch（Lyu 等 2019）	$O(\sqrt{Q T \ln^{2d+3} T})$	$\widetilde{O}(Q^{\frac{1}{2}} T^{\frac{2\nu+3d}{4\nu+2d}})$	$\widetilde{O}(Q^{\frac{1}{2}} T^{\frac{2\nu+3d}{4\nu+2d}})$	$\widetilde{O}(Q^{\frac{1}{2}} T^{\frac{2\nu+3d}{4\nu+2d}})$
串行 GP-UCB（Iwazaki 2025a）	$O(1)$	$\widetilde{O}(T^{\frac{d-\nu}{d}})$	$O(\ln^2 T)$	$O(1)$

消融与敏感性分析¶

论文在 16 次独立随机试验下统计了不同延迟 $Q$（包含 $Q=0$ 串行，以及 $Q \in \{2, 4, 8, 16, 32\}$）对经验累积后悔变化曲线的影响（实验配置包括 $\lambda=0.1$ 的高斯噪声及无噪声环境，核参数为 $\ell=0.4$；Matérn 核取 $\nu=2.5$）：

实验环境与核函数	迭代轮数 $T$	并发规模 $Q \leq 4$ 表现	大并发规模 $Q = 16, 32$ 表现	理论预测与实际契合度
SE 核 / 无噪声 ($\lambda=0$)	100 步	累积后悔迅速饱和（约 100 步停滞）	随 $Q$ 增加略有初始上升，随后完全收敛	完全验证 $O(Q \ln^{1/2} T)$ 饱和结论
Matérn 核 / 无噪声 ($d=3 > \nu=2.5$)	200 步	呈现极缓慢次线性增长	后悔随 $Q$ 适度平移，无陡峭恶化	实际 $Q$ 敏感性显著优于理论上界 $\widetilde{O}(T^{1/6} Q^{5/6})$
SE 核 / 有噪声 ($\lambda=0.1$)	200 步	与串行曲线（$Q=0$）几乎贴合重叠	后期增长斜率与串行完全一致，仅有微小纵向偏移	严密验证主定理中的加性 $Q \ln^{d+1} Q$ 偏移
Matérn 核 / 有噪声 ($\lambda=0.1$)	200 步	曲线演变平稳，增量平缓	曲线保持亚线性平行推进	验证主项仅受 $T$ 支配而与 $Q$ 解耦

关键发现¶

在有噪声环境下，当总步数 $T$ 充足（$T \gg Q$）时，随着迭代推进，不同 $Q$ 值的累积后悔增长斜率完全趋于一致；$Q$ 带来的影响仅仅是早期探索阶段在纵轴上的常数平移，彻底否定了以往理论中预测的“后悔随 $Q$ 成倍放大”现象。
在无噪声且高平滑的 SE 核场景中，由于后验方差以指数级速度快速塌缩，累积后悔在 100 次迭代左右直接陷入饱和平台，与串行优化表现出几乎等价的收敛性质。
经验性能表明，GP-BTS 无需任何人为设计的启发式预热或强制不确定性采样，凭借高斯过程后验采样的内在随机多样性，即可自适应避免采样碰撞。

亮点与洞察¶

将延迟参数从乘性转化为加性常数项：通过基于方差阈值 $\lambda^2 / Q$ 的精细化指标集切分，首次在无需初始纯探索采样的前提下证明了并行 GP 老虎机的主累积项与串行情形保持同一收敛速率。
填补无噪声并行 GP 老虎机的理论空白：借鉴无噪声标量化技术，不仅突破了以往工作直接套用噪声界导致的粗糙收敛阶，还针对光滑核首次建立了多对数阶超低后悔收敛保证。
可复用的椭圆势分析技巧：所提出的扩展后验方差行列式比值引理（引理 A.4）和望远镜级数切分技术，能够直接推广至异步多智能体强化学习、分布式参数服务器贝叶斯优化等带有通信延迟的时序决策场景。

局限与展望¶

无噪声设定下的简单后悔仍存在收敛阶落差：对于无噪声情况下的简单后悔，当前分析虽然推导出多项式收敛阶，但在 $T$ 的指数上依然落后于串行 GP-UCB 的理论最优极限，这主要受限于汤普森采样无法直接建立点对点确定性置信上界的固有随机性。
无法直接无缝拓展至 GP-BUCB：现有 GP-BUCB 算法的置信区间宽度本身就显式包含了 $Q$ 的乘性膨胀因子（$\beta_T = O(Q\gamma_T)$），且确定性 UCB 在同批采样时极易发生选点重叠，因此尚不能直接套用本文分析；未来需要针对 UCB 设计全新的多样性诱导机制。
高概率界依赖马尔可夫不等式导致常数松散：文中主定理给出的是期望后悔界，若转化为高概率界在无噪声情形下会引入 $1/\delta$ 阶依赖；如何在无噪声环境下规避鞅差集中不等式带来的多余 $O(\sqrt{T})$ 项仍是开放课题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙提出方差阈值切分与椭圆势分解技术，彻底解决了长期存在的乘性 $Q$ 惩罚理论难题。
实验充分度: ⭐⭐⭐⭐ 提供了不同延迟参数和核函数在有噪/无噪下的合成数据对比，与理论预测严格吻合。
写作质量: ⭐⭐⭐⭐⭐ 数学证明逻辑链条极其清晰严谨，关键引理与传统技术的差异与演进推导交代透彻。
价值: ⭐⭐⭐⭐⭐ 为并行和分布式贝叶斯优化奠定了坚实的理论基石，对实际大规模高通量实验具有重要指导意义。

算法 / 理论方法	SE 核界	Matérn (\(d > \nu\))	Matérn (\(d = \nu\))	Matérn (\(d < \nu\))
GP-BTS（本文）	\(O(Q \ln^{\frac{1}{2}} T)\)	\(\widetilde{O}(Q + Q^{\frac{\nu}{d}} T^{\frac{d-\nu}{d}})\)	\(O(Q \ln^{\frac{5}{2}} T)\)	\(O(Q \ln^{\frac{1}{2}} T)\)
GP-UCB-batch（Lyu 等 2019）	\(O(\sqrt{Q T \ln^{2d+3} T})\)	\(\widetilde{O}(Q^{\frac{1}{2}} T^{\frac{2\nu+3d}{4\nu+2d}})\)	\(\widetilde{O}(Q^{\frac{1}{2}} T^{\frac{2\nu+3d}{4\nu+2d}})\)	\(\widetilde{O}(Q^{\frac{1}{2}} T^{\frac{2\nu+3d}{4\nu+2d}})\)
串行 GP-UCB（Iwazaki 2025a）	\(O(1)\)	\(\widetilde{O}(T^{\frac{d-\nu}{d}})\)	\(O(\ln^2 T)\)	\(O(1)\)

实验环境与核函数	迭代轮数 \(T\)	并发规模 \(Q \leq 4\) 表现	大并发规模 \(Q = 16, 32\) 表现	理论预测与实际契合度
SE 核 / 无噪声 (\(\lambda=0\))	100 步	累积后悔迅速饱和（约 100 步停滞）	随 \(Q\) 增加略有初始上升，随后完全收敛	完全验证 \(O(Q \ln^{1/2} T)\) 饱和结论
Matérn 核 / 无噪声 (\(d=3 > \nu=2.5\))	200 步	呈现极缓慢次线性增长	后悔随 \(Q\) 适度平移，无陡峭恶化	实际 \(Q\) 敏感性显著优于理论上界 \(\widetilde{O}(T^{1/6} Q^{5/6})\)
SE 核 / 有噪声 (\(\lambda=0.1\))	200 步	与串行曲线（\(Q=0\)）几乎贴合重叠	后期增长斜率与串行完全一致，仅有微小纵向偏移	严密验证主定理中的加性 \(Q \ln^{d+1} Q\) 偏移
Matérn 核 / 有噪声 (\(\lambda=0.1\))	200 步	曲线演变平稳，增量平缓	曲线保持亚线性平行推进	验证主项仅受 \(T\) 支配而与 \(Q\) 解耦

算法 / 理论方法	核函数类型	理论累积后悔上界 \(\mathbb{E}[R_T]\)	延迟/批大小 \(Q\) 的依赖模式	是否需初始 US 预热
GP-BTS（本文）	平方指数核 (SE)	\(O(Q \ln^{d+1} Q + \sqrt{T \ln^{2d+3} T})\)	加性项 (Additive)	否
GP-BTS（基于 Vakili 等 2021c）	平方指数核 (SE)	\(O(\sqrt{Q T \ln^{d+1}(T/Q) \ln^{d+2} T})\)	乘性因子 (Multiplicative)	否
串行 GP-TS（Chowdhury 等 2017）	平方指数核 (SE)	\(O(\sqrt{T \ln^{2d+3} T})\)	\(Q=0\)（理想基线）	否
GP-BTS（本文）	Matérn 核 (\(\nu\))	\(\widetilde{O}(Q^{\frac{2\nu+d}{2\nu}} + T^{\frac{2\nu+3d}{4\nu+2d}})\)	加性项 (Additive)	否
GP-BTS（基于 Vakili 等 2021c）	Matérn 核 (\(\nu\))	\(\widetilde{O}(Q^{\frac{\nu}{2\nu+d}} T^{\frac{2\nu+3d}{4\nu+2d}})\)	乘性因子 (Multiplicative)	否
串行 GP-TS（Chowdhury 等 2017）	Matérn 核 (\(\nu\))	\(\widetilde{O}(T^{\frac{2\nu+3d}{4\nu+2d}})\)	\(Q=0\)（理想基线）	否