Asymptotically optimal search of unknown anomalies

摘要

The problem of detecting an anomalous process over multiple processes is considered. We consider a composite hypothesis case, in which the measurements drawn when observing a process follow a common distribution parameterized by an unknown parameter (vector). The unknown parameter belongs to one of two disjoint parameter spaces, depending on whether the process is normal or abnormal. The objective is a sequential search strategy that minimizes the expected detection time subject to an error probability constraint. We develop a deterministic search policy to solve the problem and prove its asymptotic optimality (as the error probability approaches zero) when the parameter under the null hypothesis is known. We further provide an explicit upper bound on the error probability for the finite sample regime.