Asymptotically Optimal Sequential Testing with Markovian Data

We study one-sided and $\alpha$-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 $\cal P$ of stochastic matrices, and the *alternative* corresponds to a disjoint set $\cal 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 $\alpha \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.

Sequential hypothesis testing aims to determine, with prescribed confidence, whether data generated by an unknown source satisfies a desired property while minimizing the expected number of samples. Classical tests typically assume independent observations; however, many real-world data streams exhibit dependence. We study sequential hypothesis testing for Markov data, where future observations depend only on the current state, with the goal of identifying the family of transition models that generated the data. This setting is motivated by applications such as reinforcement learning, where one may wish to verify whether observed trajectories satisfy a specified linear structure. We establish a lower bound on the minimum expected sample size required to identify the correct model family with confidence $1-\alpha$. We then develop a computationally efficient test whose sample complexity matches this bound as $\alpha \to 0$. We demonstrate its effectiveness in detecting MCMC sampling flaws and validating structural properties in reinforcement learning.