# Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2018.

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

- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits](https://mlsanity.com/paper/2201.06532/) (2022)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms](https://mlsanity.com/paper/2505.15141/) (2025)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Bandit Algorithms for Precision Medicine](https://mlsanity.com/paper/2108.04782/) (2021)
- [Testing Stationarity and Change Point Detection in Reinforcement Learning](https://mlsanity.com/paper/2203.01707/) (2022)
- [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)
- [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)
- [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)
- [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)
- [Collaborative Algorithms for Online Personalized Mean Estimation](https://mlsanity.com/paper/2208.11530/) (2022)
- [Kolmogorov-Smirnov Test-Based Actively-Adaptive Thompson Sampling for Non-Stationary Bandits](https://mlsanity.com/paper/2105.14586/) (2021)
- [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)
- [Dynamic Pricing and Learning under the Bass Model](https://mlsanity.com/paper/2103.05199/) (2021)
- [Using Non-Stationary Bandits for Learning in Repeated Cournot Games with Non-Stationary Demand](https://mlsanity.com/paper/2201.00486/) (2022)
- [Fast Change Identification in Multi-Play Bandits and its Applications in Wireless Networks](https://mlsanity.com/paper/2205.10366/) (2022)
- [A single algorithm for both restless and rested rotting bandits](https://mlsanity.com/paper/2604.21432/) (2026)
- [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)
- [Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approach](https://mlsanity.com/paper/2501.01291/) (2025)

## Abstract (arXiv)

Multi-armed bandit (MAB) is a class of online learning problems where a learning agent aims to maximize its expected cumulative reward while repeatedly selecting to pull arms with unknown reward distributions. We consider a scenario where the reward distributions may change in a piecewise-stationary fashion at unknown time steps. We show that by incorporating a simple change-detection component with classic UCB algorithms to detect and adapt to changes, our so-called M-UCB algorithm can achieve nearly optimal regret bound on the order of O(√MKTlog T), where T is the number of time steps, K is the number of arms, and M is the number of stationary segments. Comparison with the best available lower bound shows that our M-UCB is nearly optimal in T up to a logarithmic factor. We also compare M-UCB with the state-of-the-art algorithms in numerical experiments using a public Yahoo! dataset to demonstrate its superior performance.