# Bandit Quickest Changepoint Detection

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 45 references that are in the map.
- First posted on arXiv 22 Jul 2021.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [MIMII Dataset: Sound Dataset for Malfunctioning Industrial Machine Investigation and Inspection](https://mlsanity.com/paper/1909.09347/) (2019)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Accurate estimation of influenza epidemics using Google search data via ARGO](https://mlsanity.com/paper/1505.00864/) (2015)
- [Active multi-fidelity Bayesian online changepoint detection](https://mlsanity.com/paper/2103.14224/) (2021)
- [Bandit Change-Point Detection for Real-Time Monitoring High-Dimensional Data Under Sampling Control](https://mlsanity.com/paper/2009.11891/) (2020)

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

- [Testing Stationarity and Change Point Detection in Reinforcement Learning](https://mlsanity.com/paper/2203.01707/) (2022)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Evasive Active Hypothesis Testing with Deep Neuroevolution: The Single- and Multi-Agent Cases](https://mlsanity.com/paper/2403.10112/) (2024)
- [Fixed-Confidence Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2507.08994/) (2025)
- [RoS-Guard: Robust and Scalable Online Change Detection with Delay-Optimal Guarantees](https://mlsanity.com/paper/2511.12846/) (2025)
- [Accurate Evaluation of Quickest Changepoint Detectors via Non-parametric Survival Analysis](https://mlsanity.com/paper/2605.18798/) (2026)
- [Diagnose, Recover, Certify: Task Readiness under Hidden Dynamics Changes](https://mlsanity.com/paper/2609.20304/) (2026)

## Abstract (arXiv)

Many industrial and security applications employ a suite of sensors for detecting abrupt changes in temporal behavior patterns. These abrupt changes typically manifest locally, rendering only a small subset of sensors informative. Continuous monitoring of every sensor can be expensive due to resource constraints, and serves as a motivation for the bandit quickest changepoint detection problem, where sensing actions (or sensors) are sequentially chosen, and only measurements corresponding to chosen actions are observed. We derive an information-theoretic lower bound on the detection delay for a general class of finitely parameterized probability distributions. We then propose a computationally efficient online sensing scheme, which seamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions. We derive expected delay bounds for the proposed scheme and show that these bounds match our information-theoretic lower bounds at low false alarm rates, establishing optimality of the proposed method. We then perform a number of experiments on synthetic and real datasets demonstrating the effectiveness of our proposed method.