Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization

Shogo Iwazaki

cs.LGJun 2, 2025

Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization

Authors: Shogo Iwazaki

Organizations: LY Corporation, Tokyo, Japan

Abstract

This paper addresses the Bayesian optimization problem (also referred to as the Bayesian setting of the Gaussian process bandit), where the learner seeks to minimize the regret under a function drawn from a known Gaussian process (GP). Under a Matérn kernel with a certain degree of smoothness, we show that the Gaussian process upper confidence bound (GP-UCB) algorithm achieves $\tilde{O}(\sqrt{T})$ cumulative regret with high probability. Furthermore, our analysis yields $O(\sqrt{T \ln^2 T})$ regret under a squared exponential kernel. These results fill the gap between the existing regret upper bound for GP-UCB and the best-known bound provided by Scarlett (2018). The key idea in our proof is to capture the concentration behavior of the input sequence realized by GP-UCB, enabling a more refined analysis of the GP's information gain.

Figures & tables

Figure 1: The behavior of the realized input sequence

\mathbf{X}_{T}

(left) and the corresponding information gain

I(\mathbf{X}_{T})

(right) in the 1-dimensional BO problem with

\sigma^{2}=3

. The top left figure shows the objective function

f

realized by GP under

k=k_{\mathrm{Mat\acute{e}rn}}

with

\nu=5/2

. The bottom left figure shows the histogram of the realized inputs:

(\bm{x}_{t})_{t\in[200]}

with GP-UCB (blue) and MVR (orange) under

f

in the top left figure. Furthermore, the right plot shows the corresponding information gain

I(\mathbf{X}_{t})

under GP-UCB or MVR. We also plot the reference curve

0.5\ln(1+\sigma^{-2}t)

corresponding to Case I described in Section 3.1 . We can observe that the inputs selected by GP-UCB are concentrated around the maximizer from the left figure. Then, from the right figure, we also observe that the corresponding information gain increases more slowly than that of MVR, and behaves similarly to Case I on

t\geq 30

. More comprehensive empirical results are also provided in Appendix D .

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Average results of information gain under 20 different sample paths. The top row shows the results for the input space $\mathcal{X}=[0,1]$ with lengthscale parameter $\ell=0.1$ . The bottom row corresponds to the input space $\mathcal{X}=[0,1]^{2}$ with lengthscale $\ell=0.25$ , and from left to right, we use the Matérn 5/2 kernel, the Matérn 7/2 kernel, and the SE kernel. The shaded regions indicate one standard error.

Panel of Figure 3 — Figure 3: Quantiles of information gain over 20 different sample paths. We report the 10%, 25%, 50%, 75%, and 90% quantiles of the information gain of GP-UCB.

Bayesian Optimization

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

See all 243 papers

On Regret Bounds of Thompson Sampling for Bayesian Optimization
Mar 10, 2026Shion Takeno, Shogo IwazakiBayesian Optimization Thompson Sampling
Nagoya University · MI-6 Ltd.
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
Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization
Aug 17, 2026Shion Takeno, Shogo IwazakiThompson Sampling Multi-Armed Bandits
Nagoya University · MI-6 Ltd.

Mar 10, 2026J/K move · Enter open · S save

On Regret Bounds of Thompson Sampling for Bayesian Optimization

Shion Takeno, Shogo Iwazaki

Nagoya University · MI-6 Ltd.

Bayesian Optimization Thompson Sampling

Open paper AskPDF arXiv

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

Abstract

Bayesian Optimization

Explore similar work

On Regret Bounds of Thompson Sampling for Bayesian Optimization

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

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization