The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
For researchers in sequential decision-making and change point detection, this work corrects an incomplete asymptotic picture and provides finite-sample guarantees.
The paper studies multiple change point localization under bandit feedback, proposing an adaptive algorithm that identifies change points to a target precision with high confidence. It reveals that sample complexity depends jointly on jump magnitudes and relative positions of change points, not just jump magnitudes as previously thought.
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 $δ\to 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.