analiza aiqbench
This paper closes a theoretical gap in Bayesian optimization by establishing rigorous high-probability regret bounds for Gaussian process Thompson sampling, addressing its previous limitation to expected regret analysis. The work demonstrates that GP-TS exhibits polynomial dependence on confidence parameters under certain probabilities while providing improved cumulative regret bounds on the time horizon. These results offer practitioners a clearer theoretical understanding of the trade-offs between exploration strategies in black-box optimization scenarios.
On Regret Bounds of Thompson Sampling for Bayesian Optimization
arXiv:2603.09276v2 Announce Type: replace-cross 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$.
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$.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2603.09276 [stat.ML]
(or arXiv:2603.09276v2 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2603.09276 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 269 cuvinte
Subiecte conexe
The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret
arXiv · 16 oct. 2026
Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits
arXiv · 26 sept. 2026
Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling
arXiv · 3 sept. 2026
Future Information-Directed Sampling for Bayesian Nonstationary Bandits
arXiv · 30 sept. 2026