# A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2017.

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

- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [An empirical evaluation of active inference in multi-armed bandits](https://mlsanity.com/paper/2101.08699/) (2021)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [On Limited-Memory Subsampling Strategies for Bandits](https://mlsanity.com/paper/2106.10935/) (2021)
- [Bandit Quickest Changepoint Detection](https://mlsanity.com/paper/2107.10492/) (2021)
- [Finite-time Analysis of Globally Nonstationary Multi-Armed Bandits](https://mlsanity.com/paper/2107.11419/) (2021)
- [Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2202.00935/) (2022)
- [Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret](https://mlsanity.com/paper/2101.08980/) (2021)
- [Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Models](https://mlsanity.com/paper/2601.22538/) (2026)
- [Decentralized Competing Bandits in Non-Stationary Matching Markets](https://mlsanity.com/paper/2206.00120/) (2022)
- [Discounted Thompson Sampling for Non-Stationary Bandit Problems](https://mlsanity.com/paper/2305.10718/) (2023)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Stochastic Multi-armed Bandits with Non-stationary Rewards Generated by a Linear Dynamical System](https://mlsanity.com/paper/2204.05782/) (2022)
- [Piecewise-Stationary Multi-Objective Multi-Armed Bandit with Application to Joint Communications and Sensing](https://mlsanity.com/paper/2302.05257/) (2023)
- [Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demand](https://mlsanity.com/paper/2201.00486/) (2022)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Distributed Consensus Algorithm for Decision-Making in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2306.05998/) (2023)
- [A single algorithm for both restless and rested rotting bandits](https://mlsanity.com/paper/2604.21432/) (2026)
- [MNL-Bandit in non-stationary environments](https://mlsanity.com/paper/2303.02504/) (2023)
- [Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.14138/) (2023)
- [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)
- [Exploiting Adjacent Similarity in Multi-Armed Bandit Tasks via Transfer of Reward Samples](https://mlsanity.com/paper/2409.19975/) (2024)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)

## Abstract (arXiv)

The multi-armed bandit problem has been extensively studied under the stationary assumption. However in reality, this assumption often does not hold because the distributions of rewards themselves may change over time. In this paper, we propose a change-detection (CD) based framework for multi-armed bandit problems under the piecewise-stationary setting, and study a class of change-detection based UCB (Upper Confidence Bound) policies, CD-UCB, that actively detects change points and restarts the UCB indices. We then develop CUSUM-UCB and PHT-UCB, that belong to the CD-UCB class and use cumulative sum (CUSUM) and Page-Hinkley Test (PHT) to detect changes. We show that CUSUM-UCB obtains the best known regret upper bound under mild assumptions. We also demonstrate the regret reduction of the CD-UCB policies over arbitrary Bernoulli rewards and Yahoo! datasets of webpage click-through rates.