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 . Introduction Bayesian optimization (BO) [Kushner, 1964 , Mockus et al., 1978] is a powerful framework for black-box optimization problems. BO aims to optimize an expensive-to-evaluate black-box function using a small number of input-output pairs by adaptively querying input points based on a Bayesian model, typically a Gaussian process (GP) model. BO has been applied to a wide range of applications, such as materials informatics [Ueno et al., 2016] , AutoML [Snoek et al., 2012], and drug discovery [Korovina et al., 2020] . Alongside these applications and algorithmic developments, theoretical properties of BO have also been studied. This paper focuses on regret analysis under the assumption that the objective function is a sample path from a GP. Gaussian process upper confidence bound (GP-UCB) [Kushner, 1964 , Srinivas et al., 2010] is a BO algorithm with well-established theoretical guarantees. The theoretical performance of BO methods is often measured by cumulative regret [Srinivas et al., 2010] , for which both high-probability and expected upper bounds of GP-UCB have been derived [Srinivas et al., 2010 , Takeno et al., 2023] . High-probability upper bound of an alternative criterion called lenient regret [Merlis and Mannor, 2021] , which counts a regret exceeding a given tolerance, has also been obtained by Cai et al. [2021 ], Iwazaki [2025b].