# The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 13 May 2026.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit](https://mlsanity.com/paper/1802.03692/) (2018)
- [High-dimensional changepoint estimation via sparse projection](https://mlsanity.com/paper/1606.06246/) (2016)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality](https://mlsanity.com/paper/1810.09498/) (2018)
- [Optimal Change-Point Detection and Localization](https://mlsanity.com/paper/2010.11470/) (2020)
- [Seeded Binary Segmentation: A general methodology for fast and optimal change point detection](https://mlsanity.com/paper/2002.06633/) (2020)
- [The Influence of Shape Constraints on the Thresholding Bandit Problem](https://mlsanity.com/paper/2006.10006/) (2020)
- [A review on minimax rates in change point detection and localisation](https://mlsanity.com/paper/2011.01857/) (2020)
- [Bandit Change-Point Detection for Real-Time Monitoring High-Dimensional Data Under Sampling Control](https://mlsanity.com/paper/2009.11891/) (2020)
- [Fixed-Budget Change Point Identification in Piecewise Constant Bandits](https://mlsanity.com/paper/2501.12957/) (2025)
- [Safety Aware Changepoint Detection for Piecewise i.i.d. Bandits](https://mlsanity.com/paper/2205.13689/) (2022)
- [Clustering Items through Bandit Feedback: Finding the Right Feature out of Many](https://mlsanity.com/paper/2503.11209/) (2025)
- [Fixed-Confidence Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2507.08994/) (2025)

## Abstract (arXiv)

We study multiple change point localization under bandit feedback. An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs, and each query returns a noisy evaluation of the function. The goal is to identify a prescribed number of discontinuities, known as change points, within a target precision η and confidence level 1-δ, while using as few samples as possible. We propose an adaptive algorithm that first detects intervals likely to contain change points and then refines their locations to precision η. We establish non-asymptotic upper bounds on its sample budget, together with corresponding lower bounds. Prior work shows that jump magnitudes alone determine the asymptotic sample complexity as δ→ 0. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general δ and η, the complexity is jointly governed by the jumps and the relative positions of the change points.