# Multiple-policy Evaluation via Density Estimation

arXiv: https://arxiv.org/abs/2404.00195 · HTML: https://mlsanity.com/paper/2404.00195/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 35 references that are in the map.
- First posted on arXiv 29 Mar 2024.

## Builds on (most cited first, 21 of 21)

- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [CoinDICE: Off-Policy Confidence Interval Estimation](https://mlsanity.com/paper/2010.11652/) (2020)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?](https://mlsanity.com/paper/2005.00527/) (2020)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Bounds](https://mlsanity.com/paper/2103.05741/) (2021)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Scalable Online Exploration via Coverability](https://mlsanity.com/paper/2403.06571/) (2024)
- [Efficient median of means estimator](https://mlsanity.com/paper/2305.18681/) (2023)

## Built on by (most cited first, 2 of 2)

- [Adaptive Exploration for Multi-Reward Multi-Policy Evaluation](https://mlsanity.com/paper/2502.02516/) (2025)
- [The geometry of AI validation: From structural blindness to reusable audits](https://mlsanity.com/paper/2608.21496/) (2026)

## Abstract (arXiv)

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 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. 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 tildeO(frac1ε). 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 citenachum2019dualdice objective. Up to low order and logarithmic terms CAESAR achieves a sample complexity tildeOleft(fracH4ε2sumh=1Hmaxk∈[K]sums,afrac(dhπ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.