# Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling

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

## Key facts

- Cited by 119 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2019.

## Built on by (most cited first, 30 of 119)

- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Off-Policy Evaluation for Large Action Spaces via Embeddings](https://mlsanity.com/paper/2202.06317/) (2022)
- [Universal Off-Policy Evaluation](https://mlsanity.com/paper/2104.12820/) (2021)
- [Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning](https://mlsanity.com/paper/2103.13883/) (2021)
- [Bootstrapping Fitted Q-Evaluation for Off-Policy Inference](https://mlsanity.com/paper/2102.03607/) (2021)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Nearly Horizon-Free Offline Reinforcement Learning](https://mlsanity.com/paper/2103.14077/) (2021)
- [A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2111.06784/) (2021)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modeling](https://mlsanity.com/paper/2305.08062/) (2023)
- [On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluation](https://mlsanity.com/paper/2201.06169/) (2022)
- [Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality](https://mlsanity.com/paper/2212.09900/) (2022)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian](https://mlsanity.com/paper/2211.00716/) (2022)
- [When is Offline Two-Player Zero-Sum Markov Game Solvable?](https://mlsanity.com/paper/2201.03522/) (2022)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Flexible Option Learning](https://mlsanity.com/paper/2112.03097/) (2021)
- [Conformal Off-Policy Prediction in Contextual Bandits](https://mlsanity.com/paper/2206.04405/) (2022)
- [Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient](https://mlsanity.com/paper/2011.04019/) (2020)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic](https://mlsanity.com/paper/2603.01162/) (2026)
- [An Instrumental Variable Approach to Confounded Off-Policy Evaluation](https://mlsanity.com/paper/2212.14468/) (2022)
- [A Deep Reinforcement Learning Approach to Marginalized Importance Sampling with the Successor Representation](https://mlsanity.com/paper/2106.06854/) (2021)
- [Efficient Reinforced Feature Selection via Early Stopping Traverse Strategy](https://mlsanity.com/paper/2109.14180/) (2021)
- [Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theory](https://mlsanity.com/paper/2202.04970/) (2022)
- [When is Realizability Sufficient for Off-Policy Reinforcement Learning?](https://mlsanity.com/paper/2211.05311/) (2022)

## Abstract (arXiv)

Motivated by the many real-world applications of reinforcement learning (RL) that require safe-policy iterations, we consider the problem of off-policy evaluation (OPE) -- the problem of evaluating a new policy using the historical data obtained by different behavior policies -- under the model of nonstationary episodic Markov Decision Processes (MDP) with a long horizon and a large action space. Existing importance sampling (IS) methods often suffer from large variance that depends exponentially on the RL horizon H. To solve this problem, we consider a marginalized importance sampling (MIS) estimator that recursively estimates the state marginal distribution for the target policy at every step. MIS achieves a mean-squared error of  frac1n sumnolimitst=1HmathbbEμleft[fracdtπ(st)2dtμ(st)2 Varμleft[fracπt(at|st)μt(at|st)big( Vt+1π(st+1) + rtbig) middle| stright]right] + tildeO(n-1.5)  where μ and π are the logging and target policies, dtμ(st) and dtπ(st) are the marginal distribution of the state at tth step, H is the horizon, n is the sample size and Vt+1π is the value function of the MDP under π. The result matches the Cramer-Rao lower bound in citetjiang2016doubly up to a multiplicative factor of H. To the best of our knowledge, this is the first OPE estimation error bound with a polynomial dependence on H. Besides theory, we show empirical superiority of our method in time-varying, partially observable, and long-horizon RL environments.