mlsanityData to 14 Oct 2026

Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization

arXiv 2506.01393 ↗First posted 2 Jun 2025cs.LG stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

This paper addresses the Bayesian optimization problem (also referred to as the Bayesian setting of the Gaussian process bandit), where the learner seeks to minimize the regret under a function drawn from a known Gaussian process (GP). Under a Mat'ern kernel with a certain degree of smoothness, we show that the Gaussian process upper confidence bound (GP-UCB) algorithm achieves tildeO(√T) cumulative regret with high probability. Furthermore, our analysis yields O(√T ln2 T) regret under a squared exponential kernel. These results fill the gap between the existing regret upper bound for GP-UCB and the best-known bound provided by Scarlett (2018). The key idea in our proof is to capture the concentration behavior of the input sequence realized by GP-UCB, enabling a more refined analysis of the GP's information gain.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 34 of its 64 references that are in the map. First posted on arXiv 2 Jun 2025.

Builds on

34 of 64 references.

References · 34

  1. 2018A Tutorial on Bayesian Optimizationcited by 744
  2. 2017On Kernelized Multi-armed Banditscited by 352
  3. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
  4. 2013Learning to Optimize Via Posterior Samplingcited by 256
  5. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  6. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  7. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  8. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 139
  9. 2018A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizationscited by 99
  10. 2014Hilbert Space Methods for Reduced-Rank Gaussian Process Regressioncited by 88
  11. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 85
  12. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
22 more
  1. 2020On the Similarity between the Laplace and Neural Tangent Kernelscited by 76
  2. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  3. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  4. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 54
  5. 2019No-Regret Bayesian Optimization with Unknown Hyperparameterscited by 51
  6. 2016Time-Varying Gaussian Process Bandit Optimizationcited by 50
  7. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  8. 2021Neural Contextual Bandits without Regretcited by 40
  9. 2016Multi-fidelity Gaussian Process Bandit Optimisationcited by 31
  10. 2020Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programmingcited by 28
  11. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  12. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  13. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  14. 2016Bayesian Optimization with Exponential Convergencecited by 18
  15. 2017Frequentist coverage and sup-norm convergence rate in Gaussian process regressioncited by 17
  16. 2021Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applicationscited by 17
  17. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 17
  18. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
  19. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
  20. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  21. 2022Instance-Dependent Regret Analysis of Kernelized Banditscited by 5
  22. 2020Tight Regret Bounds for Noisy Optimization of a Brownian Motioncited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 12.

13 papers.

Sort:

  1. 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 4
  2. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  3. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 3
  4. 2026Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Boundscited by 2
  5. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  6. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 1
  7. 2026Learning to Attack: A Bandit Approach to Adversarial Context Poisoningcited by 0
  8. 2026AutoAdapt: An Automated Domain Adaptation Framework for LLMscited by 0
  9. 2026Practical Efficient Global Optimization is No-regretcited by 0
  10. 2026Regret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimizationcited by 0
  11. 2026Towards Regret Guarantees for One-Step Lookahead Bayesian Optimizationcited by 0
  12. 2026Transferring Information Across Interventions in Causal Bayesian Optimizationcited by 0
1 more
  1. 2026Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Explorationcited by 0