Online Quickest Change Detection for Multiple Gaussian Sequences Using Multi-Armed Bandits

This paper considers the online multi-stream quickest changepoint detection problem. An agent is faced with a set of independent data streams, one of which contains a changepoint at an unknown time step which shifts the mean of its distribution by an unknown amount. The goal of the agent is to minimize its detection delay while controlling for false alarms. Uninterrupted monitoring of every stream can be costly due to resource limitations, so the agent only observes one stream at each point in time. We propose an adaptive algorithm which combines an ε-greedy selection rule with a change-point detection algorithm for unknown post-change means. Our main contributions are performance bounds of our algorithm which show that it matches the asymptotic detection delay (to within a constant factor) of single-stream CUSUM. Compared with previous work, our algorithm relies on considerably fewer assumptions.