SOPE: Spectrum of Off-Policy Estimators
Year: 2022

Abstract:
Many sequential decision making problems are high-stakes and require off-policy evaluation (OPE) of a new policy using historical data collected using some other policy. One of the most common OPE techniques that provides unbiased estimates is trajectory based importance sampling (IS). However, due to the high variance of trajectory IS estimates, importance sampling methods based on state-action visitation distributions (SIS) have recently been adopted. Unfortunately, while SIS often provides lower variance estimates for long horizons, estimating the stateaction distribution ratios can be challenging and lead to biased estimates. In this paper, we present a new perspective on this bias-variance trade-off and show the existence of a spectrum of estimators whose endpoints are SIS and IS. Additionally, we also establish a spectrum for doubly-robust and weighted version of these estimators. We provide empirical evidence that estimators in this spectrum can be used to trade-off between the bias and variance of IS and SIS and can achieve lower mean-squared error than both IS and SIS.

heading: 1 Introduction
text: Many sequential decision making problems, such as automated health-care, robotics, and online recommendations are high-stakes in terms of health, safety, or finance [Liao et al., 2020, Brown et al., 2020, Theocharous et al., 2020]. For such problems, collecting new data to evaluate the performance of a new decision rule, called an evaluation policy ⇡e, may be expensive or even dangerous if ⇡e results in undesired outcomes. Therefore, one of the most important challenges in such problems is the estimation of the performance J(⇡e) of the policy ⇡e before its deployment.
Many off-policy evaluation (OPE) methods enable estimation of J(⇡e) with historical data collected using an existing decision rule, called a behavior policy ⇡b. One popular OPE technique is trajectorybased importance sampling (IS) [Precup, 2000]. While this method is both non-parametric and provides unbiased estimates of J(⇡e), it suffers from the curse of horizon and can have variance exponential in the horizon length [Jiang and Li, 2016, Guo et al., 2017]. To mitigate this problem, recent methods use stationary distribution importance sampling (SIS) to adjust the stationary distribution of the Markov chain induced by the policies, instead of the individual trajectories [Liu et al., 2018, Gelada and Bellemare, 2019, Nachum and Dai, 2020]. This requires (parametric) estimation of the ratio between the stationary distribution induced by ⇡e and ⇡b. Unfortunately, estimating this ratio accurately can require unverifiably strong assumptions on the parameters [Jiang and Huang, 2020], and often requires solving non-trivial min-max saddle point optimization problems [Yang et al., 2020]. Consequently, if the parameterization is not rich enough, then it may not be possible to represent the distribution ratios accurately, and when using rich function approximators (such as neural networks) then the optimization procedure may get stuck in sub-optimal saddle points.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In practice, these challenges can introduce error when estimating the distribution ratio, potentially leading to arbitrarily biased estimates of J(⇡e), even when an infinite amount of data is available.
In this work, we present a new perspective on the bias-variance trade-off for OPE that bridges the unbiasedness of IS and the often lower variance of SIS. Particularly, we show that
• There exists a spectrum of OPE estimators whose end-points are IS and SIS, respectively. • Estimators in this spectrum can have lower mean-squared error than both IS and SIS. • This spectrum can also be established for doubly-robust and weighted version of IS and SIS.
In Sections 3 and 4 we show how trajectory-based and distribution-based methods can be combined. The core idea establishing the existence of this spectrum relies upon first splitting individual trajectories into two parts and then computing the probability of the first part using SIS and IS for the latter. In Section 5, we introduce weighted and doubly-robust extensions of the spectrum. Finally, in Section 6, we present empirical case studies to highlight the effectiveness of these new estimators.

heading: 2 Background
text: Notation: A Markov decision process (MDP) is a tuple (S,A, r, T, , d1), where S is the state set, A is the action set, r is the reward function, T is the transition function, is the discounting factor, and d1 is the initial state distribution. Although our results extend to the continuous setting, for simplicity of notation we assume that S and A are finite. A policy ⇡ is a distribution over A, conditioned on the state. Starting from initial state S1 ⇠ d1, policy ⇡ interacts with the environment iteratively by sampling action At at every time step t from ⇡(·|St). The environment then produces reward Rt with the expected value r(St, At), and transitions to the next state St+1 according to T (·|St, At). Let ⌧ := (S1, A1, R1, S2, ..., SL, AL, RL) be the sequence of random variables corresponding to a trajectory sampled from ⇡, where L is the horizon length. Let p⇡ denote the distribution of ⌧ under ⇡.
Problem Statement: The performance of any policy ⇡ is given by its value defined by the expected discounted sum of rewards J(⇡) := E⌧⇠p⇡ [ PL t=1
t 1Rt]. The infinite horizon setting can be obtained by letting L ! 1. In general, for any random variable, we use the superscript of i to denote the trajectory associated with it. The goal of the off-policy policy evaluation (OPE) problem is to estimate the performance J(⇡e) of an evaluation policy ⇡e using only a batch of historical trajectories D := {⌧ i}mi=1 collected from a different behavior policy ⇡b. This problem is challenging because J(⇡e) must be estimated using only observational, off-policy data from the deployment of a different behavior policy ⇡b. Additionally, this problem might not be feasible if the data collected using ⇡b is not informative about the outcomes possible under ⇡e. Therefore, to make the problem tractable, we make the following standard support assumption, which implies that any outcome possible under ⇡e also has non-zero probability of occurring under ⇡b.
Assumption 1. For all s 2 S and a 2 A, the ratio ⇡e(a|s)⇡b(a|s) < 1.
Trajectory-Based Importance Sampling: One of the earliest methods for estimating J(⇡e) is trajectory-based importance sampling. This method corrects the difference in distribution of ⇡b and ⇡e by re-weighting the trajectories from ⇡b in D by the probability ratio of the trajectory under ⇡e and ⇡b, i.e.
p⇡e (⌧) p⇡b (⌧)
= QL
t=1 ⇡e(At|St) ⇡b(At|St) . Let the single-step action likelihood ratio be denoted
⇢t := ⇡e(At|St) ⇡b(At|St) and the likelihood ratio from steps j to k be denoted ⇢j:k := Qk t=j ⇢t. The fulltrajectory importance sampling (IS) estimator and the per-decision importance sampling (PDIS) estimator [Precup, 2000] can then be defined as:
IS(D) := 1
m
mX
i=1
⇢i1:L
LX
t=1
t 1Rit, PDIS(D) := 1
m
mX
i=1
LX
t=1
t 1⇢i1:tR i t,
It was shown by Precup [2000] that under Assumption 1, IS(D) and PDIS(D) are unbiased estimators of J(⇡e). That is, J(⇡e) = E⌧⇠p⇡b [IS(⌧ )] = E⌧⇠⇡b [PDIS(⌧ )]. Unfortunately, however, both IS and PDIS directly depend on the product of importance ratios and thus can often suffer from exponentially high-variance in the horizon length L, known as the “curse of horizon” [Jiang and Li, 2016, Guo et al., 2017, Liu et al., 2018].
Distribution-Based Importance Sampling: To eliminate the dependency on trajectory length, recent works apply importance sampling over the state-action space rather than the trajectory space. For any policy ⇡, let d⇡t denote the induced state-action distribution at time step t, i.e. d⇡t (s, a) = p⇡(St = s,At = a). Let the average state-action distribution be d⇡(s, a) := ( PL
t=1 t 1d⇡t (s, a))/( PL t=1
t 1). This gives the likelihood of encountering (s, a) when following policy ⇡ and averaging over time with -discounting. Let (S,A) ⇠ d⇡ and (S,A) ⇠ d⇡t denote that (S,A) are sampled from d⇡ and d⇡t respectively. The performance of ⇡e can be expressed as,
J(⇡e) = E⌧⇠p⇡e
" LX
t=1
t 1Rt # = X
s,a
LX
t=1
t 1 d⇡et (s, a)r(s, a) =
LX
t=1
t 1 ! X
s,a
d⇡e(s, a)r(s, a)
(a) =
LX
t=1
t 1 ! X
s,a
d⇡b(s, a) d⇡e(s, a)
d⇡b(s, a) r(s, a) =
X
s,a
LX
t=1
t 1d⇡bt (s, a) d⇡e(s, a)
d⇡b(s, a) r(s, a),
= E⌧⇠p⇡b
" LX
t=1
t 1 d⇡e(St, At)
d⇡b(St, At) Rt
# ,
where (a) is possible due to Assumption 1. Using this observation, recent works have considered the following stationary-distribution importance sampling estimator [Liu et al., 2018, Yang et al., 2020, Jiang and Huang, 2020],
SIS(D) := 1
m
mX
i=1
LX
t=1
t 1w(Sit , A i t)R i t,
where w(s, a) := d ⇡e (s,a)
d⇡b (s,a) is the distribution correction ratio. Notice that SIS(⌧) marginalizes over the product of importance ratios ⇢1:t, and thus can help in mitigating variance’s dependence on horizon length for PDIS and IS estimators. When an unbiased estimate of w is available, then SIS(⌧ ) is also an unbiased estimator, i.e., E⌧⇠⇡b [SIS(⌧)] = J(⇡e). Unfortunately, such an estimate of w is often not available. For large-scale problems, parametric estimation w is required in practice and we replace the true density ratios w with an estimate ŵ. However, estimating w accurately may require both a non-verifiable strong assumption on the parametric function class, and global solution to a non-trivial min-max optimization problem [Jiang and Huang, 2020, Yang et al., 2020]. When these conditions are not met, SIS estimates can be arbitrarily biased, even when an infinite amount of data is available.

heading: 3 Combining Trajectory-Based and Density-Based Importance Sampling
text: Trajectory-based and distribution-based importance sampling methods are typically presented as alternative methods of applying importance sampling for off-policy evaluation. However, in this section we show that the choice of estimator is not binary, and these two styles of computing importance weights can actually be combined into a single importance sampling estimate. Furthermore, using this combination, in the next section, we will derive a spectrum of estimators that allows interpolation between the trajectory-based PDIS and distribution-based SIS, which will often allow us trade-off between the strengths and weaknesses of these methods.
Intuitively, trajectory-based and distribution-based importance sampling provide two different ways of correcting the distribution mismatch under the evaluation and behavior policies. Trajectory-based importance sampling corrects the distribution mismatch by examining how likely policies are to take the same sequence of actions and thus applies the action likelihood ratio as the correction term. Distribution-based importance sampling corrects the mismatch by how likely policies are to visit the same state and action pairs—while remaining agnostic to how they arrived—and applies the distribution ratio as the importance weight. However, using distribution ratio and action likelihood ratio correction terms are not mutually exclusive, and one can draw on both types of correction terms to derive combined estimators.
To build intuition for why likelihood ratios and distribution ratios can naturally be combined, we consider the two rooms domain shown in Figure 3. In this example, there are two policies ⇡b,⇡e
which have different strategies for navigating from the first room to the second room. Note that while the behavior of the two policies are very different in the left room, both policies must pass through the connecting door to get to the right room at some point in time. Conditioning on having passed through the connecting door at a point in time, all parts of the trajectory that occur in the right room are independent from what has occurred in the left room by the Markov property. Thus, when considering a reward Rt that occurs in the right room, it is natural to consider the probability of reaching the door and then the probability of the action sequence policy in the right room under each policy.
Now, we formalize this intuition and show how trajectory-based and density-based importance sampling can be combined in the same estimator. Given a trajectory ⌧ , we can consider (Sz, Az), the state and action at time z in the trajectory. By conditioning on (Sz, Az), trajectory ⌧ can be separated into two conditionally independent partial trajectories ⌧0:z and ⌧z+1,L by the Markov property. Since the segments of ⌧ before and after time z are conditionally independent, then ⇢1:z , the likelihood ratio for the trajectory before time z, is conditionally independent from ⇢z+1:L and from Rt for all t z. Formally, let (Sz, Az) ⇠ d⇡bz , then,
J(⇡e) = E⌧⇠p⇡b [PDIS(⌧ )] = E⌧⇠p⇡b
" LX
t=1
t 1⇢1:tRt
#
= E⌧⇠p⇡b
" zX
t=1
t 1⇢1:tRt # +E(Sz,Az)
⇠d⇡bz
" E⌧⇠p⇡b " LX
t=z+1
t 1⇢1:z⇢z+1:tRt Sz, Az
##
= E⌧⇠p⇡b
" zX
t=1
t 1⇢1:tRt # +E(Sz,Az)
⇠d⇡bz
" LX
t=z+1
t 1E⌧⇠p⇡b [⇢1:z|Sz, Az]E⌧⇠⇡b [⇢z+1:tRt|Sz, Az] #
(a) = E⌧⇠p⇡b
" zX
t=1
t 1⇢1:tRt # +E(Sz,Az)
⇠d⇡bz
" LX
t=z+1
t 1 d⇡ez (Sz, Az)
d⇡bz (Sz, Az) E⌧⇠p⇡b
h ⇢z+1:tRt Sz, Az i#
= E⌧⇠p⇡b
" zX
t=1
t 1⇢1:tRt + LX
t=z+1
t 1 d⇡ez (Sz, Az)
d⇡bz (Sz, Az) ⇢z+1:tRt
# . (1)
where (a) follows from the following Property 1, which states that the expected value of product likelihood ratios ⇢1:z conditioned on (Sz, Az) is equal to the time-dependent state-action distribution ratio for (Sz, Az). We provide a detailed proof of Property 1 in Appendix A. Property 1 ([Liu et al., 2018]). Under Assumption 1, E⌧⇠p⇡b [⇢1:t|St = s,At = a] = d⇡et (s,a)
d ⇡b t (s,a)
.
Observe that Eq (1) is indexed by time z. Intuitively, z can be thought of as the time to switch from using distribution ratios to action likelihood ratios in the importance weight. Specifically, the distribution ratios are used to estimate the probability of being in state Sz and taking action Az at time z and action likelihood ratios are used to correct for the probability of actions taken after time z. Further observe that z does not have to be a fixed constant—z(t) can be a function of t so that each reward in the trajectory Rt can utilize a different switching time. In the next section, we show that by using a function z(t) that allows the switching time to be time-dependent, we are able to further marginalize over time and create an estimator that interpolates between average state-action distribution ratios w(s, a) = d
⇡e (s,a) d⇡b (s,a) , rather than time-dependent distribution ratios d⇡et (s,a)
d ⇡b t (s,a)
.
d⇡b (St,At)
, (b) SOPEn combines trajectory and distribution
importance sampling weights by considering the probability of each policy visiting (St n, At n), the state-action pair n steps in the past, and additionally the probability of the sub-trajectory ⌧t n+1:t from n steps in the past to t. Thus, SOPEn re-weights Rt by d⇡e (St n,At n) d⇡b (St n,At n) ⇢t n+1:t.
4 Bias-Variance Trade-off using n-step Interpolation Between PDIS and SIS
We now build upon the ideas from Section 3 to derive a spectrum of off-policy estimators that allows for interpolation between the trajectory-based PDIS and distribution-based SIS estimators. This spectrum contains PDIS and SIS at the endpoints and allows for smooth interpolation between them to obtain new estimators that can often trade-off the strengths and weaknesses of PDIS and SIS. An illustration of the key idea can be found in Figure 2.
One simple way to perform this trade-off is to control the number of terms in the product in the action likelihood ratio for each reward Rt. Specifically, for any reward Rt, we propose including only the n most recent action likelihood ratios ⇢t n+1:t in the importance weight, rather than ⇢1:t. Thus, the overall importance weight becomes the re-weighted probability of visiting (St n, At n), followed by the re-weighted probability of taking the last n actions leading up to reward Rt. This reduces the exponential impact that horizon length L has on the variance of PDIS, and provides control over this reduction via the parameter n. To get an estimator to perform this trade-off, we start with the derivation in (1) with z(t) = t n, then accumulate the time-dependent state-action distributions dt over time. The final expression for the finite horizon setting requires some additional constructs and is thus presented along with its derivations and additional discussion in Appendix B. In the following we present the result for the infinite horizon setting.
J(⇡e) = E⌧⇠p⇡b
" nX
t=1
t 1⇢1:tRt + 1X
t=n+1
t 1 d⇡e(St n, At n)
d⇡b(St n, At n) ⇢t n+1:tRt
# . (2)
Using the sample estimate of (2), we obtain the Spectrum of Off-Policy Estimators (SOPEn),
SOPEn(D) = 1
m
mX
i=1
nX
t=1
t 1⇢i1:tR i t +
1X
t=n+1
t 1ŵ(Sit n, A i t n)⇢ i t n+1:tR i t
! .
Remark 1. Note that since we generally do not have access to the true density ratios, in practice we
substitute w with the estimated density ratios ŵ similarly as in SIS. Since SOPEn is agnostic to how ŵ is estimated, it can readily leverage existing and new methods for estimating ŵ.
Observe that SOPEn doesn’t just give a single estimator, but a spectrum of off-policy estimators indexed by n. An illustration of this spectrum can be seen in Figure 3. As n decreases, the number of terms in the action likelihood ratio decreases, and SOPEn depends more on the distribution correction ratio and is more like SIS. Likewise as n increases, the number of terms in the action likelihood ratio increases, and SOPEn is closer to PDIS. Further note that that for the endpoint values of this
spectrum, n = 0 and n = L, SOPEn gives the SIS and PDIS estimators exactly (for PDIS, horizon length needs to be L instead of 1 for the estimator to be well defined),
SOPE0(D) = 1
m
mX
i=1
LX
t=1
t 1w(Sit , A i t)R i t = SIS(D),
SOPEL(D) = 1
m
mX
i=1
LX
t=1
t 1⇢i1:tR i t = PDIS(D).
5 Doubly-Robust and Weighted IS Extensions to SOPEn
An additional advantage of SOPEn is that it can be readily extended to obtain a spectrum for other estimators. For instance, to mitigate variance further a popular technique is to leverage domain knowledge from (imperfect) models using doubly-robust estimators [Jiang and Li, 2016, Jiang and Huang, 2020]. In the following we can create a doubly robust version of the SOPEn estimator.
Before moving further, we introduce some additional notation. Let,
w(t, n) :=
8 >><
>>:
d⇡e (St n,At n) d⇡b (St n,At n) ⇣Qn 1 j=0 ⇡e(At j |St j) ⇡b(At j |St j) ⌘ if t > n Qt j=1 ⇡e(Aj |Sj) ⇡b(Aj |Sj) 1  t  n 1 otherwise
Let q be an estimate for the q-value function for ⇡e, computed using the (imperfect) model. For brevity, we make the random variable ⌧ ⇠ p⇡b implicit for the expectations in this section. For a given value of n, performance (2) of ⇡e can then be expressed as,
J(⇡e) = E
" 1X
t=1
w(t, n) t 1Rt # .
We now use this form to create a spectrum of doubly-robust estimators,
J(⇡e) = E
" 1X
t=1
w(t, n) t 1Rt # +E " 1X
t=1
w(t, n) t 1q(St, At) # E " 1X
t=1
w(t, n) t 1q(St, At)
#
| {z } =0
(a) = E
" 1X
t=1
w(t, n) t 1Rt # +E " 1X
t=1
w(t 1, n) t 1q(St, A⇡et ) # E " 1X
t=1
w(t, n) t 1q(St, At)
#
= E ⇥ w(0, n) 0q(S1, A ⇡e 1 ) ⇤ +E
" 1X
t=1
w(t, n) t 1 ⇣ Rt + q(St+1, A ⇡e t+1) q(St, At)
⌘#
= E h q(S1, A ⇡e 1 ) i +E
" 1X
t=1
w(t, n) t 1 ⇣ Rt + q(St+1, A ⇡e t+1) q(St, At) ⌘# , (3)
where in (a) we used the notation A⇡et to indicate the At ⇠ ⇡e(·|St). Using A ⇡e t eliminates the need for correcting At sampled under ⇡b. We define DR-SOPEn(D) to be the sample estimate of (3), i.e., a doubly-robust form for the SOPEn(D) estimator. It can now be observed that existing doubly-robust estimators are end-points of DR-SOPEn(D) (for trajectory-wise settings, horizon length needs to be L instead of 1 for the estimator to be well defined),
DR-SOPEL(D) = Trajectory-wise DR [Jiang and Li, 2016, Thomas and Brunskill, 2016], DR-SOPE0(D) = State-action distribution DR [Jiang and Huang, 2020, Kallus and Uehara, 2020].
A variation of PDIS that can often also help in mitigating the variance of PDIS method is the Consistent Weighted Per-Decision Importance Sampling estimator (CWPDIS) [Thomas, 2015]. CWDPIS renormalizes the importance ratio at each time with the sum of importance weights, which causes CWPDIS to be biased (but consistent) and often have lower variance than PDIS.
CWPDIS(D) := LX
t=1
t 1 Pm i=1 ⇢ i 1:tR
i tPm
i=1 ⇢ i 1:t
.
Similar DR-SOPEn, we can create a weighted version of SOPEn estimator that interpolates between a weighted-version of SIS and CWPDIS:
W-SOPEn(D) := nX
t=1
t 1
mX
i=1
⇢i1:tPm i=1 ⇢ i 1:t Rit
! + 1X
t=n+1
t 1
mX
i=1
w(Sit n, A i t n)⇢ i t n+1:tPm
i=1 w(S i t n, A i t n)⇢ i t n+1:t
Rit
! .
Since, unlike PDIS, CWPDIS is a biased (but consistent) estimator, W-SOPEn interpolates between two biased estimators as endpoints. Nonetheless, we show experimentally in Section 6 that in practice W-SOPEn estimators for intermediate values of n can still outperform weighted-SIS and CWPDIS.

heading: 6 Experimental Results
text: In this section, we present experimental results showing that interpolated estimators within the SOPEn and W-SOPEn spectrums can outperform the SIS/weighted-SIS and PDIS/CWPDIS endpoints. In each experiment, we evaluate SOPEn and W-SOPEn for different values of n ranging from 0 to L. This allows us to compare the different estimators we get for each n and see trends of how the
performance changes as n varies. Additionally, we plot estimates of the bias and the variance for the different values of n to further investigate the properties of estimators in this spectrum.
For our experiments, we utilize the environments and implementations of baseline estimators in the Caltech OPE Benchmarking Suite (COBS) [Voloshin et al., 2019]. In this section, we present results on the Graph and Toy Mountain Car environments. To obtain an estimate of the density ratios ŵ, we use COBS’s implementation of infinite horizon methods from [Liu et al., 2018]. Full experimental details and additional experimental results can be found in Appendix D. Additional experiments include an investigation on the impact on the degree of ⇡e and ⇡b mismatch on SOPEn and W-SOPEn, as well as additional experiments on the Mountain Car domain.
The experimental results for the SOPEn and W-SOPEn estimators can be seen in Figures 4 and 5 respectively. We observe that for both SOPEn and W-SOPEn, the plots of mean-squared error (MSE) have a U-shape indicating that there exist interpolated estimators within the spectrum with lower MSE than the endpoints. Additionally, from the bias and variance plots, we can see that SOPEn performs a bias-variance trade-off in these experiments. We observe that as n increases and the estimators become closer to PDIS, the bias decreases but the variance increases. Likewise, as n decreases and the estimators become closer to SIS, the variance decreases but the bias increases. This bias-variance trade-off trend is very notable for the unweighted SOPEn which trades-off between biased SIS and unbiased PDIS endpoints. However, we still can see this trend even with the W-SOPEn estimator, although the trade-off is not as clean because W-SOPE interpolates between biased SIS and the also biased (but consistent) CWPDIS.
Finally, note that our plots also show the results for different batch sizes of historical data. In our plots, as batch size increases, for some domains the PDIS/CWPDIS endpoints eventually outperform the SIS/weighted-SIS endpoints. However, even in this case, there still exist interpolated estimators that outperform both endpoints.

heading: 7 Related Work
text: Off-policy evaluation (also related to counterfactual inference in the causality literature [Pearl, 2009]) is one the most crucial aspects of RL, and importance sampling [Metropolis and Ulam, 1949, Horvitz and Thompson, 1952] plays a central role in it. Precup [2000] first introduced IS, PDIS, and WIS estimates for OPE. Since then there has been a flurry of research in this direction: using partialmodels to develop doubly robust estimators [Jiang and Li, 2016, Thomas and Brunskill, 2016], using multi-importance sampling [Papini et al., 2019, Metelli et al., 2020], estimating the behavior policy [Hanna et al., 2019], clipping importance ratios [Bottou et al., 2013, Thomas et al., 2015, Munos et al., 2016, Schulman et al., 2017], dropping importance ratios [Guo et al., 2017], importance sampling the entire return distribution [Chandak et al., 2021], importance resampling of trajectories [Schlegel et al., 2019], emphatic weighting of TD methods [Mahmood et al., 2015, Hallak et al., 2016, Patterson et al., 2021], and estimating state-action distributions [Hallak and Mannor, 2017, Liu et al., 2018, Gelada and Bellemare, 2019, Xie et al., 2019, Nachum and Dai, 2020, Yang et al., 2020, Zhang et al., 2020, Jiang and Huang, 2020, Uehara et al., 2020].
Perhaps the most relevant to our work are the recent works by Liu et al. [2020] and Rowland et al. [2020] that use the conditional IS (CIS) framework to show how IS, PDIS, and SIS are special instances of CIS. Similarly, our proposed method for combining trajectory and density-based importance sampling also falls under the CIS framework. Liu et al. [2020] also showed that in the finite horizon setting, none of IS, PDIS, or SIS has variance always lesser than the other. Similarly, Rowland et al. [2020] used sufficient conditional functions to create new off-policy estimators and showed that return conditioned estimates (RCIS) can provide optimal variance reduction. However, using RCIS requires a challenging task of estimating density ratios for returns (not state-action pair) and Liu et al. [2020] established a negative result that estimating these ratios using linear regression may result in the IS estimate itself.
Our analysis complements these recent works by showing that there exists interpolated estimators that can provide lower variance estimates than any of IS, PDIS, or SIS. Our proposed estimator SOPEn provides a natural interpolation technique to trade-off between the strengths and weaknesses of these
trajectory and density based methods. Additionally, while it is known that q⇡(s, a) and d⇡(s, a) have a primal-dual connection [Wang et al., 2007], our time-based interpolation technique also sheds new light on connections between their n-step generalizations.

heading: 8 Conclusions
text: We present a new perspective in off-policy evaluation connecting two popular estimators, PDIS and SIS, and show that PDIS and SIS lie as endpoints on the Spectrum of Off-Policy Estimators SOPEn which interpolates between them. Additionally, we also derive a weighted and doubly robust version of this spectrum of estimators. With our experimental results, we illustrate that estimators that lie on the interior of the SOPEn and W-SOPEn spectrums can be used outperform their endpoints SIS/weighted-SIS and PDIS/CWPDIS.
While we are able to show there exist SOPEn estimators that are able to outperform PDIS and SIS, it remains as future work to devise strategies to automatically select n to trade-off bias and variance. Future directions may include developing methods to select n or combine all estimators for all n using -trace methods [Sutton and Barto, 2018] to best trade-off bias and variance.
Finally, like all off-policy evaluation methods, our approach carries risks if used inappropriately. When using OPE for sensitive or safety-critical applications such as medical domains, caution should be taken to carefully consider the variance and bias of the estimator that is used. In these cases, high-confidence OPE methods [Thomas et al., 2015] may be more appropriate.

heading: 9 Acknowledgement
text: We thank members of the Personal Autonomous Robotics Lab (PeARL) at the University of Texas at Austin for discussion and feedback on early stages of this work. We especially thank Jordan Schneider, Harshit Sikchi, and Prasoon Goyal for reading and giving suggestions on early drafts. We additionally thank Ziyang Tang for suggesting an additional marginalization step in the main proof that helped us unify the results for finite and infinite horizon setting. The work also benefited from feedback by Nan Jiang during initial stages of this work. We would also like to thank the anonymous reviewers for their suggestions which helped improve the paper.
This work has taken place in part in the Personal Autonomous Robotics Lab (PeARL) at The University of Texas at Austin. PeARL research is supported in part by the NSF (IIS-1724157, IIS-1638107, IIS-1749204, IIS-1925082), ONR (N00014-18-2243), AFOSR (FA9550-20-1-0077), and ARO (78372-CS). This research was also sponsored by the Army Research Office under Cooperative Agreement Number W911NF-19-2-0333, a gift from Adobe, NSF award #2018372, and the DEVCOM Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196 (ARL IoBT CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.

Review summaries:
This paper introduces a novel n-step method which interpolates between PDIS ($n=H$) and density estimation ($n=0$) methods (the DICE family). The paper derives the relationship between density ratio corrections and likelihood ratio corrections, leading to the development of the proposed algorithm. The paper empirically investigates multiple ablation studies of the bias/variance tradeoff of the proposed algroithm.