mlsanityData to 7 Oct 2026

Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning

arXiv 1909.05850 ↗First posted 12 Sep 2019stat.ML cs.LG math.OCcited by 75

Not on the map. Why?

Abstract (arXiv)

Off-policy evaluation (OPE) in reinforcement learning is notoriously difficult in long- and infinite-horizon settings due to diminishing overlap between behavior and target policies. In this paper, we study the role of Markovian and time-invariant structure in efficient OPE. We first derive the efficiency bounds for OPE when one assumes each of these structures. This precisely characterizes the curse of horizon: in time-variant processes, OPE is only feasible in the near-on-policy setting, where behavior and target policies are sufficiently similar. But, in time-invariant Markov decision processes, our bounds show that truly-off-policy evaluation is feasible, even with only just one dependent trajectory, and provide the limits of how well we could hope to do. We develop a new estimator based on Double Reinforcement Learning (DRL) that leverages this structure for OPE using the efficient influence function we derive. Our DRL estimator simultaneously uses estimated stationary density ratios and q-functions and remains efficient when both are estimated at slow, nonparametric rates and remains consistent when either is estimated consistently. We investigate these properties and the performance benefits of leveraging the problem structure for more efficient OPE.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 3; 2021: 15; 2022: 14; 2023: 10; 2024: 10; 2025: 15; 2026: 8.

75 papers.

Sort:

By area:

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  3. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  4. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  5. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  6. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiencycited by 54
  7. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 40
  8. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  9. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  10. 2021Deeply-Debiased Off-Policy Interval Estimationcited by 36
  11. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  12. 2021Post-Contextual-Bandit Inferencecited by 32
38 more
  1. 2022Off-Policy Confidence Interval Estimation with Confounded Markov Decision Processcited by 31
  2. 2021Fast Rates for the Regret of Offline Reinforcement Learningcited by 26
  3. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  4. 2021Off-Policy Evaluation in Partially Observed Markov Decision Processes under Sequential Ignorabilitycited by 24
  5. 2022Markovian Interference in Experimentscited by 22
  6. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
  7. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
  8. 2026Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statisticcited by 19
  9. 2024Model-agnostic meta-learners for estimating heterogeneous treatment effects over timecited by 18
  10. 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
  11. 2021Towards Automatic Evaluation of Dialog Systems: A Model-Free Off-Policy Evaluation Approachcited by 16
  12. 2021Projected State-action Balancing Weights for Offline Reinforcement Learningcited by 16
  13. 2023Off-Policy Evaluation for Large Action Spaces via Policy Convolutioncited by 14
  14. 2024Offline Multi-task Transfer RL with Representational Penalizationcited by 13
  15. 2023Correcting for Interference in Experiments: A Case Study at Douyincited by 12
  16. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  17. 2025Doubly Robust Alignment for Large Language Modelscited by 11
  18. 2022Bellman Residual Orthogonalization for Offline Reinforcement Learningcited by 10
  19. 2022Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiencycited by 10
  20. 2024IGC-Net for conditional average potential outcome estimation over timecited by 10
  21. 2022Policy Evaluation for Temporal and/or Spatial Dependent Experimentscited by 8
  22. 2021Estimating the Long-Term Effects of Novel Treatmentscited by 7
  23. 2023Evaluating Dynamic Conditional Quantile Treatment Effects with Applications in Ridesharingcited by 7
  24. 2023Off-policy Evaluation in Doubly Inhomogeneous Environmentscited by 7
  25. 2024Off-Policy Evaluation in Markov Decision Processes under Weak Distributional Overlapcited by 7
  26. 2025Treatment Effect Estimation for Optimal Decision-Makingcited by 7
  27. 2023Conformal Off-Policy Evaluation in Markov Decision Processescited by 6
  28. 2024Unraveling the Interplay between Carryover Effects and Reward Autocorrelations in Switchback Experimentscited by 6
  29. 2024Combining Experimental and Historical Data for Policy Evaluationcited by 6
  30. 2022Quantile Off-Policy Evaluation via Deep Conditional Generative Learningcited by 5
  31. 2024Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learningcited by 5
  32. 2025Balancing Interference and Correlation in Spatial Experimental Designs: A Causal Graph Cut Approachcited by 5
  33. 2022A Multi-Agent Reinforcement Learning Framework for Off-Policy Evaluation in Two-sided Marketscited by 4
  34. 2021Adaptive Sequential Design for a Single Time-Seriescited by 3
  35. 2022Truly Deterministic Policy Optimizationcited by 3
  36. 2022Causal Deep Reinforcement Learning Using Observational Datacited by 3
  37. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  38. 2023A Reinforcement Learning Framework for Dynamic Mediation Analysiscited by 2

50 most cited of 75 All 75 (JSON)