Asymptotically Optimal Sequential Testing with Markovian Data

Alhad Sethi; Kavali Sofia Sagar; Shubhada Agrawal; Debabrota Basu; P. N. Karthik

math.STFeb 19, 2026

Asymptotically Optimal Sequential Testing with Markovian Data

Authors: Alhad Sethi, Kavali Sofia Sagar, Shubhada Agrawal, Debabrota Basu, P. N. Karthik

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

Abstract

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.

Figures & tables

Figure 1: Test statistic trajectories over time for $Q_{\text{bad}}$ (red) and $Q_{\text{good}}$ (green), aggregated over $100$ runs. Solid curves and shaded regions show the mean $\pm 3\sigma$ ; dotted colored curves denote the boundary. The dotted black line shows the theoretical slope $D_{\mathcal{M}}^{\inf}(Q_{\text{bad}},\mathcal{P}_{\pi})$ , and the vertical line marks the mean stopping time for $Q_{\text{bad}}$ .

Figure 2: Mean statistic trajectory aggregated over $20$ runs. Shaded regions indicate $\pm 3$ standard deviations.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: On the left side, we show the average trajectory (shaded: $\pm 3$ standard deviations) taken by the statistic across time. On the right side, we plot the histogram of stopping times across the same runs.

Figure 4: We show the average trajectory (shaded: $\pm 3$ standard deviations) taken by the statistic across time. We do not observe any rejections empirically and estimate the rejection probability indirectly via importance sampling to be $1.21\times 10^{-30}\pm 2.12\times 10^{-30}$ over $n=1000$ runs.

Parameter	Value	Description
$\alpha$	$0.01$	Target Type-I error probability
$S$	$64$	State space size ( $8\times 8$ discretization)
$A$	$3$	Action space size
$d$	$\{3,5,7\}$	Tested feature dimensions (ranks)
Check Interval	$100$	Frequency of statistic evaluation (steps)
$T$ (Horizon)	$100,000$	Maximum duration of the experiment

Appendix

Table 1: Hyperparameters for the Linear MDP Experiment on Discretized MountainCar.

Panel of Figure 5 — Figure 5: Expected Stopping Time as a function of $\log\left(\frac{1}{\alpha}\right)$ for the experimental setup described in Appendix G.3 .

m	$\boldsymbol{\alpha}$	Mean Stopping Time	Mean runtime/step (s)
32	0.05	$665.65\pm 130.893$	$0.0184\pm 0.001$
64	0.05	$2516.84\pm 620.151$	$0.0796\pm 0.002$
128	0.05	$9700.55\pm 2181.039$	$0.6890\pm 0.121$

Appendix

Table 2: Comparison of mean stopping times and runtimes for different values of

m

m	$\boldsymbol{\alpha}$	Mean Stopping Time	Mean runtime/step (s)
64	0.01	$2864.83\pm 565.180$	$0.0692\pm 0.004$
64	0.05	$2516.84\pm 620.151$	$0.0796\pm 0.002$
64	0.1	$2370.36\pm 717.654$	$0.0773\pm 0.002$

Appendix

Table 3: Comparison of mean stopping times and runtimes for different values of

\alpha

Panel of Figure 6 — Figure 6: Expected stopping time as a function of $\theta\in[-0.8,-0.4]$ for the experimental setup described in Section G.4 .

Figure 7: Expected Stopping Time as a function of $\log\left(\frac{1}{\alpha}\right)$ for a fixed $\theta=-0.6$ in the experimental setup described in G.4 .

Explore similar work

Multi-Armed Sequential Hypothesis Testing by Betting
Mar 18, 2026Ricardo J. Sandoval, Ian Waudby-Smith, Michael I. JordanSequential Hypothesis Testing Statistical Hypothesis Testing
University of California, Berkeley · École Normale Supérieure & Inria, Paris
Anytime-valid simulation-based hypothesis testing
Oct 6, 2026Patrick Forré, Lydia BrennerSimulation-Based Inference Sequential Hypothesis Testing
University of Amsterdam · Nikhef
Global Sequential Testing for Multi-Stream Auditing
Feb 25, 2026Beepul Bharti, Ambar Pal, Jeremias SulamSequential Hypothesis Testing Multiple Hypothesis Testing
Johns Hopkins University · Amazon Responsible AI

Mar 18, 2026J/K move · Enter open · S save

Multi-Armed Sequential Hypothesis Testing by Betting

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

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

Sequential Hypothesis Testing Statistical Hypothesis Testing Multi-Armed Bandits

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Multi-Armed Sequential Hypothesis Testing by Betting

Anytime-valid simulation-based hypothesis testing

Global Sequential Testing for Multi-Stream Auditing