mlsanityData to 7 Oct 2026

Optimal Order Simple Regret for Gaussian Process Bandits

arXiv 2108.09262 ↗First posted 20 Aug 2021stat.ML cs.LGcited by 52

Not on the map. Why?

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.

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

Builds on

33 of 81 references.

References · 33

  1. 2019Introduction to Multi-Armed Banditscited by 475
  2. 2018BOHB: Robust and Efficient Hyperparameter Optimization at Scalecited by 466
  3. 2013Gaussian Processes for Big Datacited by 377
  4. 2017On Kernelized Multi-armed Banditscited by 348
  5. 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 202
  6. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 188
  7. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  8. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  9. 2016Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Roboticscited by 134
  10. 2020Neural Thompson Samplingcited by 127
  11. 2018Stagewise Safe Bayesian Optimization with Gaussian Processescited by 79
  12. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
21 more
  1. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 52
  2. 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
  3. 2016Truncated Variance Reduction: A Unified Approach to Bayesian Optimization and Level-Set Estimationcited by 40
  4. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  5. 2015Simple regret for infinitely many armed banditscited by 39
  6. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  7. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  8. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  9. 2016Multi-fidelity Gaussian Process Bandit Optimisationcited by 31
  10. 2018Regret bounds for meta Bayesian optimization with an unknown Gaussian process priorcited by 31
  11. 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 30
  12. 2018Best arm identification in multi-armed bandits with delayed feedbackcited by 29
  13. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  14. 2019Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?cited by 27
  15. 2017Gaussian Process bandits with adaptive discretizationcited by 20
  16. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  17. 2016Bayesian Optimization with Exponential Convergencecited by 18
  18. 2018Simple Regret Minimization for Contextual Banditscited by 16
  19. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
  20. 2019Ordinal Bayesian Optimisationcited by 7
  21. 2020On Thompson Sampling with Langevin Algorithmscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 8; 2023: 10; 2024: 9; 2025: 10; 2026: 9.

52 papers.

Sort:

By area:

  1. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  2. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  3. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  4. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  5. 2021Nearly Optimal Algorithms for Level Set Estimationcited by 17
  6. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  7. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  8. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  9. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  10. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  11. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  12. 2021Rate-optimal Bayesian Simple Regret in Best Arm Identificationcited by 11
38 more
  1. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  2. 2022Graph Neural Network Banditscited by 10
  3. 2023Delayed Feedback in Kernel Banditscited by 10
  4. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  5. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  6. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  7. 2022Lower Bounds on the Worst-Case Complexity of Efficient Global Optimizationcited by 7
  8. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  9. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  10. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  11. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  12. 2023Training-Free Neural Active Learning with Initialization-Robustness Guaranteescited by 5
  13. 2024Sample-efficient Bayesian Optimisation Using Known Invariancescited by 4
  14. 2025Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewardscited by 4
  15. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  16. 2022On Average-Case Error Bounds for Kernel-Based Bayesian Quadraturecited by 3
  17. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  18. 2025Differentially Private Kernelized Contextual Banditscited by 3
  19. 2025Distributionally Robust Active Learning for Gaussian Process Regressioncited by 3
  20. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Boundscited by 3
  21. 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 3
  22. 2023Neural-BO: A Black-box Optimization Algorithm using Deep Neural Networkscited by 2
  23. 2024Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimizationcited by 2
  24. 2024Open Problem: Order Optimal Regret Bounds for Kernel-Based Reinforcement Learningcited by 2
  25. 2024Distributed Thompson sampling under constrained communicationcited by 2
  26. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 2
  27. 2022Benefits of Monotonicity in Safe Exploration with Gaussian Processescited by 1
  28. 2024Graph Neural Thompson Samplingcited by 1
  29. 2025Near-Optimal Sample Complexity in Reward-Free Kernel-Based Reinforcement Learningcited by 1
  30. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  31. 2023Distributed Optimization via Kernelized Multi-armed Banditscited by 0
  32. 2024PINN-BO: A Black-box Optimization Algorithm using Physics-Informed Neural Networkscited by 0
  33. 2024Order-Optimal Regret in Distributed Kernel Bandits using Uniform Sampling with Shared Randomnesscited by 0
  34. 2025Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Armscited by 0
  35. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  36. 2026Sharper Guarantees for Misspecified Kernelized Bandit Optimizationcited by 0
  37. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0
  38. 2026Trajectory-Aware Best-Arm Identification for Local Search Allocation in Bayesian Optimization and Beyondcited by 0

50 most cited of 52 All 52 (JSON)