Asymptotically Optimal Sequential Testing with Markovian Data

Alhad Sethi, Kavali Sofia Sagar, Shubhada Agrawal, Debabrota Basu, P. N. Karthik
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:109294-109330, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-sethi26a, title = {Asymptotically Optimal Sequential Testing with {M}arkovian Data}, author = {Sethi, Alhad and Sagar, Kavali Sofia and Agrawal, Shubhada and Basu, Debabrota and Karthik, P. N.}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {109294--109330}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/sethi26a/sethi26a.pdf}, url = {https://proceedings.mlr.press/v306/sethi26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Asymptotically Optimal Sequential Testing with Markovian Data %A Alhad Sethi %A Kavali Sofia Sagar %A Shubhada Agrawal %A Debabrota Basu %A P. N. Karthik %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-sethi26a %I PMLR %P 109294--109330 %U https://proceedings.mlr.press/v306/sethi26a.html %V 306 %X 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.
APA
Sethi, A., Sagar, K.S., Agrawal, S., Basu, D. & Karthik, P.N.. (2026). Asymptotically Optimal Sequential Testing with Markovian Data. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:109294-109330 Available from https://proceedings.mlr.press/v306/sethi26a.html.

Related Material