Active Fixed-Sample-Size Hypothesis Testing via POMDP Value Function Lipschitz Bounds

We establish the Lipschitz continuity of the value functions of an active fixed-sample-size hypothesis testing problem when it is reformulated as a partially observed Markov decision process. These Lipschitz results enable us to develop novel upper and lower bounds on the value of information, which is the expected difference between the value functions before and after performing an experiment. Our novel Lipschitz and value-of-information results provide new practical insight into optimal policies for active fixed-sample-size hypothesis testing without resorting to approximate dynamic programming schemes or asymptotic analysis with infinite numbers of samples. We illustrate the utility of our results by showing that a simple scheme based on selecting experiments that maximize a value-of-information bound achieves near-optimal performance in simulations.

I. Introduction

Active hypothesis testing is a fundamental decision-making problem underlying: experimental design in statistics and system identification [1]–[6]; active detection and estimation in signal processing and control [7]–[9]; and, active exploration and learning in robotics and machine learning [6], [10]–[12]. Despite its importance to many disciplines across numerous applications, active hypothesis testing remains largely unsolved due to the difficulty of computing its associated value functions (and dynamic programming equations). Most investigations of active hypothesis testing have thus resorted to studying the performance of heuristic strategies in the asymptotic regime of infinite sample size (or vanishing probability of error) [1], [7], [13]–[19]. Unfortunately, insight into the importance of feedback in active hypothesis testing problems can be lost under such asymptotic analysis, with [7] notably showing that asymptotic performance measures such as error exponents can be optimized without any feedback (despite feedback being known to be important to optimize nonasymptotic performance measures, see e.g., [18]). In this paper, we develop novel nonasymptotic results for active hypothesis testing by building on recent structural results for partially observed Markov decision processes (POMDPs).