Abstract: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 $\eta$ and confidence level $1-\delta$, 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 $\eta$. 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 $\delta\to 0$. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general $\delta$ and $\eta$, the complexity is jointly governed by the jumps and the relative positions of the change points.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG); Statistics Theory (math.ST) |
| Cite as: | arXiv:2605.13252 [stat.ML] |
| (or arXiv:2605.13252v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2605.13252 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Maximilian Graf [view email]
[v1]
Wed, 13 May 2026 09:35:19 UTC (86 KB)