The Sample Complexity of Multiple Change Point Identification under Bandit Feedback

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.