mlsanityData to 7 Oct 2026

Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance

arXiv 2502.06363 ↗First posted 10 Feb 2025cs.LG stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the Gaussian process (GP) bandit problem, whose goal is to minimize regret under an unknown reward function lying in some reproducing kernel Hilbert space (RKHS). The maximum posterior variance analysis is vital in analyzing near-optimal GP bandit algorithms such as maximum variance reduction (MVR) and phased elimination (PE). Therefore, we first show the new upper bound of the maximum posterior variance, which improves the dependence of the noise variance parameters of the GP. By leveraging this result, we refine the MVR and PE to obtain (i) a nearly optimal regret upper bound in the noiseless setting and (ii) regret upper bounds that are optimal with respect to the RKHS norm of the reward function. Furthermore, as another application of our proposed bound, we analyze the GP bandit under the time-varying noise variance setting, which is the kernelized extension of the linear bandit with heteroscedastic noise. For this problem, we show that MVR and PE-based algorithms achieve noise variance-dependent regret upper bounds, which matches our regret lower bound.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 25 of its 36 references that are in the map. First posted on arXiv 10 Feb 2025.

Builds on

25 of 36 references.

References · 25

  1. 2013Learning to Optimize Via Posterior Samplingcited by 253
  2. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  3. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  4. 2016Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Roboticscited by 134
  5. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  6. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  7. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  8. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  9. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  10. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  11. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  12. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
13 more
  1. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  2. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  3. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  4. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  5. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
  6. 2020Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHScited by 16
  7. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
  8. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  9. 2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 15
  10. 2020Regret Bounds for Noise-Free Kernel-Based Banditscited by 11
  11. 2019Efficient Batch Black-box Optimization with Deterministic Regret Boundscited by 8
  12. 2024Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Explorationcited by 7
  13. 2024Tighter Confidence Bounds for Sequential Kernel Regressioncited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 5; 2026: 7.

12 papers.

  1. 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
  2. 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
  3. 2025Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?cited by 4
  4. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  5. 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 3
  6. 2026Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Boundscited by 2
  7. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 2
  8. 2026Batched Kernelized Bandits: Refinements and Extensionscited by 2
  9. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  10. 2025No-Regret Gaussian Process Optimization of Time-Varying Functionscited by 0
  11. 2026Towards Regret Guarantees for One-Step Lookahead Bayesian Optimizationcited by 0
  12. 2026Improved Regret Analysis for Parallel Gaussian Process Bandit Optimizationcited by 0