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 ${\mathrm{limsup}}_{\delta \downarrow 0}\frac{{\mathbb{E}}_p[{\tau }_{\delta }]}{\log (1/\delta )}\le (1+c(\mu ,p))T^{\star }(p),c(\mu ,p)\to 0\text{as }\mu \downarrow 0.$ Thus a single adaptive trajectory can certify multiple policy signs at the instance-specific lower-bound rate in the vanishing-floor limit.