Approximately Optimal Multi-Stream Quickest Change Detection
For researchers in sequential change detection, this work provides the first theoretical guarantees in a bandit setting without restrictive assumptions, though the optimality is only approximate and asymptotic.
The paper tackles the multi-stream quickest change detection problem with constrained sampling, proposing an algorithm that combines decaying-ε-greedy switching with a Generalized Likelihood Ratio test. It achieves approximate asymptotic first-order optimality without requiring discretized parameters or lower bounds on change magnitude, providing guarantees for light-tailed distributions.
This paper considers the constrained sampling multi-stream quickest change detection problem, also known as the bandit quickest change detection problem. One stream contains a change-point that shifts its mean by an unknown amount. The goal is to quickly detect this change while controlling for false alarms, while being only able to sample one stream at each time. We propose an algorithm that combines a decaying-$ε$-greedy stream switching rule with a Generalized Likelihood Ratio detection procedure for unknown post-change means. We provide performance bounds for our algorithm and show it achieves approximate asymptotic first-order optimality with respect to a commonly used surrogate. We are the first to provide guarantees in this setting without assumptions such as a discretized post-change parameter set or a lower bound on the magnitude of change. We provide guarantees for a wide range of light-tailed distributions, including sub-Gaussian and bounded support distributions.