mlsanityData to 7 Oct 2026

Asymptotically Optimal Sequential Testing with Markovian Data

arXiv 2602.17587 ↗First posted 19 Feb 2026math.ST cs.LG stat.MLcited by 0

Not on the map. Why?

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 23 of its 64 references that are in the map. First posted on arXiv 19 Feb 2026.

Builds on

23 of 64 references.

References · 23

  1. 2016CVXPY: A Python-Embedded Modeling Language for Convex Optimizationcited by 633
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2017A Rewriting System for Convex Optimization Problemscited by 178
  4. 2024Hypothesis testing with e-valuescited by 70
  5. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  6. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  7. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  8. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  9. 2021Regret Minimization in Heavy-Tailed Banditscited by 24
  10. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20
  11. 2020Optimal Best-Arm Identification Methods for Tail-Risk Measurescited by 17
  12. 2019Optimal Best Markovian Arm Identification with Fixed Confidencecited by 12
11 more
  1. 2022Bilinear Exponential Family of MDPs: Frequentist Regret Bound with Tractable Exploration and Planningcited by 12
  2. 2023Pure Exploration in Bandits with Linear Constraintscited by 10
  3. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  4. 2025On Stopping Times of Power-one Sequential Tests: Tight Lower and Upper Boundscited by 5
  5. 2025In-Context Learning for Pure Explorationcited by 5
  6. 2016Function-Specific Mixing Times and Concentration Away from Equilibriumcited by 4
  7. 2023Optimal Best Arm Identification with Fixed Confidence in Restless Banditscited by 3
  8. 2025FraPPE: Fast and Efficient Preference-based Pure Explorationcited by 2
  9. 2014Hypothesis testing for Markov chain Monte Carlocited by 1
  10. 2015Distinguishing Hidden Markov Chainscited by 1
  11. 2025Policy Testing in Markov Decision Processescited by 1

Built on by

Not cited yet.