# Thompson Sampling in Switching Environments with Bayesian Online Change Point Detection

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2013.

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

- [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)
- [An Information-Theoretic Analysis of Nonstationary Bandit Learning](https://mlsanity.com/paper/2302.04452/) (2023)
- [Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation](https://mlsanity.com/paper/2202.09036/) (2022)
- [A unifying framework for generalised Bayesian online learning in non-stationary environments](https://mlsanity.com/paper/2411.10153/) (2024)
- [When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution](https://mlsanity.com/paper/2104.07150/) (2021)
- [Dynamic Memory for Interpretable Sequential Optimisation](https://mlsanity.com/paper/2206.13960/) (2022)
- [Fooling Algorithms in Non-Stationary Bandits using Belief Inertia](https://mlsanity.com/paper/2511.05620/) (2025)
- [When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity](https://mlsanity.com/paper/2610.03646/) (2026)

## Abstract (arXiv)

Thompson Sampling has recently been shown to be optimal in the Bernoulli Multi-Armed Bandit setting[Kaufmann et al., 2012]. This bandit problem assumes stationary distributions for the rewards. It is often unrealistic to model the real world as a stationary distribution. In this paper we derive and evaluate algorithms using Thompson Sampling for a Switching Multi-Armed Bandit Problem. We propose a Thompson Sampling strategy equipped with a Bayesian change point mechanism to tackle this problem. We develop algorithms for a variety of cases with constant switching rate: when switching occurs all arms change (Global Switching), switching occurs independently for each arm (Per-Arm Switching), when the switching rate is known and when it must be inferred from data. This leads to a family of algorithms we collectively term Change-Point Thompson Sampling (CTS). We show empirical results of the algorithm in 4 artificial environments, and 2 derived from real world data; news click-through[Yahoo!, 2011] and foreign exchange data[Dukascopy, 2012], comparing them to some other bandit algorithms. In real world data CTS is the most effective.