Bandit Change-Point Detection for Real-Time Monitoring High-Dimensional Data Under Sampling Control

Abstract

In many real-world problems of real-time monitoring high-dimensional streaming data, one wants to detect an undesired event or change quickly once it occurs, but under the sampling control constraint in the sense that one might be able to only observe or use selected components data for decision-making per time step in the resource-constrained environments. In this article, we propose to incorporate multi-armed bandit approaches into sequential change-point detection to develop an efficient bandit change-point detection algorithm based on the limiting Bayesian approach to incorporate a prior knowledge of potential changes. Our proposed algorithm, termed Thompson-Sampling-Shiryaev-Roberts-Pollak (TSSRP), consists of two policies per time step: the adaptive sampling policy applies the Thompson Sampling algorithm to balance between exploration for acquiring long-term knowledge and exploitation for immediate reward gain, and the statistical decision policy fuses the local Shiryaev–Roberts–Pollak statistics to determine whether to raise a global alarm by sum shrinkage techniques. Extensive numerical simulations and case studies demonstrate the statistical and computational efficiency of our proposed TSSRP algorithm.

KEYWORDS:

• Adaptive sampling
• Change-point detection
• Partially observed variables
• Shiryaev–Roberts procedure
• Thompson sampling

Supplementary Materials

In the supplementary materials, we provide (A) the detailed proofs of all theorems, (B) an additional case study in Solar Flare data, (C) additional simulation studies on our proposed algorithm when raising a global alarm based on the sum of the largest r = 3 local statistics, and (D) the comparison with more global decision policies. The zip file contains R codes for our algorithm.

College of Computing;

Funding

W.Z. is supported in part by an ARC-TRIAD fellowship from the Georgia Institute of Technology, and a Computing Innovation Fellowship from the Computing Research Association (CRA) and the Computing Community Consortium (CCC). This work was completed while W.Z. was at Georgia Institute of Technology. Y.M. is supported in part by NSF grant DMS-2015405. W.Z. and Y.M. are also supported in part by the National Center for Advancing Translational Sciences of the National Institutes of Health under Award Number UL1TR002378. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health.

Acknowledgments

The authors thank the editor, the associate editor, and two reviewers for their invaluable comments that greatly help to improve the article.

Additional information

Funding

W.Z. is supported in part by an ARC-TRIAD fellowship from the Georgia Institute of Technology, and a Computing Innovation Fellowship from the Computing Research Association (CRA) and the Computing Community Consortium (CCC). This work was completed while W.Z. was at Georgia Institute of Technology. Y.M. is supported in part by NSF grant DMS-2015405. W.Z. and Y.M. are also supported in part by the National Center for Advancing Translational Sciences of the National Institutes of Health under Award Number UL1TR002378. The content is solely the responsibility of the authors and does not necessarily represent the official views of the National Institutes of Health.