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

Hongyi Zhou, Josiah P. Hanna, Jin Zhu, Ying Yang, Chengchun Shi · 2025

Read Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation by Hongyi Zhou, Josiah P. Hanna, Jin Zhu, Ying Yang, Chengchun Shi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-22492.txt.

Introduction

Hongyi Zhou and four co-authors clear up a puzzle in how we judge a new rule for acts when we can only test it on past data. Their paper is from two thousand twenty-five, in the field of learning by reward.

A core tool weighs past acts by how apt the old rule was to pick them. Past work found that guessing the old rule from a long past, even when the true rule used just the last step, cut the error of the judge. The team splits the error into bias and spread. They show the long view cuts spread while it adds some bias in small sets. As the past used grows, spread keeps falling. They stretch the result to kin tools.

Catalog record

CREATORHongyi Zhou, Josiah P. Hanna, Jin Zhu, Ying Yang, Chengchun Shi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-22492

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation Hongyi Zhou, Josiah P. Hanna, Jin Zhu, Ying Yang, Chengchun Shi Abstract 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. 1 Introduction Off-policy evaluation (OPE) focuses on estimating the average return (sum of discounted rewards) of a specific decision policy, referred to as the target policy, by leveraging historical data collected under a potentially different policy, known as the behavior policy. OPE is vital in numerous domains where direct experimentation is impractical due to high costs, potential risks, or ethical concerns, such as in healthcare ( Murphy et al., 2001 ; Hirano et al., 2003 ) , recommendation systems ( Chapelle & Li, 2011 ) and robotics ( Levine et al., 2020 ) . One widely used OPE method is importance sampling ( Precup et al., 2000 , IS, see e.g.,) , which employs a reweighting approach to handle the distribution shift between the target policy and the behavior policy. This approach is straightforward: returns generated by the behavior policy are re-weighted based on the ratio of the probability of selecting actions under the target policy to that under the behavior policy. The re-weighted returns are then averaged to produce an unbiased estimator of the target policy’s value. In the limit, as the number of trajectories increases, this estimator converges to the true value of the target policy. However, with finite samples, IS may exhibit high variance, causing considerable estimation error. Consequently, more advanced estimators have been proposed to lower its variance, including the doubly robust (DR) estimator ( Jiang & Li, 2016 ; Thomas & Brunskill, 2016 ) and marginalized IS estimator ( Liu et al., 2018 , MIS,) . Despite its limitation, IS serves as a foundation for many OPE methods and is particularly valued in practice for its unbiasedness. It is also frequently used in off-policy learning algorithms, such as the proximal policy optimization algorithm ( Schulman et al., 2017 ) , which is widely used for fine-tuning large language models ( Ouyang et al., 2022 ) . In practice, the behavior policy might be unknown and must be estimated from the historical data to construct the IS ratio. Paradoxically, IS with an estimated behavior policy results in an estimator with lower asymptotic variance and often lower finite-sample mean-squared error (MSE) compared to IS using the true behavior policy. This result has been shown in the statistics ( Henmi et al., 2007 ) , causal inference ( Hirano et al., 2003 ; Rosenbaum & Rubin, 1983 ) , multi-armed bandit ( Xie et al., 2019a ) , and Markov decision process (MDP) policy evaluation ( Hanna et al., 2021 ) literature. Furthering the paradox, Hanna et al. showed empirically that in MDPs where the true behavior policy is a first-order Markov-policy (action selection is conditioned only on the current state), the IS estimator’s MSE could be lowered by estimating a higher-order Markov-policy where action selection is conditioned on a history of preceding states ( 2021 ). However, the theoretical basis and generality of this finding was left as an open question. In this work, we establish a comprehensive theoretical framework for analyzing OPE estimators with history-dependent IS ratios; refer to Table 1 for a quick summary of our findings. Our contributions are as follows: • We demystify the aforementioned paradox for ordinary IS (OIS) estimators with history-dependent IS ratios by deriving a bias-variance decomposition of their MSEs. Our findings reveal that in large samples, the variance component becomes the leading term in the MSE and can be reduced through history-dependent behavior policy estimation. Specifically, increasing the history-length, decreases the variance . • We also show that there is no free lunch for using history-dependent IS ratios, as it comes at the price of increasing the bias of the resulting OPE estimator, which becomes non-negligible in finite samples. • We extend these findings to accommodate other variants of IS estimators, including the sequential IS (SIS), DR and MIS estimators, with the behavior policy estimated either parametrically, or non-parametrically. Interestingly, incorporating history-dependent IS ratios has different effects on the asymptotic variances of these estimators: (1) It reduces the asymptotic variance for SIS; (2) It leaves the asymptotic variance of DR unchanged when the Q-function is correctly specified, and improves the performance with a misspecified Q; (3) It increases the asymptotic variance for MIS. Table 1: Impact of incorporating history-dependent IS ratios on bias and variance across various OPE estimators, where represents an increase, represents a decrease and indicates no difference. Method bias variance Ordinary IS Sequential IS DR (with a misspecified Q ) DR (with a correct Q ) Marginalized IS 2 Literature review on OPE There is a huge literature on OPE in reinforcement learning (RL); see Uehara et al. (2022) for a recent review of existing methodologies. Current OPE methods can be grouped into four major categories: • Model-based methods . These methods estimate an MDP model from the offline data and learn the policy value based on the estimated model ( Gottesman et al., 2019 ; Yin & Wang, 2020 ; Wang et al., 2024 ) . • Direct methods . These methods estimate a value or Q-function to directly construct the policy value estimator ( Sutton et al., 2008 ; Le et al., 2019 ; Feng et al., 2020 ; Luckett et al., 2020 ; Hao et al., 2021 ; Liao et al., 2021 ; Chen & Qi, 2022 ; Shi et al., 2022b ; Li et al., 2023 ; Liu et al., 2023 ; Bian et al., 2025 ) . • IS methods . This paper focuses on the family of IS estimators, which can be further classified into three types, according to the IS ratios used to reweight the rewards: (i) OIS, which employs the product of IS ratios from the initial time to the termination time to reweight the empirical return ( Hanna et al., 2019 ; Hanna et al., 2021 ) ; (ii) SIS, which also uses the product of IS ratios but applies a different product at each time to reweight the immediate reward ( Thomas et al., 2015 ; Zhao et al., 2015 ; Guo et al., 2017 ) ; (iii) MIS, which uses an IS ratio on the marginal state-action distribution as a function of both the action and the state to

Read the complete text