Optimal Anytime-Valid Tests for Composite Nulls

We consider the problem of designing optimal level-α power-one tests for composite nulls. Given a parameter α ∈ (0,1) and a stream of X-valued observations Xn: n ≥ 1 overseti.i.d.~ P, the goal is to design a level-α power-one test τα for the null H0: P ∈ P0 subset P(X). Prior works have shown that any such τα must satisfy mathbbEP[τα] ≥ tfraclog(1/α)γ^*(P, P0), where γ^*(P, P0) is the so-called KLinf or minimum divergence of P to the null class. In this paper, our objective is to develop and analyze constructive schemes that match this lower bound as α downarrow 0. We first consider the finite-alphabet case~(|X| = m < ∞), and show that a test based on universal e-process~(formed by the ratio of a universal predictor and the running null MLE) is optimal in the above sense. The proof relies on a Donsker-Varadhan~(DV) based saddle-point representation of KLinf, and an application of Sion's minimax theorem. This characterization motivates a general method for arbitrary X: construct an e-process based on the empirical solutions to the saddle-point representation over a sufficiently rich class of test functions. We give sufficient conditions for the optimality of this test for compact convex nulls, and verify them for H"older smooth density models. We end the paper with a discussion on the computational aspects of implementing our proposed tests in some practical settings.