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

arXiv: https://arxiv.org/abs/1902.00980 · HTML: https://mlsanity.com/paper/1902.00980/

## Key facts

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

## Built on by (most cited first, 30 of 71)

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [KnowGPT: Knowledge Graph based Prompting for Large Language Models](https://mlsanity.com/paper/2312.06185/) (2023)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)
- [Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2006.16785/) (2020)
- [Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2301.12366/) (2023)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)
- [Non-stationary Bandits and Meta-Learning with a Small Set of Optimal Arms](https://mlsanity.com/paper/2202.13001/) (2022)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Event-Triggered Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2208.10790/) (2022)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Non-stationary Reinforcement Learning under General Function Approximation](https://mlsanity.com/paper/2306.00861/) (2023)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)

## 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.