Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation
Authors: Hongyi Zhou
Josiah P. Hanna
Jin Zhu
Ying Yang
Chengchun Shi
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning; Off-policy Evaluation;
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE

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.

Demystifying the Paradox of Importance Sampling with an Estimated History-Dependent Behavior Policy in Off-Policy Evaluation
Hongyi Zhou' Josiah P. Hanna 2
Jin Zhu
Ying Yang'
! Chengehun Shi
Abstract
healthcare (Murphy et al., 2001; Hirano et al., 2003), rec- ommendation systems (Chapelle & Li, 2011) and robotics (Levine et al., 2020).
This paper studies off-policy evaluation (OPE) in reinforcement learning with a focus on behav- ior policy estimation for importance sampling- Prior work has shown empirically that estimating distory-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 theoreti- cally demystify this paradox by deriving a bias- variance decomposition of the MSE of ordinary importance sampling (IS) estimators, demonstrat- ing that ceettory-deendden behavior policy estima- tion decreases their asymptotic variances while increasing their finite-sample biases. Addition- ally, as the estimated behavior policy conditions longer history, show consistent decrease in variance. We extend these findings to range of other OPE estimators, including the sequen- tial IS estimator, the doubly robust estimator and the marginalized IS estimator, with the behav- ior policy estimated either parametrically or non- parametrically.
One widely used OPE method is importance sampling (IS, see e-g., Precup et al., 2000), which employs a reweight- ing approach 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 the target policy's 's value. In the limit, as the number of trajectories increases, this estimator converges 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 vari- ance, including the doubly robust (DR) estimator (Jiang & Li, 2016; Thomas & Brunskill, 2016) and marginalized IS estimator (MIS, Liu et al., 2018). Despite its limitation, IS serves 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).
1. Introduction
In practice, the behavior policy might be unknown and must be estimated from the historical data to construct the IS ratio. Paradoxically, IS with estimated behavior policy results in an estimator with lower asymptotic variance and often lower finite-sample mean-squared error (MSE) com- pared to IS using the true behavior policy. This result has been shown in the statistics (Henmi et al., 2007), causal inference (Hirano al., 2003; Rosenbaum & Rubin, 1983), multi-armed bandit (Xie al., 2019a), and Markov deci- sion process (MDP) policy evaluation (Hanna et al., 2021) literature. Furthering the paradox, Hanna et al. showed em- pirically 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
Off-policy evaluation (OPE) focuses on estimating the av- erage return (sum of discounted rewards) of a specific de- cision policy, referred to as the target policy, by leveraging historical data collected under 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
'Department of Mathematical Science, Tsinghua University, Beijing, China CComputer Sciences Department, University of Wisconsin Madison, Madison, WI, USA 'London School of Economics and Political Science, London, UK. Correspondence to: Chengchun Shi <cc.hhi @ ase.ac.uk>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Demystifying the Paradox of IS with an Estimated History-Dependeee Behavior Policy in OPE
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).
Table 1. Impact of incorporating history-dependent IS ratios bias and variance across various OPE estimators, where t rep- resents an increase, + represents decrease and indicates no difference.
METHOD
BIAS
VARIANCE
Direct methods. These methods estimate a value or Q- function to directly construct the policy value estimator (Sutton al., 2008; Le et al., 2019; Feng et al., 2020; Luckett et al., 2020; Hao et al., 2021; Liao et al., 2021;
ORDINARY IS
SEQUENTIAL IS
DR (WITH MISSPECIFIED Q) DR (WITH CORRECT Q)
Chen & Qi, 2022; Shi et al., 2022b; Li et al., 2023a; Liu et al., 2023; Bian et al., 2025).
MARGINALIZED IS
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; 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); (ii) MIS, which uses an IS ratio on the marginal state- action distribution as function of both the action and the state to adjust the reward (Liu et al., 2018: 10 Nachum et al., 2019; Xie et al., 2019b; Dai et al., 2020; Wang et al., 2023; Zhou et al., 2023). In addition to these methods, several variants have been proposed to improve estimation accuracy, including incremental IS (Guo et al., 2017), conditional IS (Rowland et al., 2020), and state-based IS (Bossens & Thomas, 2024). These methods modify the IS ratio to enhance efficiency and are, in principle, similar to our proposal, which considers history-depence behavior policy estimation as an alternative strategy for improving IS efficiency.
IS methods.
states (2021). However, the theoretical basis and generality of this finding was left an open question.
In this work, we establish a comprehensive theoretical framework for analyzing OPE estimators with history- dependent IS ratios; refer to Table I 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 deseoryd behavior pol- icy 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 the price of increasing the bias of the resulting OPE estimator, which becomes non-negligible in finite samples.
We extend these findings 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:
Doubly robust methods. These methods combine the value Q-function estimator used in direct methods and the IS ratios used in IS to construct the policy value es- timator (Zhang et al., 2013; Jiang & Li, 2016; Thomas & Brunskill, 201 6; Farajtabar et al., 2018; Bibaut et al., 2019; Tang et al., 2020; Uehara et al., 2020; Kallus & Uehara, 2020; 2022; Liao et al., 2022). A salient fea- ture of these methods is their double-robustness property, which ensures the resulting policy value estimator's con- sistency as long either one of the two nuisance function estimators to be correctly specified, not necessarily both. Several extensions of DR have been proposed in the liter- ature, including triply robust estimators (Shi et al., 2021), semi-parametrically efficient estimators tailored to linear MDPs (Xie et al., 2023) and methods that estimate the difference in Q-functions (Cao & Zhou, 2024).
(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 im- proves the performance with misspecified Q:
(3) It increases the asymptotic variance for MIS.
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:
When the target policy itself is history dependent behavior policy has been employed to correct the off-policy distributional shift (Kallus & Uehara, 2020).
history-
2

---

Demystifying the Paradox of IS with an Estimated History-Dependeee Behavior Policy in OPE
However, in settings where the target policy is Markovian common scenario in MDPs due to the Markovian na- ture of the optimal policy (Puterman, 2014) the effects of behavior policy estimation on the accu- racy of the resulting OPE estimator have been less explored. Hanna et al. (2019; 2021) demonstrated the possibility of lower MSE with a history-dependent behavior policy for evaluating Markov policies in MDPs. However, their work largely focused on estimating Markov behavior policies and left the justification for using history as open question.
Bias under small sample Size
MSE under large sample size
Lostad stloo
Lodtect
Log [Blas]
1 WMW
MSE
history-
-12
50
253 500
750 1000 3239 1500 3750 2008
Sample size
Sample size
Figure 1. The left panel log absolute bias of the three estima- tors. The right panel shows log MSE of three different estimators. Results are averaged over 10 trials.
Our analysis significantly advances their analyses in the following ways: (i) We offer a bias-variance decomposition to theoretically demystify this paradox. (ii) We demonstrate that the variance varies monotonically with the number of preceding observations used to fit the behavior policy. (ii) As opposed to Hanna et al. (2019) and Hanna et al. (2021) whose focused on OIS estimator, our analysis extends to SIS, DR and MIS.
1. When T is known to us, the first estimator uses the oracle IS ratio Te/Tt To to estimate (TT)).
We (A) a/S = E,
R
To (4)
where En denotes the empirical average over the (S, A, R) triplets in the offline dataset. According to (I), it is immediate to see that itts is an unbiased estimator of v(Te)'.
3. Building intuition: from bandits to MDPs
This section begins with bandit example to introduce the OPE problem and IS estimators. This example serves to build intuition about how estimating a behavior policy that conditions on extra information than the true behavior policy can lead to more accurate IS estimator. We next formulate the OPE problem in MDPs and describe the IS estimators for MDPs.
2. Let n(aa denote the number of occurrences of A = a in the offline data. When ma remains unknown, it can be estimated by the sample mean estimator *o(a) n(a)/n, leading the second IS estimator that employs context-agnostic estimated IS ratio.
E,, (A( R (A)
CA 1S
3.1. A bandit example
3. Let n(s, a) and n(s) denote the number of occurrences of (S = 8, A = a) and S s in the offline data, re- spectively. When T6 is unknown and not assumed to be context-independent, it is natural to estimate n. us- ing (o(a ni ansss))/nntnnan /n(s), leading third estimator with a contexxtdeeeedeeee estimated IS ratio
Consider contextual bandit model B = (S, where S and A denote finite context and action spaces respectively, and r SS x A + R denotes deterministic reward function. At each time, the agent observes certain contextual informa- tion S S and selects action A according to behavior policy T, such that P(A- = al alS) = mo (a) SS) for any E A. Next, the environment responds by assigning numerical reward R to the agent, the conditional expectation of which, given the state-action pair, is equal to r(S, Given n independent and identically distributed (i.i.d)) copies of nantext-action-reweee triplets, OPE aims evaluate the ex- pected reward the agent would have received under certain target policy we, which may differ from ms.
(e(A) R (AIS)
CD is
= En
Let MSF denote the asymptotic MSE of a given estima- tor, obtained by removing errors that are high-order in the sample size n. The following lemma summarizes the perfor- mance of the three estimators in terms of their asymptotic MSEs.
IS estimators are motivated by the change-of sanee-of-maacc measure the- orem, which allows us to expresses the target policy's 's ex- pected reward v(Tz) based on the IS ratio and the observed reward as
Lemma 1. MSE A S MSE (U(A)) S. <SS (o1s). The first equality hold if and only if the reward function r is independent of the context whereas the second equality holds if and only if (
almost surely.
Te (A(s) To (AIS) R
((TT))
(L)
The two inequalities in Lemma 1 derive the following two seemingly paradoxical conclusions in the bandit setting:
Assuming that both ne and n. are both context independent (i.e.. Te (A]S) = xe (A). Tb (AIS)) = Ty (A)), we introduce three IS estimators that differ in their choice of the IS ratio:
We will use the symbol to denote estimators that use oracle IS ratios throughout the paper.
3

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
Even when the behavior policy is known, using an estimated IS ratio can asymptotically improve the resulting IS estimator compared to the one using the oracle behavior policy.
Conclusion 1.
policy that conditions on history leads more accurate OPE estimators in large samples even when the true behavior policy does not condition on more than the immediate pre- ceding state. Finally, the above theoretical analysis did not consider the biases of IS estimators. As depicted in the left panel of Figure I, incorporating history-dependent behavior policy estimation can increase bias in small samples. In our forthcoming analysis of MDPs, we will carefully examine the sample biases of different IS estimators.
Conclusion 2. Even when the true behavior policy is context-agnostic, incorporating context in estimating the IS ratio can asymptotically enhance the performance com- pared to using a context-agnostic ratio.
Our numerical results, reported in Figure 1, empirically confirm these conclusions. As observed in the right panel, incorporating context-dependent estimated IS ratios substan- tially reduces the MSE. Given that the y-axis visualizes the log(MSE), even seemingly close log values can correspond to considerable differences in MSE values.
3.2. OPE in MDPs
Markov decision processes. This paper focuses on a finite- horizon MDP model M characterized by a state space S, an action space A, transition kernel P S x S x A + IR, a reward function r S x A - R and finite horizon T < co. Consider a trajectory H := Ao. Ro..... Sr, Ar. Rr) generated in .M. These data are generated as follows:
In what follows, we outline a sketch of the proof to demys- tify these results. The key insight that replacing the true behavior policy with its estimator in the IS ratio plays a similar role in adding an augmentation term the IS esti- mator. This modification effectively transforms the resulting estimator into a DR estimator, which is often more efficient than IS even in bandit settings (Tsiatis, 2006; Zhang et al.,
At each time, suppose the environment arrives at a given state S. E E;
The agent then selects an action A, E A according to a behavior policy Tu (St):
2012; Dudík et al., 2014).
Next, the environment provides an immediate reward to the agent whose expected value is specified by the reward function r(S., A²);
Specifically, it can be shown that DCA and
D equal
CCA En Σ (a))(aa) + (A) "
To (A) IR -(A)]] (A)
Finally, the environment transits into new state S1+1 at time t+ 1 according to the transition function P(,)S.,AA))
CCD 01 = En Σ Te (a) + (A(s)
[ - A)..
This process repeats until the termination time, T, is reached.
respectively, where both P(a) and f(s, a) denote the sam- ple mean estimators, obtained by averaging rewards across different contexts and/or actions.
Common 1S-type estimators. Given an offline dataset with n i.i.d. trajectories, the objective of OPE to learn the ex- pected cumulative reward v(Te) = E,, (ET o Re) under different target policy Te, where 7 (0. 1] denotes the discount factor and E.,, denotes the expectation assuming the actions are assigned according to π..
In both expressions, the first terms within the curly brackets represent the direct method estimators for the policy value whereas the second terms serve as augmentation terms. The inclusion of these augmentation terms offers two advantages: (i) It debiases the bias inherent in the reward estimators, ren- dering the resulting OPE estimator asymptotically unbiased. (ii) It effectively reduces the variance of the OPE estima- tor by contrasting the observed reward with their predictor. Specifically, it can be shown that both expressions achieve no larger asymptotic variances than oiss which uses the ora- cle IS ratio. Additionally, the variance reductions are likely substantial when the reward function differs significantly from O. These discussions verify the assertions in Lemma
Let E,, denote the empirical average operator over the n trajectories in the offline dataset and A denote the product of (Au(()) IS ratios 1l (5, up to time t. Below, we detail the definitions of the three types of IS estimators introduced in
Section 2, along with the DR estimator which also employs IS ratios for OPE:
1. OIS serves as the most foundational estimator: It applies a single weight AT to reweight the entire empirical return
Gr = - 0 7" Re, leading to T = (>r
T
In summary, our bandit example has revealed several intrigu- ing conclusions that we aim to establish in MDPs. First, we will demonstrate that Conclusion remains valid across a range of IS-type estimators with history-dependent behavior policy estimators in MDPs. Second, we will expand on Conclusion 2 by demonstrating that estimating a behavior
2. SIS modifies OIS by applying a dependent ratio d reweight each reward R. resulting in o E, E R2) This adjustment reduces the vari- ance associated with the product of IS ratios since, at
each time f, only ratios up to that time are used.

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
3.
DR further employs an estimated Q-function reduce the variance of SIS. Specifically, let Q (s, a) denote the Q-function under the target policy, which measures the cumulative reward starting from given state-action pair
Assumption 2 (Realizability). There exists some 0* Io
such that %6 ==
Assumption 3 (Bounded rewards). There exists some con- stant Rmax oo such that Rg < Rmax almost surely for any L.
(s. = Σ EAA'B, (RelA, A a. S. =s).
Assumption (Coverage). There exist some constants E > 0, C. 2 such that all policy functions Ty are lower bounded by E, and (s, mo/oooosssss a) I C' holds for all state-action pair (s.
Given a Q-function estimator Q = {Q+}+ for (QT J.. DR is defined by
Assumption 5 (Differentiabilitt). All policies wo are twice differentiable with respect to the parameter 0, and both its first and second derivatives are uniformly bounded.
T
O = En
Don' Rs (i(s,
1=0
+h ()
Assumption 6 (Non-singularity). The Fisher information matrix f*, denoted by I(0*), ) is non-singular.
with the convention that A_ = 1. Since of employs the oracle ratio and leverages the double-robustnend property, remains consistent regardless of whether the Q-function correctly specified.
We make a few remarks. First, realizability assumes that the policy class Hl is rich enough to cover my. It is common assumption in machine learning Shhalev-Swwarz. & Ben- David, 2014). It will be relaxed in Section 5 by permitting nonzero approximation error. Second, the bounded rewards and coverage conditions are frequently assumed in the RI. and OPE literature (see c.g., Chen & Jiang, 2019; Fan et al., 2020; Kallus Uchara, 2022). Finally, Assumptions 5 and are widely imposed in statisties establish the theoreti- cal properties of maximum likelihood estimators (see e.g.. Casella & Berger, 2024).
4. MIS further reduces the variances of the aforementioned three estimators by replacing A which is known to suffer from the curse of horizon (Liu et al., 2018) with an MIS ratio given by w) = (S., ::)/d=,,,(SS (S, At) where e= and (-), are the marginal distributions of (St, A,) induced by policies we and Tb, respectively. This leads ot MIs E,, 7 7/w,
We will investigate the theoretical properties of these esti- mators in the next two sections.
4.1. Ordinary IS estimator
Recall from Section 3.2 that T denotes the OIS estimator with the oracle IS ratio År. Let Fois (k) denote the version that uses the k-step state-action history to compute the be- havior policy estimator 7/ and plugs it into Ar to construct the ratio estimator (k))
4. Demystifying the paradox in MDPs
In this section, we conduct rigorous theoretical analysis evaluate the impact of replacing the oracle behavior pol- icy with an estimated history-dependent behavior policy for OPE. Our analysis accommodates all four estimators discussed in Section 3.2.
Cois (k) = E,, (K)))G)
The following theorem establishes the theoretical properties of these estimators.
Although т. is Markov policy, historical observations can still be utilized to estimate it. In particular, we define the following estimator that uses k-step state-action history Hi-k:t- (S. .., A.))
Theorem 2. Assume Assumptions - 6 hold. Then
1 Var (ProjT(s) (A
MSE((oois(k)) = n
(2)
(k + 1)C R
T
(b) = arg max E,,
log (A, H, (H Σ 1=
+0
TETT
123/222
where T(k) denotes the space of mean zero random vari- ables that is orthogonal to the langent space spanned by the score vector
for some policy class Hl that satisfies the following mono- tonicity assumption:
Assumption (Monotonicity). No C IT, C .....
T
s(H, 0)
log To (o. 0=00"
Most commonly used policy classes based on logistic re- gression models or neural networks satisfy Assumption We discuss this assumption in greater detail in Appendix C.2 and impose the following assumptions.
00
and Proji(s) denotes the projection of a given random variable onto the space T refer to Appendix C.2 for
5

---

Demystifying the Paradox of IS with an Estimated History-Dependeee Behavior Policy in OPE
the detailed definitions. Moreover, for any k' < k, we have
employing history-dependent behavior policy estimation in small samples.
Var (oooin()(AAGr))) Var Var(Proigg (rroiigk)(ArGh)
(3)
Based on the aforementioned discussion, the following corollary is immediate from Theorem 2.
Var ( - Projr(e)(A(Gr))
Corollary 3. Let k and K' be two positive integers satisfying
Theorem has a number of important implications:
k' S k. Under Assumptions - 6, we have
1. Equation (2) obtains bias-variance decomposition for the MSE of Cors (k). In particular, the first term on the right-hand-
ASEA (k)) < MSE (fois (k())
(RHS) of (2) corresponds to its asymp- totic variance, which of the order O(n-1), whereas the second term upper bounds its finite-sample bias, which decays to zero at faster rate as n increases. Additionally, it is well known that the variances of IS-type estimators grow exponentially fast with the time horizon (see, e.g., Liu et al., 2018). Our error bound reveals that when us- ing estimated IS ratios, the same curse of horizon applies to the bias, which includes a factor of C for some C 2 1, where C 1 if and only if the behavior policy matches the target policy, meaning there is no off- off-policy distributional shift at all.
To summarize, Theorem 2 formally establishes the bias- variance trade-off in distory-dependent behavior policy es- timation: it decreases the asymptotic variance of the OIS estimator at the cost of increasing the finite-sample bias. Furthermore, a longer history length results in a greater reduction in variance.
4.2. Sequential IS estimator
Let (k) denote the estimator for Ae by replacing the oracle behavior policy with its estimator m/( We define Esis (l) as variant of the oracle SIS estimator V constructed based on (Ax (k)) The following theorem obtains similar bias-variance decomposition for its MSE.
In large samples, the asymptotic variance term becomes the dominating factor. This term equals the variance of E,, (1)) (r)) Thus, incorporating history-de- pendent behavior policy estimation into OIS estimators can be interpreted as a projection that projects the em- pirical return into a more constrained space for variance reduction. This interpretation aligns with our perspective on transforming IS estimators with estimated ratios into DR estimators, as illustrated in the bandit example (see Section 3.1), since DR can be viewed as projecting an IS estimator onto specific augmentation space improve efficiency (Tsiatis, 2006). Notice that the projected vari- able ProjT()) (ArGr) achieves a smaller variance than Gr itself, our result thus covers Corollary 2 in Hanna et al. (2021), suggesting that replacing the true behavior policy with its estimate reduces the asymptotic variance of the resulting OIS estimator.
Theorem 4. Assume Assumptions I - 6 hold. Then
1 n
MSH (k)) Var (PoojT()) Σ Xey Xey
1= +0
(4)
(k: + 2 Ryaax
n3/22²
In addition, the first term on the RHS of (2) is non- decreasing with respect to
Recall that the oracle SIS estimator Sss given by En ( Re). Similar to OIS, Theorem 4 suggests that using an estimated behavior policy will lower the MSE of the resulting SIS estimator in large samples through pro- jection. Meanwhile, the longer the history-length, the lower the asymptotic MSE, leading to the following corollary.
Rt).
3. Additionally, according to (3), the variance term is a monotonically non-decreasing function with respect to the history-length, which in turn demonstrates the ad- vantage of estimating high-order Markov policy over first-order policy in large samples. Mathematically, this can again be interpreted through projection: the longer the history-length, the more restrictive the constrained space used to project the empirical return, leading to greater asymptotic efficiency.
Let k and k' be two positive integers satisfying W S k. Then under Assumptions 6,
Corollary 5.
(TSIs S (USIs
4. In small samples, particularly in settings with long hori- zons, the bias term becomes neg-negli and increases exponentially with the horizon. To the contrary, the ora- cle estimator t is unbiased. This illustrates the risk of
However, estimating the behavior policy can introduce sig- nificant biases in small samples and long horizons, the mag- nitudes of which are given by the second term in (4).
6

---

Demystifying the Paradox of IS with an Estimated History-Dependeee Behavior Policy in OPE
4.3. Doubly robust estimator
Kallus & Uehara, 2020). If the estimator is already effi- cient, history-dependent behavior policy estimation can- not provide additional gains. On the other hand, when the Q-function is misspecified, there remains room for improvement, and history-dependee estimators can im- prove the estimation accuracy.
Consider the following DR estimator constructed based on the history-dependent IS ratio (k)),
T
ÖRR = En
Σ
Not (Re- Q.))
1=
The following corollary is again an immediate application of Theorem 5.
+ Σ (((S),))Te(a(()))
Corollary 7. Under Assumptions 1, 5-7,, we have for any k' S k that
with a pre-specified Q-function which is required to satisfy the following assumption:
MSE (VDD(()R(A)) (k:) S MSEA (ŌDu (K)).
Assumption 7 (Boundedness). There exists some Umax < oo such that the absolute value of U,- = Rs - (St, At) + QQ++ (a, 1 is upper bounded by 3x almost surely for any t.
The equation holds when the Q-function is correctly speci- fied. In that case, we have MSE A (k)) = MSE, (DDR) for any k.
Assumption 7 corresponds to a version of the bounded- ness condition in Assumption tailored for DR estimators. The constant Umax is expected to be much smaller than Rmax with a well-chosen Q-function. In particular, when the Q-function is correctly specified, Ug corresponds to the absolute value of the Bellman residual, which tends to con- centrate more closely around zero than R..
4.4. Marginalized importance sampling estimator
A key step in constructing the MIS estimator lies in the estimation of the MIS ratio. Unlike the previously discussed ratios ()e).. which can be known in settings such ran- domized studies, the MIS ratio depends on the marginal state distribution and is typically unknown, even when the behavior policy is given.
Theorem 6. Assume Assumptions 1, 2, 5 7 hold. Then,
In the literature, several methods have been developed to estimate the MIS ratio, such as minimax learning (Uehara et al., 2020) and reproducing kernel Hilbert space (RKHS)- based methods (Liao al., 2022). To simplify the analysis, we focus on using linear function approximation in this paper, which parameterizes each we by o (S,, A.)ay, for some state-action features 6, Adapting Example 2 from Uehara et al. (2020) to the umite-horizon setting, we derive the following closed-form expression for the estimator Öo.
T
MSE(Fdu(k)) = Var Var Car(ProjT(a)
Σ 1= t0 (ke + U2 max
An'U))
(5)
n3/2222
In addition, the first term on the RHS of (5) is non- decreasing with respect to k. However, when the Q-function is correctly-ppecifer this term becomes a constant function of k.
āo = Eo-EE Σ T (a))8))0((6:
We make two remarks regarding Theorem 6:
where E, = E,, (S,, A.) (So, An)] and the following recursive formulas for computing ā..
1. The bias- variance decomposition in (5) closely resembles that of SIS, with the key difference being that the reward R2 and its bound Rmax in (4) are replaced with U, and Umax. respectively. With well-specified Q-function, U. is expected to exhibit lower variability than RG, and Umax can be significantly smaller than Rmax. This highlights the advantages of SIS: they not only improve asymptotic variance but also reduce sinite-sample bias.
E- āg = T
Σ Te (() As ā à
The estimated MIS ratios {ū, TT (Sc. A,) he are then plugged into the oracle estimator atus to compute (0))
DR estimators over
Alternatively, the k-step history Hi-ki can be used to construct a history-dependent MIS ratio wy wx(k) E(A, Hg A.). This ratio can be interpreted as con- ditional IS ratio (Rowland et al., 2020) with Hi-kit and A, being the conditioning variable. It is also closely related to the incremental IS (INCRIS) ratio proposed by Guo et al. (2017), but differs by incorporating an additional MIS ratio for S.-k-
2. However, the second part of Theorem 6 indicates that, unlike OIS or SIS, history-dependent behavior policy estimation may not further reduce asymptotic variance when the f-uunttion is correctly specified. This is in- tuitive, as in such cases, the DR estimator is known to achieve certain efficiency bounds (Jiang & Li, 2016;
7

---

Demystifying the Paradox of IS with an Estimated History-Dependeee Behavior Policy in OPE
For estimation, (k)k:) can be parameterized similarly to Wt, using k-step features (e(k) a function of H and Ac. with parameters estimated in a manner similar to those for w. However, unlike IS and DR. incorporating history-dependent MIS ratio may increase the MSE of the resulting MIS estimator, denoted by MMs (k), Additionally, the longer the history-length, the worsen the performance. We summarize these results in the following theorem.
Theorem 9. Under Assumptions 8- 13 defined in Appendix C.3, we have
MSEA (Dois ( (k)) 1 ASE (OI1))
MSE (8SIs
S a
(SEA((DR(K))
M A
Theorem 9 demonstrates the advantages of OPE estimators with nonparametrically estimated behavior policies in large samples. While similar results have been established in the literature (see e.g.. Hanna al., 2021), they primarily focused the OIS estimator using parametric estimation of the behavior policy and required the realizabilitty assump- tion (see Assumption 2). In contrast, Theorem 9 relaxes the realizability by allowing the approximation error to decay to zero at a rate of o(n -1/4) (see Assumption 9), which is much slower than the parametric n -1/2-ratee Nonetheless, we demonstrate that the resulting OPE estimators still con- verge at the parametric rate, which is central to establish their MSEs. This faster convergence rate occurs because the policy value is smooth functional of the sieve estimator, and "smoothing" inherently improves the convergence rate. While similar findings have been documented in classical statistics literature for nonparametric regression problems (Shen, 1997; Newey et al., 1998). these phenomena have not been less explored in OPE and RL. One exception is Shi al. (2023), who considered the direct method esti- mator but did not study history-dependent behavior policy estimation.
Theorem 8. Let Tnss (k) be the MIS estimator with k-step history: Then, under regularity conditions specified in Ap-
pendix C.2, for any k' < k,
MSEA (TMIS (K)) S ASEEAUUMIS (R:)).
To appreciate why Theorem 8 holds, notice that by setting k to the horizon T. wxyk) is reduced to the A,, and the resulting estimator is reduced to SIS, which suffers from the curse of horizon and is known to be less efficient than MIS. More generally, similar to increasing the history-length leads to more variable IS ratio, thus increasing the MSE.
5. Extensions to cases where the behavior policy is estimated nonparametrically
Our analysis so far focuses on using parametric models to estimate the behavior policy or IS ratio. In practical appli- cations, nonparametric estimation of the behavior policy can be desirable to avoid the potential misspecification of the parametric model. This motivates us to investigate the performance of deetedent OPE estimators with non- parametrically estimated behavior policy.
6. Numerical studies
A common nonparametric approach is to approximate the policy set II using a sequence of sieve spaces II, Below, we demonstrate that, under certain regularity conditions (detailed in Appendix C.3), similar to the parametric case, replacing the true behavior policy with an estimated be- havior policy within the sieve space lowers the asymptotic variance of the resulting OPE estimator.
Our experiment compares several history-dependent IS esti- mators in the CartPole environment (Brockman al., 2016). Specifically, we consider the following three estimators: SIS, DR with misspecified Q Q-function, and MIS.
As shown in Figure 2, all three estimators' MSES decrease with the sample size, suggesting their consistencies. For SIS and DR with misspecified Q-functions, replacing the oracle behavior policy with history-dependeer estimator generally reduces their MSEs in large samples. Additionally, performance improves with longer history-length. However, for MIS estimators, the performance consistently worsens as we increase the history-length to estimate the MIS ratio. Finally, it is also apparent that cestory-dependem estimators generally suffer from larger biases compared to those using an oracle behavior policy. These empirical results verify our theoretical findings.
Specifically, we assume the policy class II can be rep- resented by (H) 0 E θ) with an infinite- dimensional Hilbert space O. Let θ C ...O,, C @n+1 S θ be a sequence of finite-dimensional sieve spaces. For a given sample size n, we compute the esti- mator 0n by maximizing the log-likelihood function in the sieve space On.
T log To (Ag(
(k) arg max En DEE. t=
In Appendix B, we further expand our numerical experi- ments to more complex MuJoCo environments, including (i) Inverted Pendulum, featuring a continuous action space; (ii) Double Inverted Pendulum, characterized by a higher- dimensional state space; (iii) Swimmer, an environment
Let (kis(k), Tss (k) and TDR (k) denote the OIS, SIS and DR estimators, respectively, each constructed based on the estimated behavior policy TT( kae (k)). We summarize our results as follows.
8

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
[Bias] of SIS estimators
Log MSE of estimators
where Var(h) denotes variance estimator computed via the sampling variance formula or bootstrap, & llg((n) is the Bayesian information criterion (BIC, Schwarz, 1978) penalty preventing selecting long history without substan- tial reduction of the variance. Our simulation studies (not reported in the paper) demonstrate strong empirical perfor- mance of this history selection method.
30
2.5
56101
2.5
95/3)
2.0
SEIU
[Blas]
2.0
MSE
1.5
SB141
55121
S/S/8)
SKURI
1.0
0.5
0.0
8-10000
reuido
Sample Size
Sample Size
To conclude this paper, we note that the OPE literature has been growing rapidly in recent years, expanding into several directions, including the investigation of partially observable environments (Uchara et al., 2023; Hu & Wager, 2023), heavy-tailed rewards (Xu et al., 2022; Liu et al., 2023; Rowland et al., 2023; Zhu et al., 2024; Behnamnia et al., 2025) and unmeasured confounders (Kallus & Zhou, 2020; Namkoong et al., 2020; Tennenholtz al., 2020; Nair & Jiang, 2021; Shi et al., 2022a; Wang et al., 2022; Bruns- Smith & Zhou, 2023; Xu et al., 2023; Bennett & Kallus, 2024; Shi et al., 2024; Yu et al., 2024). Our proposal is related to a growing line of research that investigates optimal experimental design for OPE (Hanna et al., 2017; Mukherjee et al., 2022; Wan et al., 2022; Li al., 2023b; Liu & Zhang, 2024; Liu et al., 2024; Sun al., 2024; Wen al., 2025). These works focus on designing optimal behavior policies prior to data collection to improve OPE accuracy whereas our proposal considers estimating behavior policies after data collection for the same purpose. The work of Liu & Zhang (2024) is particularly related as the behavior policy is computed from offline data before being run to collect more data. Both approaches share the most fundamental goal of enhancing OPE by learning behavior policies whether for data collection or retrospective estimation.
BBass| of DR estimators
Log MSE of DR estimators
DR
35
DR
3.0
DRUn
DR(3)
2.5
[Bio5]
2.0
3.5
Log
8510000
Reddad
H-rdard
tosd
R-2a0d
Ne
Sample Size
Sample Size
[Bias] of MIS estimators
Log MSE of MIS estimators
20
M530
3.0
Hist
H5101
MG2I
MS11
[Blas]
2.0
MB121
H514
1.0
R-1000
Re2000
Red0000
Herbsod
7000
Nesbog
Re10000
Rez2000
Re-2000
Restaa
R-7700
Sample Size
Sample Size
Figure 2. Absolute bias (left panel) and log MSE (right panel) of three OPE estimators: SIS (top panel). DR (middle panel). MIS (top panel). The results are averaged over 50 simulations.
Acknowledgement
with substantially different dynamics compared to the other two. The detailed results are deferred to Appendix B.
Hongyi Zhou's and Ying Yang's research was partially sup- ported by NSFC 12271286 & 11931001. Hongyi Zhou's 's re- search was also partially supported by the China Scholarship Council. Chengchun Shi's and Jin Zhu's 's research was par- tially supported by the EPSRC grant EP/W014971/1. Josiah Hanna acknowledges support from NSF (IIS-24109) I), American Family Insurance through a research partnership with the University of Jisconsin-MMadison 's Data Sci- ence Institute, the Wisconsin Alumni Research Foundation, and Sandia National Labs through a University Partnership Award. The authors thank the anonymous referees and the area chair for their insightful and constructive comments, which have led to a significantly improved version of the paper.
7. Discussion
This paper demystifies the paradox concerning the impact of history-dependee behavior policy estimation on IS-type OPE estimators by establishing bias-variance decompo- sition of their MSEs. Our analysis reveals trade-off in the choice of history-length for estimating the behavior pol- icy: increasing the history-length reduces the estimator's s asymptotic variance, but can increase its finite-sample bias. Therefore, selection of history length is crucial for applying our theory to practice.
In this section, we propose some practical guidance on the selection of history length when estimating behavior policy. Specifically, motivated by the bias-variance trade-off, we propose to select the history length that minimizes
Impact statement
This paper provides theoretical foundation for using history-dependent behavior policy estimators for OPE in re-
h" = arg min 2n Var(h) - log(n)).
9

---

Demystifying the Paradox of IS with an Estimated History-Dependee Behavior Policy in OPE
inforcement learning. Our research reveals that while these estimators may decrease accuracy with small sample sizes, they significantly improve estimation accuracy sample size increases. This insight clarifies when and how historical data should be integrated into behavior policy estimation, en- hancing the effectiveness and reliability of various off- pollicy estimators across different applications. Our work primarily engages theoretical analysis and does not directly interact with manipulate real-world systems. Consequently, it is unlikely to have negative societal consequences.
Chen, J. and Jiang, N. Informatiin-theorrtiicc considerations in batch reinforcement learning. In International Con- ference Machine Learning, pp. 1042-1051. PMLR, 2019.
Chen, X. and Qi, Z. On wosl-posed and minimax opti- mal rates of nonparametric q-function estimation in off- policy evaluation. In Proceedings of the 39th Interna- tional Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 3558- 3582. PMLR, 17-23 Jul 2022.
References
Chernozhukov, V., Chetverikov, D., and Kato, K. Gaussian approximation of suprema of empirical processes. The Annals of Statistics, pp. 1564-1597. 2014.
Behnamnia, A., Aminian, G., Aghaei, A., Shi, C., Tan, V. Y. F., and Rabiee, H. R. Log-sum-eepoonetiall estimator for off-policy evaluation and learning. In International Conference on Machine Learning. PMLR, 2025.
Chemozhukov, V., Chetverikov, D., Demirer, M., Duflo, E., Hansen, C., Newey, W., and Robins, J. Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal, 21(1):C1-668, 01 2018.
Bennett, A. and Kallus, N. Proximal reinforcement learn- ing: Efficient off-policy evaluation in partially observed markov decision processes. Operations Research, 72(3): 1071-1086, 2024.
Dai, B., Nachum, O., Chow, Y., Li, L., Szepesvari, C., and Schuurmans, D. Coindice: Off-policy confidence interval estimation. In Advances in Neural Information Processing Systems, volume 33, pp. 0398-9411. Curran Associates, Inc., 2020.
Bian, Z., Shi, C., Qi. Z., and Wang, L. Off-policy evaluation in doubly inhomogeneous environments. Journal of the American Statistical Association, to appear, 2025.
Bibaut, A., Malenica, I.. Vlassis, N., and Van Der Laan, M. More efficient off off-policy evaluation through regular- ized targeted learning. In International Conference on Machine Learning, pp. 654 663. PMLR, 2019.
Dudík, M., Erhan, D., Langford, J., and Li, L. Doubly Ro- bust Policy Evaluation and Optimization. Statistical Sci- ence, 29(4):485 511, 2014. doi: 10. 00.121//14-SS5500
Fan, J., Wang, Z., Xie, Y., and Yang, Z. A theoretical analysis of deep q-learming. In Learning for dynamics and control, pp. 486-489, PMLR, 2020.
Bossens, D. M. and Thomas, S. Low variance off-policy evaluation with state-based importance sampling. In 2024 IEEE Conference Artificial Intelligence (CAI), pp. 871- 883. IEEE, 2024.
Farajtabar, M., Chow, Y., and Ghavamzadeh, M. More robust doubly robust off-policy evaluation. ArXiv, 2018.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J.. Schulman, J., Tang, J., and Zaremba, W. Ope- nai gym, 2016. URL. https://arxiv. wwwpexivvvorraeeoomommo org/abs/ abs/ 1606. 01540.
Feng. Y., Ren, T., Tang, Z., and Liu, Q. Accountable off- policy evaluation with kernel Bellman statistics. In Pro- ceedings of the 37th International Conference on Ma- chine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 3102-3111. PMLR, 13-18 Jul 2020.
Bruns-Smith D. and Zhou, A. Robust fitted-g-evaluation and iteration under sequentially exogenous unobserved confounders. arXiv preprini arXiv:2302.0066 2023.
Cao, D. and Zhou, A. Orthogonalized estimation of differ- ence of q-functions. arXiv preprint arXiv:2406.08697, 2024.
Gottesman, O.,, Liu, Y., Sussex, S., Brunskill, E., and Doshi- Velez, F. Combining parametric and nonparametric mod- els for off-policy evaluation. In International Conference on Machine Learning, pp. 2366 266552235..2 PMLR, 2019.
Casella, G. and Berger, R. Statistical inference. CRC press, 2024.
Guo, Z. D.. Thomas, P. S., and Brunskill, E. Using options and covariance testing for long horizon off-policy pol- icy evaluation. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 2489-2495. Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 97815 9781510860964.
Chapelle, O. and Li, An empirical evaluation of thomp- son sampling. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS' 11, pp. 1449-2257, Red Hook, NY, USA, 2011. Curran Associates Inc. ISBN 9781618395999
10

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
Hanna, J., Niekum, S., and Stone, P. Importance sampling policy evaluation with estimated behavior policy. In Proceedings of the 36th International Conference on Ma- chine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2605-2613 PMLR, 09-15 Jun 2019.
Kallus, N. and Zhou, A. Confounding-robuss policy eval- uation in infinite-horizon reinforcement learning. Ad- vances in neural information processing systems, 33: 22293-22304, 2020.
Kosorok, M. R. Introduction to Empirical Processes and Semiparametric Inference. Springer New York, NY, 2008,
Hanna, J. P., Thomas, P. S., Stone, P., and Niekum, S. Data- efficient policy evaluation through behavior policy search. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, vol- ume 70 of Proceedings of Machine Learning Research, pp. 1394-1403, PMLR, 06-11 Aug 2017.
Le, H., Voloshin, C., and Yue, Y. Batch policy learning under constraints. In Proceedings of the 36th Interna- tional Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3703- 3712. PMLR, 09 15 Jun 2019.
Hanna, J. P., Niekum, S., and Stone, P. Importance sam- pling in reinforcement learning with an estimated behav- ior policy. Mach. Learn., 1 110(6): 167--317, 2021. ISSN 0885-6125.
Levine, S., Kumar, A., Tucker, G., and Fu, Offline rein- forcement learning: Tutorial, review, and perspectives on open problems. ArXiv, abs/2005.01643, 2020.
Li, G., Wu, W., Chi, Y., Ma, C., Rinaldo, A., and Wei, Y. Sharp high-probability sample complexities for policy evaluation with linear function approximation. arXiv preprint arXiv:2305. 19001, 2023a.
Hao, B., Ji, X., Duan, Y., Lu, H., Szepesvari, C., and Wang, Bootstrapping fitted g-evaluation for off-policy infer- ence. In Proceedings of the 38th International Confer- ence on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 4074 4084. PMLR, 2021.
Li, T., Shi, C., Wang, J., Zhou, F., et al. Optimal treatment allocation for efficient policy evaluation in sequential decision making. Advances in Neural Information Pro- cessing Systems, 36:48890-48905, 2023b.
Henmi, M., Yoshida, R., and Eguchi, S. Importance sam- pling via the estimated sampler. Biometrika, 94(4):985- 991, 12 2007.
Liao, P., Klasnja, P., and Murphy, S. Off- estimation of long-term average outcomes with applications to mobile health. Journal of the American Statistical Association, 1 116(533)3382-391 2021.
Hirano, K., Imbens, G. W., and Ridder, G. Efficient esti- mation of average treatment effects using the estimated propensity score. Econometrica, 71(4):1161-118) 2003.
Liao, P., Qi. Z., Wan, R., Klasnja, P., and Murphy, S. A. Batch policy learning in average reward Markov decision processes. The Annals of Statistics, 50(6):3364 -3387, 2022.
Hu, Y. and Wager, S. Off--olicy evaluation in partially observed Markov decision processes under sequential ignorability. The Annals of Statistics, 51(4):1561 1585,
2023. doi: 10. 10.1214/23-A0S2233
Liu, Q., Li. Tang, Z., and Zhou, D. Breaking the curse of horizon: infinite-horin off-policy estimation. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 5361-5371, Red Hook, NY, USA, 2018. Curran Asso- ciates Inc.
Jinng N. and Li, I.. Doubly robust off-polic value evalu- ation for reinforcement learning. In Proceedings of The
33rd International Conference on Machine Learning, vol- ume 48 of Proceedings of Machine Learning Research, pp. 652-661,, New York, New York, USA, 20-22 Jun 2016. PMLR.
Liu, S. and Zhang, S. Efficient policy evaluation with offline data informed behavior policy design. In Salakhutdinov, R., Kolter, 7.,, Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 32345-32363 PMLR, 21-27 Jul 2024.
Kallus. N. and Uehara, M. Double reinforcement learning for efficient off- policy evaluation in markov decision pro- cesses. Journal of Machine Learning Research, 21(167); 1-63, 2020. URL http: jmwrr/mm...//// org/ papers/
Kallus, N. and Uchara, M. Efficiently breaking the curse of horizon in off-policy evaluation with double reinforce- ment learning. Oper. Res., 7066):222--3344 November 2022. ISSN 0030-364X.
Liu, S. D., Chen, C., and Zhang, S. Doubly optimal policy evaluation for reinforcement learning. arXiv preprint arXi::2410002226 2024.

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
Liu, W., Tu, J., Zhang, Y., and Chen, X. Online estimation and inference for robust policy evaluation in reinforce- ment learning. arXiv preprint arXiv:2310.0258/ 2023.
Rosenbaum, R. and Rubin, D. В. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55, 1983, ISSN 00063444, 14643510.
Luckett, D. J., Laber, E. B., Kahkoska, A. R., David M. Maahs, E. M.-D., and Kosorok, M. R. Estimating dynamic treatment regimes in mobile health using v- learning. Journal of the American Statistical Association, 115(530):692-706, 2020. doi: 10.1080001621459.22 2018. 1537919.
Rowland, M., Harutyunyan, A., Hasselt, H., Borsa, D., Schaul, T., Munos, R., and Dabney, W. Conditional importance sampling for off-policy learning. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 45-55. PMLR, 2020.
Mukherjee, S., Hanma, P., and Nowak, R. D. Revar: Strengthening policy evaluation via reduced variance sam- pling. In Cussens, J. and Zhang, K. (eds.), Proceedings of the ThihtyEEigtth Conference on Uncertainty in Artifi- cial Intelligence, volume 180 of Proceedings of Machine Learning Research, pp. 1413-1422. PMLR, 01-05 Aug 2022.
Rowland, M., Tang, Y., Lyle, C., Munos, R., Bellemare, M. G., and Dabney, W. The statistical benefits of quantile lemporal-difference learning for value estimation. In In- ternational Conference on Machine Learning, pp. 29210- 29231. PMLR, 9923, 2023.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint urXiv:1707.066 2017.
Murphy, S. A., van der Laan, M. J., Robins, J. M., and Group, C. P. P. R. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1410-1423 2001.
Schwarz, G. Estimating the dimension of model. The annals of statistics, pp. 461-464 1978.
Nachum, O., Chow, Y., Dai, B., and Li, L. Dualdice: Behavior-agnoste estimation of discounted stationary distribution corrections. Advances in neural information processing systems, 32, 2019.
Shalev-Shwarte S. and Ben-David, S. Understanding ma- chine learning: From theory algorithms. Cambridge university press, 2014.
Shao, J. Mathematical Statistics. Springer, New York, 2nd edition, 2003. ISBN 978 978-0-387-00179-1. doi: 10.1007/ b98854.
Nair, Y. and Jiang, N. A spectral approach to off-policy evaluation for pomdps. arXiv preprint vrXiv:2199.10500 2021.
Shen, X. On methods of sieves and penalization. The Annals of Statistics, 25(6):2555-2511, 1997.
Namkoong, H., Keramati, R., Yadlowsky, S., and Brunskill, E. Off-policy policy evaluation for sequential decisions under unobserved confounding. Advances in Neural In- formation Processing Systems, 33:18815 1819-18831, 2020.
Shi, C., Wan, R., Cheroozhukov, V., and Song, R. Deeply- debiased off-policy interval estimation. In International conference on machine learning, pp. 9580-9599 PMLR, 2021.
Newey, W. K., Hsich, F., and Robins, Undersmoothing and bias corrected functional estimation. 1998.
Shi, C., Uchara, M., Huang. J., and Jiang, N. A minimax learning approach to off-policy evaluation confounded partially observable markov decision processes. Inter- national Conference Machine Learning, pp. 20057- 20094. PMLR, 2022a.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744 2022.
Shi, C., Zhang, S., Lu, W., and Song. R. Statistical inference of the value function for reinforcement learning in infinite- horizon settings. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(3):765-793, 12 2022b.
Precup, D., Sutton, R. S., and Singh, S. Eligibility traces for off off-policy policy evaluation. In Proceedings of the Sev- enteenth International Conference on Machine Learning, ICML. '00, pp. 759-766, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc. ISBN 1558607072.
Shi, C., Wang, X., Luo, S., Zhu, H., Ye, J., and Song, R. Dynamic causal effects evaluation a/b testing with a reinforcement learning framework. Journal of the Ameri- can Statistical Association, 118(543)2059-2077) 2023.
Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
12

---

Demystifying the Paradox of IS with an Estimated History-Dependeee Behavior Policy in OPE
Shi, C., Zhu, J., Shen, Y., Luo, S., Zhu, H., and Song, R. Off- policy confidence interval estimation with confounded markov decision process. Journal of the American Statis- tical Association, 1196545)273-2888 2024.
Wan, R., Kveton, B., and Song. R. Safe exploration for efficient policy evaluation and comparison. In Inter- national Conference Machine Learning, pp. 22491- 22511. PMLR, 2022.
Sun, K., Kong, L., Zhu, H., and Shi, C. Optimal treat- ment allocation strategies for a/b testing in partially observable time series experiments. arXiv preprint arXiv:2408.05342, 2024.
Wang. J.. Qi, Z., and Shi, C. Blessing from human-ai interaction: Super reinforcement learning in confounded environments. arXiv preprint arXiv:2209, 15448, 2022.
Wang. J., Qi, 2., and Wong, R. K. W. Projected state-action balancing weights for offline reinforcement learning. The Annals of Statistics, 5 51(: 1639 - 1665, 2023.
Sutton, R. S., Szepesvári, C., and Maei, H. R. A conver- gent o(n) algorithm for off-policy temporal-diffrence learning with linear function approximation. Advances in neural information processing systems. 21(21):1609 1616, 2008.
Wang, W., Li, Y., and Wu, X. Off-policy evaluation for
tabular reinforcement learning with synthetic trajectories. Statistics and Computing, 34(1):41, 2024. 20224
Tang, Z., Feng Y., Li, L.,, Zhou, D., and Liu, Q. Dou- bly robust bias reduction in infinite horizon off-policy estimation. In International Conference on Learning Representations, 2020.
Wen, Q., Shi, C., Yang, Y., Tang, N., and Zhu, H. Unraveling the interplay between carryover effects and reward auto- correlations in switchback experiments. In International Conference on Machine Learning. PMLR, 2025.
Tennenholtz, G., Shalit, U., and Mannor, S. Off-policy eval- uation in partially observable environments. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10276-10283, 2020.
Xie, C., Yang, W., and Zhang, Z. Semiparametrically effi- cient off-policy evaluation in linear markov decision pro- cesses. In International Conference on Machine Learning, pp. 38227-38257. PMLR, 2023.
Thomas, P. S. and Brunskill, E. Data-efficient off -oolpo pol- icy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on International Conference Machine Learning- Volume 48, ICML'16, pp. 2139-2148, JMLR.org org, 2016.
Xie, T., Ma. Y., and Wang. Y.-X. Towards optimal off- eff-policy evaluation for reinforcement learning with marginalized importance sampling. Curran Associates Inc., Red Hook, NY, USA, 2019a.
Thomas, P. S., Theocharous, G., and Ghavamzadeh, M. High-confidence off- off-policy evaluation. In AAAI Confer- ence on Artificial Intelligence, 2015.
Xie, T., Ma, Y., and Wang, Y.-X. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in neural information processing systems, 32, 2019b.
Tsiatis, A. A. Semiparametric Theory and Missing Data. Springer, 2006.
Xu, Y., Shi, C., Luo, S., Wang, L., and Song, R. Quantile off- policy evaluation via deep conditional generative learning. arXiv preprint 22 14466, 2022.
Uehara, M., Huang, J., and Jiang, N. Minimax weight and q-function learning for off-policy evaluation. In Proceed- ings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learn- ing Research, pp. 9659-9659999 -668. PMLR, 13-18 Jul 2020.
Xu, Y., Zhu, J., Shi, C., Luo, S.,, and Song, R. An instrumen- tal variable approach to confounded off-policy evaluation. In International Conference on Machine Learning, pp. PMLR, 2023.
Uchara, M., Shi, C., and Kallus, N. A review of ooflpo evaluation in reinforcement learning. arXiv preprint arXiv:2212.06355. 2022.
Yin, M. and Wang, Y.-X. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 3948-3949999 PMLR, 2020.
Uehara, M., Kiyohara, H., Bennett, A., Chernozhukov, V., Jiang, N., Kallus, N., Shi, C., and Sun, W. Future- dependent value-based off off-policy evaluation pomdps. In Advances in Neural Information Processing Systems, volume 36, pp. 15991-16008. Curran Associates, Inc., 2023.
Yu, S., Fang. S., Peng, R., Qi, 7.,, Zhou, F., and Shi, C. Two-way deconfounder for off-policy evaluation in causal reinforeement learning. Advances in Neural Information 2024.
Processing Systems,
Van Der Vaart, A. W., Wellner, J. A., van der Vaart, A. W., and Wellner, A. Weak convergence. Springer, 1996.
Zhang, B., Tsiatis, A. A., Laber, E. B., and Davidian, M. A robust method for estimating optimal treatment
13

---

Demystifying the Paradox of IS with an Estimated History-Depeneee Behavior Policy in OPE
regimes. Biometrics, 68(4):1000-1018, 05 2012. ISSN 0006-341X.
Zhang, B., Tsiatis, A. A., Laber, E. B., and Davidian, M. Robust estimation of optimal dynamic treatment regimes for sequential treatment decisions. Biometrika, 100(3): 681-694, 2013.
Zhao, X. and Zhang, Asymptotic normality of nonpara- metric m-estimators with applications to hypothesis test- ing for panel count data. Statistica Sinica, 27:931-950, 2017. URL https: /tatps://pp... semanticscholarr org/ CrggCoorpsID::00 54836455.
Zhao, Y.QQ., Zeng, D., Laber, E. B., and Kosorok, M. R. New statistical learning methods for estimating optimal dynamic treatment regimes. Journal of the American Statistical Association, 110(510):583-995 2015.
Zhou, W., Li, Y., Zhu, R., and Qu, A. Distributional shift- aware off- aff-pooliy interval estimation: A unified error quan- tification framework. arXiv preprint arXiv:2309.13277 2023.
Zhu, J., Wan, R., Qi, Z., Luo, S., and Shi, C. Robust offline reinforcement learning with heavy-tailed rewards. In International Conference on Artificial Intelligence and Statistics, pp. 541-549. PMLR, 2024.
14

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
A. Details of experiments
Bandit example Section 3.1. our illustrative example, we set the context space = {0, 1}, the action space A {0, 1}. The target policy TT set as
Te (1) PP 0.4,
T.(0) P. (A A =0) 0.6.
The behavior policy is set as
mb (1)) = (A = = 0.3,
(0) = (4 = 0) = 0.7.
Both the target and behavior policies are independent of context information. The context information S follows a Bernoulli distribution with parameter 0.5, that is,
P(S 0) P(S = 1) = 0.5.
Given context information S and action A, the reward random variable with mean 10a + 0.1 + 2s). Therefore, the reward function is deterministic function defined
a(s 10a + 0.1 2s).
For the illustrative example, we can derive the closed-form expression of the policy's value, which is 4.2.
Numerical experiments in Section 6. In Cartpole environment, the state space S is subset of R For any E S, is characterized by four elements (x, It. 0, 6), where x, i are the position and velocity of the cart, 0, 0 are the angle and angle velocity of the pole with the vertical axis. The behavior policy and the target policy are set as
To (a|s) ~ Bernoull((p6), where ps = 1/ (1 + exp (100))
Te (als) ~ Bernoulli(pe), where Pe = 1/ + (20)))0))
Given = (xx, it, 0, 0,0), the reward is defined as R = (2 2 m//maa)(2 00000005 0/0max) 1. The maximum episode length is set as 200. We use logistic regression model to estimate the behavior policy. The state transition model is set as the physical system implemented in CartPole environment the gym library. And the initial state are uniformly drawn from [-0.05, 0.05]4.
We Monte Carlo (MC) procedure approximate the true value of target policy. Specifically, run the deploy the target policy to the simulator and get a empirical cumulative reward MC. The procedure is repeated times, and the MC estimator is given by
(!)
UMC
T.
MC
In our experiments, we set 10 and the value of GMC is 92.91.
B. Additional experiment results
In this section, we examine the impact of using distory-dependen behavior policies in the OIS estimator across three MuJoCo environments: (i) Inverted Pendulum; (ii) Double Inverted Pendulum and (iii) Swimmer.
For both Inverted Pendulum and Double Inverted Pendulum, the behavior policy is modeled using a transformed Beta distribution. Specifically, we set the action to 2Z 1, where Z Beta(2 SB, 2 S0) and parameter 0 estimated by maximizing the lieeliill.o
ei = (1, 01.,,....0 .,..). The
In Swimmer, the action is two-dimensional, i.c., A (Ai, A2), and sample each component independently given the state: A Be 2 20) and A₂ ~ Deta(2+-S6, 22502), with 0 e1 = (1, 0.... 0) and 02 = = (0. .., 0).
The results, summarized in Figure 3, demonstrate that using history-ddeeedent behavior policy estimation generally reduces the MSE of OIS in large-sample settings. Moreover, the performance tends to improve with longer history lengths.
We further evaluate the use of history-dependen behavior policies in the SIS, DR, and MIS estimators within the more complex Swimmer environment. Results, presented in Figure again aligns with theory.
15

---

Demystifying the Paradox of IS with an Estimated History-Dependerr Behavior Policy in OPE
History Length
[Bies]
Log Ver
MSE
0.20
0.20
0.15
0.15
0.15
0.10
0.05
0.00
0.00
0.00
Double bord Persduuuum
15-
15
0.4
10
0.3
0.1
0.12
0.60
0.60
0.55
0.55
0.50
0.45
0.40
0.40
500
1000
2060
4000
8000
sóo
1600
8000
0.35
500
1000
2000
addo
8000
Sample Size
Figure Bias, log variance and log MSE for OIS estimators
three different enviromments
History Length
[Bias]
Log Var
MSE
-0.5
-1.0
-100
1.0
-1.5
1.5
100
-2.0
2.0
-25
-1.0
+3.5
-16
-1.5
-2.0
-20
5004
-2.0
-2.4
-2.5
-288
520
1020
2000
4000
8000
500
4000
8000
520
1020
2000
4000
8000
Sample Size
Figure 4. Bias, log variance and log MSE for OIS and MIS estimators in Swimmer environment
16

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
C. Proofs
C.1. Proof of Lemma 1
According to the definitions of o and 018
follows from straightforward calculations that
[e(A)
En Σ [a(a))(a)+
is
and
+ Tee (A)
CCD is
En Σ Te (a)
[ - F(S, A)1
Th (AIS)
According to Neyman orthogonality, both the estimated reward and estimated behavior policy can be asymptotically replaced by its oracle value without changing the OPE estimator's 's asymptotic MSE (Chernozhukov et al., 2018). As this part of the proof follows standard arguments, we provide only a sketch; interested readers may refer to, for example, the proof of Theorem in Kallus & Uehara (2020) for further details.
Specifically, 0is
can be decomposed into the following four terms:
Σ me(4)r(S,)) (A( R - r(S, (-SS
CD Is
En
(6)
(A(
(A(A)
+ En
Te(o]))[((ssa) -((,)a))))))(sa
Te
(A( [FSS, A) r(S.A)))
(7)
+
En
(A( (A)
[R ( A)]]
(8)
(A(A)))
(a(A)
[A(
(a(AA
En
(A(A) [F(S, 4) - A)).
(9)
(A
Here, the right-hand-side (RHS) of (6) is the oracle DR estimator with the true reward function and IS ratio, and (7) (9) the reminder terms, which we will show are of order (n In particular:
For fixed F and m.. (7) and (8) are of zero mean. They are of the order (n (1/2) provided that and ã. converge to their oracle values. Even when f and î. are estimated from the same data used in the evaluation, our use of tabular methods-combinee
with the fact that the number of contexts and actions is finite-ensures that these estimators belong to function classes with finite VC-dimension (Van Der Vaart et al., 1996). Therefore, standard empirical process theory (e.g., Chernozhukov et al., 2014, Corollary 5.1) can be applied to establish that these terms are indeed (n (111))).
For fixed F and Te. (9) is of the order || | r|| x || Tall where ||--r|| and || [ -Tll denote the root MSEs (RMSEs) between F(S, A) and r(S, A). and between (A(S) and (A). respectively. Crucially, the order is the product of the two RMSEs. Consequently, as they decay to zero at a rate of on (n/4) which is much slower than the parametric rate (n (1/))- this term becomes o, 1/2) as well. Again, under tabular estimation with finitely many contexts and actions, these estimators converge the parametric rate, and empirical process theories can be similarly used to handle the dependence between the estimators and the evaluation data in (9).
CD is asymptotically equivalent to the oracle DR estimator (which is unbiased). Consequently, they achieve the Therefore, Is same asymptotic variance and MSE, and we have
me(A)
MSE A
MSRA
En
Σ ne (a(a(((S
RR r(s, A)]
Tb(A)
Te(a)r(S,a) + (A(
]
Vara
En
[ -r((,
(A(A)
1 Var Σ
[A( (b(A)
(T)
R r(S. A1]
n
17

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
which is equal to
Var Σ (Exc()r(s,o))
Var (=((A) (T(A)
[R (
Similar argument yields that
MSEA (CCA)
Var
[T((A) (T(
[R E(RIAA))
Then the first inequality follows from the fact that
Var
Te (A) (A(
R2 - B([[AA])
Var
(A)
IR r(S. + Var
[e(A) (T( (r(S, A) -B(R]A))).
(A)
and that
Tee (A) (A)
To (A)
(r A) E(R]A]]S)] Var (Em(or((saa)
Var
(S) -E(A)) 2 Var
E
(A)
The equality holds if and only if Var of the reward function r.
(a(A) Tb(d)
[r A) - [[(]A))]| 0. which implies that the context S is independent
We next prove the second inequality. Since ets is unbiased, the second inequality follows from the fact that
(A)
(
= Var
R.
(A)
(A)
(T( [R (R-E(R(A)) + Var (T((A)
B(RIA))
Var
(A(A)
MSE (DTSA) + Var (T((A) E(R(A)) Z (SEA((((A)
TT(A)
The equality holds if and only if E(R]A) 0 almost surely.
C.2. Proof of Theorems Section
Details of Assumption 1. We assume that the policy class parametrized by a vector 0 = (0o,... (0o...,,0)), 0z). For any ue II and E (O....... k). the state-action pair St-;, A. affects 9 only through their interactions with 0.. In this way, we set 0, ... 0₂ 0, then my becomes Markov policy. Moreover, for any K'' k. if we fix 0.+1 policy class 11g degenerates to ll..
Oz 0, then the
Notations. Given single trajectory H = (so, do To.... ST, ar. ,T), let He-ka denote the trajectory segment (8t-k, O kc-kk.... the likelihood function trajectory H under policy no(-l.) is given by
T
P(H,0) 0)
II
To H (prx)))( a))p($4411s4 at).
Further define p(H, ne) be the likelihood function of trajectory H under policy ne- given as
p(H, Te)
II
nee (a, H, pop
1=0
The loglikelihood function is defined as L(H,0) = log H, 0) and the score function is defined
i
s H, k: 0)
log pl H,
log mo (uxl H.)
a0
30 1=0
18

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
In what follows, we write kH,,k as (H 0) to ease notation. Let Hr (Sy, "0.-..,86; ae) be the state-action trajectory up time & and s, (50: -..--.; 8t) be the trajectory up 8t- We further define
s(Ht,,))
log noe (ay)
00
5=0
T
((H,,,,0)
Σ
log (a, (
00
1=++
Proof of Theorem 2. For simplicity of notation, define
(e(a)(8))
p(H,, Te) p(H,0)
(H, Gr II
GT
Ta He-k::)
Direct calculation yields that
u 11 0) -u(H (((H,))(HH)))
(10)
00
and o0s 1. E.=1 u(H,, 8²), (kis(k) = Ei=1 ul (H, Bn). Using Taylor expansion at 0 = 8", we obtain
tois (k) -01s =
u (H,, (0, 0*) + (P,)
n2
d0
ulHt, 0*) (HH, ('(H:,0000 0', 0²) + Rni(On))
(11)
a
where the remainder can be represented
2 1 u(H H.H (O, -00) Σ s(H, s(H, (H,, 00 H. 8) (Ø, -7).
RA (H,
2n
Under the bounded rewards assumption (Assumption 3), have GT Rmax).). Under the coverage assumption (Assumption 4, we have u H, 0) OG(TCT Rmmx) and s(H,0) = O(e-l). Under the differentiability assumption 8 (Assumption 5), D0 s(H,0) = ((5-))s)))))))) Combining these facts, we obtain that the remainder term satisfies
R 1p==0p (TCH Rmax 100, 8712).
(12)
Using the property of maximum likelihood estimator (see e.g., Theorem 4.17 in Shao, 2003), have
Vn(O,, =-)==11((0
s s(H, +
(1H,0))+0pp0 Op(100 0" 12)
(13)
Further using the central limit theorem, VI/nT s( HH, 8*) converges to normal distribution with mean zero and variance T(0*), which is of order O(T). It follows that under the non-singularity assumption (Assumption 6), Combining equations (11), (12) and (13), we have
|10,, 8-1 Op VnT")
n
n s( 0", +0p
(k 11 Ruax nea
Vois
Vois
u(H, (")
==1
1
((k 1)C" Rmaxx Rmaxx ng?
Elu(H,
HH,, 8*) +0,
Rua. (14)
19

---

Demystifying the Paradox of IS with an Estimated History-Dependee Behavior Policy in OPE
where
a -111)00))))((( 1 (07) Σ s(11;,00)
Rn
n
n
72 j=1
Again, according to the central limit theorem, we have
0-) Ol = =Op ( (eTTRm-n-)
Therefore, we obtain Ra is also of order Op [k+1))c*
Ress ne²
Plug into equation (14), we obtain
1
Σ 8(H,,0" + +0p (I: ( 1)C Vn j=1
1
Roa
(k) Vos
(8))
n=²
where the predominant term on the right hand side is denoted V1. Using the fact that E[s(H, 8*)] we know that the predominant term has mean O. Meanwhile, since T(0*) (H T (H, ())), obtain
Var(vi) = Cov(vors, 21) EB/u(H, T (11 (1,,0)) Blu
( (0 ((HH,,0))
(15)
follows that Cov(vois - U1, U1) = 0. We define
(k)))= =
E RR.
as the tangent space spanned by score vector, and we define
T(k) = [w IE {u w) 0, Vu T (4:)
In fact, the whole space g² can be decomposed into T(k) + T(k)+. ir E T(k)+ is the orthogonal projection of v onto the tangent space spanned by the score vector and v v1 ((k)) the projection of vous the space of random vectors orthogonal to the score vector. Moreover, equation (15) indicates
Vois (k) Uirue
(+
Virue U1 + Rns,
(16)
with Rh3 -Op (L++1CCT
SAyCTRRan Ress ne?
Take variance on both sides, we obtain
Var(Fors(k))
Var(C v1) + Var(Rna) + 2Cov(0 v1, Rn3).
(17)
Using similar calculations, show that
Var(Pois 01) O C2T/n).
(k +1+1) 0llo
C2T R
Var (nn)))))
n2
By Cauchy- Seechy-Shhwrrz inequality, we have
Var(Ti u1) Rar(Rn))= =0 (1k 1) n2
Cov(To U1, Rlns)
n2/2g2
Since e is a constant, Var( (Ra)) is a higher order term compared to Cov Rus). Furthermore, since T is unbiased,
so
o (ks 1)C Rmax
o
ng²
20

---

Demystifying the Paradox of IS with an Estimated History-Dependers Behavior Policy in OPE
follows that Bias" (Fous (k)) is higher order compared Cov(T U1, Rns). Using bias-variance decomposition, obtain
(k + 1++1 RR
MSE((ois(())
Var(e 01) + Bias (Tois (k))) B + 0
3/2222
(1: + 11C2T R
Var (Projira)(Cob (P01s) +0
n2/2222
(k 1)C 102TTR R²
Projins)) (ATGT) +0
(18)
n//22g2
n
where ProjT(A) (+) represents the orthogonal projection of a random variable to the space T(k). This proves the first claim of Theorem 2.
We next show the second claim of Theorem In fact, for any < k, under the monotocity assumption (Assumption 1), the tangent space spanned by score vector for model I. strietly larger than that of Hg.. Therefore, we have T(k) T(+)+. follows that < T(K) S T() and the second claim of Theorem 2 directly follows from Pythagorean Theorem.
Proof of Theorem 4. The proof of Theorem 4 simply follows the proof of Theorem by taking Q(s, a) 0 and is thus omitted.
Proof of Theorem 6.
The likelihood of trajectory segment H, = (So, Ao, Ro...... St, Ar, Rτ) can be represented as:
t
Pa(Hs ) = II me (4) Ay) A₃).
It follows that the cumulative density ratio with respect to behavior policy wa can be represented
ne (A)1ss) j=1 To(A,[S)
Ps. (Hs. Po(Hs.41)
(+) II
Then the doubly robust estimator can be represented as
Pa. (Hsm
Pa. (H (Q(((S,,T))
(k) = E,
(R, (e((S,,A))
+ Pa. (Hs,)
Pa. (Hsm))
t=0
T
Pr. (Z
E, (So, Te) ) + En
(Re Qr A.) + 15::1:))
(19)
Pa. (Hs
1=0
with T.) = Sn (S, a (als) and the doubly robust estimator with oracle weight can be represented as
Ps. (H /Re Q.(S., +1Q42(411.1)
D = Qu Te) + E.
Po- (Hs441)
For notation simplicity, we denote
Pa. (HA,) 72 ( -0 (1
u( H S
Pro (HA.)
Then direct calculation yields that # as proving equation (11), (13).(13) and (14), Taylor expansion yields
20 ul Hs 0) u( Hs, 1: (),(H) 0). Under Assumption 3, 5, using similar argument
(k (k+1)TC*
ÜDR (R)
E,,,
u (Hs. (0 HA,)" T
(0n-0'+00
max
110,
0-
E²
T
(k (k+1)CCUU
= -nn
ul ((Hs )s(0', HA.
- (0' HT) + Op
n
(k 1 Umax
-EC
Σ
"H,,),,,,"" HsHH)))ss0 HA,)²
(00)Enn HT) + Op
ne²
1
21

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
Denote the main on the right hand side the last line by v2. Noted that
T
u S (H), 03) =
T
W H (') (HHr,, 071
E
E
u [ 0*) (sH,, + (HHT, 0*)) Hs
0
T
E
u H S,41 8*) (s(He, [ss(HH 0*) (8sti))
sHH 0¹) (s(H,, [s (HHT, 8 (S)(st))))
= E
u H (" 0y)s(HH,00))
k=0
where the second equality follows from total expectation formula, the fourth equality follows from the Markov property and the last equality follows from the fact that the score function vanishes at the true parameter. Thus, it follows from direct calculation that (ar = Co U2). Therefore, similar to the proof of Theorem 2, we know that 02 is the orthogonal projection of ohR onto the tangent space spanned by score function. Plugging into equation (20) and minus Vine on both sides yields
(kk +
D)CTUman
TDR (R) Urue
Ulue) 122 +Op (o
ne²
Using similar argument as proving equation (18) and combining the fact that ob is unbiased and Euy O, we obtain
Var(Projrca) (bbR) + +0 (Ks U2
MSE((DR(A)) (A))
(20)
n3/222
This finishes the first claim of Theorem 6. In order to prove Var(ProjT(H) (+b)) decreasing with respect to k we denote o² (k) Var(o Var(Projryи) (+)R)) then o² (k) Var(uz). follows that
o²(k)
1
u (S 0*)s (He, 6*) (HH,
1
u ('
72
1=
no. (Ay(S;) 7 (Uss((H,, 01) } (21)
1
Tee (A,1s))
EI Tee (Ag19))
(Us UU, 04)2
1 (00)E
To- (A,1S,) ==
n
with
U, = - Qc(e, Ad) + 12 (T).
We next prove that for any < k, the inequality o²()') - (k) holds. For = (fp..... 0x), define y = (fo..... 0x)
77 = (0.+1...., 0x) and 6* = (y","")) follows that s (H,, 0) = (s T (H,, (), s (He, 7)) for any t E {0, 1........ T). Therefore, we can conclude that
d²k)) -E ΣI (A,1)))
ΣI T. (A,1,))
To- (A,1S)) UH,(H
17))
Uis(Ho.7))
To- (A,1S))
Let 1(>") = E[s(H, 7)) (H, = E[s(H,
(H,,)²) T(H,,)))))))))) and /12 = B[s(H, 1])] then
T(0 = [T(7*)
T
IT/
I(n")
22

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
In order to calculate / (0"), ,, we apply the formula of the inversion of block matrix:
A B A-- - - C
D
- (D- -D-
(D (D-CA-IB)-
we obtain from equation (21) that
d2(bk)
(2(K) E
Σ u (Hs.. 18 1 (H)r,)))
1 177) 1
Σ
u (Hs (Hsnn)ssH)s77)
+E
a a(ts )s (HT,,
J J 111-11100"
ul ((H
+E
Σ u(Hs (HTT,T))))
1 (7
ul I )s(HT,))))
T
-E
u(Hs..)) (HI,nn')
J J'E E
u (HS.,))) (sH)))))))))))
1=0
T
=o E.
J J-1/2172 17
Σ
u H S (HH,, J 1/2
7 Σ
u (H (sHH,,))))
t=
1=
with J [(n") - T/2--1 (xx" 112- Thus, we obtain (k) 2 (k') for any K' < k. To this end, finishes the proof of Var (Pro)oo);;:)) (R)) ) is decreasing with respect to
Proof of Corollary 7.
We directly calculate (1) in equation (21).
Te (A,15;)
(2k) = E
"U,s(0", H.)
(Az1S;)
j=0
Te Te (A,1s,)
7" U,s(0' HD) 11)111 Ho
E
(Aj(S;)
Te Te(A (Ag1S;)
E
s(0", H.) E [Ui]S,, A.]
To- (A₃ S5,)
0.
(22)
where the last equality follows from Bellman equation, which indicates E UU, Sc Ar] = 0. Together with equation (21) completed the proof.
Proof of Theorem 8.
We first prove that the MIS estimators with weight function estimated by linear sieves is equivalent to the double reinforce- ment learning (DRL) estimator (Kallus & Uehara, 2020) with Q-function estimated by linear sieve, that is
.DRI. E,, Σ Wh R. - (S. + ...1 [ }.
where Q. = OT (A,, 3.) and 3, is iteratively defined as 3, = Ex (E,, + +E44),3341)
For ease of notation, we define
Q((S, = Σ (())
(.(S
Σ (c())))
23

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
Recall that i6 0c(1,, Az) By direct calculation, we have
E, のz (2 moo]
E, En (6.
(S,, 1 11.-
En Th Qr Ai)]
En {or V1 (S,, 3 }.}
En {2, -,,'2,,-1 _ v1 }
- B..
(23)
where the second to last equality obtained by the recursive definition of or. follows that 1 Te) = E, (S,, A,). Plugging into equation (23), we know that the MIS estimator is equivalent to DRL estimator.
Now, suppose the estimated weight Q-function converges to true value, then if we replace ((S,, A.) by ( the resulting estimator will have larger variance. Additionally, if the weight is estimated using all the history data, then iMIs becomes the doubly robust ÜDR estimator. The following theorem formalizes this result, indicating that for DRL estimator, the variance increases more history used estimate the weights:
We (H) (RL-Q((),A)). @ / ((
MMIS (A:) E,,
Σ t=0
We further assume that ||0; - well = 1n- and |1 - Q (n where i1 - well and ||¹: - Qell denote the root MSEs (RMSEs) between Wi (H+) and wi Ht)) and hetween Q A) and Q, A), According to Neyman orthogonality, both the estimated reward and estimated behavior policy can be asymptotically replaced by its oracle value (Chernozhukov et al., 2018) without changing the OPE estimator's asymptotic MSE (see also equations (6) (9) for detailed explanation).
Therefore, obtain that
MIIS (k) En
Σ t=0
we(Bs (.)), + (I.,)((( m) + top(n 11/3). 1/2).
After rearranging the predominant term, we obtain that Txus (A) is asymptotically equals to
(k) E, Qu Te) + E, Σ ( - -
+ Q441
the Q function is correctly specified, then
E [wx (Ar- kst, St ke) (Re Qr,S, A,) (S+1, (1 kits A
wr(Ar- k: S [Rg Qr A,) + Q1+1(S Te) St Ai-
0.
(24)
Denote U, = R₁ (S, Ar) + (S+4)). Then for any t'
Cov (wie (1tuuaAA-ttt... St-ke Ue, We (Ar -tr- Uvv
E [[We((A 14) - Se-ket) Uv SS- ke Ai-kee]
(At S. wr (Av-ww St U |E(Uu|| S Ar-
(25)
24

---

Demystifying the Paradox of IS with an Estimated History-Dependeee Behavior Policy in OPE
follows that,
T
Vara (TMIS
Var Po(So: mo) +
we
Var(Qo(So, +
Var (wx ( (Ae- St-
==
Var(QQ(So, Re)) +
Σ
Var
(Us) Ae Ae-kies Se-k:a))
n
Ww (Ar-kit St kit) Var (Ue|Ac-Rtt St-k:e))
T E [w (t
= Var(Qo Re)) +
(26)
where S.) Var(U,]AA/-sr: St- knt) Therefore, for any ke < ki
E (wf (Ai-wit Se (Ar, St)) St E (B(ur( (
:t)l) 2 Si)
S E Eiw? (Ai S. Axd A St o (A,, S:)}
E (w] (AL- St (A S,))
(27)
where the first equality is based the fact that w A Si-kaa) E [B[A St-ka]] Ar-wa, S = B[ St-ka) A A -t S.-kal and the second equality is based on Jensen's 's inequality. Thus, combining equations (26) and (27), we obtain that V (FrM(()(( s Vara (Trx(((s((k))
B[Aa k Se-
C.3. Assumptions and proof of Theorem 9
Regularity conditions for Theorem 9.
We first introduce regularity conditions for Theorem 9. Suppose θ is the parametric space equipped with norm || (@ is not necessarily finite-dimensional) Denote H. be the set of all possible trajectories and 0o be the true prameter. For trajectory H, let L(H,8 8) be the log likelihood function. let sH, [-] be the Fréchet derivative of L(H, 8) with respect to 8. For any h E O, s(H, 0) []] defined by
8 (H ()[0
L(H, 0 nh)
Om
17=0
Let IP be the probability measure of H induced by behavior policy Te, and IP, be the corresponding empirical probability measure. We impose the following regularity conditions.
Assumption 8. For any 0 in neighbourhood of 0g. IP (Ps(H, 0) s H, 0o) = O(100 - -uul)- Assumption 9. For any 0 E θ, there exists a corresponding Oon in the sieve space O,,, such that |10 - 10-0on|l = o(n -1/4). Assumption 10. On is a consistent estimator of 0 with |00, 0oll (1(441/4)
Assumption 11. For some 0, the function class F, = (HHH, class.
H 0) s(H, 0)) : ||0 Poll < 5, E H} is P-Donsker
Assumption 12. ((H,0)(M is Fréchet differentiable at the true parameter 0g with a continuous derivative 1 which satisfies
IP { ((HH,0))(4) 0.)]4]] s( 0b) s (0. - 00, Al] op(n 1112). 1/2).
Assumption 13. There exists a least favorable direction go O such that for any h E O
{((cr
Gr p(H, TT) p(H, 0o)
*(H, ((H, (ool s(H, = 0.
25

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
We make some remarks these assumptions. Assumptions 9 and 10 impose restrictions on the sieve space, requiring the sieve space well approximate the parameter space. Such conditions hold for sieve space including B-spline and deep neural network. Assumptions 11 and 12 are commonly required in semi-parametric literature (Zhao & Zhang, 2017), restricting the complexity of function class around the true parameter. Assumption 13 indicates that there exists a projection of x (p (H =e)/p(H H, fo) on the tangent space spanned by vector s(H,00) [-) This condition naturally holds when the parameter space is finite dimensional or the tangent space a closed subspace.
Proof of Theorem 9.
We first show that for any h E O,
(T - (){ 0m) - (0H] = or(().
(ii P ((s(H on(n 1/3))11/...00 IP (m)Hl op(nn 1/2).
For part (i), noted that P { (s(H, [m] - s(H,, (b)l)) IP (o,, 00)} o(1). Combining Assumption 11, the conclusion directly follows from Lemma 13.3 of Kosorok (2008). For part (ii), since sHH 0) is the Fréchet derivative of log likelihood, it follows that IP {s(H, 0o) = 0 = 01/2). Meanwhile, Assumption 9 indicates that there exists E On such that d(h, h)) = onn -144). Since On maximize P, 9) in O,, follows that P., { { (H, 0 = Therefore, P., { (H, [m]] = Pn (H, - sH, [m) which can be further decomposed into three parts;
Pn 0.)l1
(P,, P) (s sH,, 80) [M] (P,, (P)- (Pn- 0..) s(H, Bu)) s(H,6o)) [7]
PP {sHH. 00][k] ,(H, 00)
-P { (s(H, (6 8m)) sHH. 90) [b) - (s 0..) - s(H,
J1 J2 + J3-
For J1, follow a similar argument as proving claim (i), we obtain J1 = op(n 0 For J2, (V(r.222 = O(d(h,h)') o11), which indicates J/2 = Op(n (nn1/n1)))) 1/2). For J3, direct calculation yields
E E|Jal X d(Oo, (n) h) onn
Therefore, P,, s (H, J1 + J2 + J3 = or(m-112)
Combining claim (i)) and Assumption 12, obtain
P. (bHH)0)(())
(P,, - (HH())))))) (0888)))-HHHHH) ((H, - PP, (o(H, +P -pfs((H 0m) - s(H,
( 0.)
= P $00 10, 80 10 + tor(n 1/22).
(28)
Take h 0, - 00 in (28) yields
E GT p(H, Te)
8 s11, 10) 0ol
-E{s(H, (on)s 0o) 0o]3
0()
E 10, P 9oo}
Pa. (s(H,, 0o)[9u1} or 11/2).
(29)
26

---

Demystifying the Paradox of IS with an Estimated History-Dependent Behavior Policy in OPE
Then, according the Taylor expansion Oy. obtain
me) (H),,0)]6,, -bol + Op(10,, Boll ;(H);00)
(k) - S/s
Σ j=1
G
p H,, me)
GI
p 0o) s(H, (o), [bu] } + opp(n-1/2)
= Pn {s H, (o) + or(n 1/2),
where the second equality holds because of Assumption 10.
Denote the main term on the right hand side be 0z. Then by Assumption 13, we have Cov(uis: 03) By the central limit theorem, Var(uls) and Pn, {s(H, [ga]} are of order O And thus, we have:
a (A:) Var, (%) V & Var (%)1s)
which completes the first inequality in Theorem 9.
Follow very similar argument in proving Var ( S Var (Pois) we can easily prove that Var (Ts)s())) S Var A (C)1s) and Var (UDR (k:) - Var (xDb). and hence, we omit the details of proof.
27


Reviews:
[{"review_id": "cEGAT0gf1Y", "reviewer": "Reviewer_qCNN", "summary": "The paper investigates the bias-variance trade-off and the MSE in IS-based off-policy evaluation. A first part of the paper investigates bandits and shows that context-conditioning and visitation-count based approximation of the behavior policy can reduce the MSE (even though the policy is context-independent). They then evaluate different estimators for RL policies with their estimated non-Markovian behavior policy, and show this leads to reduced variance compared to non-Markovian behavior policy (longer history length leading to lower variance but exponentially growing bias) and improved asymptotic MSE. They show this principle works across different base-estimators, including OIS, Sequential IS, Doubly Robust and MIS estimators.\n\n# update after rebuttal\n\nThe authors have clarified some concepts and done additional experiments. Therefore I keep my score of accept (4).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your excellent comments and positive assessment of our paper. We will include these references, use the extra page to expand the related work and address all minor comments. In the following, we focus on clarifying your questions. \n\n**Neyman Orthogonality**. This property enables us to establish the asymptotic equivalence between an OPE estimator that uses estimated reward and behavior policy, and the one that employs their oracle values. Specifically, the difference between the two estimators can be decomposed into the following three terms:\n\n$$\\mathbb{E}_n\\Big( \\sum_a \\pi_e(a|S)[\\widehat{r}(S,a)-r(S,a)]- \\frac{\\pi_e(A|S)}{\\pi_b(A|S)}[\\widehat{r}(S,A)-r(S,A)] \\Big)+\\mathbb{E}\\_n\\Big[ \\Big(\\frac{\\pi\\_e(S,A)}{\\widehat{\\pi}_b(S,A)} - \\frac{\\pi_e(S,A)}{\\pi_b(S,A)}\\Big)[R- r(S,A)] \\Big]+\\mathbb{E}_n \\Big(\\frac{\\pi\\_e(S,A)}{\\widehat{\\pi}_b(S,A)} - \\frac{\\pi_e(S,A)}{\\pi_b(S,A)}\\Big)[\\widehat{r}(S,A)-r(S,A)] ,$$\n\nwhere $\\widehat{r}$ and $\\widehat{\\pi}_b$ denote the estimated reward and behavior policy, respectively. For the moment, let us assume these estimators are computed based on some external dataset. Then:\n\n* The first two terms are of zero mean. They are of the order $o_p(n^{-1/2})$ provided that $\\widehat{r}$ and $\\widehat{\\pi}_b$ converge to their oracle values.\n* The last term is of the order $\\|\\|\\widehat{r}-r\\|\\| \\times \\|\\|\\widehat{b}-b\\|\\|$ where $\\|\\|\\widehat{r}-r\\|\\|$ and $\\|\\|\\widehat{b}-b\\|\\|$ denote the root MSEs (RMSEs) between $\\widehat{r}(S,A)$ and $r(S,A)$, and between $\\widehat{b}(S,A)$ and $b(S,A)$, respectively. Crucially, the order is the product of the two RMSEs. Consequently, as they decay to zero at a rate of $o_p(n^{-1/4})$ -- which is much slower than the parametric rate $O_p(n^{-1/2})$ -- this term becomes $o_p(n^{-1/2})$ as well.  \n\nConsequently, the difference is $o_p(n^{-1/2})$, which establishes the asymptotic equivalence between the two estimators.\n\nWhen $\\widehat{r}$ and $\\widehat{\\pi}_b$ are estimated from the same dataset, the orders of the three terms additionally depend on the VC indices measuring the complexity of the reward and behavior policy models. Returning to our bandit example, we employ tabular methods to estimate both nuisance functions. Given the finite state and action spaces, their VC dimensions are finite as well. Additionally, both RMSEs achieve the parametric convergence rate $O_p(n^{-1/2})$. This validates our claim. \n\n**History-dependent behavior policy & history-dependent IS ratios**. Our opinion is that (i) reducing the time horizon in the IS ratio and (ii) increasing the history length in the estimation of the behavior policy are two generally different approaches to improving OPE performance, although these methods are related when considering MIS (which we will discuss in detail later). Specifically: \n\n* Approach (i) is more aggressive (in certain cases), aiming to reduce the **order** of the variance and address the curse of horizon by using shorter-history IS ratios. For example, the incremental IS (IIS) estimator you mentioned uses a fixed history length $k$. A small $k$ can reduce the estimator's variance from exponential in $T$ to polynomial ($O(T^k)$). Conceptually, this shifts the original per-decision IS (PDIS) estimator toward the MIS estimator, with IIS representing an intermediate point between PDIS and MIS. However, this comes at the cost of increased bias due to the ignored long-term dependencies. \n* Approach (ii) is more conservative, targeting the **magnitude** (rather than order) of the variance by incorporating longer history in behavior policy estimation. As our theory shows, the variance preserves the same order (and thus the curse of horizon remains). According to our bandit example, this approach effectively converts a standard IS into a DR. In contrast to approach (i), it introduces minimal bias, as proven in our theory.\n\nWe also remark that these approaches can be combined to doubly reduce IS estimator's variance. First, one may specify a history length k for the IS ratio to obtain the IIS estimator. Next, the IIS ratio can be estimated using history-dependent behavior policy estimation to further reduce the variance magnitude.\n\nHowever, the two approaches do interact when it comes to MIS, which incorporates the IS ratio of both the state and action, rather than actions alone. Consequently, using history-dependent behavior policy estimates ratios over complete histories rather than individual states alone, which becomes equivalent to employing history-dependent IS ratios.\n\nDuring the rebuttal, we have created a [figure](https://www.dropbox.com/scl/fi/pl5j53c60z7im0inbkj9j/ISRelation.jpg?rlkey=gydxh3bpo3hew8h7zuhg4kzox&st=htnlbaix&dl=0) to visualize their interactions. Specifically, applying history-dependent behavior policy estimation to MIS can yield IIS (when ignoring state ratios beyond k steps), OIS, or PDIS. To the contrary, reducing the history-dependence in IS ratios converts OIS to PDIS and PDIS to IIS", "claims_and_evidence": "The authors provide proof for all their claims, although some more background can be discussed for the reader to appreciate these.", "methods_and_evaluation_criteria": "The authors design a technique which is applicable to a wide variety of estimators and clearly demonstrate its benefit in reducing the MSE in the asymptotic case while also discussing limitations, e.g. the finite sample bias.", "theoretical_claims": "The theoretical claims are backed up by extensive, well-presented proofs. I unfortunately, could not check them all. The theorems are additionally confirmed in the experiments.", "experimental_designs_or_analyses": "The analysis uses a cartpole domain. to verify the bias and the MSE. The results are in line with the theoretical claims.\n\nThe implementations of the algorithms in the theory and especially the experiments could be more clearly described with additional details and more specific references. For instance, the implementation of the base-algorithms, any specific hyperparameters, and the details of the non-Markovian behavior policy estimation.", "relation_to_broader_scientific_literature": "The work seems to be closely related, but complementary to, other techniques for variance reduction in OPE, such as per-decision IS, weighted IS, incremental IS, conditional IS, and state-based IS. The difference to these techniques is that here the estimator's variance reduction is based on using an estimated non-Markovian behavior policy. It seems related to Sequential IS methods (e.g. PDIS and INCRIS), depending on the time window used, when combined with OIS as the backbone, but this relation is not expanded on in the text. However, the authors do show that their algorithm applied to MIS can make it comparable to SIS for $k=T$.", "essential_references_not_discussed": "In general, there are not that many references from recent years, e.g. in the sequential IS and doubly robust techniques. The paper also does not expand much on the relation to these techniques. While the technique is a plugin for a variety of estimators, it does make sense to discuss the relation to these other works. In particular, a more in depth discussion of the related techniques would clarify the contribution.\nConditional IS [1] conditions on random variables in the trajectory. Techniques which modify the importance ratio are even more directly related to your work, since modifying the behavior policy changes the importance ratio. In this category, it makes sense to discuss State-based IS [2], which is similar in spirit that it is a plugin that can be applied to (the same) variety of estimator classes (OIS, Sequential IS, MIS, DR). It modifies the ratio based on whether the states in the history contribute to the return or not. Similarly, the already included PDIS and INCRIS references can be discussed in more depth, as I would argue in some cases these are equivalent to your technique (see questions for authors).\n\n[1]  Rowland, M., Harutyunyan, A., Hasselt, H., Borsa, D., Schaul, T., Munos, R. & Dabney, W.. (2020). Conditional Importance Sampling for Off-Policy Learning. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS 2020) 108:45-55.\n\n[2] Bossens, D.M., & Thomas, P.S. (2024). Low Variance Off-policy Evaluation with State-based Importance Sampling. IEEE Conference on Artificial Intelligence (CAI 2024), 871-883.", "other_strengths_and_weaknesses": "Strengths:\n\n- The problem setting is interesting\n\n- The paper is rigorous and well-presented \n\n- The objectives are clear\n\n- The theoretical and empirical results align \n\nWeaknesses:\n\n- In some cases, a bit more background of the techniques may need to be provided for a general audience.  \n\n- The related works discussion could be expanded on, and maybe some more recent works could be included.", "other_comments_or_suggestions": "“The re-weighted returns are then averaged to produce an unbiased estimator of the target policy’s value.” This is not true for all IS based estimators. Perhaps you can stress it is ordinary importance sampling.\n\n$\\pi_e / \\pi_b \\leq C$ --> forget to mention for all $(s,a)$ ?\n\n I presume in Eq. 4, it should be $\\hat{v}_{\\text{SIS}}$.\n\nin discussion, “can increases” --> can increase", "questions_for_authors": "Appendix B.: “According to Neyman orthogonality, both the estimated reward and estimated behavior policy can be asymptotically replaced  by its oracle value (Chernozhukov et al., 2018) without changing the OPE estimator’s asymptotic MSE.” Can the authors provide explain this step? Is the Neyman orthogonality always valid?\n\nWhat is the relation between history dependent behavior policies and history-dependent importance ratios (sequential importance sampling)? I believe that your technique can be considered as a generalisation (or special case, depending how we look at it), of sequential importance sampling techniques. OIS has history length 1, incremental importance-sampling has history length k (for chosen k), and per-decision importance sampling has all past time steps until current time t as history. In your framework, the importance ratio is also history dependent. It will be interesting to see what the intuition is for the finding that a lower number of time steps of the ratio is beneficial for reducing the variance while a higher number of time steps in the behavior policy is beneficial for reducing the variance, and what is actually the key difference if any, between these two formulations. Is it fair to say that when applying a non-Markovian behavior policy to OIS, it is equivalent to per-decision importance sampling in case using all past time steps of the episode, and equivalent to incremental importance sampling when using past $k$ times steps of the episode? In short, a non-Markovian behavior policy and the importance ratio definition in sequential IS techniques seems highly related, and possibly interchangeable in the OIS case, but this relation is currently not exactly clear.\n\n\"Alternatively, the k-step history $H_{t−k:t}$ can be used\nto construct a history-dependent MIS ratio $wt (k) = E(λt |H_{t−k:t} , A_t )$ ..To appreciate why Theorem 8 holds, notice that by setting\nk to the horizon $T$ , $w_t(k)$ is reduced to the $λ_t$ , and the\nresulting estimator is reduced to SIS, which suffers from\nthe curse of horizon and is known to be less efficient than\nMIS.\" Following this and my above remark, perhaps a similar analysis can be done to derive the relation between the OIS/SIS variants with non-Markovian $\\pi_b$ and the sequential IS algorithms.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AqlIHiXW1w", "reviewer": "Reviewer_Hj4i", "summary": "The paper discusses a paradox in offline policy evaluation through importance sampling, where the performance of the target policy is estimated from a weighted average of the reward value by the ratio of the target policy and the behavioral policy. The paper suggests that the mean-squared error of the said estimator can be improved if the behavioral policy is estimated in a broader family of models. For example, if the true behavior probability is known, the paper suggests that people should replace it with the empirically estimated behavior probability. If the true behavior policy is context-independent, people should estimate it as if it were context-dependent. Finally, if the true behavior policy is Markovian, people should estimate it as if it were a higher-order Markovian function. The authors made an analogy to doubly robust estimator, though I could not fully understand the details.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback regarding the proof of Lemma 1. We acknowledge that its reliance on Neyman orthogonality may not be immediately familiar to general audience. Apart from this concept, the proof employs standard techniques, including basic calculus such as Taylor expansions. We highlight that our original proof is clear and mathematically sound. The reviewer’s concerns arise from the misunderstanding of these technical tools rather from any technical flaw in the proof itself. Having said that, we have provided an alternative proof without Neyman orthogonality below. \n\n**Proof of Lemma 1**. Define $n(a)$ as the number of times action $a$ is taken, $n(s,a)$ as the number $(s,a)$ pairs in the dataset, and $n(s)=\\sum_a n(s,a)$. We first prove the second inequality $\\textrm{MSE}_A(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}})\\le \\textrm{MSE}_A(\\widehat{v}\\_{\\text{IS}}^{\\dagger})$. For any estimator $\\widehat{v}$, it follows from the law of total variance that $$\\text{Var}(\\widehat{v})  = \\underbrace{\\mathbb{E}(\\text{Var}(\\widehat{v}| \\\\{n(a)\\\\}\\_{a} ))}\\_{I} + \\underbrace{\\text{Var}(\\mathbb{E}(\\widehat{v}|\\\\{n(a)\\\\}\\_{a} ))}\\_{II}.$$ In the following, we will show that: \n\n(i) **Term I**: The difference between $\\widehat{v}\\_{\\text{IS}}^{\\dagger}$ and $\\widehat{v}\\_{\\text{IS}}^{\\text{CA}}$ is negligible;\n\n(ii) **Term II**: $\\widehat{v}\\_{\\text{IS}}^{\\dagger}$ achieves a larger value than $\\widehat{v}\\_{\\text{IS}}^{\\text{CA}}$. \n\nCombining (i) and (ii) yields that $\\text{Var}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\dagger})\\ge  \\text{Var}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}})$. As both estimators are asymptotically unbiased, we obtain $\\text{MSE}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\dagger})\\ge \\text{MSE}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}})$.\n\nSpecifically, by direct calculation, $$\\mathbb{E}\\\\{\\text{Var}(\\widehat{v}\\_{\\text{IS}}^{\\dagger}|\\\\{n(a)\\\\}\\_a )\\\\}=\\mathbb{E}\\Big(\\frac{1}{n}\\sum_{a\\in\\mathcal{A}} \\frac{\\pi_e^2(a)}{\\pi_b^2(a)}\\frac{n(a)}{n}\\sigma_a^2\\Big),\\quad \\mathbb{E}\\\\{\\text{Var}(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}}|\\\\{n(a)\\\\}\\_{a} )\\\\} = \\mathbb{E}\\Big(\\frac{1}{n}\\sum_{a\\in\\mathcal{A}} \\frac{\\pi_e^2(a)}{(n(a)/n)^2}\\frac{n(a)}{n}\\sigma_a^2\\Big).$$\nAccording to the law of large numbers, $n(a)/n$ is to converge in probability to $\\pi_b(a)$. It follows that \n         $\\mathbb{E}\\{\\text{Var}(\\widehat{v}\\_{\\text{IS}}^{\\dagger}|\\\\{n(a)\\\\}\\_{a} )\\} - \\mathbb{E}\\{\\text{Var}(\\widehat{v}_{\\text{IS}}^{\\text{CA}}|\\\\{n(a)\\\\}\\_{a} )\\} = o(1/n)$. This proves (i). On the other hand, \n\n$$\\mathbb{E}(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}}|\\\\{n(a)\\\\}\\_{a}) = \\frac{1}{n}\\mathbb{E} \\Big(\\sum_{a\\in\\mathcal{A}} \\frac{\\pi_e(a)}{n(a)/n}\\cdot n(a)\\mathbb{E}[R|A=a] \\Big) = \\mathbb{E}\\Big(\\sum_{a\\in\\mathcal{A}} \\pi_e(a)\\mathbb{E}[R|A=a] \\Big)$$\nis independent of $n(a)$. Consequently, we have $\\text{Var}\\\\{\\mathbb{E}(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}}|\\\\{n(a)\\\\}\\_{a})\\\\}=0$. \n However, \n$$\\text{Var}\\Big(\\mathbb{E} \\\\{\\widehat{v}\\_{\\text{IS}}^{\\dagger}|\\\\{n(a)\\\\}\\_{a} \\\\}\\Big) = \\text{Var}\\left(\\frac{1}{n}\\sum_{a\\in\\mathcal{A}}\\frac{\\pi_e(a)}{\\pi_b(a)}n(a)\\mathbb{E}[R|A=a]\\right)$$\nis dependent of $n(a)$.  This verifies (ii). Meanwhile, notice that $\\text{MSE}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\dagger})\\ge \\text{MSE}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}})$ if and only if $ \\text{Var}\\\\{\\mathbb{E}(\\widehat{v}\\_{\\text{IS}}^{\\dagger}|\\\\{n(a)\\\\}_{a}) \\\\}=0$, which indicates that $\\mathbb{E}(R|A)=0$ almost surely. \n\nThe first inequality $\\textrm{MSE}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\text{CD}})\\le \\textrm{MSE}\\_A(\\widehat{v}\\_{\\text{IS}}^{\\text{CA}})$ can be similarly proven. Due to space constraints, we present only a proof sketch. Applying the law of total variance again, we obtain \n$$\\text{Var}(\\widehat{v})  = \\mathbb{E}(\\text{Var}(\\widehat{v}| \\\\{n(s,a)\\\\}\\_{s,a} )) + \\mathbb{E}(\\text{Var}(\\mathbb{E}(\\widehat{v}| \\\\{n(s,a)\\\\}\\_{s,a} ) | \\\\{n(a)\\\\}\\_{a} )) + \\text{Var}(\\mathbb{E}(\\widehat{v}|\\\\{n(a)\\\\}\\_{a} )).$$\nSimilarly, we can show that \n\n(i) The difference in the first term between the two estimators is asymptotically negligible. \n\n(ii) $\\widehat{v}\\_{\\text{IS}}^{\\text{CD}}$ achieves a smaller second term (zero), as its conditional expectation is independent of $\\\\{n(s,a)\\\\}\\_{s,a}$. \n\n(iii) The conditional expectations of both estimators are independent of $\\\\{n(a)\\\\}\\_{a}$, so the last term is zero for both estimators. \n\nConsequently, $\\widehat{v}\\_{\\text{IS}}^{\\text{CD}}$ achieves a smaller asymptotic variance, and equivalently, MSE.\n\n**Clipping effects**. Our theory is not about clipping making the estimation of the behavior policy desirable for OPE. We dedicated an entire section (Section 3) to build intuition. As can be seen in the first two equations on Page 4, estimating the behavior policy effectively transforms the original IS estimator into a doubly robust estimator, which is known to outperform standard IS estimators when the Q-/reward function is well-approximated. This explains the benefits of such an estimation.", "claims_and_evidence": "I am not convinced with the proofs. I cannot follow the proof of Lemma 1, let alone the rest of the paper.", "methods_and_evaluation_criteria": "The experiments are not clearly presented. The authors gave a numerical example in Section 3.1 with additional details in Appendix A, but they left out key details regarding the numerical values of the mean-squared errors of the estimator.", "theoretical_claims": "I cannot follow the proof of Lemma 1 in Appendix B.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "I did see papers suggesting that approximating the behavior policy offers empirical advantages over using the true behavior policy. However, I have always speculated that it has to do with clipping effects, where the estimated behavioral policies are regularized to prevent extreme values. The authors seem to have other intuitions that I am not familiar with.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I cannot follow Lemma 1 as the conclusions appear counter-intuitive. I would appreciate it if the authors could elaborate on the proof of Lemma 1. Can the authors prove it from first principles without using advanced methods like Neyman orthogonality?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bCnB7guxmH", "reviewer": "Reviewer_KUNq", "summary": "The paper provides a theoretical analysis of why estimating a history-dependent behavior policy in off-policy evaluation (OPE) can reduce mean squared error (MSE). The authors derive a bias-variance decomposition for OPE estimators and show that history-dependent behavior policy estimation reduces variance at the cost of increasing finite-sample bias. Theoretical results establish that the variance reduction is monotonic as history length increases, except for the Marginalized Importance Sampling (MIS) estimator, which worsens with more history. Empirical results on CartPole validate these theoretical findings.\n\n## update after rebuttal\nThe authors have addressed my concerns in the rebuttal. I appreciate the additional clarifications and intuitions provided. I no longer have major concerns with the submission and have updated my score accordingly.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Choice of History Length**  Excellent comment. We fully agree that optimal selection of history length is crucial for applying our theory to practice. In response, we have **developed a method during the rebuttal, supported by promising simulation results**. Our approach is motivated by the bias-variance trade-off revealed in our theory: while increasing history length reduces asymptotic variance for OIS/SIS/DR estimators, it might increase finite-sample bias. We therefore propose to select the history length that minimizes $h^* = \\arg\\min_h [2n\\widehat{\\text{Var}}(h) - h\\log(n)]$ where:\n- $\\widehat{\\text{Var}}(h)$ denotes variance estimator computed via the sampling variance formula or bootstrap; \n- $k\\log(n)$ is the BIC penalty (Schwarz, 1978) preventing selecting long history without substantial reduction of the variance.\n\n[Results](https://www.dropbox.com/scl/fi/02eppzq8qpjygt4cxmc28/SelectKBIC.png?rlkey=k30z87thebot3la7apnvsob11&st=wvta6lho&dl=0) show that in all cases, OIS estimators with our adaptively selected history achieve the lowest MSE compared to those using fixed history.\n\n**No novel insights from experiments**.  The primary aim of our paper is to provide a rigorous theoretical analysis of how history-dependent behavior policy estimation affects the bias and variance of OPE estimators. Our main contribution lies in establishing these theories, through the derived bias-variance trade-offs. Accordingly, our experiments are to empirically verify these theories rather than to derive new insights. Indeed, our experimental results align with the theory. \n\n**MuJoCo**. As suggested, we conducted simulations in MuJoCo Inverted Pendulum environment during rebuttal. [Results](https://www.dropbox.com/scl/fi/egiz1bjz3pztlqs5p1lzb/mujoco.jpg?rlkey=qrg7wjltut5tcpbhlurspligd&st=vmssm274&dl=0) again, align with our theory.\n\n**No new method**. First, as noted in the ICML 2025 Call for Papers, \"Theory of Machine Learning\" is a core research area -- in parallel to RL, deep learning, and optimization. Our paper falls within this category. \n\nSecond, while not introducing new method, our theoretical analysis offers useful guidelines to practitioners. Table 1 shows that history-dependent behavior policy estimation should be used with OIS, SIS, DR estimators with misspecified Q-function, but may be unnecessary for DR with correct Q-functions or MIS estimators. \n\nThird, we did develop a new method for history length selection during rebuttal and obtained promising empirical results (see our response #1). We are happy to use the extra page to present this method shall our paper be accepted. \n\n**Variance reduction effect in IS**. We respectfully clarify a potential misunderstanding regarding our theoretical contributions. While the benefits of **designing** optimal proposal distributions for IS (pre data collection) are indeed well-established (Liu & Zhang, 2014) and connected to the literature on optimal experimental design for policy learning (Agarwal et al., 2019) and policy evaluation (Hanna et al., 2017; Mukherjee, 2022; Li et al., 2023), our work addresses a different problem: the theoretical benefits of **estimating** such distributions (post data collection). In other words, we did not consider policy design, but study how history-dependent behavior policy estimation impacts OPE — a question only empirically explored (and solely for OIS estimators) in prior work (Hanna, 2019, 2021). To our knowledge, our analysis provides the first theoretical foundation for these empirical observations.\n\n**The lack of experimental details**. We would like to make some clarifications:\n\n* We detailed the DGP and the episode length in Appendix A.1. All data were generated by this  DGP **without additional sampling strategies**. \n* As for implementation, we mentioned the use of logistic regression for behavior policy estimation in Appendix A.1. To be more specific, we employed **scikit-learn’s LogisticRegression with all hyperparameters kept at their default values** (no custom tuning). \n* During rebuttal, we have created an [anonymous repository](https://www.dropbox.com/scl/fi/8hxbqti3t9yu1boeb7u7e/code.zip?rlkey=yq1adjgw84cmc20va59rsc1o1&st=5022v5pc&dl=0) containing all the code for implementation. \n\n**Essential reference**. While we are happy to include the paper by Liu and Zhang (2024), we respectfully disagree that it is an essential reference. This paper is about the **design** of behavior policies whereas we study **estimating** such policies. While the reviewer describes their behavior policy as \"non-parametrically estimated,\" we find no discussion of nonparametric estimation in this paper. \n\nRegarding nonparametric methods more broadly: while potentially relevant and worthwhile to cite, they are not central to our focus on history-dependent estimation. We included Kallus & Uehara (2020) who employed history-dependent behavior policy estimation to handle history-dependent target policies. Happy to include other references", "claims_and_evidence": "1. The paper claims that history-dependent behavior policy estimation leads to variance reduction in OPE estimators, which is well-supported by both theoretical derivations and empirical results.\n2. The claim that this variance reduction comes at the cost of increased finite-sample bias is also well-grounded, as the paper provides a bias-variance decomposition to justify this trade-off.\n3. However, the paper does not formally establish when the increased bias outweighs variance reduction, making it unclear how to choose an optimal history length in practical applications.", "methods_and_evaluation_criteria": "1. The paper does not introduce a new method or algorithm but instead provides an analytical perspective on existing estimators.\n2. The choice of CartPole as an evaluation environment is somewhat limited, as prior OPE work typically includes MuJoCo tasks to assess generalization.", "theoretical_claims": "1. The variance reduction property of history-dependent estimation is well-supported by the derived bias-variance decomposition.\n2. The paper introduces a projection-based interpretation, which is conceptually interesting but follows naturally from standard variance-reduction techniques.\n3. While the theoretical results explain when variance is reduced, they do not explicitly analyze how estimation errors in the learned behavior policy affect bia.", "experimental_designs_or_analyses": "1. The empirical results confirm the theoretical findings, showing that variance decreases and bias increases as history length grows.\n2. The lack of details on experimental setup makes reproducibility difficult—there is no appendix detailing implementation choices, hyperparameters, or sampling strategies.\n3. There are no novel insights provided in the experiment section.", "relation_to_broader_scientific_literature": "1. The paper builds on prior work in off-policy evaluation (OPE) and importance sampling, particularly extending prior bias-variance analysis in OPE settings.\n2. There is a line of research on non-parametric behavior policy estimation that has already been demonstrated to outperform parametric methods in various environments, yet this is not acknowledged.", "essential_references_not_discussed": "Liu and Zhang (2024) published at ICML studies offline-informed behavior policy selection and is directly related to this paper’s topic. This work is a representative of the various  non-parametric behavior policy estimation methods.", "other_strengths_and_weaknesses": "Strengths:\n1.The projection-based interpretation offers a useful mathematical lens on the variance reduction effect.\n\nWeaknesses:\n1. The paper does not introduce a new method, and the analysis itself is not particularly novel, as the variance reduction effect is well understood in the context of importance sampling.", "other_comments_or_suggestions": "1. The literature review should include non-parametric behavior policy estimation in a more structured way.\n2. A more detailed discussion on practical implications—such as guidance on choosing history length—would make the results more practical.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a theoretical analysis of history-dependent behavior policy estimation in off-policy evaluation (OPE), demonstrating that it reduces variance at the cost of increased finite-sample bias. The authors provide both theoretical derivations and empirical validation on CartPole. The rebuttal addressed reviewers' concerns, offering additional clarifications and intuitions that have helped resolve initial doubts. However, the paper still lacks practical guidance on selecting the optimal history length, and the experimental evaluation remains limited to CartPole, with insufficient details on implementation choices, making reproducibility difficult.

The theoretical contributions are sound but not entirely novel, as variance reduction via history-dependent behavior policies is well-established. Nonetheless, the paper is a valuable addition to the literature, offering clear insights into bias-variance trade-offs in OPE. While the paper could benefit from more detailed practical implications and a broader experimental evaluation, the rebuttal has alleviated major concerns. Therefore, I recommend acceptance.
Decision: Accept (poster)