# Taming Non-stationary Bandits: A Bayesian Approach

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2017.

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

- [Continual Learning as Computationally Constrained Reinforcement Learning](https://mlsanity.com/paper/2307.04345/) (2023)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [BOTS: A Unified Framework for Bayesian Online Task Selection in LLM Reinforcement Finetuning](https://mlsanity.com/paper/2510.26374/) (2025)
- [An empirical evaluation of active inference in multi-armed bandits](https://mlsanity.com/paper/2101.08699/) (2021)
- [Module-wise Adaptive Distillation for Multimodality Foundation Models](https://mlsanity.com/paper/2310.04550/) (2023)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (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)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)
- [Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret](https://mlsanity.com/paper/2101.08980/) (2021)
- [Reinforcement Learning for Combining Search Methods in the Calibration of Economic ABMs](https://mlsanity.com/paper/2302.11835/) (2023)
- [Discounted Thompson Sampling for Non-Stationary Bandit Problems](https://mlsanity.com/paper/2305.10718/) (2023)
- [Non-Stationary Latent Auto-Regressive Bandits](https://mlsanity.com/paper/2402.03110/) (2024)
- [Fast Change Identification in Multi-Play Bandits and its Applications in Wireless Networks](https://mlsanity.com/paper/2205.10366/) (2022)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Existence conditions for hidden feedback loops in online recommender systems](https://mlsanity.com/paper/2109.05278/) (2021)
- [SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzing](https://mlsanity.com/paper/2211.03285/) (2022)
- [Non-Stationary Contextual Bandit Learning via Neural Predictive Ensemble Sampling](https://mlsanity.com/paper/2310.07786/) (2023)
- [Forced Exploration in Bandit Problems](https://mlsanity.com/paper/2312.07285/) (2023)
- [Dynamic Memory for Interpretable Sequential Optimisation](https://mlsanity.com/paper/2206.13960/) (2022)
- [Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting](https://mlsanity.com/paper/2409.05980/) (2024)
- [Improving Portfolio Optimization Results with Bandit Networks](https://mlsanity.com/paper/2410.04217/) (2024)
- [Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2410.05734/) (2024)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [Thompson Sampling-Based Learning and Control for Unknown Dynamic Systems](https://mlsanity.com/paper/2506.22186/) (2025)
- [TS-Insight: Visualizing Thompson Sampling for Verification and XAI](https://mlsanity.com/paper/2507.19898/) (2025)
- [A Modularized Framework for Piecewise-Stationary Restless Bandits](https://mlsanity.com/paper/2604.10177/) (2026)
- [Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits](https://mlsanity.com/paper/2606.23933/) (2026)
- [Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits](https://mlsanity.com/paper/2609.19709/) (2026)

## Abstract (arXiv)

We consider the multi armed bandit problem in non-stationary environments. Based on the Bayesian method, we propose a variant of Thompson Sampling which can be used in both rested and restless bandit scenarios. Applying discounting to the parameters of prior distribution, we describe a way to systematically reduce the effect of past observations. Further, we derive the exact expression for the probability of picking sub-optimal arms. By increasing the exploitative value of Bayes' samples, we also provide an optimistic version of the algorithm. Extensive empirical analysis is conducted under various scenarios to validate the utility of proposed algorithms. A comparison study with various state-of-the-arm algorithms is also included.