Policy testing asks whether the value of a given policy exceeds a prescribed threshold while using as few observations as possible. Although existing methods provide worst-case guarantees, developing an instance-optimal and computationally tractable algorithm is challenging because the corresponding lower-bound optimization problem is non-convex.
In this talk, I first study single-policy testing in discounted Markov decision processes under a generative model. I derive an instance-specific sample-complexity lower bound and show that its seemingly difficult optimization problem can be reformulated using a reversed Markov decision process. This reformulation exchanges the objective and constraint, allowing us to apply policy-gradient methods. Building on this idea, I introduce Policy Testing via Simulation and Tracking (PTST), an algorithm that adaptively selects informative state–action pairs, tracks the optimal sampling allocation, and stops once sufficient evidence has been collected. PTST is computationally tractable and asymptotically matches the instance-specific lower bound.
Finally, I discuss joint policy testing in the forward model, where the learner must evaluate several policies using a single adaptive trajectory. I present PT-ACE, which addresses the additional navigation and flow constraints and achieves instance-specific asymptotic optimality in this more challenging setting.