# Optimal Order Simple Regret for Gaussian Process Bandits

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 81 references that are in the map.
- First posted on arXiv 20 Aug 2021.

## Builds on (most cited first, 30 of 33)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [BOHB: Robust and Efficient Hyperparameter Optimization at Scale](https://mlsanity.com/paper/1807.01774/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics](https://mlsanity.com/paper/1602.04450/) (2016)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Stagewise Safe Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1806.07555/) (2018)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimation](https://mlsanity.com/paper/1610.07379/) (2016)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [Simple regret for infinitely many armed bandits](https://mlsanity.com/paper/1505.04627/) (2015)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [Corruption-Tolerant Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2003.01971/) (2020)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Multi-fidelity Gaussian Process Bandit Optimisation](https://mlsanity.com/paper/1603.06288/) (2016)
- [Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior](https://mlsanity.com/paper/1811.09558/) (2018)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Best arm identification in multi-armed bandits with delayed feedback](https://mlsanity.com/paper/1803.10937/) (2018)
- [Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?](https://mlsanity.com/paper/1905.12298/) (2019)
- [Gaussian Process bandits with adaptive discretization](https://mlsanity.com/paper/1712.01447/) (2017)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)
- [Bayesian Optimization with Exponential Convergence](https://mlsanity.com/paper/1604.01348/) (2016)
- [Simple Regret Minimization for Contextual Bandits](https://mlsanity.com/paper/1810.07371/) (2018)

## Built on by (most cited first, 30 of 54)

- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Uniform Generalization Bounds for Overparameterized Neural Networks](https://mlsanity.com/paper/2109.06099/) (2021)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Nearly Optimal Algorithms for Level Set Estimation](https://mlsanity.com/paper/2111.01768/) (2021)
- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency](https://mlsanity.com/paper/2310.15351/) (2023)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Open Problem: Tight Online Confidence Intervals for RKHS Elements](https://mlsanity.com/paper/2110.15458/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Rate-optimal Bayesian Simple Regret in Best Arm Identification](https://mlsanity.com/paper/2111.09885/) (2021)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Graph Neural Network Bandits](https://mlsanity.com/paper/2207.06456/) (2022)
- [Delayed Feedback in Kernel Bandits](https://mlsanity.com/paper/2302.00392/) (2023)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [Sample Complexity of Kernel-Based Q-Learning](https://mlsanity.com/paper/2302.00727/) (2023)
- [Near-Optimal Algorithm for Non-Stationary Kernelized Bandits](https://mlsanity.com/paper/2410.16052/) (2024)
- [Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization](https://mlsanity.com/paper/2209.09655/) (2022)
- [Provably and Practically Efficient Neural Contextual Bandits](https://mlsanity.com/paper/2206.00099/) (2022)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [Training-Free Neural Active Learning with Initialization-Robustness Guarantees](https://mlsanity.com/paper/2306.04454/) (2023)
- [Sample-efficient Bayesian Optimisation Using Known Invariances](https://mlsanity.com/paper/2410.16972/) (2024)
- [Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2506.04775/) (2025)
- [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 Average-Case Error Bounds for Kernel-Based Bayesian Quadrature](https://mlsanity.com/paper/2202.10615/) (2022)
- [(Private) Kernelized Bandits with Distributed Biased Feedback](https://mlsanity.com/paper/2301.12061/) (2023)

## Abstract (arXiv)

Consider the sequential optimization of a continuous, possibly non-convex, and expensive to evaluate objective function f. The problem can be cast as a Gaussian Process (GP) bandit where f lives in a reproducing kernel Hilbert space (RKHS). The state of the art analysis of several learning algorithms shows a significant gap between the lower and upper bounds on the simple regret performance. When N is the number of exploration trials and γN is the maximal information gain, we prove an tildeO(√γN/N) bound on the simple regret performance of a pure exploration algorithm that is significantly tighter than the existing bounds. We show that this bound is order optimal up to logarithmic factors for the cases where a lower bound on regret is known. To establish these results, we prove novel and sharp confidence intervals for GP models applicable to RKHS elements which may be of broader interest.