On the Game-Theoretic Nature of Optimality in Active Hypothesis Testing

Active Hypothesis Testing (AHT) is a fundamental problem across information theory, multi-armed bandits, and operations research, but a clear characterization of its optimal large deviation behaviour has long been an open challenge. We build upon the work of Komiyama et al. (NeurIPS 2022), which presents a computationally intractable and conceptually unclear formulation of the optimal exponent $R^{go}\_{\infty}$ of the error probability. We characterize this optimal error-exponent, in the limit that the sample budget $T \to \infty$, as the value of a certain two-player zero-sum differential game. This dynamic game, played over the normalized interval $[0,1]$, has two players, Nature and Agent. The state variable $y_t$ at time $t$ is the negative log-likelihood of the observed samples till then. We show that the players aim to optimize the second-smallest coordinate of the terminal state $y_1$. As a result, we obtain a time-dependent Hamilton-Jacobi-Isaacs (HJI) Partial Differential Equation (PDE) that is used to develop the first numerical schemes in the literature to accurately approximate $R^{go}\_{\infty}$. Additionally, we can derive existing and new alternate bounds for $R^{go}\_{\infty}$ using the viscosity solution theory of HJI PDEs. Finally, we establish a remarkable time-scaling property of the HJI viscosity solution, which reduces the dynamics to a new time-invariant PDE and provides a novel geometric description of optimality in AHT.