mlsanityData to 7 Oct 2026

Non-Stationary Bandit Learning via Predictive Sampling

arXiv 2205.01970 ↗First posted 4 May 2022cs.LG stat.MLcited by 21

Not on the map. Why?

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.

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

Builds on

34 of 91 references.

References · 34

  1. 2016Deep Exploration via Bootstrapped DQNcited by 518
  2. 2017A Tutorial on Thompson Samplingcited by 420
  3. 2013Learning to Optimize Via Posterior Samplingcited by 253
  4. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  5. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  6. 2018Learning to Optimize under Non-Stationaritycited by 85
  7. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 84
  8. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 75
  9. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  10. 2021Reinforcement Learning, Bit by Bitcited by 59
  11. 2017Rotting Banditscited by 57
  12. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
22 more
  1. 2018Information-Directed Exploration for Deep Reinforcement Learningcited by 52
  2. 2016Time-Varying Gaussian Process Bandit Optimizationcited by 50
  3. 2014Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewardscited by 41
  4. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
  5. 2018Satisficing in Time-Sensitive Bandit Learningcited by 38
  6. 2018An Information-Theoretic Analysis for Thompson Sampling with Many Actionscited by 35
  7. 2018An Efficient Bandit Algorithm for Realtime Multivariate Optimizationcited by 34
  8. 2017Taming Non-stationary Bandits: A Bayesian Approachcited by 30
  9. 2021From Predictions to Decisions: The Importance of Joint Predictive Distributionscited by 28
  10. 2022A New Look at Dynamic Regret for Non-Stationary Stochastic Banditscited by 28
  11. 2017Non-Stationary Bandits with Habituation and Recovery Dynamicscited by 23
  12. 2020Algorithms for Non-Stationary Generalized Linear Banditscited by 23
  13. 2021Deciding What to Learn: A Rate-Distortion Approachcited by 23
  14. 2018On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problemscited by 15
  15. 2019Efficient Change-Point Detection for Tackling Piecewise-Stationary Banditscited by 15
  16. 2021The Value of Information When Deciding What to Learncited by 15
  17. 2020A Change-Detection Based Thompson Sampling Framework for Non-Stationary Banditscited by 10
  18. 2013Thompson Sampling in Switching Environments with Bayesian Online Change Point Detectioncited by 8
  19. 2022Gaussian Imagination in Bandit Learningcited by 5
  20. 2019Thompson Sampling with Information Relaxation Penaltiescited by 4
  21. 2021Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Banditscited by 4
  22. 2022Rotting Infinitely Many-armed Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 4; 2025: 4; 2026: 5.

21 papers.

Sort:

  1. 2023Continual Learning as Computationally Constrained Reinforcement Learningcited by 35
  2. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  3. 2022Non-Stationary Bandits with Auto-Regressive Temporal Dependencycited by 10
  4. 2023A Definition of Non-Stationary Banditscited by 9
  5. 2023A Stability Principle for Learning under Non-Stationaritycited by 9
  6. 2024A unifying framework for generalised Bayesian online learning in non-stationary environmentscited by 5
  7. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  8. 2024Non-Stationary Latent Auto-Regressive Banditscited by 3
  9. 2024On Bits and Bandits: Quantifying the Regret-Information Trade-offcited by 3
  10. 2022Fast Change Identification in Multi-Play Bandits and its Applications in Wireless Networkscited by 2
  11. 2024Practical Bayesian Algorithm Execution via Posterior Samplingcited by 2
  12. 2023Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Samplingcited by 1
9 more
  1. 2025Power Constrained Nonstationary Bandits with Habituation and Recovery Dynamicscited by 1
  2. 2023Revisiting Weighted Strategy for Non-stationary Parametric Banditscited by 0
  3. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  4. 2025In-Context Decision Making for Optimizing Complex AutoML Pipelinescited by 0
  5. 2025Conformal bandits: bringing statistical validity and reward efficiency under weak arm separabilitycited by 0
  6. 2026On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimizationcited by 0
  7. 2026Not all uncertainty is alike: volatility, stochasticity, and explorationcited by 0
  8. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0
  9. 2026Future Information-Directed Sampling for Bayesian Nonstationary Banditscited by 0