Adaptive Joint Testing of Policies in Discounted Markov Decision Processes

We study fixed-confidence joint policy testing in discounted tabular Markov decision processes under active exploration. Given a finite family of target policies, the learner observes a single adaptive trajectory and must certify the sign of every target-policy value with probability at least $1-\delta$. We identify the instance-specific first-order benchmark for this problem: a characteristic time $T^\star(p)$, defined by a max--min program over stationary occupancy measures and sign-flipped alternatives. We then develop PT-ACE$(\mu)$, an online algorithm that couples stabilized exchange-based learning of a bottleneck occupancy allocation, trajectory-compatible navigation from averaged occupancies, and parallel certified policywise stopping via scalar frontier tests. Under a trajectory-side anchor-policy ergodicity condition, and when run with certified numerical subroutines and vanishing input tolerances, PT-ACE$(\mu)$ is $\delta$-correct and, for every sufficiently small admissible fixed floor $\mu>0$, satisfies $$ \limsup_{\delta\downarrow0} \frac{\mathbb E_p[\tau_\delta]}{\log(1/\delta)} \le (1+c(\mu,p))T^\star(p), \qquad c(\mu,p)\to0\quad\text{as }\mu\downarrow0. $$ Thus a single adaptive trajectory can certify multiple policy signs at the instance-specific lower-bound rate in the vanishing-floor limit.