Learning Where to Look: UCB-Driven Controlled Sensing for Quickest Change Detection
This work addresses the problem of efficiently detecting changes in data streams for applications like monitoring and learning in piecewise stationary environments, representing a novel method for a known bottleneck.
The paper tackles the multichannel quickest change detection problem with bandit feedback and controlled sensing by proposing two novel UCB-inspired detection procedures that adaptively select data streams to observe, achieving first-order asymptotic optimality in detection delay under false-alarm constraints and outperforming state-of-the-art methods in simulations with computational savings.
We study the multichannel quickest change detection problem with bandit feedback and controlled sensing, in which an agent sequentially selects one of the data streams to observe at each time-step and aims to detect an unknown change as quickly as possible while controlling false alarms. Assuming known pre- and post-change distributions and allowing an arbitrary subset of streams to be affected by the change, we propose two novel and computationally efficient detection procedures inspired by the Upper Confidence Bound (UCB) multi-armed bandit algorithm. Our methods adaptively concentrate sensing on the most informative streams while preserving false-alarm guarantees. We show that both procedures achieve first-order asymptotic optimality in detection delay under standard false-alarm constraints. We also extend the UCB-driven controlled sensing approach to the setting where the pre- and post-change distributions are unknown, except for a mean-shift in at least one of the channels at the change-point. This setting is particularly relevant to the problem of learning in piecewise stationary environments. Finally, extensive simulations on synthetic benchmarks show that our methods consistently outperform existing state-of-the-art approaches while offering substantial computational savings.