mlsanityData to 7 Oct 2026

An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge

arXiv 2205.14775 ↗First posted 29 May 2022stat.ML cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

We propose an algorithm for non-stationary kernel bandits that does not require prior knowledge of the degree of non-stationarity. The algorithm follows randomized strategies obtained by solving optimization problems that balance exploration and exploitation. It adapts to non-stationarity by restarting when a change in the reward function is detected. Our algorithm enjoys a tighter dynamic regret bound than previous work on the non-stationary kernel bandit setting. Moreover, when applied to the non-stationary linear bandit setting by using a linear kernel, our algorithm is nearly minimax optimal, solving an open problem in the non-stationary linear bandit literature. We extend our algorithm to use a neural network for dynamically adapting the feature mapping to observed data. We prove a dynamic regret bound of the extension using the neural tangent kernel theory. We demonstrate empirically that our algorithm and the extension can adapt to varying degrees of non-stationarity.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 32 of its 63 references that are in the map. First posted on arXiv 29 May 2022.

Builds on

32 of 63 references.

References · 32

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  4. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  5. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  6. 2017On Kernelized Multi-armed Banditscited by 348
  7. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  8. 2020Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernelcited by 185
  9. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  10. 2020Finite Versus Infinite Neural Networks: an Empirical Studycited by 156
  11. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  12. 2020Neural Thompson Samplingcited by 127
20 more
  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2018Learning to Optimize under Non-Stationaritycited by 85
  3. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 84
  4. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  5. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  6. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  7. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  8. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  9. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 48
  10. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  11. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  12. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  13. 2021Neural Contextual Bandits without Regretcited by 40
  14. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  15. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  16. 2021Batched Neural Banditscited by 22
  17. 2021Uniform Generalization Bounds for Overparameterized Neural Networkscited by 21
  18. 2021No-Regret Algorithms for Time-Varying Bayesian Optimizationcited by 19
  19. 2019Randomized Exploration for Non-Stationary Stochastic Linear Banditscited by 18
  20. 2022Learning Neural Contextual Bandits Through Perturbed Rewardscited by 17

Built on by

Cited by year (2026 to 7 Oct)

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

17 papers.

Sort:

  1. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  2. 2024Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimalcited by 6
  3. 2024Principled Bayesian Optimisation in Collaboration with Human Expertscited by 5
  4. 2024Lower Bounds for Time-Varying Kernelized Banditscited by 5
  5. 2024Safe Time-Varying Optimization based on Gaussian Processes with Spatio-Temporal Kernelcited by 4
  6. 2025Non-Stationary Lipschitz Banditscited by 3
  7. 2025Tracking Most Significant Shifts in Infinite-Armed Banditscited by 1
  8. 2025Constrained Feedback Learning for Non-Stationary Multi-Armed Banditscited by 1
  9. 2026Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Lossescited by 1
  10. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  11. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  12. 2025Asymptotic Performance of Time-Varying Bayesian Optimizationcited by 0
5 more
  1. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  2. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0
  3. 2026Near-Optimal Regret in Adversarial Kernel Banditscited by 0
  4. 2026Instance-dependent Stochastic Lipschitz banditcited by 0
  5. 2026Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Explorationcited by 0