# Sliding-Window Thompson Sampling for Non-Stationary Settings

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 71 references that are in the map.
- First posted on arXiv 8 Sep 2024.

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

- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [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)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [Taming Non-stationary Bandits: A Bayesian Approach](https://mlsanity.com/paper/1707.09727/) (2017)
- [On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials](https://mlsanity.com/paper/1903.07082/) (2019)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits](https://mlsanity.com/paper/1902.01575/) (2019)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection](https://mlsanity.com/paper/1302.3721/) (2013)
- [Unimodal Thompson Sampling for Graph-Structured Arms](https://mlsanity.com/paper/1611.05724/) (2016)
- [Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces](https://mlsanity.com/paper/1911.07755/) (2019)
- [Truthful Learning Mechanisms for Multi-Slot Sponsored Search Auctions with Externalities](https://mlsanity.com/paper/1405.2484/) (2014)
- [Thompson Sampling for Dynamic Pricing](https://mlsanity.com/paper/1802.03050/) (2018)

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

- [Procedural Memory Is Not All You Need: Bridging Cognitive Gaps in LLM-Based Agents](https://mlsanity.com/paper/2505.03434/) (2025)
- [Agentic Personalisation of Cross-Channel Marketing Experiences](https://mlsanity.com/paper/2506.16429/) (2025)
- [Rising Rested Bandits: Lower Bounds and Efficient Algorithms](https://mlsanity.com/paper/2411.14446/) (2024)
- [Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2508.16027/) (2025)
- [Combinatorial Rising Bandits](https://mlsanity.com/paper/2412.00798/) (2024)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [Improving Portfolio Optimization Results with Bandit Networks](https://mlsanity.com/paper/2410.04217/) (2024)
- [Partition Tree Weighting for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2502.19325/) (2025)
- [Thompson Sampling-Based Learning and Control for Unknown Dynamic Systems](https://mlsanity.com/paper/2506.22186/) (2025)
- [Buzz, Choose, Forget: A Meta-Bandit Framework for Bee-Like Decision Making](https://mlsanity.com/paper/2510.16462/) (2025)
- [Adaptive Requesting in Decentralized Edge Networks via Non-Stationary Bandits](https://mlsanity.com/paper/2601.08760/) (2026)
- [Rising Multi-Armed Bandits with Known Horizons](https://mlsanity.com/paper/2602.10727/) (2026)
- [Periodic Bootstrap Thompson Sampling For Periodically Non-Stationary Bandit Problems](https://mlsanity.com/paper/2607.16986/) (2026)
- [402Pilot: An x402 Decision Layer for Autonomous Agent Micropayments](https://mlsanity.com/paper/2608.01341/) (2026)
- [Future Information-Directed Sampling for Bayesian Nonstationary Bandits](https://mlsanity.com/paper/2609.33981/) (2026)
- [When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity](https://mlsanity.com/paper/2610.03646/) (2026)
- [Choosing LLMs for Strategic Agent Interactions](https://mlsanity.com/paper/2610.18354/) (2026)

## Abstract (arXiv)

Non-stationary multi-armed bandits (NS-MABs) model sequential decision-making problems in which the expected rewards of a set of actions, a.k.a.~arms, evolve over time. In this paper, we fill a gap in the literature by providing a novel analysis of Thompson sampling-inspired (TS) algorithms for NS-MABs that both corrects and generalizes existing work. Specifically, we study the cumulative frequentist regret of two algorithms based on sliding-window TS approaches with different priors, namely textitBeta-SWTS and textitγ-SWGTS. We derive a unifying regret upper bound for these algorithms that applies to any arbitrary NS-MAB (with either Bernoulli or subgaussian rewards). Our result introduces new indices that capture the inherent sources of complexity in the learning problem. Then, we specialize our general result to two of the most common NS-MAB settings: the textitabruptly changing and the textitsmoothly changing environments, showing that it matches state-of-the-art results. Finally, we evaluate the performance of the analyzed algorithms in simulated environments and compare them with state-of-the-art approaches for NS-MABs.