The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
The authors propose LocalizeChangePoints, an adaptive algorithm for finding multiple change points in a piecewise-constant function using bandit feedback. It establishes non-asymptotic sample complexity bounds that depend jointly on jump magnitudes and the relative positions (spacings) of the change points. This method optimizes sampling by adapting to local spacings, achieving a precision dependence of log(1/eta).