# Discounted Thompson Sampling for Non-Stationary Bandit Problems

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 18 May 2023.

## Builds on (most cited first, 10 of 10)

- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Taming Non-stationary Bandits: A Bayesian Approach](https://mlsanity.com/paper/1707.09727/) (2017)
- [The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms](https://mlsanity.com/paper/2002.10121/) (2020)
- [Tracking Most Significant Arm Switches in Bandits](https://mlsanity.com/paper/2112.13838/) (2021)
- [Learning Contextual Bandits in a Non-stationary Environment](https://mlsanity.com/paper/1805.09365/) (2018)
- [On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variables](https://mlsanity.com/paper/1810.09006/) (2018)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)

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

- [Task Selection and Assignment for Multi-modal Multi-task Dialogue Act Classification with Non-stationary Multi-armed Bandits](https://mlsanity.com/paper/2309.09832/) (2023)
- [Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits](https://mlsanity.com/paper/2410.05734/) (2024)
- [A Modularized Framework for Piecewise-Stationary Restless Bandits](https://mlsanity.com/paper/2604.10177/) (2026)
- [402Pilot: An x402 Decision Layer for Autonomous Agent Micropayments](https://mlsanity.com/paper/2608.01341/) (2026)

## Abstract (arXiv)

Non-stationary multi-armed bandit (NS-MAB) problems have recently received significant attention. NS-MAB are typically modelled in two scenarios: abruptly changing, where reward distributions remain constant for a certain period and change at unknown time steps, and smoothly changing, where reward distributions evolve smoothly based on unknown dynamics. In this paper, we propose Discounted Thompson Sampling (DS-TS) with Gaussian priors to address both non-stationary settings. Our algorithm passively adapts to changes by incorporating a discounted factor into Thompson Sampling. DS-TS method has been experimentally validated, but analysis of the regret upper bound is currently lacking. Under mild assumptions, we show that DS-TS with Gaussian priors can achieve nearly optimal regret bound on the order of tildeO(√TBT) for abruptly changing and tildeO(Tβ) for smoothly changing, where T is the number of time steps, BT is the number of breakpoints, β is associated with the smoothly changing environment and tildeO hides the parameters independent of T as well as logarithmic terms. Furthermore, empirical comparisons between DS-TS and other non-stationary bandit algorithms demonstrate its competitive performance. Specifically, when prior knowledge of the maximum expected reward is available, DS-TS has the potential to outperform state-of-the-art algorithms.