# Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling

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

## Key facts

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

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

- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [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)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modeling](https://mlsanity.com/paper/2305.08062/) (2023)
- [Flexible Option Learning](https://mlsanity.com/paper/2112.03097/) (2021)
- [A Deep Reinforcement Learning Approach to Marginalized Importance Sampling with the Successor Representation](https://mlsanity.com/paper/2106.06854/) (2021)
- [Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff](https://mlsanity.com/paper/2110.15590/) (2021)
- [POTEC: Off-Policy Learning for Large Action Spaces via Two-Stage Policy Decomposition](https://mlsanity.com/paper/2402.06151/) (2024)
- [Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Bounds](https://mlsanity.com/paper/2103.05741/) (2021)
- [Good SFT Optimizes for SFT, Better SFT Prepares for Reinforcement Learning](https://mlsanity.com/paper/2602.01058/) (2026)
- [Stable Asynchrony: Variance-Controlled Off-Policy RL for LLMs](https://mlsanity.com/paper/2602.17616/) (2026)
- [Marginal Density Ratio for Off-Policy Evaluation in Contextual Bandits](https://mlsanity.com/paper/2312.01457/) (2023)
- [Scaling Marginalized Importance Sampling to High-Dimensional State-Spaces via State Abstraction](https://mlsanity.com/paper/2212.07486/) (2022)
- [Off-Policy Evaluation for Human Feedback](https://mlsanity.com/paper/2310.07123/) (2023)
- [SOPE: Spectrum of Off-Policy Estimators](https://mlsanity.com/paper/2111.03936/) (2021)
- [Off-Policy Actor-Critic with Emphatic Weightings](https://mlsanity.com/paper/2111.08172/) (2021)
- [Low Variance Off-policy Evaluation with State-based Importance Sampling](https://mlsanity.com/paper/2212.03932/) (2022)
- [Model-based Offline Reinforcement Learning with Local Misspecification](https://mlsanity.com/paper/2301.11426/) (2023)
- [Value-aware Importance Weighting for Off-policy Reinforcement Learning](https://mlsanity.com/paper/2306.15625/) (2023)
- [Hindsight-DICE: Stable Credit Assignment for Deep Reinforcement Learning](https://mlsanity.com/paper/2307.11897/) (2023)
- [STITCH-OPE: Trajectory Stitching with Guided Diffusion for Off-Policy Evaluation](https://mlsanity.com/paper/2505.20781/) (2025)
- [Exploiting Similarities in A/B Testing with Off-Policy Estimation](https://mlsanity.com/paper/2506.10677/) (2025)
- [Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation](https://mlsanity.com/paper/2608.24146/) (2026)
- [Proactive Service Agents: A Unified Decision Framework, Methods, and Evaluation](https://mlsanity.com/paper/2609.03727/) (2026)
- [Importance Sampling Placement in Off-Policy Temporal-Difference Methods](https://mlsanity.com/paper/2203.10172/) (2022)
- [Stackelberg Batch Policy Learning](https://mlsanity.com/paper/2309.16188/) (2023)
- [Concept-driven Off Policy Evaluation](https://mlsanity.com/paper/2411.19395/) (2024)

## Abstract (arXiv)

Off-policy policy estimators that use importance sampling (IS) can suffer from high variance in long-horizon domains, and there has been particular excitement over new IS methods that leverage the structure of Markov decision processes. We analyze the variance of the most popular approaches through the viewpoint of conditional Monte Carlo. Surprisingly, we find that in finite horizon MDPs there is no strict variance reduction of per-decision importance sampling or stationary importance sampling, comparing with vanilla importance sampling. We then provide sufficient conditions under which the per-decision or stationary estimators will provably reduce the variance over importance sampling with finite horizons. For the asymptotic (in terms of horizon T) case, we develop upper and lower bounds on the variance of those estimators which yields sufficient conditions under which there exists an exponential v.s. polynomial gap between the variance of importance sampling and that of the per-decision or stationary estimators. These results help advance our understanding of if and when new types of IS estimators will improve the accuracy of off-policy estimation.