Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
This addresses the need for efficient change point detection in real-world applications like chemistry and manufacturing, though it is incremental as it builds on existing bandit methods.
The paper tackles the problem of identifying change points in piecewise constant functions under bandit feedback, introducing a fixed-confidence bandit framework and proving that a variant of Track-and-Stop is asymptotically optimal with instance-dependent lower bounds.
Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry to manufacturing. In practice, it is often required to confidently identify the locations of the abrupt changes in these functions as quickly as possible. For this, we introduce a fixed-confidence piecewise constant bandit problem. Here, we sequentially query points in the domain and receive noisy evaluations of the function under bandit feedback. We provide instance-dependent lower bounds for the complexity of change point identification in this problem. These lower bounds illustrate that an optimal method should focus its sampling efforts adjacent to each of the change points, and the number of samples around each change point should be inversely proportional to the magnitude of the change. Building on this, we devise a simple and computationally efficient variant of Track-and-Stop and prove that it is asymptotically optimal in many regimes. We support our theoretical findings with experimental results in synthetic environments demonstrating the efficiency of our method.