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 α=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, α∗ 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
α∗
Standard (mean ± SD)
Uniform (mean ± SD)
Gain [95% CI]
Trid
10
GP-UCB
1/4
0.043 ± 0.021
0.013 ± 0.005
0.030 [0.021,0.039]
Trid
10
LogEI
1/4
0.044 ± 0.024
0.013 ± 0.004
0.032 [0.022,0.043]
Trid
10
GP-TS
1/4
0.019 ± 0.012
0.013 ± 0.004
0.006 [0.001,0.012]
Rosenbrock
20
GP-UCB
1/4
0.168 ± 0.132
0.056 ± 0.010
0.112 [0.066,0.179]
Rosenbrock
20
LogEI
1/4
0.162 ± 0.051
0.057 ± 0.011
0.105 [0.083,0.127]
Rosenbrock
20
GP-TS
1/4
0.075 ± 0.017
0.061 ± 0.014
0.014 [0.003,0.025]
Appendix
Table 2: Final inference regret under calibrated exploration. For each objective–acquisition pair, α∗ 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 α=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 ± SD)
Uniform (mean ± SD)
Gain [95% CI]
Trid
10
GP-UCB
0.043 ± 0.021
0.028 ± 0.012
0.015 [0.005,0.027]
Trid
10
LogEI
0.044 ± 0.024
0.027 ± 0.009
0.018 [0.007,0.030]
Trid
10
GP-TS
0.019 ± 0.012
0.024 ± 0.012
−0.006 [ −0.011 ,0.000]
Rosenbrock
20
GP-UCB
0.168 ± 0.132
0.126 ± 0.040
0.042 [ −0.010 ,0.111]
Rosenbrock
20
LogEI
0.162 ± 0.051
0.120 ± 0.027
0.041 [0.020,0.064]
Rosenbrock
20
GP-TS
0.075 ± 0.017
0.065 ± 0.009
0.010 [0.002,0.018]
Appendix
Table 3: Final inference regret at the fixed exploration exponent α=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 α=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 α=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.
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
We study a widely used Bayesian optimization method, Gaussian process Thompson sampling (GP-TS), under the assumption that the objective function is a sample path from a GP. Compared with the GP upper confidence bound (GP-UCB) with established high-probability and expected regret bounds, most analyses of GP-TS have been limited to expected regret. Moreover, whether the recent analyses of GP-UCB for the lenient regret and the improved cumulative regret upper bound can be applied to GP-TS remains unclear. To fill these gaps, this paper shows several regret bounds: (i) a regret lower bound for GP-TS, which implies that GP-TS suffers from a polynomial dependence on 1/δ with probability δ, (ii) an upper bound of the second moment of cumulative regret, which directly suggests an improved regret upper bound on δ, (iii) expected lenient regret upper bounds, and (iv) an improved cumulative regret upper bound on the time horizon T. Along the way, we provide several useful lemmas, including a relaxation of the necessary condition from recent analysis to obtain improved regret upper bounds on T.
Bayesian optimization (BO) is widely used as a standard approach for expensive black-box optimization. However, BO algorithms often involve parameters that must be specified in advance, and their performance can strongly depend on these choices. We propose a framework for optimizing such parameters using sample paths drawn from a Gaussian process (GP) inferred from the information available at the start of BO. We use cumulative regret as the performance metric for a BO algorithm. By running the BO algorithm on the generated sample paths, we obtain an empirical estimate of its expected cumulative regret for a given parameter configuration. Optimizing this estimate allows us to identify parameter configurations that, given the currently available information, are expected to achieve low cumulative regret. Since this parameter optimization is itself a black-box optimization problem, we employ another BO procedure to solve it, which we refer to as outer BO. Through experiments, we demonstrate that the proposed framework can effectively select parameter configurations that achieve strong performance among a range of candidate configurations.