# Asymptotically Optimal Sequential Testing with Markovian Data

arXiv: https://arxiv.org/abs/2602.17587 · HTML: https://mlsanity.com/paper/2602.17587/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 64 references that are in the map.
- First posted on arXiv 19 Feb 2026.

## Builds on (most cited first, 23 of 23)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Hypothesis testing with e-values](https://mlsanity.com/paper/2410.23614/) (2024)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [Optimal Best-Arm Identification Methods for Tail-Risk Measures](https://mlsanity.com/paper/2008.07606/) (2020)
- [Finding good policies in average-reward Markov Decision Processes without prior knowledge](https://mlsanity.com/paper/2405.17108/) (2024)
- [Optimal Best Markovian Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1912.00636/) (2019)
- [Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planning](https://mlsanity.com/paper/2210.02087/) (2022)
- [Pure Exploration in Bandits with Linear Constraints](https://mlsanity.com/paper/2306.12774/) (2023)
- [On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Bounds](https://mlsanity.com/paper/2504.19952/) (2025)
- [In-Context Learning for Pure Exploration](https://mlsanity.com/paper/2506.01876/) (2025)
- [Function-Specific Mixing Times and Concentration Away from Equilibrium](https://mlsanity.com/paper/1605.02077/) (2016)
- [FraPPE: Fast and Efficient Preference-based Pure Exploration](https://mlsanity.com/paper/2508.16487/) (2025)
- [Optimal Best Arm Identification with Fixed Confidence in Restless Bandits](https://mlsanity.com/paper/2310.13393/) (2023)
- [Hypothesis testing for Markov chain Monte Carlo](https://mlsanity.com/paper/1409.7986/) (2014)
- [Policy Testing in Markov Decision Processes](https://mlsanity.com/paper/2505.15342/) (2025)
- [Distinguishing Hidden Markov Chains](https://mlsanity.com/paper/1507.02314/) (2015)

## Built on by (most cited first, 2 of 2)

- [The optimal betting wealth growth rate](https://mlsanity.com/paper/2604.25280/) (2026)
- [Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning](https://mlsanity.com/paper/2607.17201/) (2026)

## Abstract (arXiv)

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 α → 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.