# Fixed-Confidence Multiple Change Point Identification under Bandit Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 7 Oct 2026).
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 11 Jul 2025.

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

- [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)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free](https://mlsanity.com/paper/1902.00980/) (2019)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Thresholding Bandit for Dose-ranging: The Impact of Monotonicity](https://mlsanity.com/paper/1711.04454/) (2017)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Optimal Change-Point Detection and Localization](https://mlsanity.com/paper/2010.11470/) (2020)
- [Sample complexity of partition identification using multi-armed bandits](https://mlsanity.com/paper/1811.05654/) (2018)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [Bandit Quickest Changepoint Detection](https://mlsanity.com/paper/2107.10492/) (2021)
- [A General Framework for Clustering and Distribution Matching with Bandit Feedback](https://mlsanity.com/paper/2409.05072/) (2024)
- [Sequential Adaptive Design for Jump Regression Estimation](https://mlsanity.com/paper/1904.01648/) (2019)
- [Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits](https://mlsanity.com/paper/2410.07638/) (2024)
- [Active Learning of Piecewise Gaussian Process Surrogates](https://mlsanity.com/paper/2301.08789/) (2023)
- [Optimal Multi-Objective Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2501.13607/) (2025)
- [Fixed-Budget Change Point Identification in Piecewise Constant Bandits](https://mlsanity.com/paper/2501.12957/) (2025)
- [Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond](https://mlsanity.com/paper/2503.01701/) (2025)

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

- [The Sample Complexity of Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2605.13252/) (2026)

## Abstract (arXiv)

Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry to manufacturing. In practice, it is often required to confidently identify the locations of the abrupt changes in these functions as quickly as possible. For this, we introduce a fixed-confidence piecewise constant bandit problem. Here, we sequentially query points in the domain and receive noisy evaluations of the function under bandit feedback. We provide instance-dependent lower bounds for the complexity of change point identification in this problem. These lower bounds illustrate that an optimal method should focus its sampling efforts adjacent to each of the change points, and the number of samples around each change point should be inversely proportional to the magnitude of the change. Building on this, we devise a simple and computationally efficient variant of Track-and-Stop and prove that it is asymptotically optimal in many regimes. We support our theoretical findings with experimental results in synthetic environments demonstrating the efficiency of our method.