mlsanityData to 7 Oct 2026

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

arXiv 1706.00090 ↗First posted 31 May 2017stat.ML cs.IT cs.LGcited by 77

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider the problem of sequentially optimizing a black-box function f based on noisy samples and bandit feedback. We assume that f is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yielding a commonly-considered non-Bayesian form of Gaussian process bandit optimization. We provide algorithm-independent lower bounds on the simple regret, measuring the suboptimality of a single point reported after T rounds, and on the cumulative regret, measuring the sum of regrets over the T chosen points. For the isotropic squared-exponential kernel in d dimensions, we find that an average simple regret of ε requires T = Omegabig(frac1ε2 (logfrac1ε)d/2big), and the average cumulative regret is at least Omegabig( √T(log T)d/2 big), thus matching existing upper bounds up to the replacement of d/2 by 2d+O(1) in both cases. For the Mat'ern-nu kernel, we give analogous bounds of the form Omegabig( (frac1ε)2+d/nubig) and Omegabig( T^fracnu + d2nu + d big), and discuss the resulting gaps to the existing upper bounds.

Key facts. Cited by 77 papers in the map (data through 7 Oct 2026). First posted on arXiv 31 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 15; 2023: 13; 2024: 9; 2025: 17; 2026: 11.

77 papers.

Sort:

By area:

  1. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  2. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  3. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  4. 2021Neural Contextual Bandits without Regretcited by 40
  5. 2021Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learningcited by 38
  6. 2022Model-based Causal Bayesian Optimizationcited by 26
  7. 2023On the Sublinear Regret of GP-UCBcited by 25
  8. 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 23
  9. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  10. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  11. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  12. 2021Nearly Optimal Algorithms for Level Set Estimationcited by 17
38 more
  1. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  2. 2022Communication Efficient Distributed Learning for Kernelized Contextual Banditscited by 15
  3. 2022Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimizationcited by 14
  4. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  5. 2021Collaborative Pure Exploration in Kernel Banditcited by 13
  6. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  7. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  8. 2022Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Timescited by 12
  9. 2023Quantum Bayesian Optimizationcited by 12
  10. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  11. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
  12. 2023Delayed Feedback in Kernel Banditscited by 10
  13. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  14. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  15. 2022Lower Bounds on the Worst-Case Complexity of Efficient Global Optimizationcited by 7
  16. 2022Global Optimization with Parametric Function Approximationcited by 7
  17. 2022Collaborative Learning in Kernel-based Bandits for Distributed Userscited by 6
  18. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  19. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  20. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  21. 2022Instance-Dependent Regret Analysis of Kernelized Banditscited by 5
  22. 2022Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimizationcited by 5
  23. 2023Adaptation to Misspecified Kernel Regularity in Kernelised Banditscited by 5
  24. 2024Principled Bayesian Optimisation in Collaboration with Human Expertscited by 5
  25. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  26. 2023Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fieldscited by 4
  27. 2024Sample-efficient Bayesian Optimisation Using Known Invariancescited by 4
  28. 2025Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewardscited by 4
  29. 2025Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Boundscited by 4
  30. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  31. 2021Bayesian Optimistic Optimisation with Exponentially Decaying Regretcited by 3
  32. 2022Efficient Kernel UCB for Contextual Banditscited by 3
  33. 2022On Average-Case Error Bounds for Kernel-Based Bayesian Quadraturecited by 3
  34. 2022Regret Bounds for Noise-Free Cascaded Kernelized Banditscited by 3
  35. 2023On the Suboptimality of GP-UCB under Polynomial Effective Optimismcited by 3
  36. 2024NeoRL: Efficient Exploration for Nonepisodic RLcited by 3
  37. 2024Regional Expected Improvement for Efficient Trust Region Selection in High-Dimensional Bayesian Optimizationcited by 3
  38. 2025Differentially Private Kernelized Contextual Banditscited by 3

50 most cited of 77 All 77 (JSON)