mlsanityData to 14 Oct 2026

Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation

arXiv 2505.22492 ↗First posted 28 May 2025cs.LG cs.AI stat.MLcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

This paper studies off-policy evaluation (OPE) in reinforcement learning with a focus on behavior policy estimation for importance sampling. Prior work has shown empirically that estimating a history-dependent behavior policy can lead to lower mean squared error (MSE) even when the true behavior policy is Markovian. However, the question of why the use of history should lower MSE remains open. In this paper, we theoretically demystify this paradox by deriving a bias-variance decomposition of the MSE of ordinary importance sampling (IS) estimators, demonstrating that history-dependent behavior policy estimation decreases their asymptotic variances while increasing their finite-sample biases. Additionally, as the estimated behavior policy conditions on a longer history, we show a consistent decrease in variance. We extend these findings to a range of other OPE estimators, including the sequential IS estimator, the doubly robust estimator and the marginalized IS estimator, with the behavior policy estimated either parametrically or non-parametrically.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 56 of its 94 references that are in the map. First posted on arXiv 28 May 2025.

Builds on

56 of 94 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learning8 Dec
  2. 2024Doubly Optimal Policy Evaluation for Reinforcement Learning3 Oct

Other references · 54

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  4. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  6. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 286
  7. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  8. 2019Batch Policy Learning under Constraintscited by 244
  9. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
  10. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  11. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  12. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
38 more
  1. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 119
  2. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 119
  3. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 95
  4. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  5. 2020Batch Policy Learning in Average Reward Markov Decision Processescited by 69
  6. 2019Off-Policy Evaluation in Partially Observable Environmentscited by 66
  7. 2020Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settingscited by 65
  8. 2020CoinDICE: Off-Policy Confidence Interval Estimationcited by 64
  9. 2020Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confoundingcited by 61
  10. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  11. 2020Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learningcited by 57
  12. 2019Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimationcited by 48
  13. 2019Off-Policy Estimation of Long-Term Average Outcomes with Applications to Mobile Healthcited by 42
  14. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 41
  15. 2021Bootstrapping Fitted Q-Evaluation for Off-Policy Inferencecited by 40
  16. 2020Accountable Off-Policy Evaluation With Kernel Bellman Statisticscited by 36
  17. 2021Deeply-Debiased Off-Policy Interval Estimationcited by 36
  18. 2021A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processescited by 36
  19. 2018Importance Sampling Policy Evaluation with an Estimated Behavior Policycited by 34
  20. 2022On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluationcited by 33
  21. 2022Off-Policy Confidence Interval Estimation with Confounded Markov Decision Processcited by 31
  22. 2020Dynamic Causal Effects Evaluation in A/B Testing with a Reinforcement Learning Frameworkcited by 29
  23. 2017Data-Efficient Policy Evaluation Through Behavior Policy Searchcited by 26
  24. 2021Off-Policy Evaluation in Partially Observed Markov Decision Processes under Sequential Ignorabilitycited by 24
  25. 2021A Spectral Approach to Off-Policy Evaluation for POMDPscited by 21
  26. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 21
  27. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
  28. 2019Combining Parametric and Nonparametric Models for Off-Policy Evaluationcited by 17
  29. 2019More Efficient Off-Policy Evaluation through Regularized Targeted Learningcited by 17
  30. 2021Projected State-action Balancing Weights for Offline Reinforcement Learningcited by 16
  31. 2022ReVar: Strengthening Policy Evaluation via Reduced Variance Samplingcited by 16
  32. 2022Safe Exploration for Efficient Policy Evaluation and Comparisoncited by 15
  33. 2023Efficient Policy Evaluation with Offline Data Informed Behavior Policy Designcited by 14
  34. 2023The Statistical Benefits of Quantile Temporal-Difference Learning for Value Estimationcited by 14
  35. 2023Robust Fitted-Q-Evaluation and Iteration under Sequentially Exogenous Unobserved Confounderscited by 13
  36. 2023Off-policy Evaluation in Doubly Inhomogeneous Environmentscited by 7
  37. 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
  38. 2023Distributional Shift-Aware Off-Policy Interval Estimation: A Unified Error Quantification Frameworkcited by 6

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Designing Time Series Experiments in A/B Testing with Transformer Reinforcement Learningcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs
  2. 2025Behaviour Policy Optimization: Provably Lower Variance Return Estimates for Off-Policy Reinforcement Learning
  3. 2024Policy Gradient with Active Importance Sampling
  4. 2026Rethinking Importance Sampling in LLM Policy Optimization: A Cumulative Token Perspective
  5. 2024Kernel Metric Learning for In-Sample Off-Policy Evaluation of Deterministic RL Policies
  6. 2020Reliable Off-policy Evaluation for Reinforcement Learning
  7. 2025Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol
  8. 2023Statistically Efficient Variance Reduction with Double Policy Estimation for Off-Policy Evaluation in Sequence-Modeled Reinforcement Learning