mlsanityData to 7 Oct 2026

Lower Bounds for Time-Varying Kernelized Bandits

arXiv 2410.16692 ↗First posted 22 Oct 2024stat.ML cs.IT cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

The optimization of black-box functions with noisy observations is a fundamental problem with widespread applications, and has been widely studied under the assumption that the function lies in a reproducing kernel Hilbert space (RKHS). This problem has been studied extensively in the stationary setting, and near-optimal regret bounds are known via developments in both upper and lower bounds. In this paper, we consider non-stationary scenarios, which are crucial for certain applications but are currently less well-understood. Specifically, we provide the first algorithm-independent lower bounds, where the time variations are subject satisfying a total variation budget according to some function norm. Under ℓ∞-norm variations, our bounds are found to be close to an existing upper bound (Hong et al., 2023). Under RKHS norm variations, the upper and lower bounds are still reasonably close but with more of a gap, raising the interesting open question of whether non-minor improvements in the upper bound are possible.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 22 of its 29 references that are in the map. First posted on arXiv 22 Oct 2024.

Builds on

22 of 29 references.

References · 22

  1. 2017On Kernelized Multi-armed Banditscited by 348
  2. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  3. 2013Non-stationary Stochastic Optimizationcited by 173
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  5. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  6. 2018Learning to Optimize under Non-Stationaritycited by 85
  7. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  8. 2018Adversarially Robust Optimization with Gaussian Processescited by 61
  9. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  10. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  11. 2016Time-Varying Gaussian Process Bandit Optimizationcited by 50
  12. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
10 more
  1. 2021Optimal Dynamic Regret in Exp-Concave Online Learningcited by 39
  2. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  3. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  4. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 27
  5. 2023On the Sublinear Regret of GP-UCBcited by 25
  6. 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
  7. 2021No-Regret Algorithms for Time-Varying Bayesian Optimizationcited by 19
  8. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  9. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  10. 2022On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedbackcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 4.

5 papers.

  1. 2026Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hyperspherecited by 4
  2. 2025Non-Stationary Lipschitz Banditscited by 3
  3. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  4. 2026Near-Optimal Regret in Adversarial Kernel Banditscited by 0
  5. 2026Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Explorationcited by 0