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

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

## Key facts

- Cited by 1 papers 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 56)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1604.00923/) (2016)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [More Robust Doubly Robust Off-policy Evaluation](https://mlsanity.com/paper/1802.03493/) (2018)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/1908.08526/) (2019)
- [A Review of Off-Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2212.06355/) (2022)
- [Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning](https://mlsanity.com/paper/1909.05850/) (2019)
- [Batch Policy Learning in Average Reward Markov Decision Processes](https://mlsanity.com/paper/2007.11771/) (2020)
- [Off-Policy Evaluation in Partially Observable Environments](https://mlsanity.com/paper/1909.03739/) (2019)
- [Statistical Inference of the Value Function for Reinforcement Learning in Infinite Horizon Settings](https://mlsanity.com/paper/2001.04515/) (2020)
- [CoinDICE: Off-Policy Confidence Interval Estimation](https://mlsanity.com/paper/2010.11652/) (2020)
- [Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confounding](https://mlsanity.com/paper/2003.05623/) (2020)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning](https://mlsanity.com/paper/2002.04518/) (2020)
- [Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation](https://mlsanity.com/paper/1910.07186/) (2019)
- [Off-Policy Estimation of Long-Term Average Outcomes with Applications to Mobile Health](https://mlsanity.com/paper/1912.13088/) (2019)
- [Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2110.15332/) (2021)
- [Bootstrapping Fitted Q-Evaluation for Off-Policy Inference](https://mlsanity.com/paper/2102.03607/) (2021)
- [Accountable Off-Policy Evaluation With Kernel Bellman Statistics](https://mlsanity.com/paper/2008.06668/) (2020)
- [Deeply-Debiased Off-Policy Interval Estimation](https://mlsanity.com/paper/2105.04646/) (2021)
- [A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2111.06784/) (2021)

## Built on by (most cited first, 1 of 1)

- [Designing Time Series Experiments in A/B Testing with Transformer Reinforcement Learning](https://mlsanity.com/paper/2602.01853/) (2026)

## 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.