TITLE: Active Hypothesis Testing: Musings on the Non-Asymptotic Case

Exploration-exploitation problems abound in applications such as anomaly detection, target localization, dynamical system tracking, medical diagnosis, wireless body area sensor networks etc. Initially, one is unclear about the state of the environment and the goal is to take observations that refine the understanding of the state. If one has a series of ``experiments’’ (or queries), each of which provide information about the state, an important question is how to design that sequence of experiments to enable a decision about the environmental state as quickly as possible. In particular, it is of interest to determine the next best experiment as a function of the past observations. A formulation of this problem is active hypothesis testing which has been persistently studied since the 1940s. In contrast to much prior work, our focus is on analyzing performance for a fixed number of experiments or queries. We first review our prior active decision making work for motivation. For this problem, we provide asymptotically tight lower and upper bounds on the optimal misclassification probability. In the analysis, we also solve a sub-problem that can be viewed as a generalization of the classical Chernoff-Stein lemma to a setting with multiple hypotheses and multiple experiments. One asymptotically optimal strategy for this generalized problem is Chernoff's open-loop randomized experiment selection. We show that there are other strategies that are also asymptotically optimal, but with substantially better non-asymptotic performance. The design of these novel strategies is based on an information theoretic quantity (the expected confidence rate). We can formulate the problem of maximizing the confidence rate as a Markov Decision Process problem (MDP) thus enabling the use of dynamic programming to solve the MDP. We also explore neural network implementations to solve the MDP; success is strongly tied to the particular implementation and the design of the right metric as informed by our analytical work. Our infinite horizon solutions are shown to outperform recent strategies in the finite horizon case. We make connections to key information theoretic quantities that have been previously considered and provide numerical results.