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

arXiv: https://arxiv.org/abs/2506.01393 · HTML: https://mlsanity.com/paper/2506.01393/

## 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 (most cited first, 30 of 34)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations](https://mlsanity.com/paper/1805.12168/) (2018)
- [Hilbert Space Methods for Reduced-Rank Gaussian Process Regression](https://mlsanity.com/paper/1401.5508/) (2014)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [On the Similarity between the Laplace and Neural Tangent Kernels](https://mlsanity.com/paper/2007.01580/) (2020)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Multi-fidelity Gaussian Process Bandit Optimisation](https://mlsanity.com/paper/1603.06288/) (2016)
- [Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming](https://mlsanity.com/paper/2004.11408/) (2020)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Bayesian Optimization with Exponential Convergence](https://mlsanity.com/paper/1604.01348/) (2016)
- [Frequentist coverage and sup-norm convergence rate in Gaussian process regression](https://mlsanity.com/paper/1708.04753/) (2017)
- [Gaussian Process Uniform Error Bounds with Unknown Hyperparameters for Safety-Critical Applications](https://mlsanity.com/paper/2109.02606/) (2021)
- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)

## Built on by (most cited first, 13 of 13)

- [Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2507.09828/) (2025)
- [Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere](https://mlsanity.com/paper/2602.17940/) (2026)
- [On Regret Bounds of Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2603.09276/) (2026)
- [Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds](https://mlsanity.com/paper/2603.01470/) (2026)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)
- [Learning to Attack: A Bandit Approach to Adversarial Context Poisoning](https://mlsanity.com/paper/2603.00567/) (2026)
- [AutoAdapt: An Automated Domain Adaptation Framework for LLMs](https://mlsanity.com/paper/2603.08181/) (2026)
- [Practical Efficient Global Optimization is No-regret](https://mlsanity.com/paper/2603.25311/) (2026)
- [Regret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimization](https://mlsanity.com/paper/2605.22561/) (2026)
- [Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization](https://mlsanity.com/paper/2606.00956/) (2026)
- [Transferring Information Across Interventions in Causal Bayesian Optimization](https://mlsanity.com/paper/2606.01457/) (2026)
- [Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration](https://mlsanity.com/paper/2608.18863/) (2026)

## 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.