mlsanityData to 7 Oct 2026

Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere

arXiv 2602.17940 ↗First posted 20 Feb 2026cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the dimension-dependent logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers Omega(√T (ln T)d (ln ln T)-d) cumulative regret, where T and d represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires Omega(ε-2(ln frac1ε)d (ln ln frac1ε)-d) time steps to find an ε-optimal point. We also provide the improved O((ln T)d+1(ln ln T)-d) upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to dimension-independent logarithmic factors under a hyperspherical input domain.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 28 of its 47 references that are in the map. First posted on arXiv 20 Feb 2026.

Builds on

28 of 47 references.

References · 28

  1. 2018A Tutorial on Bayesian Optimizationcited by 734
  2. 2019Scalable Global Optimization via Local Bayesian Optimizationcited by 359
  3. 2017On Kernelized Multi-armed Banditscited by 348
  4. 2013Learning to Optimize Via Posterior Samplingcited by 253
  5. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 188
  6. 2013Bayesian Optimization in a Billion Dimensions via Random Embeddingscited by 178
  7. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  8. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  9. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 137
  10. 2024Vanilla Bayesian Optimization Performs Great in High Dimensionscited by 87
  11. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  12. 2018Adversarially Robust Optimization with Gaussian Processescited by 61
16 more
  1. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  2. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  3. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  4. 2021Neural Contextual Bandits without Regretcited by 40
  5. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  6. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  7. 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
  8. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  9. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  10. 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 12
  11. 2020Regret Bounds for Noise-Free Kernel-Based Banditscited by 11
  12. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  13. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  14. 2022Provably and Practically Efficient Neural Contextual Banditscited by 6
  15. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  16. 2025High-dimensional Nonparametric Contextual Bandit Problemcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 2
  2. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  3. 2026Towards Regret Guarantees for One-Step Lookahead Bayesian Optimizationcited by 0
  4. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 0