Abstract
In reinforcement learning applications, we often want to accurately estimate the return of several policies of interest. We study this problem, multiple-policy high-confidence policy evaluation, where the goal is to obtain high-confidence estimates for the values of $K$ policies simultaneously. We introduce a novel approach that "couples" trajectories to share data between policies, achieving sample complexity that scales with policy dissimilarity rather than the total number of policies.
Introduction
Policy evaluation—estimating the expected return of a specific strategy—is a fundamental task in reinforcement learning (RL). In practice, researchers often need to evaluate a large set of $K$ policies, for instance, during hyperparameter tuning or when comparing various training checkpoints.
Standard on-policy evaluation requires running each policy independently, leading to a sample complexity that grows linearly with $K$. While off-policy methods can reuse data, they frequently suffer from high variance or require complex environment models that do not scale well with state-space size. This paper proposes a middle ground: a high-confidence evaluation framework that is more efficient than independent runs but more robust than pure model-based estimation.
Methods: Coupling Trajectories
The core innovation is the Coupled Trajectory Sampler. Instead of drawing independent samples for every policy, the algorithm "couples" them. When multiple policies reside in the same state and choose the same action, the algorithm uses a single environment transition to update the state for all such policies. This "trajectory stitching" allows policies to share the cost of exploration.
The framework consists of two main components:
- High-Confidence Policy Evaluation (Algorithm 1): A wrapper that utilizes a sampling oracle to generate trajectories and compute confidence intervals for each policy's return.
- Coupled Trajectory Sampler (Algorithm 2): The engine that implements the coupling logic described above.
For scenarios without a simulator, a Preprocessing Phase (Algorithm 4) is introduced. This phase learns to reach critical states using existing policies, effectively constructing a sampling oracle from real-world interactions.
Theoretical Analysis and Key Insights
The authors introduce a new metric: Expected Disagreement. This metric, denoted as $\mathcal{D}$, represents the number of unique state-action pairs visited by the set of policies. The sample complexity of the proposed algorithm scales with this disagreement rather than $K$. Specifically, the authors prove a sample complexity of approximately $\tilde{O}\left(\frac{\mathcal{D}(\mathcal{K}^1)}{\epsilon^2} + KH\right)$.
In favorable MDPs where policies overlap significantly, the cost of evaluating $K$ policies can become nearly independent of $K$. For example, in certain MDP structures, standard uniform sampling requires $\Omega(K/\epsilon^2)$ samples, whereas the coupled sampler requires only $O(1/\epsilon^2)$—a $K$-fold efficiency gain.
Limitations and Unfavorable Instances
Despite its strengths, the method is not "instance optimal" in every scenario. The authors identify "unfavorable" MDP instances where the topology prevents effective coupling. In these cases, a simple round-robin or uniform mixture approach might be more efficient.
Current theoretical guarantees are also limited to tabular MDPs with finite states and actions. Extending these concepts to continuous state spaces via function approximation remains a significant area for future research. Additionally, the preprocessing phase required to build a sampling oracle can be computationally expensive in environments with vast state spaces.
Conclusion
This work provides a theoretical bridge between model-free Monte Carlo estimation and model-based trajectory synthesis. By leveraging policy agreement through coupling, it offers a path toward significantly more efficient multi-policy evaluation, particularly when policies are similar.
Summary updated