The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

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 $\hat{I}\cdot$ and confidence level $1-\hat{I}´$, 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 $\hat{I}\cdot$. 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 $\hat{I}´\to 0$. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general $\hat{I}´$ and $\hat{I}\cdot$, the complexity is jointly governed by the jumps and the relative positions of the change points.