Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

Hwanwoo Kim; Jungwoo Hong; Kyungjae Lee

stat.MLOct 12, 2026

Exploration strategies for Gaussian process bandit optimization with inference regret guarantees

Authors: Hwanwoo Kim, Jungwoo Hong, Kyungjae Lee

Organizations: Department of Mathematical Sciences, University of Texas at Dallas · Department of Statistics, Korea University

Abstract

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.

Figures & tables

Figure 1: Cumulative regret and inference regret under noisy Bayesian optimization. The query strategy achieves favorable cumulative regret behavior and concentrates evaluations near the true maximizer, yet the posterior mean recommendation remains suboptimal. From the user’s perspective, however, the noisy evaluations do not reveal which queried points are actually close to the true maximizer. This illustrates that a sublinear cumulative regret guarantee does not necessarily imply vanishing inference regret.

Figure 2: Schedule sensitivity of uniform random exploration. Average final inference regret over 20 independent runs across six synthetic benchmarks, with shaded bands representing one standard deviation. Dashed horizontal lines denote standard BO, while solid curves denote BO with uniform random exploration. Lower values indicate better performance.

Figure 3: HPO and control trajectories. All methods use LogEI; both exploration rules use

\alpha=1/2

. Means are shown with pointwise

1.96

-standard error bands over 30 independent runs. Panels use separate vertical scales: (a,b) best validation log loss (lower is better); (c) recommended controller return on 50 terrains fixed within each optimization run (higher is better). The dotted line marks the threshold of mean return 200.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Study	Dimension	Budget	Initial	Number of Runs
Benchmark function comparison	10, 20, 30	400 BO	2	20
Uniform–MVR comparison	2	400 BO	2	15
YAHPO car / sylvine	14 / 28	120 / 200 total	10	30
Lunar Lander	12	400 total	24	30

Appendix

Table 1: Evaluation budgets, initial designs, and numbers of runs.

Figure 4: Benchmark function inference regret trajectories under calibrated exploration. Standard BO (Standard) and BO with uniform random exploration (Uniform) are compared using GP-UCB, LogEI, and GP-TS across six benchmark functions. For each objective–acquisition pair,

\alpha^{*}

is selected from the five-value grid:

\{1/4,1/3,1/2,2/3,3/4\}

to minimize averaged final inference regret. Dashed and solid curves denote Standard and Uniform, respectively, while colors indicate the acquisition function. Curves show the mean inference regret over 20 random seeds, with shaded regions representing one standard deviation. Lower values indicate better performance. Because inference regret is evaluated at the current posterior mean maximizer, the trajectories need not be monotone.

Objective	Dim.	Acquisition	$\alpha^{*}$	Standard (mean $\pm$ SD)	Uniform (mean $\pm$ SD)	Gain [95% CI]
Trid	10	GP-UCB	$1/4$	0.043 $\pm$ 0.021	0.013 $\pm$ 0.005	0.030 [0.021,0.039]
Trid	10	LogEI	$1/4$	0.044 $\pm$ 0.024	0.013 $\pm$ 0.004	0.032 [0.022,0.043]
Trid	10	GP-TS	$1/4$	0.019 $\pm$ 0.012	0.013 $\pm$ 0.004	0.006 [0.001,0.012]
Rosenbrock	20	GP-UCB	$1/4$	0.168 $\pm$ 0.132	0.056 $\pm$ 0.010	0.112 [0.066,0.179]
Rosenbrock	20	LogEI	$1/4$	0.162 $\pm$ 0.051	0.057 $\pm$ 0.011	0.105 [0.083,0.127]
Rosenbrock	20	GP-TS	$1/4$	0.075 $\pm$ 0.017	0.061 $\pm$ 0.014	0.014 [0.003,0.025]

Appendix

Table 2: Final inference regret under calibrated exploration. For each objective–acquisition pair,

\alpha^{*}

is selected from

\{1/4,1/3,1/2,2/3,3/4\}

to minimize mean final inference regret. Standard denotes standard BO, while Uniform denotes BO with uniform random exploration. Table entries are based on 20 independent runs. Gains measure the improvement of Uniform over Standard; bold values indicate gains whose pointwise 95% bootstrap confidence intervals exclude zero. Lower inference regret is better.

Figure 5: Benchmark function inference regret trajectories at a fixed exploration exponent. Standard BO (Standard) and BO with uniform random exploration (Uniform) are compared using GP-UCB, LogEI, and GP-TS across six benchmark functions, with the exploration exponent fixed at

\alpha=1/2

. Dashed and solid curves denote Standard and Uniform, respectively, while colors indicate the acquisition function. Curves show the mean inference regret over 20 random seeds, with shaded regions representing one standard deviation. Lower values indicate better performance.

Objective	Dim.	Acquisition	Standard (mean $\pm$ SD)	Uniform (mean $\pm$ SD)	Gain [95% CI]
Trid	10	GP-UCB	0.043 $\pm$ 0.021	0.028 $\pm$ 0.012	0.015 [0.005,0.027]
Trid	10	LogEI	0.044 $\pm$ 0.024	0.027 $\pm$ 0.009	0.018 [0.007,0.030]
Trid	10	GP-TS	0.019 $\pm$ 0.012	0.024 $\pm$ 0.012	$-0.006$ [ $-0.011$ ,0.000]
Rosenbrock	20	GP-UCB	0.168 $\pm$ 0.132	0.126 $\pm$ 0.040	0.042 [ $-0.010$ ,0.111]
Rosenbrock	20	LogEI	0.162 $\pm$ 0.051	0.120 $\pm$ 0.027	0.041 [0.020,0.064]
Rosenbrock	20	GP-TS	0.075 $\pm$ 0.017	0.065 $\pm$ 0.009	0.010 [0.002,0.018]

Appendix

Table 3: Final inference regret at the fixed exploration exponent

\alpha=1/2

. Standard denotes standard BO, while Uniform denotes BO with uniform random exploration. Table entries are based on 20 independent runs. Gains measure the improvement of Uniform over Standard; bold values indicate gains whose pointwise 95% bootstrap confidence intervals exclude zero. Lower inference regret is better.

Figure 6: Final HPO comparisons across acquisition functions. Differences in final best-observed validation log loss between exploration-aided BO and standard BO (Standard) over 30 independent runs. Uniform denotes BO with uniform random exploration, while Greedy Packing denotes BO with approximate greedy packing exploration. Both exploration strategies use

\alpha=1/2

. Positive values indicate lower validation loss than Standard. Markers show mean improvements, and horizontal lines show pointwise 95% bootstrap confidence intervals. Filled markers indicate intervals excluding zero.

Figure 7: Evolution of a Lunar Lander controller during BO. Recommended controllers from standard BO (Standard) and BO with uniform random exploration using $\alpha=1/2$ (Uniform) at four stages during LogEI runs sharing the same random seed. Each panel shows the final frame on a representative terrain, and the reported score is the controller’s mean return over the 50 terrains shared by the two methods.

Objective	Method	Final inference regret	Runtime (s)	Runtime / Standard
Ackley 2D	Standard	0.066 (0.025)	174 (24)	1.00
	Uniform	0.030 (0.020)	104 (14)	0.60
	MVR	0.462 (0.902)	186 (12)	1.07
Rastrigin 2D	Standard	0.684 (0.693)	144 (13)	1.00
	Uniform	0.540 (0.640)	90 (11)	0.63
	MVR	0.755 (0.601)	153 (6)	1.06

Appendix

Table 4: Final inference regret and runtime on the two-dimensional benchmarks. Entries report the mean (the standard deviation) over 15 random seeds. Runtime ratios are computed relative to standard BO on the same objective. Lower values indicate better performance for both metrics.

Figure 8: Final inference regret and runtime. Final inference regret (top; logarithmic scale) and measured end-to-end optimizer runtime (bottom) over 15 random seeds. Points represent individual runs, horizontal segments indicate medians, and diamonds indicate means.

Explore similar work

Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
Aug 19, 2026Matthias Mandl, Hanne KekkonenBayesian Optimization Non-Stationary Bandits
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
On Regret Bounds of Thompson Sampling for Bayesian Optimization
Mar 10, 2026Shion Takeno, Shogo IwazakiBayesian Optimization Thompson Sampling
Nagoya University · MI-6 Ltd.
Pre-training of Bayesian Optimization Algorithm through Bayesian Optimization
Oct 7, 2026Satoshi Katayama, Shoyo Hunt, Shintaro Masuda +1Bayesian Optimization Black-Box Optimization
Nagoya Institute of Technology

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

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

Matthias Mandl, Hanne Kekkonen

Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft

Bayesian Optimization Non-Stationary Bandits Dynamic Regret Minimization UCB Algorithms Multi-Armed Bandits

Open paper AskPDF arXiv

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

\tildeγ_T/T=\widetilde{\mathcal O}(ε^{1/2})

and expected average regret

\widetilde{\mathcal 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/ε

Abstract

Explore similar work

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

On Regret Bounds of Thompson Sampling for Bayesian Optimization

Pre-training of Bayesian Optimization Algorithm through Bayesian Optimization