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/\delta$ with probability $\delta$, (ii) an upper bound of the second moment of cumulative regret, which directly suggests an improved regret upper bound on $\delta$, (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$.

In many fields of modern science and technology, such as drug discovery and materials development, researchers face the challenge of finding the best design or solution through expensive and time-consuming experiments. To solve this problem efficiently, a trial-and-error AI algorithm called Thompson sampling is widely used in practice to select the next experiment based on current data. Although it has demonstrated strong practical performance, our theoretical understanding of its reliability has been limited. To address these theoretical gaps, this study provides several new mathematical proofs regarding the performance of Thompson sampling, which particularly shows that Thompson sampling can quickly identify sufficiently good solutions. These findings provide a mathematical foundation that explains when and why Thompson sampling can be trusted in critical decision-making processes. Ultimately, this theoretical advancement helps minimize wasted trials and maximize safety in high-stakes industries where physical experiments are exceptionally expensive.