Asymptotically Optimal Sequential Testing with Markovian Data
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal sequential tests yield log-optimal e-processes
It has been recently shown that e-processes are sufficient for sequential testing in the following sense: every level-$α$ sequential test can be obtained by thresholding an e-process at $1/α$. However, in the above resul…
Risk-Sensitive Stochastic Optimal Control as Rao-Blackwellized Markovian Score Climbing
Stochastic optimal control of dynamical systems is a crucial challenge in sequential decision-making. Recently, control-as-inference approaches have had considerable success, providing a viable risk-sensitive framework t…
Decision MakingSequential Decision MakingAsymptotically Optimal Procedures for Sequential Joint Detection and Estimation
We investigate the problem of jointly testing multiple hypotheses and estimating a random parameter of the underlying distribution in a sequential setup. The aim is to jointly infer the true hypothesis and the true param…
Planning with a Learned Policy Basis to Optimally Solve Complex Tasks
Conventional reinforcement learning (RL) methods can successfully solve a wide range of sequential decision problems. However, learning policies that can generalize predictably across multiple tasks in a setting with non…
Reinforcement Learning (RL)Optimal Best Markovian Arm Identification with Fixed Confidence
We give a complete characterization of the sampling complexity of best Markovian arm identification in one-parameter Markovian bandit models. We derive instance specific nonasymptotic and asymptotic lower bounds which ge…