Gaussian Process Bandits with Paired Auxiliary Observations

Weibo Huang; Qing Feng; Ruihao Zhu; Cheng Hua

cs.LGOct 17, 2026

Gaussian Process Bandits with Paired Auxiliary Observations

Authors: Weibo Huang, Qing Feng, Ruihao Zhu, Cheng Hua

Organizations: Antai College of Economics and Management, Shanghai Jiao Tong University · School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University

Abstract

Bayesian optimization (BO) is widely used for expensive black-box optimization, yet observation noise makes each evaluation less informative and slows posterior learning. Standard BO learns from costly outcomes gathered during optimization. In many applications, however, low-cost auxiliary data are available beforehand. We introduce Auxiliary-Informed Gaussian Process Bandit (AI-GPB), a variance-reduction method that combines an offline estimate of the auxiliary mean with a correction coefficient learned from paired online observations. Notably, it exploits correlation between paired observation errors without requiring the auxiliary mean to approximate the objective. We establish finite-sample GP confidence bounds and regret guarantees, including explicit cumulative and simple regret rates for Matérn kernels. Numerical experiments across continuous BO benchmarks with varied landscapes and dimensions show consistent reductions in cumulative and simple regret relative to vanilla GP-UCB, even when within-pair correlation is moderate and the auxiliary mean is estimated from noisy offline data.

Figures & tables

Figure 1: Mechanism of AI-GPB. The example uses a one-dimensional cross-section of the Ackley function with

\rho=0.9

. Panel (a) shows

f

g

, and the offline estimate

\widehat{g}_{N}

. Panel (b) compares the uncorrected and corrected observation errors. Panel (c) shows the GP posteriors and next queries of Vanilla GP-UCB and AI-GPB after the same initial queries. Shading denotes 90% posterior bands.

Figure 2: Cumulative regret over the online horizon. Curves report means over 20 replications, and shading denotes one standard error of the mean. All methods share the same initialization within each replication.

		Mean cumulative regret $R_{1000}$
Method	$\rho^{2}$	Ackley	Branin	Rosenbrock	Six-Hump Camel
Vanilla GP-UCB	–	$1219.4$	$518.9$	$382.2$	$322.2$
AI-GPB	$0.25$	$1113.5\;(8.7\%)$	$471.3\;(9.2\%)$	$327.4\;(14.3\%)$	$301.0\;(6.6\%)$
	$0.5$	$996.9\;(18.2\%)$	$424.5\;(18.2\%)$	$289.8\;(24.2\%)$	$255.7\;(20.6\%)$
	$0.8$	$603.0\;(50.6\%)$	$309.9\;(40.3\%)$	$227.1\;(40.6\%)$	$210.1\;(34.8\%)$

Table 1: Cumulative regret at

T=1000

. Results are averaged over 20 replications. AI-GPB entries also report percentage reductions relative to Vanilla GP-UCB.

Figure 3: Simple regret over the adaptive horizon. Curves report mean

\log_{10}S_{t}

over 20 replications, and shading denotes one standard error of the mean. All methods share the same initialization within each replication.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel A: Cumulative-regret experiments
Task	$d$	Domain $\mathcal{X}$	$f_{\mathrm{raw}}^{\star}$
Ackley	$2$	$[-5,5]^{2}$	$0$
Branin	$2$	$[-5,10]\times[0,15]$	$0.3979$
Rosenbrock	$2$	$[-2.048,2.048]^{2}$	$0$
Six-Hump Camel	$2$	$[-3,3]\times[-2,2]$	$-1.0316$
Panel B: Simple-regret experiments

Appendix

Table 2: Summary of the benchmark problems. Global minima are rounded to four decimal places. Detailed function definitions follow [ 21 ] .

Figure 4: Online coefficient estimation at

\rho^{2}=0.8

. Curves report RMSE relative to

\lambda^{\star}

. Shading denotes one pointwise bootstrap standard error.

Figure 5: Effect of offline sample size. Curves report means over 20 replications, with

N=16M

and

T=1000

. Shading denotes one standard error of the mean. Dashed lines show the known-

g

references at the corresponding correlation levels.

Task	$M=16$	$M=128$	$M=1024$	Known- $g$
	AI-GPB
Ackley	0.894	0.570	0.494	0.483
Branin	0.444	0.497	0.597	0.572
Rosenbrock	0.698	0.573	0.594	0.564
Six-Hump Camel	0.571	0.653	0.652	0.638

Appendix

Table 3: Offline sample size at

\rho^{2}=0.8

. Entries report the ratio of mean cumulative regret to that of Vanilla GP-UCB over

20

independent runs.

		$\rho^{2}$
Task	$b$	$0.25$	$0.5$	$0.8$
Ackley	$0.10$	0.951	0.923	0.601
	$0.35$	0.888	0.739	0.474
	$0.50$	0.913	0.817	0.540
Branin	$0.10$	0.885	0.722	0.605
	$0.35$	0.890	0.798	0.571

Appendix

Table 4: Exploration sensitivity. Entries report mean cumulative regret of AI-GPB relative to Vanilla GP-UCB at the same

b

, based on

10

independent runs.

Bayesian Optimization

Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.

See all 235 papers

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
Aug 17, 2026Shion Takeno, Shogo IwazakiThompson Sampling Multi-Armed Bandits
Nagoya University · MI-6 Ltd.
Exploration strategies for Gaussian process bandit optimization with inference regret guarantees
Oct 12, 2026Hwanwoo Kim, Jungwoo Hong, Kyungjae LeeGaussian Process Bandits Bayesian Optimization
Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University
Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
Aug 19, 2026Matthias Mandl, Hanne KekkonenGaussian Process Bandits Bayesian Optimization
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft

Aug 17, 2026J/K move · Enter open · S save

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization

Shion Takeno, Shogo Iwazaki

Nagoya University · MI-6 Ltd.

Thompson Sampling Multi-Armed Bandits Bayesian Optimization Gaussian Processes Gaussian Process Bandits

Open paper AskPDF arXiv

This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization. The known regret upper bounds for the widely used GP batched upper confidence bound and GP batched Thompson sampling (GP-BTS) suffer from a multiplicative factor with respect to the batch size

Q

. To avoid this degradation, existing analyses require a polynomial number of uncertainty sampling (US) for

Q

at the beginning of optimization. However, this initial US phase is often ineffective in practice. This paper shows that the regret upper bound without the multiplicative factor on

Q

can be achieved without the initial US phase, using GP-BTS as an example. Furthermore, we show much better regret upper bounds in the noiseless setting than in the noisy setting, as in the sequential GP bandit setting.

Abstract

Bayesian Optimization

Explore similar work

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

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