Multiple-policy Evaluation via Density Estimation

Yilei Chen, Aldo Pacchiano, Ioannis Ch. Paschalidis

TL;DR

The paper introduces CAESAR, a novel algorithm designed to evaluate the performance of multiple Reinforcement Learning (RL) policies simultaneously and efficiently. By combining a low-cost "coarse estimation" phase with an adaptive importance sampling strategy, CAESAR achieves instance-dependent sample complexity that scales with the overlap between policies, significantly outperforming methods that evaluate policies in isolation.

What Problem Does This Paper Address?

In Reinforcement Learning, we often need to estimate the "value" (expected total reward) of many different policies—for example, when tuning hyperparameters or comparing different training iterations. Evaluating these policies one by one is extremely sample-inefficient because it ignores the fact that many policies might visit the same states and take the same actions.

While online evaluation (interacting with the environment) is common, it can be dangerous or impractical in sensitive domains like medicine. Offline evaluation is safer but relies heavily on the "coverage" of the available data. The authors tackle the Multiple-Policy Evaluation (MPE) problem: how can we collect a single, optimized dataset that allows us to accurately estimate the values of $K$ different target policies at once?

Methods

The authors propose a two-phase pipeline called CAESAR (Coarse and Adaptive EStimation with Approximate Reweighing):

  1. Phase I: Coarse Estimation. The key insight here is that to design a good sampling strategy, you don't need perfect knowledge of where your target policies go. You only need a "coarse" estimate—accurate within a constant multiplicative factor. The authors prove this can be done with a sample complexity of $\tilde{O}(1/\epsilon)$, which is much cheaper than the standard $\tilde{O}(1/\epsilon^2)$ required for precise evaluation.
  2. Phase II: Optimal Sampling & IDES.
    • Using the coarse estimates, CAESAR solves a convex optimization problem to find an approximately optimal sampling distribution ($\mu^*$) that covers the "visitation footprint" of all $K$ policies.
  3. To actually calculate the values, they introduce IDES (Importance Density EStimation). IDES is a subroutine that estimates importance weighting ratios by minimizing a step-wise quadratic loss function. This is a non-trivial extension of the DualDICE algorithm, specifically adapted for finite-horizon tasks to avoid the "curse of horizon" (exponential variance).
Figure 1. The scheme of CAESAR . In Phase I, we collect ˜O(1/ϵ) trajectories for each target policies π1, . . . , πK and obtain coarse estimators of their visitation distributions ˆdπ1, . . . , ˆdπK. Based on the coarse estimator, we can generate an approximately optimal sampling dataset which has good coverage over the visitations of target policies. In Phase II, we sample data from the approximately optimal dataset and leverage the coarse estimators from Phase I to perform importance density estimation for each target policies by implementing IDES . With the estimated importance density ˆwπ1, . . . , ˆwπK, we can output the final performance evaluators ˆV π1, . . . , ˆV πK.

Datasets

This is a theoretical paper focused on algorithmic guarantees and sample complexity bounds. As such, it does not evaluate on standard empirical benchmarks like Atari or MuJoCo. Instead, the authors use a constructed two-layer MDP (Markov Decision Process) to analytically demonstrate that their sample complexity avoids the pitfalls of previous state-of-the-art methods.

Key Insights and Ideas

  • Multiplicative Accuracy is Sufficient: You don't need to know exactly how often a policy visits a state to know that you should sample that state. Coarse estimation provides enough information to build a near-optimal sampling distribution at a fraction of the cost.
  • Instance-Dependence: The sample complexity of CAESAR naturally adapts to the set of policies. If the $K$ policies are very similar, the cost is close to evaluating a single policy. If they are diverse, the cost increases, but only as much as necessary to cover the unique parts of their trajectories.
  • Breaking the $1/d_{max}$ Barrier: Previous work suffered from a dependency on $1/d_{max}$ (the maximum visitation probability across policies at a state). If a state was rarely visited by all policies, the old bounds would explode. CAESAR avoids this, making it much more robust in environments with "bottleneck" states.

Key Results

  • Sample Complexity: CAESAR achieves a total sample complexity of $\tilde{O}\left(\frac{H^4}{\epsilon^2}\sum_{h=1}^H\max_{k\in[K]}\sum_{s,a}\frac{(d_h^{\pi^k}(s,a))^2}{\mu^*_h(s,a)}\right)$. This bound is "instance-dependent," meaning it reflects the intrinsic difficulty of the specific set of policies being evaluated.
  • Single-Policy Consistency: In the special case where $K=1$, the complexity becomes independent of the state and action space sizes, matching the efficiency of standard Monte Carlo estimation.
  • Deterministic Policy Bound: For a set of deterministic policies, the authors establish an upper bound of $\tilde{O}(\text{poly}(H)S^2A/\epsilon^2)$, which is consistent with reward-free exploration limits.

Limitations and Future Work

  • Horizon Dependency: The current bound has an $H^4$ dependency (where $H$ is the time horizon). The authors suspect this is a result of the step-wise loss function used in IDES and conjecture that a more global loss function could reduce this to $H^2$.
  • Reward-Agnosticism: CAESAR currently designs its sampling distribution based only on where policies go, not what rewards they find. Incorporating reward information (variance-aware sampling) could further optimize the process.
  • Lower Bounds: The theoretical lower bound for the multiple-policy evaluation problem remains an open question that the authors highlight for future research.

Summary updated

Abstract

We study the multiple-policy evaluation problem where we are given a set of $K$ policies and the goal is to evaluate their performance (expected total reward over a fixed horizon) to an accuracy $ε$ with probability at least $1-δ$. We propose an algorithm named $\mathrm{CAESAR}$ for this problem. Our approach is based on computing an approximate optimal offline sampling distribution and using the data sampled from it to perform the simultaneous estimation of the policy values. $\mathrm{CAESAR}$ has two phases. In the first we produce coarse estimates of the visitation distributions of the target policies at a low order sample complexity rate that scales with $\tilde{O}(\frac{1}ε)$. In the second phase, we approximate the optimal offline sampling distribution and compute the importance weighting ratios for all target policies by minimizing a step-wise quadratic loss function inspired by the DualDICE \cite{nachum2019dualdice} objective. Up to low order and logarithmic terms $\mathrm{CAESAR}$ achieves a sample complexity $\tilde{O}\left(\frac{H^4}{ε^2}\sum_{h=1}^H\max_{k\in[K]}\sum_{s,a}\frac{(d_h^{π^k}(s,a))^2}{μ^*_h(s,a)}\right)$, where $d^π$ is the visitation distribution of policy $π$, $μ^*$ is the optimal sampling distribution, and $H$ is the horizon.
BibTeX
@inproceedings{chen2025multiple,
  author = {Yilei Chen and Aldo Pacchiano and Ioannis Ch. Paschalidis},
  title = {{Multiple-policy Evaluation via Density Estimation}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=8nelB0aMry},
}
Figure