# Learning Contextual Bandits in a Non-stationary Environment

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2018.

## Built on by (most cited first, 26 of 26)

- [Dynamic Causal Bayesian Optimization](https://mlsanity.com/paper/2110.13891/) (2021)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [HyperBandit: Contextual Bandit with Hypernewtork for Time-Varying User Preferences in Streaming Recommendation](https://mlsanity.com/paper/2308.08497/) (2023)
- [Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning](https://mlsanity.com/paper/2207.05742/) (2022)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits](https://mlsanity.com/paper/2311.05794/) (2023)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [Dynamic Embedding Size Search with Minimum Regret for Streaming Recommender System](https://mlsanity.com/paper/2308.07760/) (2023)
- [Linear Bandits with Memory: from Rotting to Rising](https://mlsanity.com/paper/2302.08345/) (2023)
- [Disentangled Representation for Diversified Recommendations](https://mlsanity.com/paper/2301.05492/) (2023)
- [Discounted Thompson Sampling for Non-Stationary Bandit Problems](https://mlsanity.com/paper/2305.10718/) (2023)
- [Information-Gathering in Latent Bandits](https://mlsanity.com/paper/2207.03635/) (2022)
- [Contextual Bandits and Optimistically Universal Learning](https://mlsanity.com/paper/2301.00241/) (2022)
- [BayesCNS: A Unified Bayesian Approach to Address Cold Start and Non-Stationarity in Search Systems at Scale](https://mlsanity.com/paper/2410.02126/) (2024)
- [Periodic-GP: Learning Periodic World with Gaussian Process Bandits](https://mlsanity.com/paper/2105.14422/) (2021)
- [Forced Exploration in Bandit Problems](https://mlsanity.com/paper/2312.07285/) (2023)
- [Enhancing Bandit Algorithms with LLMs for Time-varying User Preferences in Streaming Recommendations](https://mlsanity.com/paper/2602.08067/) (2026)
- [When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution](https://mlsanity.com/paper/2104.07150/) (2021)
- [Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums](https://mlsanity.com/paper/2206.00861/) (2022)
- [Online Learning with Costly Features in Non-stationary Environments](https://mlsanity.com/paper/2307.09388/) (2023)
- [Adaptive Interventions with User-Defined Goals for Health Behavior Change](https://mlsanity.com/paper/2311.09483/) (2023)
- [Influencing Bandits: Arm Selection for Preference Shaping](https://mlsanity.com/paper/2403.00036/) (2024)
- [Meta Policy Switching for Secure UAV Deconfliction in Adversarial Airspace](https://mlsanity.com/paper/2506.21127/) (2025)
- [A Direct Approach for Handling Contextual Bandits with Latent State Dynamics](https://mlsanity.com/paper/2604.08149/) (2026)
- [Linear and Neural Dueling Bandits with Delayed Feedback](https://mlsanity.com/paper/2605.26554/) (2026)

## Abstract (arXiv)

Multi-armed bandit algorithms have become a reference solution for handling the explore/exploit dilemma in recommender systems, and many other important real-world problems, such as display advertisement. However, such algorithms usually assume a stationary reward distribution, which hardly holds in practice as users' preferences are dynamic. This inevitably costs a recommender system consistent suboptimal performance. In this paper, we consider the situation where the underlying distribution of reward remains unchanged over (possibly short) epochs and shifts at unknown time instants. In accordance, we propose a contextual bandit algorithm that detects possible changes of environment based on its reward estimation confidence and updates its arm selection strategy respectively. Rigorous upper regret bound analysis of the proposed algorithm demonstrates its learning effectiveness in such a non-trivial environment. Extensive empirical evaluations on both synthetic and real-world datasets for recommendation confirm its practical utility in a changing environment.