mlsanityData to 7 Oct 2026

On Regret Bounds of Thompson Sampling for Bayesian Optimization

arXiv 2603.09276 ↗First posted 10 Mar 2026stat.ML cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 33 of its 60 references that are in the map. First posted on arXiv 10 Mar 2026.

Builds on

33 of 60 references.

References · 33

  1. 2017A Tutorial on Thompson Samplingcited by 420
  2. 2017On Kernelized Multi-armed Banditscited by 348
  3. 2013Learning to Optimize Via Posterior Samplingcited by 253
  4. 2014Predictive Entropy Search for Efficient Global Optimization of Black-box Functionscited by 201
  5. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  6. 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 125
  7. 2017Multi-fidelity Bayesian Optimisation with Continuous Approximationscited by 120
  8. 2018A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizationscited by 98
  9. 2020Scalable Constrained Bayesian Optimizationcited by 84
  10. 2019ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendationscited by 77
  11. 2017Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Spacecited by 76
  12. 2020Pathwise Conditioning of Gaussian Processescited by 63
21 more
  1. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  2. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  3. 2017Multi-dueling Bandits with Dependent Armscited by 35
  4. 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 23
  5. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  6. 2021Bayesian Optimization for Cascade-type Multi-stage Processescited by 17
  7. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
  8. 2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 15
  9. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  10. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  11. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  12. 2023qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson samplingcited by 11
  13. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  14. 2020Lenient Regret for Multi-Armed Banditscited by 8
  15. 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 7
  16. 2023Bounding Box-based Multi-objective Bayesian Optimization of Risk Measures under Input Uncertaintycited by 5
  17. 2024Regret Analysis for Randomized Gaussian Process Upper Confidence Boundcited by 4
  18. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  19. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  20. 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 3
  21. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  2. 2026Towards Regret Guarantees for One-Step Lookahead Bayesian Optimizationcited by 0