# Non-Stationary Bandit Learning via Predictive Sampling

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 91 references that are in the map.
- First posted on arXiv 4 May 2022.

## Builds on (most cited first, 30 of 34)

- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Information-Directed Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1812.07544/) (2018)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Satisficing in Time-Sensitive Bandit Learning](https://mlsanity.com/paper/1803.02855/) (2018)
- [An Information-Theoretic Analysis for Thompson Sampling with Many Actions](https://mlsanity.com/paper/1805.11845/) (2018)
- [An Efficient Bandit Algorithm for Realtime Multivariate Optimization](https://mlsanity.com/paper/1810.09558/) (2018)
- [Taming Non-stationary Bandits: A Bayesian Approach](https://mlsanity.com/paper/1707.09727/) (2017)
- [From Predictions to Decisions: The Importance of Joint Predictive Distributions](https://mlsanity.com/paper/2107.09224/) (2021)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Algorithms for Non-Stationary Generalized Linear Bandits](https://mlsanity.com/paper/2003.10113/) (2020)
- [Non-Stationary Bandits with Habituation and Recovery Dynamics](https://mlsanity.com/paper/1707.08423/) (2017)
- [Deciding What to Learn: A Rate-Distortion Approach](https://mlsanity.com/paper/2101.06197/) (2021)
- [On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems](https://mlsanity.com/paper/1802.08380/) (2018)
- [Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits](https://mlsanity.com/paper/1902.01575/) (2019)
- [The Value of Information When Deciding What to Learn](https://mlsanity.com/paper/2110.13973/) (2021)
- [A Change-Detection Based Thompson Sampling Framework for Non-Stationary Bandits](https://mlsanity.com/paper/2009.02791/) (2020)
- [Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection](https://mlsanity.com/paper/1302.3721/) (2013)

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

- [Continual Learning as Computationally Constrained Reinforcement Learning](https://mlsanity.com/paper/2307.04345/) (2023)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [A Stability Principle for Learning under Non-Stationarity](https://mlsanity.com/paper/2310.18304/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [A unifying framework for generalised Bayesian online learning in non-stationary environments](https://mlsanity.com/paper/2411.10153/) (2024)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs](https://mlsanity.com/paper/2601.01069/) (2026)
- [Non-Stationary Latent Auto-Regressive Bandits](https://mlsanity.com/paper/2402.03110/) (2024)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Fast Change Identification in Multi-Play Bandits and its Applications in Wireless Networks](https://mlsanity.com/paper/2205.10366/) (2022)
- [Practical Bayesian Algorithm Execution via Posterior Sampling](https://mlsanity.com/paper/2410.20596/) (2024)
- [Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling](https://mlsanity.com/paper/2310.07786/) (2023)
- [Power Constrained Nonstationary Bandits with Habituation and Recovery Dynamics](https://mlsanity.com/paper/2511.02944/) (2025)
- [Not all uncertainty is alike: volatility, stochasticity, and exploration](https://mlsanity.com/paper/2605.19215/) (2026)
- [Revisiting Weighted Strategy for Non-stationary Parametric Bandits](https://mlsanity.com/paper/2303.02691/) (2023)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [In-Context Decision Making for Optimizing Complex AutoML Pipelines](https://mlsanity.com/paper/2508.13657/) (2025)
- [Conformal bandits: bringing statistical validity and reward efficiency under weak arm separability](https://mlsanity.com/paper/2512.09850/) (2025)
- [On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization](https://mlsanity.com/paper/2603.18514/) (2026)
- [Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent](https://mlsanity.com/paper/2605.25590/) (2026)
- [Future Information-Directed Sampling for Bayesian Nonstationary Bandits](https://mlsanity.com/paper/2609.33981/) (2026)

## Abstract (arXiv)

Thompson sampling has proven effective across a wide range of stationary bandit environments. However, as we demonstrate in this paper, it can perform poorly when applied to non-stationary environments. We show that such failures are attributed to the fact that, when exploring, the algorithm does not differentiate actions based on how quickly the information acquired loses its usefulness due to nonstationarity. Building upon this insight, we propose predictive sampling, an algorithm that deprioritizes acquiring information that quickly loses usefulness. Theoretical guarantee on the performance of predictive sampling is established through a Bayesian regret bound. We provide versions of predictive sampling for which computations tractably scale to complex bandit environments of practical interest. Through numerical simulations, we demonstrate that predictive sampling outperforms Thompson sampling in all non-stationary environments examined.