Research map / Reinforcement learning / MDPs and planning
Multiple-policy Evaluation via Density Estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CAESAR, an offline-style multiple-policy evaluation algorithm that coarsely estimates target-policy visitation distributions, builds an approximately optimal mixture sampling distribution, and estimates importance ratios with a step-wise DualDICE-inspired loss (IDES).
Problem
Evaluating the expected total reward of K target policies simultaneously to accuracy epsilon with probability 1-delta in episodic tabular MDPs, with sample complexity that exploits overlap among target policies' visitation distributions.
Approach
Compute a coarse estimate of each target policy's visitation distribution, derive a mixture sampling distribution minimizing the maximum visitation-ratio variance across policies, then estimate importance-weight ratios step by step via a quadratic DualDICE-style loss, with median-of-means for high probability.
Key results
- CAESAR achieves sample complexity tilde-O(H^4/eps^2 sum_h max_k sum_{s,a} (d_h^{pi^k})^2/mu*_h), with high probability accuracy eps for all K target policies.
- For deterministic target policies, the sample complexity is bounded by tilde-O(poly(H) S^2 A / eps^2) independent of K (up to log terms).
- Illustrative example shows prior trajectory-synthesis bound scales as K/eps^2 whereas CAESAR's scales as 1/eps^2 when visitations coincide at the relevant layer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CAESAR to evaluate policies with identical visitation distributions rather than evaluating each policy separately | Multiple-policy evaluation on the two-layer MDP example · Two-layer MDP example | sample complexity: \tilde{O}(\frac{K}{\epsilon^2}) -> \tilde{O}(\frac{1}{\epsilon^2}) | Helped |
| Evaluate identical target policies with CAESAR | CAESAR · Single-policy evaluation | sample complexity: \tilde{O}(\frac{\text{poly}(H)}{\epsilon^2}) | Helped |
| Use CAESAR for deterministic target policies | CAESAR · Multiple deterministic policies | sample complexity: \tilde{O}\left(\frac{\text{poly}(H)S^2A}{\epsilon^2}\right) | Helped |
Surprising findings
- The optimal sampling distribution may not be realizable by any single policy, motivating the convex hull of target-policy visitations as the feasible set.
Limitations
- H^4 dependence from step-wise error propagation, conjectured improvable to H^2
- Results are for tabular finite-horizon MDPs only
- Analysis is theoretical with no empirical experiments reported
Experimental setup
Metrics: sample complexity
Baselines: naive uniform sampling over target policies trajectory-synthesis multiple-policy evaluation (on-policy) model-based estimator
Builds on: DualDICE Monte Carlo policy evaluation trajectory synthesis Freedman's inequality Median of Means
Closest papers by meaning
- Adaptive Exploration for Multi-Reward Multi-Policy Evaluation (ICML 2025 · similarity 0.86)
- Efficient Multi-Policy Evaluation for Reinforcement Learning (AAAI 2025 · similarity 0.86)
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.85)
- Logarithmic Smoothing for Pessimistic Off-Policy Evaluation, Selection and Learning (NeurIPS 2024 · similarity 0.85)
- Doubly Optimal Policy Evaluation for Reinforcement Learning (ICLR 2025 · similarity 0.85)
- Combining Experimental and Historical Data for Policy Evaluation (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.