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
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 ρ=0.9 . Panel (a) shows f , g , and the offline estimate gN . 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 R1000
Method
ρ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 log10St 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
Task
d
Domain X
fraw⋆
Panel A: Cumulative-regret experiments
Ackley
2
[−5,5]2
0
Branin
2
[−5,10]×[0,15]
0.3979
Rosenbrock
2
[−2.048,2.048]2
0
Six-Hump Camel
2
[−3,3]×[−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 ρ2=0.8 . Curves report RMSE relative to λ⋆ . 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.
AI-GPB
Task
M=16
M=128
M=1024
Known- g
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 ρ2=0.8 . Entries report the ratio of mean cumulative regret to that of Vanilla GP-UCB over 20 independent runs.
ρ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.
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.
Existing cumulative regret guarantees for Bayesian optimization (BO) do not necessarily characterize the quality of the algorithm's final output. This gap is critical under noisy evaluations, where the goal is to return a single high-quality recommendation. To address it, we introduce efficient exploration strategies that can be incorporated into any BO procedure by occasionally replacing the acquisition query with an exploration query. To validate this approach, we bound the Gaussian process posterior standard deviation over the search space via the fill distance of the queries, which measures the largest region left unexplored. We then use this result to derive upper bounds on the inference regret, i.e., the gap between the global optimum and the function value at the algorithm's returned point. Empirically, these exploration strategies improve the final recommendations of existing BO algorithms on synthetic benchmarks, hyperparameter optimization, and a control task.
Hwanwoo Kim, Jungwoo Hong, Kyungjae Lee
Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University
We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields γ~T/T=O(ε1/2) and expected average regret O(ε1/4) in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on 1/ε.
Matthias Mandl, Hanne Kekkonen
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft