SOPE: Spectrum of Off-Policy Estimators
Authors: Christina Yuan
Yash Chandak
Stephen Giguere
Philip S. Thomas
Scott Niekum
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
off-policy policy evaluation

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 state-action 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.

SOPE: Spectrum of Off-Policy Estimators
Christina J. Yuan University of Texas at Austin cjyuan ww...x.s..euuuu
Yash Chandak
Stephen Giguere
University of Massachusetts
University of Texas at Austin
ychandak @cs @ww.e..um.m us.umass.edu
@giguree@es.utexan
Philip S. Thomas
Scott Niekum
University of Massachusetts
University of Texas at Austin sniekum @ cs. etu
pthomas @cs. sissumasseel edu
Abstract
Many sequential decision making problems are high-stakes and require off off-policy evaluation (OPE) of 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 state- action distribution ratios can be challenging and lead to biased estimates. In this paper, we present new perspective on this bias-variance trade-off and show the existence of 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 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.
1 Introduction
Many sequential decision making problems, such as automated health-care, robotics, and online recommendations are high-stakes in terms of health, safety, finance [Liao et al., 2020, Brown et al., 2020, Theocharous et al., 2020]. For such problems, collecting new data to evaluate the performance of new decision rule, called an evaluation policy Te, may be expensive even dangerous if results in undesired outcomes. Therefore, one of the most important challenges in such problems is the estimation of the performance J(me) of the policy n. before its deployment.
Many off-policy evaluation (OPE) methods enable estimation of J(Tr) with historical data collected using existing decision rule, called behavior policy Tg. One popular OPE technique is trajectory- based importance sampling (IS) [Precup, 2000]. While this method is both non- por-aaamettiic and provides unbiased estimates of J J(Te), 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 distri- bution 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 berween the stationary distribution induced by Te and т₁, Unfortunately, estimating this ratio accurately can require unverifiably strong assumptions 2020], and often requires solving non-trivial min-max saddle point optimization problems (Yang 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.
the parameters [Jiang and Huang,
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In practice, these challenges can introduce error when estimating the distribution ratio, potentially leading to arbitrarily biased estimates of (TT), 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-basee bassed and distribution- methods can be combined. The core idea establishing the existence of this spectrum relies upon first splitting individual trajec- tories 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.
2 Background
Notation: A Markov decision process (MDP) is a tuple r,,,,,,T,,,, d1), where S is the state set, A is the action set, is the reward function, T is the transition function, y is the discounting factor, and di is the initial state distribution. Although our results extend to the continuous setting, for simplicity of notation the state. Starting from initial state S1 ~ d1, policy π interacts with the environment iteratively by sampling action Ar at every time step t from (-|)S)). The environment then produces reward Rd with the expected value r(S,, At). and transitions to the next state S according to 7(-|S,, Ad). Let T (,,, Ri, S2, ..., St, AL, R2) be the sequence of random variables corresponding to trajectory sampled from where L is the horizon length. Let pa denote the distribution of T under π.
assume that S and A are finite. A policy π is distribution over A, conditioned on
The performance of any policy æ is given by its value defined by the expected discounted sum of rewards (TT == Er-p- /Etn 70 Rt]. The infinite horizon setting can be obtained by letting L -> oo. In general, for any random variable, we use the superscript of to denote the trajectory associated with it. The goal of the off oof-cp policy evaluation (OPE) problem is to estimate the performance (Ize) of an evaluation policy Te using only batch of historical trajectories D [r') collected from different behavior policy me- This problem is challenging because J(TA) must estimated using only observational, off-policy data from the deployment of a different behavior policy Ta. Additionally, this problem might not be feasible if the data collected using 7s is not informative about the outcomes possible under me. Therefore, to make the problem tractable, we make the following standard support assumption, which implics that any outcome possible under Te also has non zero probability of occurring under Tb-
Problem Statement:
Assumption 1. For all s E S and a E A, the ratio (a(a)) (a
< <C.
Trajectory-Base Based Importance Sampling: One of the earliest methods for estimating (Tx) is trajectory-based importance sampling. This method corrects the difference distribution of my and Te by re-weighting the trajectories from Te in D by the probability ratio of the trajectory under (A.1S)) Let the single-step action likelihood ratio be denoted (r) I. (A(.)))))
Te and Tb. i.e. Pr. (T)
[.) and the likelihood ratio from steps to k be denoted PJ: = I Pt. The full- trajectory importance sampling (IS) estimator and the per-decision importance sampling (PDIS)
P: = 3. (A.
estimator [Precup, 2000] can then be defined as:
PDIS(D) 1 m
IS(D) = PIL
R
Pi R
was shown by Precup [2000] that under Assumption 1, DSD and PDIS are unbiased estimators of J (TTT). That J = Er-p-, [IS(T) = E, (PDIS(T) 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 T., 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 de denote the induced state-action distribution at time step I, i.e. di (8.0) (S = 8, At = a). Let the average state-action distribution be d (s. = Df (s..a))((Ern 1 1 This gives the likelihood of encountering (s, a) when following policy и and averaging over time with y-discounting. Let (S, A) d" and (S, A) ~ dā denote that (S, A) are sampled from de and dī respectively. The performance of Te can be expressed as,
[mme) E ETTEES
R
(s,
Σ
y0-1
Σ d' (s)
1=1
(a)
( a
t d a) d (s,a)
r as, = ΣΣ
t- di (s, a)
( r(s,a);
d' d a)
3.a
8,0 t=1
d (Se, As) d (St, Ar)
Rs.
where (a) is possible due to Assumption 1. Using this observation, recent works have considered the following Jiang and Huang, 2020],
importance sampling estimator [Liu et al., 2018, Yang et al., 2020,
m
SIS
w A))
m
where w(ss a) (',(,,) is the distribution correction ratio. Notice that SIS(T) marginalizes over the product of importance ratios P1:t. and thus can help in mitigating variance's dependence on horizon length for PDIS and IS estimators. When unbiased estimate of w is available, then SIS(r) also an unbiased estimator, i.e., Er-7, BIs=,((IS(TT)) = J(ze). Unfortunately. such an estimate of w is often not available. For large-scale problems, parametric estimation is required in practice and replace the true density ratios wo 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 non-trivial min-max optimization problem [Jiang and Huang, 2020, Yang et al., 2020]. When these conditions met, SIS estimates can be arbitrarily biased, even when an infinite amount of data is available.
(x.a)
3 Combining Trajectory-Based and Density-Based Importance Sampling
Trajectory-basee and distribution-based importance sampling methods are typically presented as alter- native methods of applying importance sampling for off-polis evaluation. However, in this section we show that the choice of estimator is not binary, and these two styles of computing importance weights actually be combined into 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-bu baasdd SIS, which will often allow trade-off between the strengths and weaknesses of these methods.
Intuitively, trajectory-basse based and distribution- based importance sampling provide two different ways of correcting the distribution mismatch under the evaluation and behavior policies. Trajectory-basee 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-ban based importance sampling corrects the mismatch by how likely policies are visit the same state and action pairs-white while remaining agnostic to how they arrived- and applies the distribution ratio 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 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 mb Te
3

---

Figure 1: Illustration of two room domain. The domain consists of two rooms, the left room and the right room separated by con- necting door. Th and T. are two different poli- cies that move from the left room to the right room. Note that, although тr and Tee have two different behaviors the left room and right room, both pass through the connecting door.
Feg
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 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 RG 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- importance sampling can be combined in the same estimator. Given trajectory т. can consider (S,, Ag), the state and action at time : in the trajectory. By conditioning on (S,, Ag), trajectory T can be separated into two conditionally independent partial trajectories To:s and 1.+1LL & by the Markov property. Since the segments of T before and after time z are conditionally independent, then Pl:s, the likelihood ratio for the trajectory before time 2, is conditionally independent from Pæ-1:L and from R₂ for all t 2 2. Formally, let (Sz, Ag) ~ d then,
(mT,) E Ereppy
[PDIS(T)
E Eropey
Σn Ps
2
E Erpppy
Σ
xt PI: Pt: Re
E(S2.de) wdl
E EYmPan
Σ x P1:PP+1n Sz, As
1=--11
E Erapps
pi: Ri
+ E(sziAz) wd
E Erippn (p1:2|S2, Aa] E Er IP=+1:t Ro A.]
1=1
11=++1
(a) E
Eyopan
x 1- Pulll
+ E(seida) wid
d. (S2, A2) d (S2, Az)
E. Er-rey ( S2, As
1==+1
d= (Sz, As) (S A.)
Erropyy
Σ
Pu +
Σ Am2++1
Pz U241alk Rs
(I)
where (a) follows from the following Property 1, which states that the expected value of product likelihood ratios Pi:s conditioned on AS,,A.) is equal to the time depedeeendent state-action distribution ratio for (Sz, Az). We provide a detailed proof of Property in Appendix A.
Property 1 ([Liu al., 2018)). Under Assumption 1, E |paa 8, A. = A,
(s.a)
(s.a)
Observe that Eq (1) is indexed by time 2. 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 S₂ and taking action A, at time Z and action likelihood ratios are used to correct for the probability of actions taken after time z. Further observe that does not have to be a fixed constant-z(1) can a function of so that each reward in the trajectory R; can utilize 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 estimator that interpolates between average state-action (s.a).
(s.() rather than time-dependent distribution ratios d. (o.o) distribution ratios w(s, a) = (=,())))

---

71
Re
1hb
Th
7b
Fp-ner
Fpp
Fiir Agg Re
(a) PDIS
(b) SOPE..
(c) SIS
Figure 2: Illustrations of the PDIS, SOPE,, and SIS estimators. The dotted blue line represents an example trajectory drawn from Te. and the solid red line represents example trajectory from тa- All three importance sampling methods work by re-weighting each reward R₂ in the trajectory from xe- (a) Trajectory-basee PDIS works by re-weighting each reward by
Px. (Tais) the probability ratio of the
(r.(Tra)"
sub-trajectory leading up to RG under the πy and Re. respectively. This factors into P1:,, the product of t action likelihood ratios. (c) Distribution- under Te and Th, and re-weights R, by d (S),A)) (b) SOPE,, combines trajectory and distribution importance sampling weights by considering the probability of each policy visiting (St-n, A A(-n). the state-action pair n steps in the past, and additionally the probability of the sub-trajectory Tt Tt-++I:t d (S..nAAA))) 7 (Sc Pt-n+
SIS considers the probability of encountering (S,,AA)
AS..)...A.)
from n steps in the past to l. Thus, SOPE,, re-weights RG by
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 off-policy estimators that allows for interpolation between the trajectory-basee
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 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 each reward Rg Specifically, for any reward RG, we propose including only the n most recent action likelihood ratios Pr-n+1:t in the importance weight, rather than P1:t- Thus, the overall importance weight becomes the re-weithted probability of visiting (S..n. At-n), followed by the re-weighted probability of taking the last actions leading up to reward R, This reduces the exponential impact that horizon length has on the variance of PDIS, and provides control over this reduction via the parameter To get estimator perform this trade-off, start with the derivation in (1) with at) = n. then accumulate the dime-dependent state-action distributions de over time. The final expression for the finite horizon setting requires some additional constructs and thus presented along with its derivations and additional discussion in Appendix B. In the following present the result for the infinite horizon setting.
d (S Ar-n) (S At-n) -+ RA
J(Te) = EToppy
Σ
Put PLaRR
t=
Using the sample estimate of (2), obtain the Spectrum of Off-Policy Estimators (SOPE,),
SO) 1
R
"(S 1 A
Ri
[=++1
Remark 1. Note that since we generally do have access to the true density ratios, in practice substitute w with the estimated density ratios ie similarly as in SIS. Since SOPE,, is agnostic to how is estimated, can readily leverage existing and new methods for estimating w.
Observe that SOPE, doesn't it just give single estimator, but spectrum of off-policy estimators indexed by n. An illustration of this spectrum can be seen Figure 3. As n decreases. the number of terms in the action likelihood ratio decreases, and SOPE,, depends more the distribution correction ratio and more like SIS. Likewise as n increases, the number of terms in the action likelihood ratio increases, and SOPE,, is closer to PDIS. Further note that that for the endpoint values of this
5

---

#=L
#=1
==
n=L
S
S
A1
A1
== L-1
S2
S2
One-step Backup Biased
n
Low-Varlance
S
S
A
Ac-1
St.
ST.
A
A
PDIS
Interpolated Estimators
Monte-Carlo Return Unbiased
Unblased
Less-Blas
Blased
High-Variance
Less-Variance
Less-Variance
High-Variance
On the left side of the figure, we show an illustration the SOPE, spectrum of estimators. For the purpose of this illustration, consider that only the last time step there is a non-zero reward Rr. The SOPE,, spectrum allows for control of how much an estimate depends on distribution ratios action likelihood ratios. Notice that SOPE, results in SIS, SOPE, results PDIS estimator, and other values of n result in new interpolated estimators. As an analogy, consider the packup-diagran [Sutton and Barto, 2018] for the n-step q-estimate as illustrated on the right-hand side of the solid vertical line. Notice that in the nt-tep q-estimate, returns are backed up from possible outcomes, whereas in n-step interpolation estimators the probabilities are 'backed-up' from the possible histories. (In the diagram, bias- variane characterization of PDIS and SIS is based on typical practical observations [Voloshin al., 2019, Fu al., 2021], however when oracle density ratios are available, and there are also edge cases, particularly for short horizon problems, where SIS can have higher variance than PDIS [Liu et al., 2020, Metelli al., 2020)).
Figure 3:
worth noting that SIS not biased
spectrum, n 0 and n L, SOPE, gives the SIS and PDIS estimators exactly (for PDIS, horizon length needs to be L instead of sc for the estimator to be well defined),
m
SOPE,(D)
(S) A SIS(D),
i=1
SOPE, =
R = PD)S(D).
5 Doubly-Robust and Weighted IS Extensions to SOPE,,
An additional advantage of SOPE,, is that it can be readily extended to obtain a spectrum for other estimators. For instance, to mitigate variance further a popular technique 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 doubly robust version of the SOPE,, estimator.
Before moving further, we introduce some additional notation. Let,
te Ar-n) 1. A.A..n n) Ne (Ag18))) j= no( 70(,,18))
(I (A (5-:))
if n
(1
w(t,n)
1 1stán otherwise

---

Let be an estimate for the q-value function for computed using the (imperfect) model. For brevity, we make the random variable T Pro implicit for the expectations in this section. For given value of n, performance (2) of The can then be expressed as,
[mm)) = E Σ ntttnn)''11 Rs
We now use this form to create spectrum of doubly-robust estimators,
(
E
Σ wlt,n)y -
Re
+ E
" Ac) wlt, n)y
E
Σ wlt, "0 Ac)
=0
(a)
E
m(tt 11y" Rde
E
Σ 1=1
mrtt 1,
q(S,, 1, A7xi)
Σ
w(t, (o(t,n))t11(0
E
[w(0, A[o] [u(. +
w(t, wtt, (1:001((: 19 - g(S Ail)
= E ATo)
+
Σ w(t,n))'' (Re 7gl (R
q(S A.))
(3)
where in (a) we used the notation AT to indicate the Ar (-1et. Using A eliminates the need for correcting A sampled under тg. We define DR-SOPE, to be the sample estimate of (3), i.e., a doubly-robust form for the SOPE,, (D) estimator. can now be observed that existing doubly-robust estimators end-points of DR-SOPE, (D) (for trajectory-wise settings, horizon length needs to be L instead of oo for the estimator to be well defined),
DR-SOPEZ(D) = Trajectory-wise DR [Jiang and Li, 2016, Thomas and Brunskill, 2016], DR-SOPE,(D) State-action distribution DR [Jiang and Huang, 2020, Kallus and Uchara, 2020].
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.
TIL
P 1i=1 Pia
CWPDIS(D) Σ
Similar DR- SOPE, create weighted version of SOPE, estimator that interpolates between a weighted--vrrson of SIS and CWPDIS:
w [S Af. )p n+ w(S) (S A )1 Pp
W-SOPE, (D) = Σ
R
+
R
-== Pla
1==+1
Since, unlike PDIS, CWPDIS a biased (but consistent) estimator, W-SOPE, interpolates between two biased estimators endpoints. Nonetheless, show experimentally in Section 6 that in practice W-SOPE, estimators for intermediate values can still outperform weighted- and CWPDIS.
Experimental Results
this section, we present experimental results showing that interpolated estimators within the SOPE,, and W-SOPF,, spectrums can outperform the STS/weighted-SIS and PDIS/CWPDIS endpoints. In each experiment, we evaluate SOPF,, and W-SOPE, for different values of n ranging from 0 to L. This allows us to compare the different estimators get for each n and see trends of how the
7

---

MSE
Squared Estimate
Vaniacee Estimate
Tejectones
256
107
512
10"2
1024
2045
1071
4096
10
10
10"4
0192
10:1
10
0
15
15
step VaLue
step value
n stetep vaice
(a) SOPE, on Graph Domain
MSF
Blas Squared Estimate
Vaniance Estimate
1x100
10
1x100
Trajetooris
256
512
10a
2x100
1024
2048
10m1
20
80
p-itep
(b) SOPE, on Toy Mountain Car Domain
Figure 4: Experimental results from evaluating the SOPE,, estimator on the Graph and Toy Mountain Car domains. The x-axis for each plot indicates the value of in the SOPE,, estimate. The shaded regions denote 95% confidence regions on the mean of MSE. Recall that SOPE, gives SIS and SOPE, gives PDIS. The evaluation and behavior policies are Te 0) 0.9 and mi (a =
0.5
for the experiments on the Graph Domain and and (a 0) = 0.5 and ma = 0) 0.6 for the Toy Mountain Car domain. In both these domains, we can see that there exist interpolating estimators
in the SOPE,, spectrum that outperform SIS and PDIS, and that the SOPE,, spectrum empirically performs bias-variance trade-off.
performance changes as n varies. Additionally, we plot estimates of the bias and the variance for the different values of 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 Graph and Toy Mountain Car environments. To obtain an estimate of the density ratios u. experimental details and additional experimental results can be found in Appendix D. Additional experiments include investigation the impact on the degree of ne and Ta mismatch SOPE,, and W-SOPE,, as well as additional experiments on the Mountain Car domain.
COBS's implementation of infinite horizon methods from [Liu et al., 2018]. Full
The experimental results for the SOPE, and W-SOPE, estimators can be seen in Figures 4 and 5 respectively. We observe that for both SOPE,, and W-SOPE,, the plots of mean- gean-squared error (MSE) have 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 SOPE,, performs bias-variance trade-off in these experiments. We observe that as 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-variae variance trade-off trend is very notable for the unweighted SOPE,, which trades-off between biased SIS and unbiased PDIS endpoints. However, we still can see this trend even with the W-SOPE, estimator, although the 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-SII endpoints. However, even this case, there still exist interpolated estimators that outperform both endpoints.

---

Bias Squared Estimate
Veriance Estimate
Trgestoree
256
10"1
10
512
10
1011
10
15
30
15
n. step value
step viliee
stete Value
(a) W-SOPF. Graph Domain
MSE
Bias Squared
Variance
10"
Trajectoriss
20
60
00
0
n-Step value
17: 11stee valle
n-step Valuee
(b) W-SOPE, Toy Mountain Car Domain
Figure 5: Experimental results from evaluating the W-SOPE,, estimator on the Graph and Toy Mountain Car domains. The r-axis for each plot indicates the value of in the SOPE,, estimate. The shaded regions denote 95% confidence regions on the mean of MSE. Recall that W-SOPE gives weighted-SIS and W-SOPE, gives CWPDIS. The evaluation and behavior policies are n. 0) 0.9 and (a 0) 0.7 for the experiments on the Graph Domain and and ae(a = 0) 0.5 and (a = 0) 0.9 for the Toy Mountain Car domain. both these domains, we can see that
although we do not get as clean of a bias-variance trade-off as when we use SOPE,, there still exist interpolating estimators in the W-SOPE, spectrum that outperform SIS and PDIS.
7 Related Work
Off-policy evaluation (also related 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 flurry of research in this direction: using partial- models 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 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], J. and estimating state-action distributions [Hallak and Mannor, 2017, 7, Liu et al., 2018 8, Gelada and Bellemare, 2019, Xie al., 2019, Nachum and Dai, 2020, Yang 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 [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) using RCIS requires a challenging task of estimating density ratios for returns (not state-action pair) and Liu et al. [2020] established negative result that estimating these ratios using linear regression may result in the IS estimate itself.
provide optimal variance reduction. However,
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 SOPF,, provides natural interpolation technique trade-off between the strengths and weaknesses of these

---

trajectory and density based methods. Additionally, while it is known that (" a) and d" ds a) have a primal-dual connection [Wang al., 2007], our time-based interpolation technique also sheds new light on connections between their n-step generalizations.
8 Conclusions
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 the Spectrum of Off-Policy Estimators SOPE, which interpolates between them. Additionally, we also derive a weighted and doubly robust version of this spectrum of estimators. With experimental results, we illustrate that estimators that lie on the interior of the SOPE, and W-SOPE, spectrums can be used outperform their endpoints SIS/weighted-SSS and PDIS/CWPDIS.
While we are able to show there exist SOPE, estimators that are able to outperform PDIS and SIS, remains as future work to devise strategies to automatically select to trade-off bias and variance. Future directions may include developing methods to select n or combine all estimators for all n using X-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 the estimator that is used. In these cases, high-confidence OPE methods [Thomas et al., 2015] may be more appropriate.
9
Acknowledgement
We thank members of the Personal Autonomous Robotics Lab (PeARL) at the University of Texas Austin for discussion and feedback 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 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 thank the anonymous reviewers for their suggestions which helped improve the paper.
additional marginalization step in the main proof
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 11S- 107, IIS-1749204 I18-1925,82), ONR (N00014-18-2 and ARO (78372-CS). This research was also sponsored by the Army Research Office under Cooper- ative Agreement Number W91 1991NNF-1-2200333, gift from Adobe, NSF award #2018372, and the DEVCOM Army Research Laboratory under Cooperative Agreement W91 19F-117--2-011 (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 reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
AFOSR 1P49550-20-1-000
References
Léon Bottou, Jonas Peters, Joaquin Sathooner-Canndlla Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. The Journal of Machine Learning Research, 14(1):3207-322 -2260 2013.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint 0rXiv:1606.01544 2016.
Daniel Brown, Russell Coleman, Ravi Srinivasan, and Scott Niekum. Safe imitation learning via fast bayesian reward inference from preferences. In International Conference on Machine Learning, pages 1165-1177. PMLR, 2020.
Yash Chandak, Scott Niekum, Bruno Castro da Silva, Erik Learned-Miller, Emma Brunskill, and Philip S Thomas. Universal off-policy evaluation. arXiv preprint SXX::2104.12820 2021.
10

---

Justin Fu, Mohammad Norouzi, Ofir Nachum, George Tucker, Ziyu Wang, Alexander Novikov, Mengjiao Yang. Michael R Zhang, Yutian Chen, Aviral Kumar, et al. Benchmarks for deep off-policy evaluation. arXiv preprini arXiv:2 16596, 2021.
Carles Gelada and Mare G Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3647-3655, 2019.
Zhaohan Daniel Guo, Philip Thomas, and Emma Brunskill. Using options and covariance testing for long horizon pooicy policy evaluation. arXiv preprint arXiv: arXiv:1703.00 seor::773333333 2017.
Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In International Conference on Machine Learning, pages 1372-1383, PMLR, 2017.
Assaf Hallak, Aviv Tamar, Rémi Munos, and Shie Mannor. Generalized emphatic temporal difference learning: Bias-variance analysis. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, 2016.
Josiah Hanna, Scott Niekum, and Peter Stone. Importance sampling policy evaluation with an estimated behavior policy. In International Conference on Machine Learning, pages 2605-2613 PMLR, 2019.
Daniel G Horvitz and Donovan J Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260):663-685, 1952.
Nan Jiang and Jiawei Huang. Minimax confidence interval for off- evaluation and policy optimization. arXiv preprint arXiv:2002.02081, 2020.
Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In International Conference Machine Learning, pages 652-661. PMLR, 2016.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off- off-policy eval- uation in markov decision processes. Journal of Machine Learning Research, 21(167):1-63. 2020.
Peng Liao, Predrag Klasnja, and Susan Murphy. Off-policy estimation of long-term average outcomes with applications to mobile health. Journal of the American Statistical Association, pages 1-10, 2020.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou, Breaking the curse of horizon: Infinite- horizon off- off-policy estimation. arXiv preprint 18X1v:1810.124299 2018.
Yao Liu, Pierre-Luc Bacon, and Emma Brunskill. Understanding the curse of horizon off- off-policy evaluation via conditional importance sampling. In International Conference on Machine Learning. pages 6184-6193, PMLR, 2020.
Rupam Mahmood, Huizhen Yu, Martha White, and Richard Sutton. Emphatic temporal-differene learning. arXiv preprint 15X.v:150..01569 2015.
Alberto Maria Metelli, Matteo Papini, Nico Montali, and Marcello Restelli. Importance sampling techniques for policy optimization. Journal of Machine Learning Research, 21(141):1-75, 2020.
Nicholas Metropolis and Stanislaw Ulam. The monte carlo method. Journal of the American statistical association, 44(247):335-333 341, 1949.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare G Bellemare. Safe and efficient off-policy reinforcement learning. arXiv preprint 1606:v660600266 2016.
Ofir Nachum and Bo Dai. Reinforcement learning via Fenchel- Rockaflllrr duality. arXiv preprint arXiv:2001.01866, 2020.
Matteo Papini, Alberto Maria Metelli, Lorenzo Lupo, and Marcello Restelli. Optimistic policy optimization via multiple importance sampling. In International Conference on Machine Learning, pages 4989-4999. PMLR, 2019.

---

Andrew Patterson, Sina Ghiassian, D Gupta, A White, and M White. Investigating objectives for pollcc value estimation in reinforcement learning, 2021.
Judea Pearl. Causality. Cambridge university press, 2009.
Doina Precup. Eligibility traces for off- policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000.
Mark Rowland, Anna Harutyunyan, Hado Hasselt, Diana Borsa, Tom Schaul, Rémi Munos, and Will Dabney. Conditional importance sampling for off-policy learning. In International Conference on Artificial Intelligence and Statistics, pages 45-55, PMLR, 2020.
Matthew Schlegel, Wesley Chung, Daniel Graves, Jian Qian, and Martha White. Importance resampling for off-policy prediction. arXiv preprint PrXiv:1906.04328, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT Press, Cambridge, MA, 2 edition, 2018.
Georgios Theocharous, Yash Chandak, Philip S Thooms, and Frits de Nijs. Reinforcement learning for strategic recommendations, arXiv preprint arXiv:2009.07346. 2020.
Philip Thomas and Emma Brunskill. Data-efficient off- off-policy policy evaluation for reinforcement learning. International Conference on Machine Learning, pages 2139-2148, 2016.
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High-confidence off-policy evaluation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Philip S Thomas. Safe reinforcement learning. PhD thesis, University of Massachusetts Libraries, 2015.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off- policy evaluation. In International Conference on Machine Learning, pages 9659-9668. PMLR, 2020.
Cameron Voloshin, Hoang M Le, Nan Jiang, and Yisong Yue. Empirical study of off off-policy policy evaluation for reinforcement learning. arXiv preprint arXiv: 1.06544, 2019.
Tao Wang, Michael Bowling, and Dale Schuurmans. Dual representations for dynamic programming and reinforcement learning. In 2007 IEEE International Symposium Approximate Dynamic Programming and Reinforcement Learning, pages 44-51. IEEE, 2007.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off off-policy evaluation for rein-
forcement learning with marginalized importance sampling. arXiv preprint arXiv:1906.033: 2019.
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized lagrangian. arXiv preprint arXiv:2007.03433 2020.
Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. arXiv preprint arxiv:2002.09072 2020.
12


Reviews:
[{"review_id": "uykNYyctDVK", "reviewer": "Reviewer_VgQT", "summary": "The paper considers the problem of off-policy evaluation and shows that it is possible to interpolate between the two common families of algorithms: importance sampling of policies which is unbiased but high variance, and correcting state distributions, which is low variance but could be very biased since the distributions need to be estimated. The resulting algorithm is tested empirically on small tabular tasks and it is shown that there are indeed intermediate values in the spectrum that achieve better MSE than either of the extremes.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "This paper was a pleasure to read. Despite not having strong experiments, the key idea is very cool and advances off-policy research in a clear way, and the paper is written very well. I only have a couple of high-level comments / questions, and some minor proofreading remarks.\n\n1) Figure 1 intuition is important but gets lost afterwards. It would be great to show that the error is lowest when split at the hallway, but for that z would need to depend on the state. Can the authors provide an intuition about this?\n2) Larger experiments are promised (optimistically!) in the appendix but not found. I think smaller experiments are fine, but it would be nice to have more insight about the trends. For example it seems that when the policies are further apart n=1 is optimal (single importance sampling ratio). Do the authors have intuition of what this would look like in practice?\n\nMinor comments\n* Lines 29-30: something funky with the phrasing\n* 68: d^pi_t is usually phrased as probability which might be clearer. Also I guess it should be s_t, a_t\n* Big equation on page 2: Something off with the indices here — shouldn't the sum start at t=0 (since numbering rewards starts from 0 in tau)? \n* Also, shouldn’t d_0 be a part of the definition of d^pi for probability of (s,a) at the initial time step?\n* 115: third I think? Marking the relevant equality would be clearer\n* Figure 3(b): why does variance decrease for the intermediate amounts of trajectories?\n* 159: Maybe named paragraph here?\n* 160: CWPDIS mentioned for the first time\n* 162: amount amount\n* Figure 4: it would be clearer to denote lines by policy distance instead, since the targets are different for the two tasks\n* 181-182: No larger continuous state spaces in the appendix :(\n* 198: what is H here?\n* 200: has has", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HWc0Hu1_RSc", "reviewer": "Reviewer_EWnS", "summary": "The scope of the paper is within off-policy evaluation (OPE) in reinforcement learning (RL). The paper aims to develop a spectrum of OPE methods which interpolate between trajectory based importance sampling (IS) and stationary state distribution IS. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "To briefly summarize my review and justify my score, I believe the paper is wrong. The method introduced relies on Lemma 1 which as far as I can tell is not correct. This perhaps leads to some inconsistent results which the authors do not address in the experimental section. Having said that, I think the idea of generating a family of estimators interpolating between IS and SIS is a good one, and I will therefore do my best to provide feedback which will be useful in the future if the authors can find a mathematically consistent way to generate such estimators.\n\nThe estimators presented in the paper rely on the derivation of equation (1), which uses Lemma 1. I believe the Lemma is wrong. An easy way to see that the Lemma is probably wrong is that the LHS is independent of \\gamma and L and only depends on the MDP dynamics and policies, while the density ratios on the RHS do depend on \\gamma. As a quick counter example to demonstrate it, think of a deterministic two state system, which always starts at s0, with two actions (a0 and a1). The agent always starts at s0, from which a0 leaves the agent in s0 and a1 transitions to the absorbing state s1. Assume a state independent evaluation/behavior policy which has probability \\pi_{e/b}(a0) to take action a0. To compute the LHS of lemma 1 for S_z = s0 (ignoring actions for now), we note that if S_z = s0, it means a0 was always taken, and therefore E[\\rho_{1:z} | S_z = s0] = (\\pi_{e}(a0) / \\pi_{b}(a0))^z. On the other hand the RHS can be shown to be equal \\frac{\\sum_t^L \\gamma^t \\pi_{e}(a0)}{\\sum_t^L \\gamma^t \\pi_{e}(a1)}. Note that these expression may differ slightly depending on how to interpret an inconsistency the authors have in the notation and definition which I will detail later. These quantities are obviously different. Looking at the actual proof in the appendix, one place where it is wrong is in their use of the term P_{e/b}(S_z, A_z) which is not well defined as the probability of the MDP being in (S_z, A_z) is a function of time which is absent in the derivation. In their proof and justification of a later part of the derivation the authors invoke explicitly incorporating the time into the state which might help here. If you do that you can maybe make the claim that \\gamma = 1, and get rid of that dependency, but as the counter example shows you will still not get the Lemma 1 equivalence. More importantly, the inclusion of that assumption (time explicit in the state) is misleading. While it is possible to do it, it is a very uncommon practice in RL (usually for the episodic case you just have the episode end at a given time but have time dependent value function/policies), and if the authors make that very unusual and restrictive assumption it should not be hidden at the end of the appendix.\n\nBased on this error alone, I do not believe the paper is publishable at this point. Additionally, while I do not expect the empirical results to be valid given the error, I think there are several inconsistencies in the results which can suggest that something is wrong:\nFig 3 and 4 top middle : if n=0 corresponds to SIS and n=L to PDIS the bias should be monotonically decreasing with n. Instead it is not monotonic in Fig 3 and sometimes monotonically increasing in fig 4.\nFig 3 and 4 bottom right : Why for some parameter (# of trajectories or epsilon) the variance increases with n and for some decreases, where the logic of interpolation between SIS to PDIS would predict monotonic increase for all.\n\nSome other comments:\n- The definition of J(\\pi) and d^\\pi is inconsistent between the first paragraph of the \"notation\" section in the background and the \"density based IS\" section (indexing of t).\n- Maybe I missed it, but CWPDIS is never discussed before it is given before eq. 3, and is not cited. While it would be familiar to people who know the OPE literature well, it is not used commonly enough to appear without citation. On that note, it is a little ironic that eq. 3 appears as an analogue of CWPDIS without proof of consistency, since CWPDIS was originally introduced by Pillip Thomas of an example of how naively meshing two estimators (in the case presented in his thesis meshing PDIS and WIS into what was then known as WPDIS) can easily result in inconsistent estimators.\n- In any future work, I would strongly encourage the authors to include a continuous environment in their experiments. One of the main failing mechanisms of SIS compared to IS is that any type of non-markovianity (or partial observability) would lead to inconsistent estimators. Meanwhile such partial observability doesn't effect IS as long as the policies are Markovian. Thus, it would be interesting to see how interpolation between SIS and IS can work in continuous domains where a form of partial observability is introduced through function approximation.\n\nLast, I would like to point out that the paper has too many typos for what I feel is acceptable in a submission.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "At the moment, OPE papers of this sort are mostly theoretical and therefore have limited societal impact. The long term goal of OPE work is to allow deployment of RL policies in risk sensitive domains, which would have negative impact if not done properly. The authors acknowledge the importance of OPE in that regard and thus satisfy the criterion for discussing the potential negative impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 to 8"}, "extra_text": {}}, {"review_id": "9M1Xt9ZXj9x", "reviewer": "Reviewer_eekS", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "I recommend to accept this paper. [S1] The connection between density ratio and likelihood ratio corrections is insightful. [S2] The proposed algorithm is simple and provides an avenue to avoid a common criticism of DICE methods: the difficulty in estimating the density ratio and resultant bias. [S3] The empirical evaluation is motivating. Finally, [S4] the paper is quite well-written and very clear.\n\nI have only very minor reservations: [W1] the empirical investigation exclusively uses weighted-PDIS and weighted-SIS, so interpolates between two biased methods. [W2] By using small toy domains where SIS can perfectly estimate the density ratio, many  of the stated difficulties of SIS are not investigated, leaving open-ended the contribution of this paper in harder problem settings.\n\n---\n\n**[W1]**: Weighted estimators\n\nI would be curious to see a more clear demonstration of the bias-variance tradeoff by additionally investigating the non-weighted versions of these estimators---at the very least a non-weighted version of PDIS. The bias on the graph MDP is sufficiently small for all values of the estimator, that I wonder if the empirical estimate of bias is more noise than signal (Figure 3a), but I would have expected to see the bias decay more strongly as n -> L. In the case of Figure 4a, I am surprised that the PDIS estimate _increases_ bias over the weighted-SIS estimate leaving the bias-variance tradeoff claims poorly supported.\n\n---\n\n**[W2]**: Small domains\n\nI generally don't mind small domains. I believe they were harmful in this case where the true density ratio is representable within the function approximation class. Using even the toy Mountain Car domain with a reduced function approximator would provide some additional value by demonstrating the impact of the proposed n-step estimator when SIS has much worse bias. Currently the best value of $n$ is often very close to 0 (near SIS), but in larger/more realistic settings I wonder if this would continue to be the case.\n\n---\nMinor question: would it be possible to derive an expression for minimizing the MSE w.r.t. parameter $n$ analytically? I wonder if this could be estimated easily from the data. At the very least, I would be curious to see how effectively an n-fold cross-validation approach selects the optimal value of $n$.\n\n---\n\n**Edit after discussion period:**\n\nAfter concerns about the correctness of the proof have been resolved, I continue to feel this paper is a solid contribution to the field. My previous concerns were only minor in strength and have been well-addressed with the author response and I do not feel that I would need to re-review after the new experiments are added to the paper. I recognize the discussion period was rather quiet for this paper, but frankly, I believe this paper left little need for added discussion---to me it is a clear accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact are sufficiently addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6Eq16U7bQJ6", "reviewer": "Reviewer_TiwR", "summary": "The paper proposes an estimator for off-policy evaluation (OPE) that unifies trajectory-based per-decision importance sampling with stationary distribution importance sampling using an n-step approach analogous to multistep temporal-difference learning. The paper presents n-step estimators for both ordinary importance sampling and weighted importance sampling, and investigates their properties on two tabular OPE environments.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "I recommend publishing the paper at NeurIPS 2021 despite minor concerns about scope.\n\n**Quality:**\n\nThe proposed estimator is derived in a principled fashion, and the experiments are aimed at understanding properties of the proposed estimator and seem well-done to me.\nThe main thing that disappointed me about the paper was that it restricted itself to n-step methods instead of also doing the obvious next step and incorporating exponential weighting to get an estimator analogous to TD($\\lambda$).\nA secondary concern is that there is no guidance for how to set the \"switching time\" parameter for an environment a priori.\nIn general I'm not a fan of introducing parameters, but the paper appears to do it for the purposes of better understanding two existing algorithms instead of doing it to improve performance, so I'm ok with it.\nOne could also argue that another experiment in a larger domain is needed, but I was satisfied with the existing experiments.\n\n**Clarity:**\n\nThe paper is written clearly and is very easy to understand. There are some minor grammatical errors throughout (some of which I've pointed out below). The paper doesn't try to obfuscate or dress up what it's doing, which is frankly a breath of fresh air.\n\n**Significance:**\n\nThe proposed method provides a useful unification of two existing algorithms (useful because intermediate values can often perform better than either extreme), which could easily be built upon. Interestingly, the n-step approach forms a bridge to multi-step TD learning, which provides another perspective on the problem.\n\n**Originality:**\n\nThe paper takes a well-known technique (n-step estimates) and applies it to a different problem. To the best of my knowledge the proposed method is novel.\n\n**Misc. comments, questions, and suggestions for improvement:**\n\nLine 29: There's an extra \"can\" in this sentence.\n\nLine 31: \"If\" should be lowercase.\n\nLine 42: \"the first part\" is repeated.\n\nLine 43: \"using\" should be uppercase.\n\nLine 69: It was a little confusing to define $c=\\sum_{t=0}^{L} \\gamma^t$ instead of just writing it out.\n\nLine 146: \"to\" is repeated.\n\nLine 151: should be \"allow us to control the variance's dependency\"\n\nLine 162: \"amount\" is repeated.\n\nFigure 3: Thank you for plotting confidence intervals! I can easily see whether differences are statistically significant by checking if the shaded regions overlap.\n\nLine 160: The acronym CWPDIS is never actually defined anywhere that I could find. I'm guessing it's Conditional? Weighted Per-Decision Importance Sampling?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I was satisfied with the paper's discussion of limitations and societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of off-policy evaluation and shows that it is possible to interpolate between the importance sampling estimator, which is unbiased but high variance, and correcting state distributions, which is low variance but could be very biased since the distributions need to be estimated. The authors showed that the optimal estimator with lowest MSE is indeed taking an intermediate values in the spectrum to mix these two estimators. 

The proposed estimator is derived in a principled fashion, the results are insightful, and the paper is very well written. Generally this paper's contribution are non-trivial yet interesting, and it can definitely be a valuable addition in the vast literature of off-policy evaluation in RL. Some potential drawback of this paper includes simplistic experiments that are aimed only for proof-of-concept, and the restriction to to n-step estimators.  During the discussion phase, the reviewer also recommends doing another round of improvement before publications to study the confounding effect of these two estimators. Please try to do so to improve the (already good) quality of this work. 

In general I believe the merits of this work surpass the improvements required. So I also recommend acceptance.

Decision: Accept (Poster)