Multi-Armed Sequential Hypothesis Testing by Betting

Ricardo J. Sandoval; Ian Waudby-Smith; Michael I. Jordan

stat.MEMar 18, 2026

Multi-Armed Sequential Hypothesis Testing by Betting

Authors: Ricardo J. Sandoval, Ian Waudby-Smith, Michael I. Jordan

Organizations: University of California, Berkeley · École Normale Supérieure & Inria, Paris

Abstract

We consider a variant of sequential testing by betting where, at each time step, the statistician is presented with multiple data sources (arms) and obtains data by choosing one of the arms. We consider the composite global null hypothesis $\mathscr{P}$ that all arms are null in a certain sense (e.g. all dosages of a treatment are ineffective) and we are interested in rejecting $\mathscr{P}$ in favor of a composite alternative $\mathscr{Q}$ where at least one arm is non-null (e.g. there exists an effective treatment dosage). We posit an optimality desideratum that we describe informally as follows: even if several arms are non-null, we seek $e$ -processes and sequential tests whose performance are as strong as the ones that have oracle knowledge about which arm generates the most evidence against $\mathscr{P}$ . Formally, we generalize notions of log-optimality and expected rejection time optimality to more than one arm, obtaining matching lower and upper bounds for both. A key technical device in this optimality analysis is a modified upper-confidence-bound-like algorithm for unobservable but sufficiently "estimable" rewards. In the design of this algorithm, we derive nonasymptotic concentration inequalities for optimal wealth growth rates in the sense of Kelly [1956]. These may be of independent interest.

Figures & tables

Panel of Figure 1 — Figure 1: Empirical growth rates for the one-sided bounded mean testing problem from Example C.1 under “easy” (left) and “hard” (right) data generating processes. We consider three algorithms in addition to SPRUCE . Oracle Arm has oracle access to and solely pulls the optimal arm. Round Robin pulls the arms one-by-one until all of them have been selected, and starts the process over again. Random Selection samples uniformly at random the arm to be played in round $n$ . All four algorithms employ the regret-based test statistic from Algorithm 2 and only differ in the way the arms are selected. Lastly, we note that the empirical growth rates of Round Robin and Random Selection are close to but nevertheless strictly greater than zero.

Panel of Figure 2 — Figure 2: Distribution of stopping times when $\alpha=0.001$ for the one-sided bounded mean testing problem from Example C.1 under “easy” (left) and “hard” (right) data generating processes. In addition to SPRUCE , we evaluate three algorithms whose description can be found the caption of Figure 1 . We use the following shorthand for the log-increment under the optimal arm and its optimal portfolio: $\ell_{1,\mathsf{Q}}\left(a_{\mathsf{Q}}\right)\coloneqq\log\left(\bm{\lambda}_{\mathsf{Q}}(a_{\mathsf{Q}})^{\top}\mathbf{E}_{1}\left(a_{\mathsf{Q}}\right)\right)$ .

Panel of Figure 3 — Figure 3: Empirical growth rates (left) and distribution of stopping times when $\alpha=0.001$ (right) for the average treatment effect testing problem from ( 55 ) for four different algorithms. Round Robin pulls the arms one-by-one until all of them have been selected, and starts the process over again. Random Selection samples uniformly at random the arm to be played in round $n$ . All four algorithms compute their test statistic following the form given in Equation 61 ; that is, they only differ in the way they select the arm to pull (i.e., treatment variation to test) at each time step.

Explore similar work

Aug 10, 2026

From Approachability Residuals to Anytime-Valid Evidence: The Online Convex Geometry of Testing by Betting

Betting-based sequential tests and Blackwell approachability are linked by a rate-explicit reduction through support-function residuals. For a compact convex target

S

and vector observations

r_t

, an OCO learner selects a predictable normal

w_t

and produces

q_t=\langle w_t,r_t\rangle-h_S(w_t)

. We prove the exact pathwise identity

\dist(\bar r_T,S) =\frac1T\sum_{t=1}^Tq_t+\frac{\Reg_T}{T}.

When

|q_t|\leq B

, composing this identity with one-sided betting yields a finite-time transfer: if the OCO and log-wealth regrets are at most

a_T

and

\ell_T

, respectively, then a target gap exceeding

\frac{a_T}{T} +2B\sqrt{\frac{\log(1/α)+\ell_T}{T}}

forces rejection by time

T

, while non-rejection certifies the converse radius. We then formulate a controlled stochastic experiment in which an action selected after

w_t

satisfies Blackwell's supporting-halfspace condition for every null mean payoff. The resulting wealth is an e-process under adaptive nulls; sublinear OCO regret gives stochastic approachability, whereas persistent mean separation under an alternative gives exponential wealth at rate at least

δ^2/(4B^2)

. Deterministic Blackwell games and passive tests are, respectively, the noise-free and singleton-action cases of this protocol. Bounded two-sample means, kernel MMD, and active heterogeneous data sources instantiate the reduction. The resulting connection is exact algebraically, quantitative at finite time, and operational when experiments are controlled.

Jinze Zhao

University of California, San Diego

Sequential Hypothesis Testing

Ask PDF

Feb 19, 2026

Asymptotically Optimal Sequential Testing with Markovian Data

We study one-sided and

α

-correct sequential hypothesis testing for data generated by an ergodic, finite-state Markov chain. The null hypothesis is that the unknown transition matrix belongs to a prescribed set

P

of stochastic matrices, and the alternative corresponds to a disjoint set

Q

. We establish a non-asymptotic instance-dependent lower bound on the expected stopping time of any valid sequential test under the alternative, which is asymptotically tight. Our novel analysis improves the existing lower bounds, which are either asymptotic or provably sub-optimal in this setting. Our lower bound incorporates both the stationary distribution and the transition structure induced by the unknown Markov chain. We further propose an optimal test whose expected stopping time matches this lower bound asymptotically as

α\to 0

. We illustrate the usefulness of our framework through applications to sequential detection of model misspecification in Markov Chain Monte Carlo and to testing structural properties, such as the linearity of transition dynamics, in Markov decision processes. Our findings yield a sharp and general characterization of optimal sequential testing procedures under Markovian dependence.

Alhad Sethi, Kavali Sofia Sagar, Shubhada Agrawal +2

Indian Institute of Science, Bangalore · Indian Institute of Technology, Hyderabad · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL

Sequential Hypothesis Testing Markov Models

Ask PDF

Mar 20, 2026

Learning to Bet for Horizon-Aware Anytime-Valid Testing

We develop horizon-aware anytime-valid tests and confidence sequences for bounded means under a strict deadline

N

. Using the betting/e-process framework, we cast horizon-aware betting as a finite-horizon optimal control problem with state space

(t, \log W_t)

, where

t

is the time and

W_t

is the test martingale value. We first show that in certain interior regions of the state space, policies that deviate significantly from Kelly betting are provably suboptimal, while Kelly betting reaches the threshold with high probability. We then identify sufficient conditions showing that outside this region, more aggressive betting than Kelly can be better if the bettor is behind schedule, and less aggressive can be better if the bettor is ahead. Taken together these results suggest a simple phase diagram in the

(t, \log W_t)

plane, delineating regions where Kelly, fractional Kelly, and aggressive betting may be preferable. Guided by this phase diagram, we introduce a Deep Reinforcement Learning approach based on a universal Deep Q-Network (DQN) agent that learns a single policy from synthetic experience and maps simple statistics of past observations to bets across horizons and null values. In limited-horizon experiments, the learned DQN policy yields state-of-the-art results.

Ege Onur Taga, Samet Oymak, Shubhanshu Shekhar

Department of Electrical and Computer Engineering, University of Michigan, Ann Arbor, USA.

Anytime-Valid Inference

Ask PDF