Keeping the Best: The K-Best rule for Efficient Quickest Change Detection with Unknown Post-Change Distribution

Abstract

We study the problem of quickest change detection (QCD) when the post-change distribution has parametric uncertainty. The generalized likelihood ratio (GLR) cumulative sum (CuSum) procedure is known to be asymptotically optimum in this setting. However, this rule requires significant memory and computational resources, making it difficult to implement in practice. To overcome this limitation, sliding window approaches, such as the window-limited GLR CuSum and window-limited adaptive CuSum tests, have been employed, where the test statistic is computed over a fixed window of the latest observations. We propose the K-Best rule which instead keeps track of K hypothesized change points that have the largest test statistic. This allows the hypothesized change points to reduce epistemic uncertainty over time, while restricting the number of hypothesized change points considered. We characterize the growth rate of the K-Best window necessary to achieve the detection performance of the GLR-CuSum rule and quantify the computational benefits over the existing windowing approaches.