mlsanityData to 7 Oct 2026

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

arXiv 1910.06508 ↗First posted 15 Oct 2019cs.LG stat.MLcited by 36

Not on the map. Why?

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.

Key facts. Cited by 36 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 9; 2022: 6; 2023: 8; 2024: 2; 2025: 4; 2026: 6.

36 papers.

Sort:

By area:

  1. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  2. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  3. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
  4. 2022Off-Policy Evaluation for Large Action Spaces via Embeddingscited by 53
  5. 2021Universal Off-Policy Evaluationcited by 43
  6. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  7. 2023Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modelingcited by 34
  8. 2021Flexible Option Learningcited by 24
  9. 2021A Deep Reinforcement Learning Approach to Marginalized Importance Sampling with the Successor Representationcited by 19
  10. 2021Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoffcited by 13
  11. 2024POTEC: Off-Policy Learning for Large Action Spaces via Two-Stage Policy Decompositioncited by 13
  12. 2021Non-asymptotic Confidence Intervals of Off-policy Evaluation: Primal and Dual Boundscited by 11
24 more
  1. 2026Good SFT Optimizes for SFT, Better SFT Prepares for Reinforcement Learningcited by 10
  2. 2023Marginal Density Ratio for Off-Policy Evaluation in Contextual Banditscited by 9
  3. 2022Scaling Marginalized Importance Sampling to High-Dimensional State-Spaces via State Abstractioncited by 7
  4. 2026Stable Asynchrony: Variance-Controlled Off-Policy RL for LLMscited by 7
  5. 2023Off-Policy Evaluation for Human Feedbackcited by 6
  6. 2021SOPE: Spectrum of Off-Policy Estimatorscited by 5
  7. 2021Off-Policy Actor-Critic with Emphatic Weightingscited by 5
  8. 2022Low Variance Off-policy Evaluation with State-based Importance Samplingcited by 5
  9. 2023Model-based Offline Reinforcement Learning with Local Misspecificationcited by 5
  10. 2023Value-aware Importance Weighting for Off-policy Reinforcement Learningcited by 4
  11. 2023Hindsight-DICE: Stable Credit Assignment for Deep Reinforcement Learningcited by 4
  12. 2025STITCH-OPE: Trajectory Stitching with Guided Diffusion for Off-Policy Evaluationcited by 2
  13. 2026Proactive Service Agents: A Unified Decision Framework, Methods, and Evaluationcited by 2
  14. 2022Importance Sampling Placement in Off-Policy Temporal-Difference Methodscited by 1
  15. 2023Stackelberg Batch Policy Learningcited by 1
  16. 2024Concept-driven Off Policy Evaluationcited by 1
  17. 2025Exploiting Similarities in A/B Testing with Off-Policy Estimationcited by 1
  18. 2026Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluationcited by 1
  19. 2022Marginalized Operators for Off-policy Reinforcement Learningcited by 0
  20. 2023Conservative Exploration for Policy Optimization via Off-Policy Policy Evaluationcited by 0
  21. 2025When Machine Learning Meets Importance Sampling: A More Efficient Rare Event Estimation Approachcited by 0
  22. 2025DOLCE: Decomposing Off-Policy Evaluation/Learning into Lagged and Current Effectscited by 0
  23. 2026Controllable User Simulationcited by 0
  24. 2026Quotient DAGs for Off-Policy Evaluation:Forward-Flow Importance Sampling and Exact Slate Propensitiescited by 0