On Regret Bounds of Thompson Sampling for Bayesian Optimization

Shion Takeno; Shogo Iwazaki

stat.MLMar 10, 2026

On Regret Bounds of Thompson Sampling for Bayesian Optimization

Authors: Shion Takeno, Shogo Iwazaki

Organizations: Nagoya University · MI-6 Ltd.

Abstract

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$ .

Explore similar work

Aug 19, 2026

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

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/ε

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

Ask PDF

Feb 16, 2026

Frequentist Regret Analysis of Gaussian Process Thompson Sampling via Fractional Posteriors

We study Gaussian Process Thompson Sampling (GP-TS) for sequential decision-making over compact, continuous action spaces and provide a frequentist regret analysis based on fractional Gaussian process posteriors, without relying on domain discretization as in prior work. We show that the variance inflation commonly assumed in existing analyses of GP-TS can be interpreted as Thompson Sampling with respect to a fractional posterior with tempering parameter

α\in (0,1)

. We derive a kernel-agnostic regret bound expressed in terms of the information gain parameter

γ_t

and the posterior contraction rate

ε_t

, and identify conditions on the Gaussian process prior under which

ε_t

can be controlled. As special cases of our general bound, we recover regret of order

\tilde{\mathcal{O}}(T^{\frac{1}{2}})

for the squared exponential kernel,

\tilde{\mathcal{O}}(T^{\frac{2ν+3d}{2(2ν+d)}} )

for the Matérn-

ν

kernel, and a bound of order

\tilde{\mathcal{O}}(T^{\frac{2ν+3d}{2(2ν+d)}})

for the rational quadratic kernel. Overall, our analysis provides a unified and discretization-free regret framework for GP-TS that applies broadly across kernel classes.

Somjit Roy, Prateek Jaiswal, Anirban Bhattacharya +2

Department of Statistics, Texas A&M University, College Station, TX 77843, USA · Daniels School of Business, Purdue University, West Lafayette, IN 47907, USA · Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706, USA

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

Ask PDF

Aug 17, 2026

Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization

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.

Shion Takeno, Shogo Iwazaki

Nagoya University · MI-6 Ltd.

Thompson Sampling Multi-Armed Bandits Bayesian Optimization Gaussian Processes

Ask PDF