Asymptotically Optimal Sequential Testing with Markovian Data

Motivation

• Known: i.i.d. 데이터에 대한 sequential hypothesis testing 이론은 SPRT 이래로 잘 정립되어 있으며, Markovian dependence 하에서도 singleton null 대 singleton alternative 또는 singleton null 대 composite alternative에 대한 연구(Fields et al., 2025; Fauß et al., 2020 등)가 존재한다.
• Gap: 기존 연구는 Markovian data에 대해 asymptotic한 lower bound만 제공하거나, singleton null(단일 known P0)만을 다뤄 composite null P 전체를 상대로 uniform Type-I error를 보장해야 하는 어려움을 포착하지 못했으며, non-asymptotic하고 instance-dependent한 lower bound가 부재했다.
• Why: composite null과 composite alternative를 모두 다루는 sharp한 non-asymptotic 특성화는 MCMC 오설정 탐지, MDP에서의 구조적 성질 검증(예: transition dynamics의 linearity) 등 실제 응용에서 unknown transition matrix 하에서의 최적 sequential decision-making을 가능하게 하므로 중요하다.
• Approach: stationary-weighted KL divergence의 infimum으로 정의되는 information quantity Dinf_M(Q,P)를 이용해 non-asymptotic lower bound를 유도하고, 이를 asymptotically (α→0) 달성하는 sequential test를 설계한다.

Achievement

Figure 2. Mean statistic trajectory aggregated over 20 runs. Shaded

alternative Q 하에서 EQ[τα]에 대한 최초의 non-asymptotic instance-dependent lower bound(Theorem 3.3)를 증명했으며, log(1/α) 항에 Dinf_M(Q,P)라는 stationary-weighted KL divergence의 infimum이 곱해지는 형태와 α-독립적 구조 항을 포함한다. 또한 이 bound를 α→0에서 first order로 달성하는 test(Theorem 4.1)를 제시했고, MCMC 오설정 탐지 및 MDP에서의 linear transition dynamics 검증에 적용하여 유용성을 입증했다.

How

Figure 1. Test statistic trajectories over time for Qbad (red) and

• 유한 상태 ergodic Markov chain (P, µ)로 생성된 데이터에 대해 H0: P∈P vs H1: P∈Q를 구성
• α-correct, power-one stopping time τα에 대한 lower bound를 Poisson equation의 해에 대한 uniform control(Proposition 3.1)을 활용하여 도출
• 두 transition matrix 간 stationary-weighted divergence를 하한하는 Pinsker-type inequality(Proposition 4.3)를 새롭게 증명
• martingale 기반 구성을 활용해 lower bound를 point-wise/first-order로 달성하는 sequential test 설계
• MCMC misspecification detection(target stationary distribution과의 일관성 검증, Section 5.1)과 MDP에서 linear transition dynamics 검증(Section 5.2)에 프레임워크를 적용, 실험적으로 test statistic trajectory(Figure 1, 2)를 통해 검증

Originality

• composite null과 composite alternative를 모두 다루는 최초의 non-asymptotic instance-dependent lower bound 제시 (기존 Fields et al. 2025는 singleton null만 다룸)
• Dinf_M(Q,P)라는 새로운 information quantity를 stationary distribution과 transition structure를 모두 반영하여 정의
• 독립적인 이론적 기여로서 Pinsker-type inequality(Proposition 4.3)와 Poisson equation solution의 uniform control(Proposition 3.1)을 제시
• likelihood ratio의 uniform boundedness 가정 없이 분석을 수행하여 기존 문헌보다 일반적인 조건에서 결과 도출
• MCMC 오설정 탐지와 MDP 구조 검증(linearity of transition dynamics)이라는 두 가지 응용을 통해 프레임워크의 범용성을 입증

Limitation & Further Study

• lower bound와 test의 optimality가 α→0의 asymptotic regime에서의 first-order matching이며, 유한 α에서의 상수 인자까지 tight한지는 불명확
• best policy identification(BPI) 문헌의 non-asymptotic lower bound를 직접 적용하면 loose할 수 있다고 언급하나, 자신들의 방법이 policy testing 등 인접 문제로 얼마나 잘 확장되는지는 향후 연구로 남김(Ariu et al. 2025와의 연계)
• 실험은 소규모 예시(Figure 1, 2에서 20회 반복 실행)에 그쳐 대규모 실제 응용에서의 실증적 검증이 제한적
• finite-state Markov chain에 한정되어 있어 continuous state space나 non-ergodic 설정으로의 확장은 다루지 않음

Evaluation

총평: Markovian dependence 하에서 composite null/alternative를 다루는 sequential testing에 대해 non-asymptotic instance-dependent lower bound와 이를 달성하는 test를 최초로 제시한 이론적으로 견고하고 의미 있는 연구이나, 실험적 검증과 유한 표본에서의 tightness에 대한 추가 논의가 필요하다.