Doubly Robust Bias Reduction in Infinite Horizon Off-Policy Estimation
Authors: Ziyang Tang*
Yihao Feng*
Lihong Li
Dengyong Zhou
Qiang Liu
Venue:  (2020)
Keywords: off-policy evaluation
infinite horizon
doubly robust
reinforcement learning

Abstract: Infinite horizon off-policy policy evaluation is a highly challenging task due to the excessively large variance of typical importance sampling (IS) estimators. Recently, Liu et al. (2018) proposed an approach that significantly reduces the variance of infinite-horizon off-policy evaluation by estimating the stationary density ratio, but at the cost of introducing potentially high risks due to the error in density ratio estimation. In this paper, we develop a bias-reduced augmentation of their method, which can take advantage of a learned value function to obtain higher accuracy. Our method is doubly robust in that the bias vanishes when either the density ratio or value function estimation is perfect.  In general, when either of them is accurate, the bias can also be reduced. Both theoretical and empirical results show that our method yields significant advantages over previous methods.

Published as a conference paper at ICLR 2020
DOUBLY ROBUST BIAS REDUCTION IN INFINITE HORIZON OFF-POLICY ESTIMATION
Ziyang Tang
Yihao Feng
The University of Texas at Austin ztang@os. utexas. edu
The University of Texas at Austin yihaoles www.aa.aa...... eddu
Lihong Li
Dengyong Zhou
Qiang Liu
Google Research
Google Research
The University of Texas at Austin iqiang utexas. edu
lihong@google..o com
dennyzhou@google. com
ABSTRACT
Infinite horizon off off-poliiy policy evaluation is a highly challenging task due to the excessively large variance of typical importance sampling (IS) estimators. Recently, Liu et al. (20T8)) proposed an approach that substantially reduces the variance of infinite horizon off- off-policy evaluation by estimating the stationary density ratio, but at the cost of introducing biases due errors density ratio estimation. In this paper, we develop a bias-reduced augmentation of their method, which can take advantage of a learned value funetion improve accuracy. Our method is doubly robust in that the bias vanishes when either the density ratio or value function estimation is perfect. In general, when either of them is accurate, the bias also be reduced. Both theoretical and empirical results show that our method yields significant advantages over previous methods.
INTRODUCTION
key problem in reinforcement learning (RL) (Sutton & Barto 1998) is off-policy policy evaluation: given fixed target policy of interest, estimating the average reward garnered by agent that follows the policy, by only using data collected from different behavior policies. This problem widely encountered in many real-life applications (e.g.. Mur.hh et al. 2001 Li et al. 2011 Bottou et al.)
2013: l'homas et al. 2017). , where online experiments are expensive and high-quality simulators are difficult to build. It also serves key algorithmic component of off-policy policy optimization (e.g..
Dudik et al. 2011 Jiang & Li, 2016: Thomas & Brunskill] 2016 Liu et al. 2019b).
There are major families of approaches policy evaluation. The first approach is to build simulator that mimics the reward and next-state transitions of the real environment (e.g., Fonteneau al. 2013). While straightforward, this approach strongly relies on the model assumptions in building the simulator, which may invalidate evaluation results. The second approach is to use importance sampling correct the sampling bias in off off-policy data, that an (almost) unbiased estimator can be obtained (Liu) 2001] [Strehl
@oteel et al. 2010 Bottou et al., 2013). A major limitation, however, that importance sampling can become inaccurate due high variance. particular, most existing IS-based estimators compute the weight as the product of the importance ratios of many steps in the trajectory, causing excessively high variance for problems with long or infinite horizon, yielding curse of horizon (Liu et al. 2018a).
Recently, Liu et al. (2018a) proposes a new estimator for infinite-horizon off-policy evaluation, which presents significant advantages to standard importance sampling methods. Their method directly estimates the density ratio between the state stationary distributions of the target and behavior policies, instead of the trajectories, thus avoiding exponential blowup of variance in the horizon. While Liu et al.7s s method shows much promise by significantly reducing the variance, in practice, it may suffer from high bias due to the error or model misspecficiation when estimating the density ratio function.
"The first authors contributed equally this work.

---

Published as a conference paper at ICLR 2020
In this paper, we develop doubly robust estimator for infinite horizon off- off-policy estimation, by integrating Liu et al. method with information from an additional value function estimation. This significantly reduces the bias Liu al. (s method once either the density ratio, the value function estimation is accurate (hence doubly robust). Since Liu et al. method already promises low variance, additional bias reduction allows us achieve significantly better accuracy for practical problems.
Technically, our new bias reduction method provides a new angle of double robustness for off -oolic evaluation, orthogonal to the existing literature of doubly robust policy evaluation that solely devotes to variance reduction aJang & Li 2016 Thomas & Brunskill 2016 Farajtabar et al. 2018). mostly based on the idea of control variates (e.g. Asmussen Glynn 2007). Our double robustness for bias reduction is significantly different, and instead yields an intriguing connection with the fundamental primal-dual relations between the density (ratio) functions and value functions (e.g., [Bertseka]] 2000), Puterman 2014). This new perspective can inspire more efficient algorithms for policy evaluation, and lead to unified frameworks for these types of double robustness future work.
BACKGROUND
Infinite Horizon Off-Policy Estimation Let M A,,,, be a Markov decision process (MDP) with state space S, action space A, reward function r, transition probability function T, and initial-state distribution Mo. A policy æ maps states to distributions over A, with ((a ())s) being the probability of selecting given s. The average discounted reward for æ, with given discount y (0.1) is defined
E I'r E
R
E TOWT T-000
lim
where = {st, az, Ti rrJosIST is a trajectory with states, actions, and rewards collected by fol- lowing policy in the MDP, starting from Su Mu- Given a set of trajectories, D {st af ,t problem aims to estimate the average discounted reward R for another target policy (als).
((() Issign0sree collected under a behavior policy To(a]s), the off-policy evaluation
Estimation via Value Function The value function for policy is defined as the expected accu- mulated discounted future rewards started from a certain state: (*(s) Ex E /'r, (0 s]. We use r" r=(()= = E Ba [r(s, (rs))ssss a)] to denote the average reward for state s given policy л. Under the definition, the value function can be seen as a fixed point of the Bellman equation:
V" (s) = r" (s) 7P**
pa V* == (1) (V"(s) (s')], V (I)
where (s) is the average of the next value function given the current state and policy æ; see Appendix[AL. for details.
The value function and the expected reward RD is related in the following straightforward way
Rº (1 (o [V)(s))
where the expectation is with respect to the distribution mo(s) of the initial states 8o at time t.
Therefore, given approximation V of V", and samples Do = {~0 Jisigno drawn from po(s), we can estimate 1TT by
(8)
7)
VAL
no
Note that this estimator off- off-policy in nature, since it requires no samples from the target policy m.
Estimation via State Density Function Denote d-) as average visitation of in time step t.
The state density function, or the discounted average visitation, defined as:
IT 7ddrel)) = -1 (1-7) E Ed)d
d (s) = lim T-420
Eto
For average case when 7 = 1, the definition of H² is the same. However, the definition of value function is different. We will assume 7 < throughout our main paper for simplicity; for average case check appendix B for more details.
2

---

Published as a conference paper at ICLR 2020
where (1 () can be viewed as the normalization factor introduced by Ei=o
Similar to Bellman equation for value function, the state density function can also be viewed as a fixed point the following recursive equation (Liu et al. 2018a Lemma 3):
d= (5') (1 7)')) TT"
where d"d=(s)= = Σ (()ss (3)
The operator T is adjoint operator of p used in T see Appendix for discussion.
the density function dy known, provides an alternative way for estimating the expected reward RT, by noting that
We that both density function d and value function V can be used to estimate the expected reward R., We clarify the connection in detail Appendix A.I
Off-Policy State Visitation Importance Sampling Equation can not directly used for off- policy estimation, since it involves expectation under the behavior policy [iu et al. (2018a) addressed this problem by introducing a change of measures via importance sampling:
π <(ass)
dx(x)
R = Egndang (- W Wn/so
r(s, a)
with
Wx/mo (8)
(5)
Tu(als)
d (s)
where W=/mo mo (s) is the density ratio function of d, and dua.
Given an approximation of w//oo and samples = (s) ai heismogiss collected from policy no, we can estimate R as:
!0
n
T
T(a)ss))
n
T Taa (8) (2)
Rsis
i
(0())))
Ti To (s;))))))
w
(6)
(6)
To (a,
(4) (4)
i=1
where Z is the normalized constant of the importance weights.
3 DOUBLY ROBUST ESTIMATOR
Doubly robust estimator is first proposed into reinforcement learning community to solve contextual bandit problem by Dudik al. (2011) as an estimator combining inverse propensity score (IPS) estimator and direct method (DM) estimator.
Jiang Li (016) introduce the idea of doubly robust estimator into off off-policy evaluation rein- forcement learning. It incorporates an approximate value function as control variate to reduce the variance importance sampling estimator. Inspired by previous works, we propose new doubly robust estimator based on our infinite horizon off-policy estimator R
3.1 DOUBLY ROBUST ESTIMATOR FOR INFINITE HORIZON MDP
The value-based estimator A [V] and density-ratio-based estimator Riss [ are expected to be accurate when V and i are accurate, respectively. Our goal is to combine their advantages, obtaining doubly robust estimator that is accurate once either V or w is accurate.
To simplify the problem, it is useful to examine the limit of infinite samples, with which R [V]
and Reys (7) converge to the following limit of expectations:
RSs == lim RSss w = Σ (s))
7,70000
R [ : lim RE V (1 (11))) Σ (s)))u(s).
(8)
230
3

---

Published as a conference paper at ICLR 2020
Here and throughout this work, assume V and @ are fixed pre-defined approximations, and only consider the randomness from the data D.
A first observation is that expect to have r se V --p=V V by Bellman equation ① when V approximates the true value V Plugging this into Rais [ in Equation 7 we obtain the following "bridge estimator", which incorporates information from both w and V:
bridge
W
Σ
(>> dao (s)((s),
(9)
where operator p defined Bellman equation defined by
TT]
The corresponding empirical estimator
Roddgee
7
10
(o)()))
(((()) (1) T(ai(si) p(olft)).
(10)
7
72
To(ai)ss))
where 71 normalized constant of important weights each empirical estimation.
Ei=1
EE r'ū(s))
T-1 y 7 (0s )Bx/ (at are self- and Z = E'= 2t=
(3)
However, directly estimating R² using the bridge estimator R Rinigee w) yields a poor estimation, because it includes the errors from both @ and V and can be "doubly worse". However, we can construct our "doubly robust" estimator by canceling Risiage (V, (t) out from Riss [ū) and Re [V]:
P w
Σ r (s)dno + (1 7) Σ (s))o(()
Σ (v(s)) (P) dao ())))))).)))))))))))))))))
Riis [+]
Re [V]
Rigiogo (V,
(11)
And its corresponding empirical estimator can be written as:
R
Wi
R ir
+ R [V] R bridge (V, [,
Doubly Robust Bias Reduction The double robustness of RR (V, ui reflected in the following key theorem, which shows that it is accurate once either V or w is accurate.
Theorem 3.1 (Doubly Robustness). Let RTglV @i == limmo.n.T-ss Rix! LV, O) be the limit of RōR when it has infinite samples. Following the definition above, we have
R [V, [w - R.T Eswitog (=)())
(12)
where Eq and em errors of V and w, respective, defined follows
d w(s).
eD (ss)
E (s)
The error Eg of û is measured by the difference with the true density ratio d, (s) dno (s), and the error Eq V V is measured using the Bellman residual.
From the theorem we can see that, V is exact ( = V*), we have Ep = 0; if w is exact (@ = dx/ dno), have e 0. Therefore, our estimator is consistent (i.e., lim -o oo
Rij V @ R*)
either V or are exact. The estimator is thus doubly robust this sense. In contrast, R ( and R [V] can be more sensitive to the error of to and V. respectively:
R R
Egnde, (Sa(s))(ss)
R R Egndry (s)E
Variance Analysis Different from the bias reduction, the doubly robust estimator does not guar- antee the reduce the variance over [0) or [V] in general. However,
show in the following result, we can break the variance of Ri [V. ( into two parts. The first the variance of [V] which is often relatively small. The second is generally no greater than the variance of
Rg [w]. and can be much smaller when V R V Moreover, R [V] and R (0] avoid the curse of horizon by design, so their variances tend to be much smaller than the corresponding estimators that apply IPS correction on the trajectories.
4

---

Published as a conference paper at ICLR 2020
Algorithm 1 Infinite Horizon Doubly Robust Estimator
Input: Transition data DTo- = {s; dz ((()) Jisign,osesT from policy mo:
Du { Jigsgmo be samples from initial distribution μou target policy x, value function estimate V: density ratio estimate 0.
Estimation: Use RōR in (IT) to estimate R" using sample from and Do-
Proposition 3.1 (Variance Analysis), Assume Ro VV 0) is estimated based on sample Do Po and Dao dag. which we assume be independent of each other. We have
VarDo,
RBR
[ö] = VarDa [
+ VarD=a
[ ūi)
(13)
with R V, 20 = Rg R5)s((0 [0]]
Bridge IV, úi = ED., (+)( and (v) the TD error of V,
(g(() r - V(()) + (s)
with r- (s) VarD.n RR [V, T)) can be small when V is close to the true value V*, or (v(s) 20
((s,a)t(a)s) ()) (o)ss), (s)
T(dls)/=oalssVV()
Therefore,
From the proposition we can see that when V is close to the true value V*, the variance of the residual Ep may be negligibly small compared to the variance of R [w]. A further comparison of the variances between R [V, w] and Rgis [0) is provided in Appendix A.3 In the case when the TD error Ey is negligible, we have VarD,. R [V, @i]
VarD,
[ Typically, the variance AL
of [ is smaller than Riis [w] since the variance of importance sampling methods heavily depends on the effective sample size, which less controllable compared R [V]. Therefore, the variance of our doubly robust estimator may even be smaller than that of R [w) in practice.
The variance in (33 is sum of terms because of the assumption that samples from fnn and d are independent. In practice, they have dependency but it is possible to couple the samples from μoo and dr, certain way to further decrease the variance, which we leave future work.
Proposed Algorithm for Off-Policy Evaluation Suppose we have already obtained V and ú as estimations of V and Wn/mo. respectively, we can directly use equation [1] to estimate R A detail procedure is described in Algorithm
DOUBLE ROBUSTNESS AND LAGRANGIAN DUALITY
In this section, reveal surprising connection between double robustness and Lagrangian duality. We show that our doubly robust estimator is equivalent to the Lagrangian function of primal-dual formulation of policy evaluation. This connection of interest in itself, and may provide a foundation for deriving more effective algorithms.
We start with the following classic, optimization formulation of policy evaluation (Puterman,
2014):
Rd min { (1 - (1->)) (s)
s.t. V(s) 2 r. +ss
Vs
(14)
where we find V maximize its average value, subject to inequality constraint on the Bellman equation. It can be shown that the solution of (14) is achieved by the true value function VA hence yielding expected reward R
Introducing a Lagrangian multiplier 2 O. we can derive the Lagrangian function L(V, p) of 14
L(V.)) = (1 (1- - Σ (s)) - Σ ((s)(V(s) r" (P)+)**(((s))
(15)
Comparing L(V,p) with our estimator R [V, w in we can see that they are in fact equivalent in expectation.
5

---

Published as a conference paper at ICLR 2020
Theorem 4.1 (Primal Dual). 1) Define /// (s)
p(a) dugg (s)
We have
L(V. p) = RRR V, Wp/nol and hence
L(V. = L(V*, .p) R" A V.
which suggests that L(V. p) is "doubly robust" in that it equals R if either V V or p dn
II) The primal problem (14) forms a strong duality with the following dual problem,
RD
max
(p(s))
p(s') (1 >))o0(s) +TT"
As yot) (16)
P20
where T is defined in
This shows that the dual problem is equivalent to constraint p using the fixed point equation 3 and
maximize the average reward given distribution Since the unique fixed point of (3) is dz (s) )), the
solution of (16) naturally yields the true reward HºT hence forming zero duality gap with (14).
is natural to intuit the double robustness of the Lagrangian function. From (T)). L(V,p) p) can be viewed as estimating the reward R using value function with correction of Bellman residual (V -T >P*V) If V = V*, the estimation equals the true reward and the correction equals zero. From the dual problem (16). L(V. p) can be viewed as estimating Rd using density function p. corrected by the residual (p - (1 7)100 7T" p). We again get the true reward if dz.
turns out that we can use the primal-dual formula when y for the average reward case. We clarify it in appendix B
obtain the double robust estimator
Remark The fact that the density function dz forms a dual variable of the value function V is widely known in the optimal control and reinforcement learning literature (c.g.. Bertsekas [2000] Puterman 2014: de Farias & Van Roy. 2003), and has been leveraged in various works for policy optimization. However, does not seem to be well exploited in the literature of off-policy policy evaluation.
RELATED WORK
Off-Policy Value Evaluation The problem of off-policy value evaluation has been studied exten-
sively in contextual bandits and MDPs (Fonteneau et al.) 2013 Li et al. 2015 Jiang & Li 2016 2016: Liu et al., 2018b) Farajtabar al. [018)] Hanna et al. 2019 Xie et al. 2019:Rowland et al. 2019). However, most of the existing works are based on importance sampling (IS) to correct the mismatch between the distribution of the whole trajectories induced by the be-
Thomas & Brunskill
havior and target policies, which faces the "curse of horizon" (Liu et al. long-horizon (or infinite-horizon) problems.
2018a when extended to
Several other works (Guo al.
& Mannor 2017 Liu et al. 2018a
Gelada & Bellemare
2019; Nachum et al. 2019: Liu et al. 2019a) have been proposed to address the high variance issue the long-horizon problems. Liu al. (2018a) apply importance sampling on the average visitation distribution of state-action pairs, instead of the distribution of the whole trajectories, providing an effective approach to break "the curse of horizon". However, they require to learn density ratio function over the whole state-action pairs, which may induce large bias. Our work incorporates the density ratio and value function estimation, which significantly reduces the induced bias of two estimators, resulting a doubly robust estimator.
Our work is also closely related DR techniques used in finite horizon problems (Murphy et al. 2001 Dudik et al. 2011: Jiang & Li 2016: Thomas & Brunskill] 2016 Farajtabar et al. [2015 8). which incorporate an approximate value function as control variates to estimators. Different from existing DR approaches, value function, which reveals the relationship between density (ratio) learning (Liu et al.) 201 8a) and value function learning. Based on this interesting observation, we further obtain the doubly robust estimator for estimating average reward in anfinitehhorizo problems.
work is related to the well known duality between the density and the
A recent work (Xie et al. 2019) has also explored the idea of tracking marginal state distribution shifts at every single time step in an episode, instead the stationary state distribution across all time steps (Liu al. 2018a). It provides additional benefits for understanding and analyzing problems

---

Published as a conference paper at ICLR 2020
On Policy (Monte Carlo)
Naive Average Weighted DR
Density Ratio
Value Estimate
Our Method
10-2
10
10
10-4
10-3
10
10
10
10-6
10-8
10
10
10
10
10
10"
(a) MSE
(b) Bias Square
(c) Variance
10-15.
10-30
10-30
10-2.
10-35
10-35
10-35
4
10 10-45
10
10
4.0
500
1000
1500
0.0
0.2
0.6
0.8
1.0
0.0
0.2
0.4
1.0
(d) MSE with H/ changes
(e) Bias square with changes
(f) Bias square with / changes
Figure 1: Off Policy Evaluation Results on Taxi. Default parameter, discounted factor = 0.99,
mixed ratio a = 3 1, horizon length H = 600. For (a)-(c) the x-axis the number of trajectories and y-axis corresponds to MSE, Bias Square and Variance, respectively. For (d) we fix the total number of samples (number trajectories times horizon length) and change the horizon length as x-axis and observe the MSE. (e) and (f) show the change the mixed ratio of B with the change of bias. We repeat each experiment for 1000 runs.
such short horizon and time-variant MDPss They call this approach marginalized importance sampling (MIS). Later on, Kallus & Uehara (2019a) incorporate the DR technique to improve the MIS estimator. Independent of this work, Kallus & Ucharal (2019b); Uehara (2019) extend previous works to propose estimators can be viewed as variant of ours.
Primal-Dual Value Learning Primal-dual optimization techniques have been widely used for off-policy value function learning and policy optimization (Liu al. [2015] Chen & Wang 2016 Dai et al. 2017: 2018 Feng et al. 2019). Nevertheless, the duality between density and value function has not been well explored in the literature of off policy value estimation. Our work proposes new doubly robustness technique for off- off-policy value estimation, which can be naturally viewed as the Lagrangian function of the primal-dual formulation of policy evaluation, providing an alternative unified view for off policy value evaluation.
EXPERIMENT
In this section, we conduct simulation experiments on different environmental settings to compare our new doubly robust estimator with existing methods. We mainly compare with infinite horizon based estimator including state importance sampling estimator (Liu al. 2018a)) and value function estimator. We do not report results on the vanilla trajectory-basse importance sampling estimators because their significant higher variance, but we do compare with the doubly robust version induced by Thomas & Brunskill (2016) nself-normalized variant of Jiang & Li (2066)). In all experiments compare with Monte Carlo and naive average as Liu et al. (2018) Sa) suggested. The ground truth for each environment is calculated by averaging Monte Carlo estimation with very large sample size.
7

---

Published as a conference paper at ICLR 2020
* On Policy (Monte Carlo)
Naive Average Weighted DR
Density Ratio
Value Estimate
Our Method
10
10
10-40
10:1
10
10-2
10-1-
10
10-
10-2
10-3
10-2 20
40
60
200
560
10
20
40
80
200
500
20
40
80
200
500
10-2
500
800
700
650
1000
Sianpli
Semple Size
Semple
Hotizon
(a) MSE
(b) Bias Square
(c) Variance
(d) MSE with H changes
Figure 2: Off Policy Evaluation Results on Puck-Mountain. We set discounted factor 0.995 as default. For (a)-(c) we set the horizon H = 1000 and the x-axis is the number of trajectories for used for evaluation. For (d) we fix the total number of samples and change the horizon length.
10"
10
10-3
10a
10
10-1
10-2
10-2
10
10-1
10
10-2
10-1
10-3
10-1
20
40
80
200
500
20
40
80
200
500
20
80
200
500
500
600
700
850
1000
Sample Size
Sample Size
Sample Size
Horizon
(a) MSE
(b) Bias Square
(c) Variance
(d) MSE with H changes
Figure 3: Off Policy Evaluation Results on InvertedPendulum-v2. We set discounted factor = 0.995 as default. For (a)-(c) we set the horizon H = 1000 and the x-axis is the number of trajectories for used for evaluation. For (d) we fix the total number of samples and change the horizon length.
Taxi Environment We follow Liu et al. (2018a)'s 's tabular environment Taxi, which has 2000 states and 6 actions in total. For more experimental details, please check appendix [.]
We pre-train two different V. and V trained with a small and fairly large size of samples, respectively, where V is very close to true value function y but V is relatively further from it. Similarly we pre-train ā and f Rs d,. For estimation we use mixed ratio a, B to control the bias of the input V, where V =av (1 a and p B + (1 3)
Figure T (a) show results of comparison for different methods as we changing the number of trajectories. We can see that the MSE performance of value function(R and state visitation importance sampling( RRgis) estimators are mainly impeded by their large biases, while method has much less bias thus it can keep decreasing as sample size increase and achieves same performance as on policy estimator. Figure d) shows results if we change the horizon length. Notice that here we keep the number of samples to be the same, so if we increase our horizon length we will decrease the number trajectories in the same time. We can see that our method alongside with all infinite horizon methods will get better result as horizon length increase. Figure (igureee)-Ef [fe)-(f) indicate the "double robustness" of our method, where our method benefits from either a better V a better p.
Puck-Mountain Puck-Mountain is an environment similar to Mountain-Car except that the goal of Puck-Mountain is to push the puck as high as possible in local valley, which has continuous state space of R and a discrete action space similar to Mountain- Car. We use the softmax functions of optimal Q-function as both target policy and behavior policy, where the temperature of the behavior policy is higher (encouraging exploration). For more details constructing policies and training algorithms for density ratio and value functions, please check appendix C.2
8

---

Published as a conference paper at ICLR 2020
Figure 2 (c) show results of comparison for different methods changing the number of trajectones. Similar to taxi, we find our method has much lower bias than density ratio and value function estimation, which yields better MSE. In Figure the performance for all infinite horizon estimator will not degenerate as horizon increases, while finite horizon method such as finite weighted horizon doubly robust will suffer from larger variance as horizon increases.
InvertedPendulum InvertedPendulum a pendulum that has its center of mass above its pivot point. We use the implementation of InvertedPendulum from OpenAl gym (Brockman et al. 2016), which is a continuous control task with state space in R and we discrete the action space to be {-1, 003,, 0.2, 0, 0.2, 0.3, 1}. More experiment details can be found in appendix C.2
In Figure 3 ac) our method again significantly reduces the bias, which yields a better MSE comparing with value and density estimation. Figure also shows that our method consistently outperforms all other methods as the horizon increases with fixed total timesteps.
7 CONCLUSION
In this paper, we develop a new doubly robust estimator based on the infinite horizon density ratio and off policy value estimation. Our proposed doubly robust estimator be accurate long as one of the estimators are accurate, which yields significant advantage comparing to previous estimators. Future directions include deriving more novel optimization algorithms learn value function and density(ratio) function by using the primal dual framework.
ACKNOWLEDGEMEN
This work is supported in part by NSF CRII 1830161 and NSF CAREER 1846421. We would like to acknowledge Google Cloud for their support.
REFERENCES
Søren Asmussen and Peter W Glynn. Stochastic simulation: algorithms and analysis, volume 57. Springer Science & Business Media, 2007.
Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2nd edition, 2000. ISBN 1886529094.
Léon Bottou, Jonas Peters, Joaquin Quinonero-Candela, Denis Xavier Charles, D. Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. Counterfactual reasoning and learning systems: The example of computational advertising. Journal of Machine Learning Research, 14:3207-3260, 2013.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint T00.v::660600154440 2016.
Yichen Chen and Mengdi Wang. Stochastic primal-dual methods and sample complexity of rein- forcement learning. arXiv preprint arXiv: 2016.
Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual kernel embeddings. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1458-1467, 2017. CoRR abs/1607.0445
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED: Convergent reinforcement learning with nonlinear function approximation. In Proceedings of the Thirty-Fifth International Conference Machine Learning (ICML), pp. 1133-1142, 2018.
Daniela Pucci de Farias and Benjamin Van Roy. The linear programming approach to approximate dynamic programming. Operations Research, 51(6):850-86 2003.
Miroslav Dudík, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning (ICML), pp. 1097-1104, 2011.

---

Published as a conference paper at ICLR 2020
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 1446-1455, 2018.
Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the bellman equation. Neural Information Processing Systems (NeurIPS), 2019.
Raphael Fonteneau, Susan A. Murphy, Louis Wehenkel, and Damien Ernst. Batch mode reinforcement learning based on the synthesis of artificial trajectories. Annals of Operations Research, 208(1): 383-416, 2013.
Carles Gelada and Mare Bellemare, Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3647-3655, 2019.
Zhaohan Guo, Philip S. Thomas, and Emma Brunskill, Using options and covariance testing for long horizon off- off-policy policy evaluation. In Advances in Neural Information Processing Systems 30 2017.
(NIPS), pp.
Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In Proceedings of the 34th International Conference Machine Learning (ICML), pp. 1372-1383, 2017.
Josiah Hanna, Scott Niekum, and Peter Stone. Importance sampling policy evaluation with an estimated behavior policy. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 2605-2613, 2019.
Nan Jiang and Lihong Li. Doubly robust off-policy evaluation for reinforcement learning. In Proceedings of the 23rd International Conference on Machine Learning (ICML), pp. 652-661, 2016.
Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evalua- tion markov decision processes. arXiv preprint 190i: 085266, 2019a.
Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon: Double reinforcement learning in infinite-horizz processes. arXiv preprint (0t9::/990000000 2019b.
Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. Unbiased offline evaluation of contextual- bandit-based news article recommendation algorithms. In Proceedings of the 4th International Conference on Web Search and Data Mining (WSDM), pp. 297-306, 2011.
Lihong Li. Rémi Munos, and Csaba Szepesvári. Toward minimax off-policy value estimation. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 608 616, 2015.
Bo Liu, Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. In UAI, pp. 504-513. Citeseer, 2015.
Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer Series in Statistics. Springer- Verlag, 2001. ISBN 0387763694.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinite- horizon off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5361- 5371, 2018a.
Yao Liu, Omer Gottesman, Aniruddh Raghu, Matthieu Komorowski, Aldo Faisal, Finale Doshi- Velez, and Emma Brunskill. Representation balancing mdps for off- policy evaluation. In Advances in Neural Information Processing Systems, pp. 2644-2653, 2018b.
Yao Liu, Pierre-Luc Bacon, and Emma Brunskill. Understanding the curse of horizon in off-policy evaluation via conditional importance sampling. arXiv preprint arXiv:1910.080 2019a.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. arXiv preprint arXiv: 1 1904.08473 2019b.
10

---

Published as a conference paper at ICLR 2020
Susan A. Murphy, Mark van der Laan, and James M. Robins. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 96(456):1410- 1423, 2001.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostie estimation of discounted stationary distribution corrections. Neural Information Processing Systems (NeurIPS), 2019.
Martin L. Puterman. Markov Decision Processes.: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
Mark Rowland, Anna Harutyunyan. Hado van Hasselt, Diana Borsa, Tom Schaul, Rémi Munos, and Will Dabney. Conditional importance sampling for off-policy learning. arXiv preprint ArXiv:1910.07479, 2019.
Alexander L. Strehl, John Langford, Lihong Li, and Sham M. Kakade. Learning from logged implicit exploration data. In Advances in Neural Information Processing Systems 23 (NIPS-10) pp. 2217-2225, 2010.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, March 1998. ISBN 0-262-19398-1
Philip S. Thomas and Emma Brunskill. Data-efficient off off-py policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference Machine Learning (ICML), pp. 2139-2148, 2016.
Philip S. Thomas, Georgios Theocharous, Mohammad Ghavamzzdeh, Ishan Durugkar, and Emma Brunskill. Predictive off-policy policy evaluation for nonstationary decision problems, with applications to digital marketing. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 4740-4745, 2017.
Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and Q-function learning for off off-policy evaluation, 2019. 1rXiv:1910.12800
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Optimal off-policy evaluation for reinforcement leam- ing with marginalized importance sampling. Neural Information Processing Systems (NeurIPS), 2019.

---

Published as a conference paper at ICLR 2020
A PROOF
A.1 TRANSITION OPERATOR FOR BELLMAN EQUATION
For simplicity, we define the following two operators thorough our proofs to simplify our notations.
Definition A.I. Given a policy π and the unknown environment transition T, we define T and p over any function f 8 - R
(T")) Σ [(((saa))((())
()) Σ T(s
Using these operator notations, we can rewrite the above two recursive equations as:
V r" +PVVV d = 71-7)u0 + dT.
where (8)) = (- a)].
These transition operators have the following nice adjoint property.
Lemma A.2. For two function f and if the following summation is finite, will have
(PP (T))))
(17)
Proof.
((P'n)))0(5) = E [ g(s)
Es(') [I(51)50)7((1))00)
(T))
Using this property we can actually using Bellman Equations re-derive the two different way get R
Σr 1== I'r
R lim E,00n T4000
Σ 7t
( (0))
Ev (I 7TT) d=(s)
Σ CII-PP' -PP") (*(dd()
(r)ss)d
12

---

Published as a conference paper at ICLR 2020
A.2 PROOF OF THEOREM 3.1
Theorem 3.1 (Doubly Robustness). Lel Do T6 =- lim TT -00 D2 V,,0 ( be the limit of Pox when it has infinite samples. Following the definition above, we have
R [V, [w] R²= Bswding (em())) (+)]
(12)
where Ep and E are errors of V and w. respective. defined as follows
(x) i())
- (()))-r(()) (()))==()))(())--p
c@ d (s)
The error Eq of i is measured by the difference with the true density ratio da (s) dao (5), and the enror Eq of is measured using the Bellman residual.
Proof. Using the property of the operator, we can rewrite (1 - ())(ss) using Bellman equation as dx 7T dz thus we have
R V (11-7) -1 7) Σ (s))(((s)
Σ (ss (d= - dx) (s)
(P-
and similarly if we break r" as (I-
VV (I-
for sis i we have:
Riss [w] = Σ (I yp v (s)d
where da = dro T for short.
Compare with R =
V (s)d we can see the main difference between Ras and RTAL with H are they replace da and dæ and V with V respectively. If we add them together and minus the connection estimator, we have we will have:
R V, u R" =Riis [w] + R Raridge IV, [] Rd
Σ ( 7P*) V (s)da( (I yp=) (s)dr((s
- -I - ypa) (s)d - - -p=) V (*))d<(())
Σ (1- (V- (s)] ds)
dno (s))p())))E
= E -Egrdd lEp (s))
V where the third equation because (P- (V* V (1- (I (p-p x - (P-PP=) V. Similarly, the bias for RRR and Riis can be calculated as:
RSis [7]
R (T 7D") (*) (da(s) - (s))
(s)dr
= E E (=)(
and
R
11 R (I (p)) (=)))d++
(n (s)d (s)
= =Banden (Wa) (5)=p(s)}
13

---

Published as a conference paper at ICLR 2020
A.3 MORE DISCUSSIONS ON THE VARIANCE IN PROPOSITION 3.1
Recall the proposition
Proposition 3.1 (Variance Analysis). Assume RT [V W) is estimated based sample Do po and Dro ~ drg- which we assume to be independent of each other. We have
VarDu,
(Ribel (V, mi] VarrD
[ [RiaL
VarDzo
R
V 0
(13)
with Ris,, [,ū) = RSsis (7))
Ribridee [V, [i] = =EDD. [F and (b) the TD error of V,
(p(() p= -s))
with (s) r(s, (a)ss) /o mo(ass). (=)
(a Dar (R [V, wi) can be small when V is close to the true value V*, or (p(s) =0
Therefore,
Proof. Since PR 0J Ma [V] + R [V, and we have the assumption that the samples from Do and Dmo are independent, the proposition comes immediately.
Intuitively, the variance of R pieces of orthogonal randomness of R [V, w and R [ in details, and we state the analysis as the following theorem.
w less than Ris We want to quantitatively study every
Theorem A.3. Let VarDro
IV @i] be defined in Proposition 3.1 and suppose the normalization is constant (and hence ordinary importance sampling which is unbiased). Then we can furthe break into two terms
P
Varp.o
R V. w0
Var (()) +E (())) (81(8, + 78,((,,
(18)
where (s) = (ss)
is the Bellman residual(not the empirical one), 81 (s, a) s(als)
mo(a|s) mo(a|s) (s, (s) is the randomness for action and 62(s, a, ) na(a|e) V(s)) p Vs)(s is the
I(als))
randonmess for transition operator over over function V. Both on and 6g is zero mean we condition s.
Compared with Var
R [ we have:
1 (
Var 12 [0]]
(19)
Proof. R [V, () can be written as
1 Σ ((s) (Bx/ (als) (B. -V()).
n2
where B2/mo is short for =(als) mo(ale)
We can break (als) - ((s) into
B (c)s)(((())))) + +D())) - ((s)
-(- + (Ba/zo (als)r(s,)) r (s)) +7 (8./n, (s)
60
=- + +1 + 70 (s,
14

---

Published as a conference paper at ICLR 2020
where Ep = P" is the Bellman residual and the if we condition have the expectations for dj and ò2 are Also notice that we condition over s then Ep(s) become constant thus it is independent to 61 and 62. Thus we have:
Var (()) +
Var
Var [((s)Ep(s) + T0 - (d
Therefore have:
(1 21 Var (so))+ [K()) +B ()) +))
Var RRR [V,
no
For Var Rais ④ have:
1 Var ((()))))))
Var
Rai [ū]
n
Var (ū())) (s) (())))))))))))))
(Var (+(()) [+)) x (8) (s)
From the theorem we can see that the variance of residual comes from two parts, the majority part relies on the variance of [s)] is usually much smaller than rd as the majority variance of state visitation importance sampling. When V Rs V*, (s) O, the variance of residual only comes from 5j (s, a) and 02 a, s').
In practice when we get trajectories data from uu, to get samples uniformly from dzo- we can either draw sample s, depends on its discounted factor 7 or add an importance weight y as we did in our empirical estimator equation (6) and equation (10).
A.4 PROOF OF THEOREM
Theorem 4.1 (Primal Dual). I) Define Wp/zo (s)
p(x) dzg (3)
We have
and hence which suggests that L(V, p) is "doubly robust" in that it equals RR if either V V p dn.
L(V, p) Rox V, Wppmol
L(V, = L(V= P)) R", VV,
II) The primal problem
[4] forms a strong duality with the following dual problem,
R"
max
p((s)
s.t. p(s') = (01-))po(s))
p(s)) (
As v (16)
P20
where T is defined in 3
Proof. The Lagrangian can be written as:
L(V.p) =(1 - 7) Σ (s(s)
(V(s)
- (s) - vP)
Σ ())())
(I- V(s) Σ (s))r((s)
-1Grngg V N.x0//mo
= = (mp/
E - (1--)))(()VV())
(T- -u- p(s)) Σp(s)
Σ ((1 m)) - -(I- + (s)))r(ss.
15

---

Published as a conference paper at ICLR 2020
We that the Lagrangian L(V, p) is actually our doubly robust estimator RiR IV, w/ p//50 From the last equation we can derive our dual as:
Ed(srr
max P20
p(s) (1-7)u000) + >TTTp(s), Vs.
B DOUBLY ROBUST ESTIMATOR FOR AVERAGE CASE
B. PRIMAL DUAL FRAMEWORK
We start from primal dual framework to get our doubly robust estimator similar to section g To estimate the average reward of given policy æ,, consider solve the following linear program- ming:
[(ss)=((s)
max P20
p(s) =, TT
TT)s)) Vs,
(20)
where p(s) the stationary distribution of states under P=, and the objective is the average reward given
Consider the Lagrangian above linear programming:
L(V,p,0) (((s)r - ( -T - -5( E p(s) 1)
=
-()) +
(21)
From Equation 21
get the dual formula as:
min
V.a
s.t.
E
(
2 0, Vs,
(22)
where V(s) is the value function and ū is the average reward we want to optimize.
Notice that in average case, V (8) can viewed as the fixed-point solution to the following Bellman equation:
4" (8) Eg alsod, (V*((') = E (r(s, T..
Note that this explains the constraint and only if pick R" find V to guarantee the - -M - (s) 2 0 holds true.
constraint 5 +
B.2 DOUBLY ROBUST ESTIMATOR
We want to build the doubly robust estimator via the lagrangian. However, the Lagrangian consist of three term p. V and J. It is counter-intuitive we already given estimator of R into our estimator.
better way solve this problem is to remove the constraint p(s) 1, but we divide it as an self-normalization. Then our Lagrangian becomes
L(V. p) p()(s)r (s) E. ((s)(((s)- -T*
Ep(s)
which can be utilized to define the doubly robust estimator for average reward.
16

---

Published as a conference paper at ICLR 2020
Definition B.1. Given learned value function ((s) for policy and estimated density ratio (s) for wx/m0 (8), we define
RØ [, 00 ExanSED ((s) BB//o (al))r(al)(((+((())))))
EeED w(s)
where Br/sa (a|s) x(als) To(a]s]
Similarly to Theorem
3.1
we will have our double robustness for our average doubly robust estimator:
Theorem B.2. Suppose we have infinite samples and we can get
Exnddr
((s) (=((s) ((5) + ((s)+P*V(S (()
R [V, u]
E Bandro [(({)]
Then we have where ep and a are errors of V and w, respective, defined as follows
R V, [0 R = Bendoo {=)())E(())
(23)
((s)
(s)
Ep(s) Tx - - + -=v - R
E
Egndan (()s)
E
dio (s)
Proof. A key observation is that
Eand [wn/so (s)Ep (s)] = Egnd, (T*(() - ((()) + (s)) - Ra
(Egndy (s)] R + Egnd, (-V P=)(s))
=0
Thus we have
R |V, W6
Rt= =ooddoo
((s)
(R +ep(s)) Rr
Egnd n
(s))
((s) (8)
E, Eg-doo
((()s 34 (8)
Egnda
((s)
-E
Egnday (m)] (p())
Eandep (W (s)
= -Egnden
Similar to discounted case we have RT [V, T] R if either @ or V is accurate.
17

---

Published as a conference paper at ICLR 2020
C EXPERIMENTAL DETAILS
C.I. TABULAR CASE: TAXI
Behavior and Target Policies Choosing We an on-policy Q-learning get sequence of policy To, 11 1 #19 as data size increases. We pick the last policy T19 (almost optimum) as our target policy and iTIs as our behavior policy guarantee that those policies are far away. We set our discounted factor 0.99.
Train V and ñ Separate from testing, we use a set of independent sample to first train value function V and density function P. Both and p have bias due to finite sample approximation.
For training V and P. we choose to Monte Carlo method to estimate V and p. We first the finite samples to get an estimated model ['s' |s, a) and rewards function f(s, a) and do- Then we solve the following linear equation (by iteration like power method, which is actually Monte Carlo):
V(s) Σ ((
(5, a(, Σ (d)ls,a))(()))
(s, = (s)))
p(s) = (1 - ()) + Tiss'sss a))
8,a
Estimate RD Using V and / We put V. and p into the Lagrangian equation 15) as our doubly robust estimator. For those states we haven't 't visited, we set (s)) and p(s) as 0 and we nolm-normalized the p to get fair estimation.
C.2 CONTINUOUS STATES OFF-POLICY EVALUATION
Evaluation Environments We evaluate method on two infinite horizon environments: Puck- Mountain and InvertedPendulum.
Puck-Mountain is environment similar Mountain-car, except that the goal of the task is push the puck as high as possible in local valley whose initial position is at the bottom of the valley. If the ball reaches the top sides of the valley, will hit roof and changes the speed to its opposite direction with half of its original speeds. The rewards was determined by the current velocity and height of the puck.
InvertedPendulum is pendulum that has its center of mass above its pivot point. It is unstable and without additional help will fall over. We train a near optimal policy that can make the pendulum balance for a long horizon. For both behavior and target policies, we assume they are good enough to keep the pendulum balance and will never fall down until they reach the maximum timesteps. We use the implementation from OpenAl Gym (Brockman et al. 2016) and changing the dynamic by adding some additional zero mean Gaussian noise to the transition dynamic.
Behavior and Target Policies Learning We use the open source implementatior of deep Q- learning to train a 32 x 32 MLP parameterized Q-function to converge. We then use the softmax policy of learned the Q-function the behavior policy To, we set a relative large temperature which encourages exploration. We set the temperature of the behavior policy To = 1.88 for Puck-Mountain and To 1.50 for InvertedPendullm respectively.
the target policy x. which has default temperature
1. For
Training of density ratio (s)) and value function (ss) We use a seperate training dataset with 200 trajectories whose horizon length is 1000 learn the density ratio (s)) and the value function
18

---

Published as a conference paper at ICLR 2020
Algorithm 2 Optimization of density ratio w
Input: Transition data D = {s;, a, 8/, ri Fi from the behavior policy Wo: a target policy и for which want to estimate the expected reward. Discount factor y E (0, 1), starting state
Du = {5j (0) );== from initial distribution.
Initial the density ratio ((s) vna (s) to be a neural network parameterized by 0, f(s) - (s(()
to be neural network parameterized by 3. We need ensure that the final layer of is softmax layer.
for iteration = I.2....,T do
Randomly choose a batch M S fi.....,e n uniformly from the transition data D and a batch Mo S (1..... m) uniformly from start states Dg-
for iteration = 1,2...., K do
Update the parameter B by B + 3 Eg V VeL(wo, 08), where
[wo, fa)
(wu(()) - rwo(s)) π (a:ls;)) 1 {u(a:(s;)
(16))1165) - -(1-7) |Mol JEMo
Σ f(s))
IM
EM
end for Update the parameter 0 by + - Eg VoL(ws end for
Output: the density ratio = wp-
Algorithm 3 Optimization of value function
Input: Transition data D {st, d2 si, rx) r= from the behavior policy un; a target policy æ for which we want to estimate the expected reward. Discount factor 7 E (0, 1).
Initial the value function (s) = (s) ) to neural network parameterized by o. f(s) = fo(s) to be neural network parameterized by B.
for iteration = 1,2....,T do Randomly choose batch M S {l...., ......,,) n uniformly from the transition data D. for iteration 1,2...., K do
Update the parameter / by B + 3 + V (s).. where
L(V f2)
Σ
((va(s)- T((:(ss)
1 (r= + -Vo((1)) fs(s.) 2 fs(:s)
M
(o(a)(s;)
EEM
end for Update the parameter & by o + 0 -o V VoL end for
Output: the density ratio i = Vg-
(s). For the training of density ratio, we adapt the algorithm 2 in Liu et al. (2018a) to train neural network parameterized wo (s). Instead of taking the test function f(s) into RKHS H.g, we
parameterize the test function f(s) = fa(s) to be neural network with parameter 3, and perform minimax optimization over parametr and f3. A detail description can be found in Algorithm 2
Similarly, for the training of value function, we use primal-dual based optimization methods Dai jtt al. 2018 Feng et al. 2019) to minimize the bellman residual:
1
Σ iEM
(Vv(s))
1 [a,,(s)) (r. + (Vo(s))) fo(s.) - 100--21666 fa(ss)))) <o (s))
min max DEEF M
where (s)s) is the parameterized value function and fs(() is the test function. We also perform minimax over parameter & and B. A detail description can be found in Algorithm
For the network structures, use 32 feed forward neural networks to parameterize value function Va and density ratio (s),, and we use one hidden neural network with units to parameterize the test function [s()). We Adam Optimizer for all our experiments.
19

---

Published as a conference paper at ICLR 2020
* On Policy (Monte Carlo)
Naive Average
Density Ratio
Model-base
Value Estimate
Weighted DR
Our Method
10-2
10
10
10
10
10-4
10
10
10-b
10-8
162
10a
10
10
10
(a) MSE
(b) Bias Square
(c) Variance
Figure 4: Additional results on Taxi, with an extra curve for model based method.
Estimate RD using V and @ Given data samples from the policy Nu. We directly R in to estimate R².
equation
D ADDITIONAL EXPERIMENTAL RESULTS
We add a standard model-based baseline in Figure 4 following the same procedure as Liu et al. (2018a) Sall Figure 4 shows that the performance of the model-based approach largely depends of the size of the data, which is consistent with that in Liu et al. (2018a).
20


Reviews:
[{"review_id": "rkelhjsaYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new algorithm for the off-policy evaluation problem in reinforcement learning. It combines the value function learning method and the stationary distribution ratio estimators. The proposed method achieves double robustness, which means the proposed estimator is consistent as long as the value function or ratio estimator is consistent. Empirical results on some control domains are presented to verify the effectiveness of the algorithm.\n\nI think this paper has some nice contribution to the area, by introducing a doubly robust estimator based on the density ratio, and also a new idea to achieve double robustness. I will vote for accept, but I think there is room for improvement of this paper.\n\nDetailed comments:\n - The proposed estimator is not using control variate but using dual structure between value function and stationary distribution ratio, which is a novel idea comparing with similar doubly robust estimators. \n - Theorem 3.2, or at least the way it is presented, is less intuitive and makes me confused. If the variance of the DR estimator is always larger than the variance of value function, why I should use this estimator instead of value function. If the argument is the MSE of value function is potentially larger due to the bias. Then an effective analysis would be about MSE instead of variance.\n - If I have an oracle of density ratio, is the doubly robust estimator still unbiased, which is generally true for DR using control variate? This would be an important point to compare this work with control variate methods.\n - Very recent work https://arxiv.org/abs/1908.08526 also proposes a doubly robust estimator in similar settings. It's worth to mention it in the related work.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Syga485aKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Comments : \n\nThis paper provides an approach for reducing bias in long horizon off-policy evaluation (OPE) problems, extending recent work from Liu et al., 2018 that estimates the ratio of the stationary state distributions in off-policy evaluation for reducing variance. The paper provides a doubly robust method for reducing bias, since it requires separately estimating a value function. The key idea of the paper is to provide low variance, low bias OPE since their approach relies on accurately estimating the state distribution ratio and also the estimation of the value function. \n\nThe paper provides a follow up on Liu et al., 2018 and other recent works in off-policy learning that tries to estimate the state distribution ratio directly, but can introduce high inaccuracy if the obtained ratio estimates are inaccurate. In line of that, this approach seems useful as it tries to reduce the error from inaccurate ratio estimates by incorporating prior works with an additional value function estimation. \n\nFurthermore, the paper introduces a new perspective to doubly robust estimation that tries to reduce bias, instead of variance in previously known OPE literature (Jiang et al., 2016; Thomas et al., 2016). It is interesting to see how doubly robust can be related to primal-dual relations and the connections between these approaches, which is a novel contribution to the best of my knowledge. \n\n- The fundamental connection comes from observing OPE withdoubly robust estimator that estimates \\hat{V} and equation 6 that incorporates the ratio of the state density. This is clearly written in equations 7 and 8, that are two ways of evaluating the value function with off-policy samples known in the literature.\n\n- It uses the property of the Bellman recursive expression for the estimated value function of doubly robust OPE estimator and uses it in the OPE with state density ratio, leading to equation 9, and obtaining the bridge estimator that now relies on both estimates of value function \\hat{V} and the state density ratio. Although initially this does not seem useful, but the authors clarify this and how a bias reducting method can be achieved as in equation 11. \n\n- It is a nice and elegant trick, exploiting the connections between OPE estimators leading to a bias reduction method that seems quite interesting. \n\n- The most interesting part of the paper comes from section 4 that exploits the connection between doubly robust approaches with Lagrangian duality, and that their approach is equivalent to a primal dual formulation of policy evaluation. This stands out in itself as a novel contribution of the paper. Equations 14 and 15 best writes down the connections, as to how policy evaluation can be formualted as a Lagrangian function for optimization. \n\n- Although the authors point out how equation 15 is equivalent to equation 11 - this does not seem straight forward at first unless carefully looked at. I would encourate the authors to perhaps add more clarity that exploits this connection, to make the paper more self-contained. \n\n- In terms of experiments, the paper compares the doubly robust approach with previous works that estimates the density ratio, along with other baseline comparisons such as weighted DR. In both the two evaluated problems, their approach seems useful in terms of obtaining better accuracy (lower MSE). \n\n- However, I am not sure to what extent this approach can be scaled to more complicated tasks for OPE? Are there any example domains where the proposed method fails, or is difficult to scale up to more complicated tasks? \n\n- The current set of experiment results seems adequate, given the theoretical contribution and that most OPE papers evaluate on such domains. But overall, it might be useful to analyse the significance of this approach when scaling to more complicated domains. \u000b\n\n\nOverall, I think the paper has a neat and elegant theoretical contribution, exploiting the connection of OPE with primal-dual frameworks that seems quite novel to me. Experimental set of results are properly presented too showing significance of the approach compared to previously known baselines. I think such papers exploting connections with other literature is useful for the community in general, and this paper has significantly novel theoretical contribution. Hence, I would recommend for acceptance of this paper. \n\n\u000b", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkl5PWypYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "  *Synopsis*:\n  This paper provides a new doubly robust estimator for off-policy policy evaluation, based on the new infinite horizon technique (i.e. using an estimate of the state density ratio as opposed to long products of action importance weights). They show the doubly robust estimator's bias is dependent on a product of the error of the value function estimate and stationary distribution ratio estimate, which provides improvements over the initial infinite horizon estimator. They also provide some nice discussion of the relation of their method and Lagrangian duality, which was quite interesting and insightful. Finally, the paper shows the usual empirical comparisons.\n\n  Main Contributions:\n  - Doubly robust estimator for infinite horizon off-policy policy evaluation\n\n  *Review*:\n  Overall, I quite like this paper and think the quality is at a high level. The proposed doubly robust estimator is well supported theoretically and empirically and improves on the prior art. I am recommending a weak accept for this paper as it will be a nice contribution for the community, but I have some clarifications/updates I would like to see to improve the readability of the paper (specifically C4).\n\n  I also have a few questions, and clarifications that I would like the authors to address during the rebuttal period.\n\n  *Clarifications*:\n  C1: In the section \"Off-policy state visitation importance sampling\", doesn't equation 4 involve an expectation over the target policy? Or am I missing something here?\n\n  C2: The bias of the estimator decreases as our estimate of the density ratio and value function improves. It might be useful to more clearly compare this bias to the original estimator proposed by Liu.\n\n  C3: Proof of theorem 3.1: I would like you to clearly finish the proof. I think clarity and completeness in appendices is importance over conciseness as there is usually no limit on pages.\n\n  C4: The proof of theorem 3.2 is not obviously linked to theorem A.3. The proof for theorem 3.2 should be clearly stated and included in the appendix, without an unstated implicit link to A.3. This will make your theoretical analysis more clearly understandable, and expendable for future work. I will happily increase my score if this is clarified in a future version. I also will decrease my score if this is not clarified.\n\n  *Competitors*\n\n  - You may want to include a model based approach, just for completeness (as in the infinite horizon paper from Liu).\n\n  *Questions*\n  \n   Q1: I'm curious about the difference between using an ANN for estimating the density ratio (as opposed to a kernel method). Have you run experiments with the kernel method proposed in Liu's paper? While I don't think it is necessarily needed for the paper to be complete, I think the difference would be interesting to see what factors contribute to the algorithm's better performance.\n\n\n  Minor typos not taken into account for the review:\n  - Section 3.1 \"it is useful to exam the\": exam -> examine\n  - Section 4: \"hence yielding an true expected reward\": an -> a\n  - Section 4: \"it is natural to intuitize\": intuitize -> intuit?\n  - The sentence right before section 4 could use a rewrite.\n  - For readability it would be useful to include theorem statements ahead of proofs in the appendix.\n  - Theorem A.3: do you mean with \\hat{R} defined in 3.2 (not the variance as this is not defined in 3.2).\n\nEdit:\n\n- Due to the author rebuttal and updates to the paper I've increased my score.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a doubly robust off-policy evaluation method that uses both stationary density ratio as well as a learned value function in order to reduce bias.
The reviewers unanimously recommend acceptance of this paper.
Decision: Accept (Spotlight)