Bandit Quickest Changepoint Detection
  Many industrial and security applications employ a suite of sensors for
detecting abrupt changes in temporal behavior patterns. These abrupt changes
typically manifest locally, rendering only a small subset of sensors
informative. Continuous monitoring of every sensor can be expensive due to
resource constraints, and serves as a motivation for the bandit quickest
changepoint detection problem, where sensing actions (or sensors) are
sequentially chosen, and only measurements corresponding to chosen actions are
observed. We derive an information-theoretic lower bound on the detection delay
for a general class of finitely parameterized probability distributions. We
then propose a computationally efficient online sensing scheme, which
seamlessly balances the need for exploration of different sensing options with
exploitation of querying informative actions. We derive expected delay bounds
for the proposed scheme and show that these bounds match our
information-theoretic lower bounds at low false alarm rates, establishing
optimality of the proposed method. We then perform a number of experiments on
synthetic and real datasets demonstrating the effectiveness of our proposed
method.
