# Efficient Change-Point Detection for Tackling Piecewise-Stationary Bandits

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

## Key facts

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

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

- [Continual Learning as Computationally Constrained Reinforcement Learning](https://mlsanity.com/paper/2307.04345/) (2023)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [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 empirical evaluation of active inference in multi-armed bandits](https://mlsanity.com/paper/2101.08699/) (2021)
- [A Definition of Non-Stationary Bandits](https://mlsanity.com/paper/2302.12202/) (2023)
- [Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret](https://mlsanity.com/paper/2101.08980/) (2021)
- [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)
- [Rising Rested Bandits: Lower Bounds and Efficient Algorithms](https://mlsanity.com/paper/2411.14446/) (2024)
- [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)
- [Learning to Price Supply Chain Contracts against a Learning Retailer](https://mlsanity.com/paper/2211.04586/) (2022)
- [A Risk-Averse Framework for Non-Stationary Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2310.19821/) (2023)

## Abstract (arXiv)

We introduce GLR-klUCB, a novel algorithm for the piecewise iid non-stationary bandit problem with bounded rewards. This algorithm combines an efficient bandit algorithm, kl-UCB, with an efficient, parameter-free, changepoint detector, the Bernoulli Generalized Likelihood Ratio Test, for which we provide new theoretical guarantees of independent interest. Unlike previous non-stationary bandit algorithms using a change-point detector, GLR-klUCB does not need to be calibrated based on prior knowledge on the arms' means. We prove that this algorithm can attain a O(√TA UpsilonTlog(T)) regret in T rounds on some "easy" instances, where A is the number of arms and UpsilonT the number of change-points, without prior knowledge of UpsilonT. In contrast with recently proposed algorithms that are agnostic to UpsilonT, we perform a numerical study showing that GLR-klUCB is also very efficient in practice, beyond easy instances.