On Regret Bounds of Thompson Sampling for Bayesian Optimization

• URL: http://arxiv.org/abs/2603.09276v1
• Date: Tue, 10 Mar 2026 07:02:20 GMT
• Title: On Regret Bounds of Thompson Sampling for Bayesian Optimization
• Abstract summary: This paper shows several regret bounds for GP-TS under the assumption that the objective function is a sample path from a GP.<n>We provide several useful lemmas, including a relaxation of the necessary condition from recent analysis to obtain improved regret upper bounds on $T$.
• Score: 11.839451192366786
• License: http://creativecommons.org/licenses/by/4.0/
• 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/δ$ 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$.

Related papers

• Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization [11.839451192366786]
  We study the regret analysis for parallel Gaussian process (GP) bandit optimization.<n>This paper shows that the regret upper bound without the multiplicative factor on $Q$ can be achieved without the initial US phase.
  arXiv  Detail & Related papers  (2026-08-17T12:30:40Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization [3.6985338895569204]
  We show that the Gaussian process GP-UCB algorithm achieves $tildeO(sqrtT)$ cumulative regret with high probability.<n>Our analysis yields $O(sqrtT ln2 T)$ regret under a squared exponential kernel.
  arXiv  Detail & Related papers  (2025-06-02T07:38:58Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  We quantify the excess risk incurred using approximate posterior probabilities in batch binary decision-making.<n>We identify regimes where recalibration alone addresses most of the regret, and regimes where the regret is dominated by the grouping loss.<n>On NLP experiments, we show that these quantities identify when the expected gain of more advanced post-training is worth the operational cost.
  arXiv  Detail & Related papers  (2025-03-23T10:52:36Z)
• Regret Analysis for Randomized Gaussian Process Upper Confidence Bound [9.967062483758632]
  This paper analyzes the randomized variant of GP-UCB called improved randomized GP-UCB.<n>We show that GP-UCB using a constant confidence parameter can incur linearly growing expected cumulative regret.
  arXiv  Detail & Related papers  (2024-09-02T06:49:29Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
  arXiv  Detail & Related papers  (2023-07-14T13:56:11Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  We show that it is possible to obtain regret scaling as $mathcalO(sqrtV_1star K)$ in reinforcement learning with large state spaces. We demonstrate that existing techniques based on at least squares estimation are insufficient to obtain this result.
  arXiv  Detail & Related papers  (2021-12-07T00:29:57Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)
• On Information Gain and Regret Bounds in Gaussian Process Bandits [8.499604625449907]
  Consider the optimization of an expensive to evaluate and possibly non- sequential objective function $f$ from noisy feedback observations. For the Matern family of kernels, lower bounds on $gamma_T$, and regret under the frequentist setting, are known.
  arXiv  Detail & Related papers  (2020-09-15T10:15:29Z)
• Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding [42.669970064867556]
  We show how to characterize the trade-off between regret bounds of GP bandit algorithms and complexity of the posterior distributions. We observe state of the art accuracy and complexity trade-offs for GP bandit algorithms applied to global optimization.
  arXiv  Detail & Related papers  (2020-03-23T21:05:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.