mlsanityData to 7 Oct 2026

A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free

arXiv 1902.00980 ↗First posted 3 Feb 2019cs.LG stat.MLcited by 71

Not on the map. Why?

Abstract (arXiv)

We propose the first contextual bandit algorithm that is parameter-free, efficient, and optimal in terms of dynamic regret. Specifically, our algorithm achieves dynamic regret O(min√ST, Delta^frac13T^frac23) for a contextual bandit problem with T rounds, S switches and Delta total variation in data distributions. Importantly, our algorithm is adaptive and does not need to know S or Delta ahead of time, and can be implemented efficiently assuming access to an ERM oracle. Our results strictly improve the O(min S^frac14T^frac34, Delta^frac15T^frac45) bound of (Luo et al., 2018), and greatly generalize and improve the O(√ST) result of (Auer et al, 2018) that holds only for the two-armed bandit problem without contextual information. The key novelty of our algorithm is to introduce replay phases, in which the algorithm acts according to its previous decisions for a certain amount of time in order to detect non-stationarity while maintaining a good balance between exploration and exploitation.

Key facts. Cited by 71 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 12; 2022: 16; 2023: 21; 2024: 7; 2025: 8; 2026: 6.

71 papers.

Sort:

By area:

  1. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  2. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  3. 2023KnowGPT: Knowledge Graph based Prompting for Large Language Modelscited by 30
  4. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  5. 2021Tracking Most Significant Arm Switches in Banditscited by 27
  6. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  7. 2022Stochastic Rising Banditscited by 18
  8. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  9. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  10. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  11. 2020Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learningcited by 15
  12. 2023Smooth Non-Stationary Banditscited by 13
38 more
  1. 2021Bandit Algorithms for Precision Medicinecited by 12
  2. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  3. 2021Learning User Preferences in Non-Stationary Environmentscited by 10
  4. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  5. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  6. 2023A Definition of Non-Stationary Banditscited by 9
  7. 2023A Stability Principle for Learning under Non-Stationaritycited by 9
  8. 2021Generalized non-stationary banditscited by 8
  9. 2021On Limited-Memory Subsampling Strategies for Banditscited by 8
  10. 2022Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Armscited by 8
  11. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  12. 2021On Slowly-varying Non-stationary Banditscited by 7
  13. 2022Event-Triggered Time-Varying Bayesian Optimizationcited by 7
  14. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  15. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  16. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  17. 2023Adversarial Rewards in Universal Learning for Contextual Banditscited by 5
  18. 2023Linear Bandits with Memory: from Rotting to Risingcited by 5
  19. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  20. 2022Rotting Infinitely Many-armed Banditscited by 4
  21. 2022Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Designcited by 4
  22. 2023Discounted Thompson Sampling for Non-Stationary Bandit Problemscited by 4
  23. 2024Adaptive Smooth Non-Stationary Banditscited by 4
  24. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  25. 2025Non-Stationary Lipschitz Banditscited by 3
  26. 2022Bridging Adversarial and Nonstationary Multi-armed Banditcited by 2
  27. 2022Contextual Bandits and Optimistically Universal Learningcited by 2
  28. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
  29. 2023An Improved Relaxation for Oracle-Efficient Adversarial Contextual Banditscited by 2
  30. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  31. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  32. 2024Cost-efficient Knowledge-based Question Answering with Large Language Modelscited by 2
  33. 2026A single algorithm for both restless and rested rotting banditscited by 2
  34. 2021Periodic-GP: Learning Periodic World with Gaussian Process Banditscited by 1
  35. 2022Adversarial Bandits against Arbitrary Strategiescited by 1
  36. 2023MNL-Bandit in non-stationary environmentscited by 1
  37. 2023An Adaptive Method for Weak Supervision with Drifting Datacited by 1
  38. 2023Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Samplingcited by 1

50 most cited of 71 All 71 (JSON)