Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

Haowei Wang; Yilin Zheng

stat.MLOct 14, 2026

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

Authors: Haowei Wang, Yilin Zheng

Organizations: National University of Singapore Singapore

Abstract

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$ . We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$ , we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn- $5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.

Figures & tables

Simple regret	Matérn kernel	Takeno and Iwazaki [12]	Ours
Upper bound	$1<\nu<d$	$O(N^{-\nu/d}(\log N)^{\nu/d+1/2})$	$O(N^{-\nu/d}\sqrt{\log N})$
	$\nu=d>1$	$O(N^{-1}(\log N)^{5/2})$	$O(N^{-1}\sqrt{\log N})$
	$\nu>d$	$O(N^{-1}\sqrt{\log N})$	$O(N^{-\nu/d}\sqrt{\log N})$
Lower bound	$\nu=5/2,\ d=1$	—	$\Omega(N^{-5/2}\sqrt{\log N})$

Table 1: Comparison of worst-case expected simple regret bounds under noiseless observations. The previous bounds are for GP-BTS with fixed delay

Q

and finite decision sets. The last column reports the bounds for standard GP-TS.

Explore similar work

Mar 10, 2026

On Regret Bounds of Thompson Sampling for Bayesian Optimization

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

Shion Takeno, Shogo Iwazaki

Nagoya University · MI-6 Ltd.

Bayesian Optimization Thompson Sampling

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

Oct 14, 2026

Fully sequential Gaussian process regression for preference learning

We study continuous global optimization problems in which the objective function cannot be directly evaluated; rather, we observe only which of two selected design points appears to perform better, subject to noise. Such comparisons complicate the use of Gaussian process regression because they yield non-Gaussian posteriors. We consider a fully sequential approximation, based on moment-matching, that yields a fast closed-form update of the metamodel's mean and covariance. We then propose DOVE, a fully sequential sampling policy that combines an information gain criterion with randomized sampling designed to control error accumulation. Under fairly standard regularity conditions, we prove convergence rates for both statistical error and expected simple regret that depend on kernel smoothness. To our knowledge, these are the first such rates for fully sequential approximate Bayesian inference in continuous global optimization.

Ilya O. Ryzhov

Bayesian Optimization Gaussian Process Regression Preference Learning

Ask PDF