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/\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$.
Introduction
Bayesian Optimization (BO) is the standard framework for optimizing expensive, "black-box" functions where evaluations are costly—ranging from hyperparameter tuning in deep learning to experimental design in chemistry. Two primary acquisition functions dominate the landscape: GP-UCB (Upper Confidence Bound) and GP-TS (Thompson Sampling).
While GP-UCB has long enjoyed rigorous theoretical guarantees, GP-TS is often preferred in practice because it is randomized and does not require the manual tuning of a confidence parameter. However, the theoretical understanding of GP-TS has historically lagged behind. This paper provides a major theoretical upgrade for GP-TS, addressing critical gaps regarding high-probability failure, lenient regret, and optimal scaling over time.
The High-Probability Challenge: The $\delta$ Problem
A core focus of this research is the "failure probability" ($\delta$). In BO theory, we seek bounds that hold with probability at least $1-\delta$. For GP-UCB, these bounds typically scale logarithmically with $1/\delta$, meaning the algorithm is very robust against rare failures.
This paper establishes a regret lower bound for GP-TS, proving that it fundamentally suffers from a polynomial dependence on $1/\delta$. By constructing a synthetic two-armed bandit problem, the authors show that because GP-TS is randomized, it is inherently more prone to rare, high-regret events than its deterministic counterpart, GP-UCB. This "confidence ceiling" explains why GP-TS has been harder to analyze in high-probability settings.
Methodology: Second Moment Analysis
To improve the existing upper bounds despite this inherent limitation, the authors utilize Second Moment Analysis. Instead of analyzing the expected regret directly, they bound the second moment of the cumulative regret. This allows for a more effective application of Markov’s inequality to tighten the dependence on $\delta$.
Additionally, the authors leverage the Identical Distribution Property—a unique feature of Thompson Sampling where, given the history of observations, the point chosen by the algorithm and the true global optimizer are identically distributed. This property allows for a more elegant decomposition of regret terms than previous methods.
Key Theoretical Contributions
1. Tighter High-Probability Bounds
By analyzing the second moment, the authors established a new upper bound: $R_T = \tilde{O}(\sqrt{T \gamma_T \log T / \delta})$. This is a significant improvement over previous state-of-the-art results for GP-TS, tightening the dependence on the failure probability by a factor of $1/\sqrt{\delta}$.
2. First Lenient Regret Guarantees
The paper provides the first theoretical guarantees for lenient regret in GP-TS. Lenient regret is a modern metric that only counts "bad" steps where the algorithm's choice is significantly worse than the optimum. The authors prove that the expected lenient regret for GP-TS is polylogarithmic in $T$, matching the best-known results for GP-UCB.
3. Optimal Time Scaling
The authors confirmed that GP-TS achieves the $\tilde{O}(\sqrt{T})$ cumulative regret bound. This finally puts GP-TS on equal footing with GP-UCB regarding how the algorithm scales over long time horizons, resolving an open question in the field.
Broadening Applicability for Matérn Kernels
For researchers using Matérn kernels—the most common choice in Gaussian Process modeling—the authors provided a significant relaxation of conditions. They showed that the optimal $O(\sqrt{T})$ regret bound holds under much looser smoothness requirements ($\nu > 2$) than previously thought. This ensures that the theoretical guarantees for GP-TS are applicable to a much wider range of real-world objective functions.
Conclusion and Future Work
This paper bridges the gap between the practical popularity of Thompson Sampling and its theoretical justification. While the authors proved that GP-TS will likely always be more susceptible to rare failures than GP-UCB (the polynomial $\delta$ dependence), they have significantly narrowed the performance gap in all other metrics. Future work may explore whether "variance inflation"—artificially boosting the GP variance—could further improve the $\delta$ dependence to match the logarithmic scaling of GP-UCB.
Summary updated