Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning
Authors: Ali Mousavi
Lihong Li
Qiang Liu
Denny Zhou
Venue:  (2020)
Keywords: reinforcement learning
off-policy estimation
importance sampling
propensity score

Abstract: Off-policy estimation for long-horizon problems is important in many real-life applications such as healthcare and robotics, where high-fidelity simulators may not be available and on-policy evaluation is expensive or impossible.  Recently, \citet{liu18breaking} proposed an approach that avoids the curse of horizon suffered by typical importance-sampling-based methods. While showing promising results, this approach is limited in practice as it requires data being collected by a known behavior policy. In this work, we propose a novel approach that eliminates such limitations. In particular, we formulate the problem as solving for the fixed point of a "backward flow" operator and show that the fixed point solution gives the desired importance ratios of stationary distributions between the target and behavior policies.  We analyze its asymptotic consistency and finite-sample
generalization. Experiments on benchmarks verify the effectiveness of our proposed approach.


Published as a conference paper at ICLR 2020
BLACK-BOX OFF-POLICY ESTIMATION FOR INFINITE-HORIZON REINFORCEMENT LEARNING
Ali Mousavi"
Lihong Li"
Qiang Liu
Dengyong Zhou'
"Google Research
Unnierriity of Texas, Austin iqiangecs utexas edu
(a 1 imous, 1 hong, dennyzhou @goog com
ABSTRACT
Off-policy estimation for long-horias monizooizonn problems is important in many real-life applications such as healthcare and robotics, where high-fideliti simulators may not be available and on-policy evaluation expensive or impossible. Recently, Liu et al. (2018) proposed an approach that avoids the curse of horizon suffered by typical importance-samplng baaeed methods. While showing promising results, this approach is limited in practice as it requires data be drawn from the stationary distribution of a known behavior policy, In this work, we propose a novel approach that eliminates such limitations. In particular, for the fixed point of a certain operator. Using tools from Reproducing Kernel Hilbert Spaces (RKHSs), we develop new estimator that computes importance ratios of stationary distributions, without knowledge of how the off-policy data are collected. We analyze its asymptotic consistency and finite-sample generalization. Experiments on benchmarks verify the effectiveness of our approach.
formulate the problem solving
INTRODUCTION
As reinforcement learning (RL) is increasingly applied to crucial real-life problems like robotics, recommendation and conversation systems, off-policy estimation becomes even more critical. The task here is to estimate the average long-term reward of a target policy, given historical data collected by (possibly unknown) behavior policies. Since the reward and next state depend on what action the policy chooses, simply averaging rewards in off- policy data does not estimate the target policy's long-term reward. Instead, proper correction must be made to remove the bias in data distribution.
One approach is to build simulator that mimics the reward and next-state transitions in the real world, and then evaluate the target policy against the simulator (e.g.. (ontenea et al., 2013 le et al., 2019). While the idea natural, building a high-fidelity simulator could be extensively challenging in numerous domains, such as those that involve human interactions. Another approach is to use propensity scores importance weights, so that we could use the weighted average of rewards in off off-policy data as a suitable estimate of the average reward of the target policy. The latter approach is more robust, as it does not require modeling assumptions about the real world's 's dynamics. It often finds more success in short-horizon problems like contextual bandits, but its variance often grows exponentially in the horizon, a phenomenon known as "the curse of horizon" (Liu et al. 2018).
To address this challenge, [Lu et al. (2018) proposed to solve an optimization problem of minimax nature, whose solution directly estimates the desired propensity score of states under the stationary distribution, avoiding explicit dependence horizon. While their method is shown give more accurate predictions than previous algorithms, it is limited in several important ways:
The method requires that data be collected by known behavior policy. In practice, however, such data are often collected over an extended period of time by multiple, unknown behavior policies. For example, observational healthcare data typically contain patient records, whose treatments were provided by different doctors in multiple hospitals. each following potentially different procedures that are not always possible to specify explicitly.
The method requires that the off-policy data reach the stationary distribution of the behavior policy. In reality, it may take a very long time for a trajectory to reach the stationary distribution, which may be impractical due various reasons like costs and missing data.

---

Published as a conference paper at ICLR 2020
In this paper, introduce novel approach for the off-policy estimation problem that overcome these drawbacks. The main contributions of our work are three-fold:
We formulate the off-policy estimation problem into one of solving for the fixed point of an operator. Different from the related, and similar, Bellman operator that goes forward in time, this operator is backward in time.
We develop a new algorithm, which does not have the aforementioned limitations of Liu et al. (2018), and analyze its generalization bounds. Specifically, the algorithm does not require that the off- policy data come from the stationary distribution, or that the behavior policy be known.
We empirically demonstrate the effectiveness of our method on several classic control benchmarks. In particular, we show that, unlike Liu et al. (2018), our method is effective even if the off off-policy data has not reached the stationary distribution.
In the next section, we give brief overview recent and related works. We then move to describing the problem setting that have used in the course of the paper and our off-policy estimation approach. Finally, we present several experimental results to show the effectiveness of our method.
Notation. In the following, we ( to denote the set of distributions over set X. The &g norm of vector is | Given real-valued function f defined some set X, let || = VIx Mx) Finally, we denote by [ni] the set (1, and {AA) the indicator function.
2 RELATED WORKS
Our work focuses on estimating a scalar (average long-term reward) that summarizes the quality of a policy and has extensive applications in practice. This is different from value function or policy learning from off-policy data (e.g.. Precup et al. [001] Maei et al. 2010 Sutton et al. 2016 Munos et al. 2016 Metelli et al. 2018), where the major goal
ensure stability and convergence. Yet, these two problems share numerous core techniques, such as importance reweighting and doubly robustness. Off Off-policy estimation and evaluation can also be used
component for policy optimization (e.g..Jiang & Li 2016 Gelada & Bellemare] 2019 Liu et al. 2019 Zhang et al. 2019).
Importance reweighting, or inverse propensity scoring, has been used for off- off-policy RL (e.g.. Precup et al. 2001 Murphy et al.] [001] [L et al.] 2015) Munos et al., [2016] Hanna et al.) |017]| [ie et al.
2019. Its accuracy can be improved by various techniques (Jiang & Li 2016) Thomas & Brunskill 2016 Guo et al., 2017, Farajtabar et al. 2018). However, these methods typically have a variance
that grows exponentially with the horizon, limiting their application to mostly short-horizon problems
like contextual bandits (Dudík et al. 2011 Bottou et al. 2013).
There have been recent efforts to avoid the exponential blow-up of variance in basic inverse propensity scoring, A few authors explored the alternative to estimate the propensity score of state's stationary distribution (Liu et al. 2018 Gelada & Bellemare 2019), when behavior policies are known. Later, Nachum et (2019) extended this idea to situations with unknown behavior policies. However, their approach only works for the discounted reward criterion. In contrast, our work considers the more general and challenging undiscounted criterion. In the next section, briefly mention the setting under which we study this problem and then present our black-box off-policy estimator.
Our black-box estimator is inspired by previous work for black-box importance sampling (Liu & Lee 2017). Interestingly, the authors show that it is beneficial to estimate propensity scores from data without using knowledge of the behavior distribution (called proposal distribution that paper), even if it is available; see also Hesmii et al. (2007) for related arguments. Similar benefits may exist for our black-box off-policy estimator developed here, although systematic study outside the scope of this paper.
3 PROBLEM SETTING
Consider a Markov decision process (MDP) (Puterman 1994 M = US,.A,,RR Po. po. 7). where S and A are the state and action spaces, P is the transition probability function, R is the reward function,
2

---

Published as a conference paper at ICLR 2020
Po A(S) is the initial state distribution, and [0, 1] is the discount factor. A policy maps states to a distribution over actions: x S A (AA,, and r[ is the probability of choosing action in state by policy x. With fixed и,, trajectory follows
(Sa. an, 81, "1."1..... is generated as
8o ~ po(), a ~ (-1s6), rt R(st, at), $441 P(-(s,,)))
Vt 2 0.
Given a targel policy we consider two reward criteria, undiscounted (7 = 1) and discounted (y < 1), where Eg [1] indicates the trajectory T is controlled by policy T.
T
(undiscounted)
= lim Ex T-200
= E E( bi,
(1)
T
[=]
(discounted)
Pz.A
= (1 - 7) E
rz
(2)
t=0
In the above, d,r is the stationary distribution over S x A, which exists and is unique under certain assumptions (Levin & Peres 2017).
The 7 < 1 case can reduced to the undiscounted case of = 1, but not vice versa. Indeed, one can show that the discounted reward in equation cantioonnnnnnnnn can be interpreted as the stationary distribution of an induced Markov process, whose transition function is a mixture of P and the initial-state distribution Po- We refer interested readers Appendix A more details. Accordingly, in the following and without the loss of generality, we will merely focus on the more general undiscounted criterion in equation I and suppress the unnecessary dependency on po and 7.
In the off-policy estimation problem, we are interested in estimating Pa for a given target policy и. However, instead of having access on-policy trajectories generated by æ, have set of transitions collected by some unknown (i.e., "black-box" or behavior-agnostic (Nachum et al. 2019)
behavior mechanism ТBEH:
D = {(s ag Ti. ss)ssiinn
Therefore, the goal of off-policy estimation is to estimate Pz based on D, for a given target policy и.
The setting we described above is quite general, covering number of situations. For example, твEh might be single policy and might consist of one or multiple trajectories collected by твEн- In this special case, s 8 for 1 < n,; this is the off- off-policy RL scenario widely studied (e.g.. Precup et al. 2001; Sutton et al. 2016 Munos et al., 2016)] Liu et al. 2018 Gelada & Bellemare/ 2019). Furthermore, if тAEH æ, we recover the on-policy setting. On the other hand, MAEH and D can consist of multiple policies and their corresponding trajectories. In this situation, unlike the single policy case s/ and 8 might originate from two distinct policies. In general, one can consider
TBE as a distribution over S x A where (s;, a;) in D are sampled from. Having introduced the general setting of the problem, we will describe our estimation approach in the next section.
BLACK-BOX ESTIMATION
Our estimator is based on the following operator defined on functions over A. For discrete state-action spaces, given any d E R
B, Byd(s, a) <(ass)
Σ
P(slE,a)d(E,o)
(3)
SES,aEA
While we will develop the rest of the paper using the discrete version above for simplicity, the continuous version can be similarly obtained without affecting the estimator and results:
Byd(s,a) = ((ass) [ dP(s)).o)d({.o).
(4)
E,a
where P is now interpreted as the transition kernel.
For simplicity in exposition, assume rewards are deterministic. However, everything in this work generalizes directly to the of stochastic rewards.
3

---

Published as a conference paper at ICLR 2020
We should note that B is indeed different from the Bellman operator PPuterman 1994): although they have some similarities. In particular, given some state-action pair (s, a), the Belmman operator is defined using next state s' of (s, a), while B is defined using previous state-actions (5 a)) that transition to 8. It is this sense that B5 backward (in time). Furthermore, as we will show later, d has the interpretation of distribution over 8 A. Therefore, B₂ describes how visitation flows from (E, a) to (s, a) and hence, we call it the backward flow operator. Note that similar forms of B have appeared in the literature, usually used encode constraints in a dual linear program for an MDP (e.g.. [ang et al. 2007] Wang 2017 Dai et al., 2018). However, the application of B for the off- off-policy estimation problem as considered here appears new the best our knowledge.
An important property of B is that, under certain assumptions, the stationary distribution d, is the unique fixed point that lies in AS x A) (Levin & Peres 2017):
dx d and d₂ A A).
(S)
This property is the key element we use to derive our estimator as we describe in the following.
4.1 BLACK-BOX ESTIMATOR
In most cases, off-policy estimation involves weighted average of observed rewards r; D. We therefore aim to directly estimate these (non-negative) weights which we denote by w {w;} E A[m]];; that is, w; 2 for [n] and Σx= w; 1. Note that the normalization of may be ensured by techniques such as self-normalize importance sampling (Liu 200T). Once such is obtained, the estimated reward is given by:
Px
(6)
Effectively, any E A(nl) defines an empirical distribution which we denote by d over S x A::
n
(s, = Σ w. w, = 5, =
Equation 6 equivalent to Ar Rle.a)=d [r]. Comparing to equation we naturally want to optimize so that d, is close to dg. Therefore, inspired by the fixed-point property of d, in equation 5 the problem naturally becomes one of minimizing the discrepancy between dy and B dw In practice, w is often represented in a parametric way:
W/ = w Σ W
W ==
2 0,
(8)
where (.) is parametric model, such as neural networks, with parameters w E Q. We have now reached the following optimization problem:
min D(d dw))
wen
where D(- |]] is some discrepancy function between distributions. In practice, B is unknown, and must be approximated by samples in the dataset D:
Badm((s = T(lss) Σ ws 1 s).
Clearly, B.d is valid distribution over S x A induced by and D, and the black-box estimator solves for w by minimizing D(d, B,
4.2 BLACK-BOX ESTIMATOR WITH MMD
There are different choices for D(- || in equation and multiple approaches to solve it (e.g., Nguyen et al., 2010 Dai et al. 2017: Here, describe such algorithm based on Maximum Mean Discrepancy (MMD) MManndet et al. (017a)). For simplicity. the discussion in this subsection assumes S x A is finite, but the extension continuous S x A is immediate.
4

---

Published as a conference paper at ICLR 2020
Let k(+,)) be positive definite kernel function defined on (S x A)). Given two real-valued functions,
and 9, defined on S A we define the following bilinear functional
k ifi gl
f(s.a) k ((s,,), ( a).
(10)
Clearly, we have [f: f] 2 0 for any due to the positive definiteness of k. In addition, k is called strictly integrally positive definite if k [f; f) = 0 implies || O.
Let H be the reproducing kernel Hilbert space (RKHS) associated with the kernel function k. This sum of countably many terms: f()) = Σi u² k((s", a)), where {u*} C R. and {(s', a's',a)) SSx A. The space H is equipped with an inner product defined as follow: given f.9 E H such that f= E= k((s aa)) and g E; u$ k((s", a))..) the inner product (f. == Ei, w'nd k(s", aa), (s², a²) )), which induces the norm defined by I1/l :-
the unique Hilbert space that includes functions that can be expressed
=-VV=vVv, VEnr w'u'k((st at), (9) a))).
Given H. the maximum mean discrepancy between two distributions, fa and μ2, defined by (24 |l (2) == sup (E [f] [f). s.t. II =
SE#
Here, f may be considered as a discriminator, playing similar role as the discriminator network in generative adversarial networks (Goodfellow al.) 2014), measure the difference between (l and
12. A useful property of MMD is that it admits a closed-forn expression (Gretton et al. (012)):
D& (11 μ2) = k [M - M25 11 - [2]
= k [P1: [1] 2k [P1: μ2] + k [ [2]
where k -] is defined in equation T0 and we used the bilinear property [s ... Interested readers
are referred to surveys (e.g. Berlinet & Thomas- Agnan background on RKHS and MMD.
2011 Muandet et al. 2017b) for more
Applying MMD to our objective, we have
(d || B,dd)) = k (dws dwl 2k dwi Bad + k
Baddui Brdu)]
In the above, both dw and d are simply probability mass functions on a finite subset of S x A, consisting of state-actions encountered in D. It follows immediately from equation I0 that
k [dw: dwl = Σ i.j
waw k((s;, az), (s,,
K
k dwi Bx Badu)
Σ
wa Σ T T(a'ls/ T(alls)) az) (s),
=
1.j
Badui Brdu]]
Σ
waw
Σ
((d)s)((())))) (s),,())
Defining Ki,j := i.j
2K (k(1)
+ (2) we can express the objective as a function w (since {wx}
depends w; equation g
((w)
Σ
Kig
(11)
4J
Remark 4.1. Mini-batch training an effective approuch solve large-scale problems. However, the objective E(W) is not in a form that is ready for mini-batth training, as w: requires normalization (equation 8) that involves all data in D. Instead, we may equivalently minimize L(w) == log E(w), which can be turned into form that allow mini-batch training, using trick that is also useful in other machine learning contexts (e.g., Jean et al. 2015). See Appendix for more details.
Algorithm D in Appendix summarizes our estimator. We next present theoretical analysis of our approach. We show the consistency of our result and provide sample complexity bound.
5

---

Published as a conference paper at ICLR 2020
4.3 THEORETICAL ANALYSIS
Consistency. The following theorem shows that the exact minimizer of equation Sorioonyocciini coincides with the fixed point of B., and the objective function measures the norm of the estimation error in an induced RKHS. To simplify exposition, we assume x = (8, a) and x' = (s', a') successive action- state pair following æ: x' dx z). where d (z' x) is the transition probability from x to x', that is, du (z' x) P(s' s,a)T(a'|s) Similarly, we denote by (z, .²) = ((5, (s, (3', a')) an independent copy of (x, )')
Theorem 4.1. Suppose k is strictly integrally positive definite, and dæ is the unique fixed point of B in equation Then, for any d E AS x A). [he(d || B,d)= =0 =0 Furthermore, (x B.d) equals an MMD between d and d with transformed kernel: [& I d2 = Dx(d dz),
d dx-
where k(x,, J.) a positive definite kernel, defined by
k(I, E, (k(, σ) k(z, - k(r', , I) + k(r, (x) (x,
where the expectation is with respect to x' ~ d.(. x)) and n' ~ dzl. (.1 8). with x' and n' drawn independently.
Generalization. We next give a sample complexity analysis. In practice, the estimated weight v based on minimizing the empirical loss (dw B,dw), where B is replaced by the empirical approximation B,, The following theorem compares the empirical weights v with the oracle weight w, obtained by minimizing the expected loss (cl,, Bydw), with the exact transition operator B
W(s;, a5; w)/n. Denote by W = (:: w): w E 2t the model class of W (::w).. Assume w is the minimizer of the empirical loss D || Brd and w" the minimizer of expected loss Dy(dw) B,dw). Assume {o:)0= are i.i.d. samples. Then, with probability 1 - we have
Theorem 4.2. Assume the weight function is decided by
16r max + tr v log((/6))
(da B.ds) Dx B,dw.) I 16r R, (W) +
Vn
where R.(W) denotes the expected Rademacher complexity of W with data size n, and Tmax max(I|WVll sup, vk(I,=)), with [|W]l == sup(l|W]lle W W). This suggests gener- alization error of O(1/ /T) RM) O(1/Vn),, which is typical for parametric families of functions.
EXPERIMENTS
In this section, present experiments compare the performance of our proposed method with other baselines on the off off-po evaluation problem. In general and for each experiment, we use behavior policy TBEH generate trajectories of length TEEН. We then use these generated samples from behavior policy to estimate the expected reward of given target policy To compare our approach with other baselines, we use the root mean squared error (RMSE) with respect to the average long-term reward of the target policy The latter is estimated using a trajectory of length Ttar > 1. In particular, we compare our proposed black-box approach with the following basclines:
naive averaging baseline in which simply estimate the expected reward of target policy by averaging the rewards over the trajectories generated by the hehavior policy.
model-based baseline where we use the kernel regression technique with a standard Gaussian RBF kernel. We set the bandwidth of the kernel to the median (or 25th or 75th percentiles) of the pairwise euclidean distances between the observed data points.
inverse propensity score (IPS) baseline introduced by Liu et al. 20188)
We will first use a simple MDP from Thomas & Brunskill 2016 to highlight the IPS drawback we previously mentioned in Section [] We then move to classical control benchmarks.

---

Published as a conference paper at ICLR 2020
Modelwin
-30
F=1
F-11
-35-
1-p
100 RASSE
-40
Our Method
Hales
3
-15-
1-p
p
(a)
r=1
2
(b)
340
Figure I: (a) ModelWin MDP from Thomas & Brunskill (016). (b) The RMSE of different methods change the length of horizon w.r.t the target policy reward. IPS depends the horizon length while our method is independent of the horizon length.
5.1 TOY EXAMPLE
The ModelWin domain first introduced in TTooas Brunskill (2016) is fully observable MDP with three states and two actions as denoted in Figure The agent always begins in and should choose between two actions 01 and a2. the agent chooses a1, then with probability of p and 1 - p makes transition to $2 and $3 and receives reward of r 1 and hand, if the agent chooses ag, then with probability of p and 1 p it makes a transition to 83 with the reward of -1 and $2 with the reward of 1, respectively. Once the agent is in either $2 or $3. goes back to the 81 in the next step without any reward. In our experiments, we set p = 0.4.
- 1, respectively. On the other
We define the behavior and target policies as the following. In the target policy, once the agent is in $1. it chooses a1 and ag with the probability of 0.9 and 0.1, respectively. On the other hand and for the behavior policy, once the agent is 81, it chooses aj and 02 with the probability of 0.7 and 0.3, respectively. We calculate the average on-policy reward from samples based on running a trajectory of length TTAR = 50, 000 collected by the target policy. We estimate this on-policy reward using trajectories of length TEEE E {4,8 16, 32, 64, 128} collected by the behavior policy, In each case, we set the number of trajectories such that the total number of transitions (i.e., TBER times the number of trajectories) is kept constant. For example, for TBEH 4 and TBEH = 8 we use 50,000 and 25,000 trajectories, respectively. Since the problem has finitely many state-actions, we use the tabular method and hence, equation I turns into a quadratic programming. We then report the result of each setting based on 10 Monte- Carlo samples.
As we can see in Figure Fb)) the naive averaging method performs poorly consistently and indepen- dent of the length of trajectories collected by the behavior policies. On the other hand, IPS performs poorly when the collected trajectories have short-horizon and gets better the horizon length of trajectories get larger. This is expected for IPS- - as mentioned in Section T it requires data be drawn from the stationary distribution. In contrast, shown in (b), our black-box approach performance is independent of the horizon length, and substantially better.
5.2 CLASSIC CONTROL
We now focus four classic control problems. We begin by briefly describing each problem and then compare the performance of our method with other approaches on these problems. Note that for these problems are episodic, we convert them into infinite-horizon problems by resetting the state to a random start state once the episode terminates.
Pendulum. In this environment, the goal is to control a pendulum in a vertical position. State variables are the pole angle 0 and velocity Ó. The action a is the torque in the set 2-2, - 1, 1,2) applied to the base. We set the reward function to -62 + 0.1 + 0.001a²)
Mountain Car. For this problem, the goal is drive up the car to top of a hill. Mountain Car has state space of I2 (the position and speed of the car) and three possible actions (negative, positive, or zero acceleration). We set the reward to + 100 when the car reaches the goal and -1 otherwise.
7

---

Published as a conference paper at ICLR 2020
Cartpole
Pendulum
Mounteincar
Acrobot
Our Pursce
Hihe
UK
25
Figure 2: The RMSE of different methods w.r.t the target policy reward as we change the number of trajectories. Our black-box approach outperforms other methods on three problems.
Cartpole
Pendulum
Model booed
34-
Trajectortes
of Trajectories
Trejectortes
of Trijecooiie
The median and error bars at 25th and t5th percentiles of different methods w.r. the target policy reward as we change the number of trajectories. The trend of results is similar Figure 2
Figure 3:
The goal here is to prevent an attached pole to a cart from falling by changing the cart's s velocity. Cartpole has state space of IR4 (cart position, velocity, pole angle and velocity) and two possible actions (moving left or right). Reward is -100 when the pole falls and +1 otherwise.
Cartpole.
Acrobot. In this problem, our goal is swing a 2-link pendulum above the base. Acrobot has a state space of IR (sin(.) and cos(.) of both angles and angular velocities) and three possible actions (applying +1, or -1 torque on the joint). Reward is +100 for reaching the goal and -1 otherwise.
For each environment, we train a optimal policy 7 using the Neural Fitted Q Iteration algorithm (Riedmiller 2005). We then set the behavior and target policies as TBEH = 7r + (1 0n) )x- and .2 + (1 oz) where r- denotes a random policy, and 0 S 00, < 1 are two constant values making the behavior policy distinct from the target policy. In our experiments, we set aj = 0.7 and 02 = 0.9. In order to calculate the on-policy reward, use single trajectory collected by π with T TAR = 50, 000. For off -ff-cy data, we use multiple trajectories collected by тВEн with use 3-layer (having 30, 20, and 10 hidden neurons) feed-forward neural network with the sigmoid activation function as our parametric model in equation B For each setting, we report results based on 20 Monte-Carlo samples.
TBEE 200. In all the cases,
Figure 2 shows the log of RMSE w.r.t. the target policy reward as we change the numher of trajectories collected by the behavior policy. We should note that all methods except the naive averaging method have hyperparameters to be tuned. For each method, the optimal set of parameters might depend on the number of trajectories (i.e., size of the training data). However, in order to avoid excessive tuning and to show how much each method is robust to a change in the number of trajectories, we only tune different methods based on 50 trajectories and use the same set of parameters for other settings. As we can see, the naive averaging performance is almost independent of the number of trajectories. Our method outperforms other approaches on three environments and it is only the Acrobot in which IPS performs comparably to our black-box approach. In order to have a robust evaluation against outliers, we have plotted the median and error bars at 25th and th percentiles in Figure 3 we compare the Figures 2 and 3 we notice that the trend of results is almost the same in both. In Appendix G have studied how changing 0N of the behavior policy affects the final RMSE.
6 CONCLUSIONS
In this paper, we presented a novel approach for solving the off-policy estimation problem in the long-horizon setting, Our method formulates the problem solving for the fixed point of "backward flow" operator. We showed that unlike previous works, our approach does not require the knowledge of the behavior policy or stationary off- off-policy data. We presented experimental results to show the effectiveness of our approach compared to previous baselines. In the future, we plan to use structural domain knowledge to improve the estimator and consider a random time horizon in episodic RI.
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Alain Berlinet and Christine Thomas-Agnan, Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
Léon Bottou, Jonas Peters, Joaquin Seliionero-Candele 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.
Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1458 1467, 2017.
Bo Dai, Albert Shaw, Niao He, Lihong Li, and Le Song. Boosting the actor with dual critic. In Proceedings of the 6th International Conference on Learning Representations (ICLR), 2018.
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.
Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust ooflpc evaluation. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 1446-1455, 2018
Raphael Fonteneau, Susan A. Murphy, Louis Wehenkel, and Damien Ernst. Batch mode reinforcement learning based on the synthesis artificial trajectories. Annals of Operations Research, 208(1): 383-416, 2013.
Carles Gelada and Mare G. Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In Proceedings of the 33rd AAAI Conference Artificial Intelligence (AAAI), pp. 3647-3655, 2019.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems 27 (NIPS), pp. 2672-2680, 2014.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(Ma)):733-773, 2012.
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 (NIPS), pp. 2489-2498, 2017.
Josiah Hanna, Peter Stone, and Scott Niekum. Bootstrapping with models: Contidence intervals for off- off-policy evaluation. In Proceedings of the 31 AAAI Conference on Artificial Intelligence (AAAI), pp. 4933 4934. 2017.
Masayuki Henmi, Ryo Yoshida, and Shinto Eguchi. Importance sampling via the estimated sampler. Biometrika, 94(4):985 991, December 2007.
Eugene Ie, Chih-Wei Hsu, Martin Mladenov, Vihan Jain, Sanmit Narvekar, Jing Wang, Rui Wu, and Craig Boutilier. RecSim: configurable simulation platform for recommender systems, 2019. CoRR abs/1909.044477.
Sébastien Jean, KyungHyun Cho, Roland Memisevic, and Yoshua Bengio. On using very large target vocabulary for neural machine translation. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 1-10, 2015.
Nan Jiang and Lihong Li. Doubly robust off off-policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 652-661, 2016.

---

Published as a conference paper at ICLR 2020
David A. Levin and Yuval Peres. Markov Chains and Mixing Times. American Mathematical Society, 2nd edition, 2017. ISBN 1470429624.
Lihong Li, Remi 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.
Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer Series in Statistics. Springer- Verlag, 2001. ISBN 0387763694.
Qiang Liu and Jason D. Lee. Black-box importance sampling. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 952-961, 2017.
Qiang Liu and Dilin Wang. Stein variational gradient descent as moment matching. In Advances in Neural Information Processing Systems (NIPS), pp. 8854-8863, 2018.
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 31 (NeurIPS), 2018.
Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Off-policy policy gradient with state distribution correction. In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI), 2019.
Hamid Reza Maci, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S, Sutton. Toward off off-policy learning control with function approximation. In Proceedings of the 27th International Conference on Machine Learning (ICML), pp. 719-726, 2010.
Alberto Maria Metelli, Matteo Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Advances in Neural Information Processing Systems 31 (NIPS), pp- 5447-5459, 2018.
Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends in Machine Learning, 10(1-2):1-144 2017a.
Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, Bernhard Schölkopf, et al. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends( in Machine Learning, 1114,, 2017b.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc G. Bellemare. Safe and efficient off- policy reinforcement learning. In Advances Neural Information Processing Systems 29 (NIPS), pp. 1056-1054, 2016.
Susan Murphy, Mark van der Laan, and James M. Robins. Marginal mean models for dynamic regimes. Journal of the American Staristical Association, 96(456) 14233 2001.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. 2019.
XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11))5847-586 2010.
Doina Precup, Richard S. Sutton, and Sanjoy Dasgupta. Off-policy temporal-difference learning with funtion approximation. In Proceedings of the 18th Conference Machine Learning (ICML), pp. 417-424, 2001.
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Intersciencee, New York, 1994. ISBN 0-471-61977-9.
Martin Riedmiller. Neural fitted q iteration first experiences with a data efficient neural reinforcement learning method. In European Conference Machine Learning, pp. 317-328. Springer, 2005.
10

---

Published as a conference paper at ICLR 2020
Richard S. Sutton, A. Rupam Mahmood, and Martha White. An emphatic approach to the problem of pofliy 2016.
difference learning. Journal of Machine Learning Research, 17(73):1-2)
Philip S. Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 1139-2148, 2016.
Mengdi Wang. Primal-dual learning: Sample complexity and sublinear run time for ergodic Markoy decision problems, 2017. CoRR abs/17 1iN/1710.06000
Tao Wang, Daniel J. Lizotte, Michael H. Bowling, and Dale Schuurmans. Stable dual dynamic programming. In Advances in Neural Information Processing Systems 20 (NIPS), pp. 1569-1576, 2007.
Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. In Advances in Neural Information Processing Systems 32 (NeurIPS-19), 2019.
Shangtong Zhang, Wendelin Boehmer, and Shimon Whiteson. Generalized off-policy actor-critic. In Advances in Neural Information Processing Systems 32 (NeurIPS-19) 2019.

---

Published as a conference paper at ICLR 2020
A REDUCTION FROM DISCOUNTED TO UNDISCOUNTED REWARD
The same reduction is used in Liu ct al. (2018). For completeness, we give the derivation details here, for the case of finite state/actions. The derivation can be extended to general state-action spaces, with proper adjustments in notation.
Let (su. ag. ru, $1, a1,...) be trajectory generated by and de A(S A) be the distribution of (st, ar). Clearly,
do(s, a)
Po(s)T(a(s)
d1+1(8,a)
E((E f.o
14 ->> 0.
Using a matrix form, the recursion above can be written equivalently as dr+1 = P dr, where Pa is given by
(a = ((s)))
The discounted reward of policy is
Px. (1 E)
r'r
(R(a)dd,,
1=0
with
dx,x: (1 7) (do + tdl + 72 + ...).
Multiplying both sides of above by 7P' we have
7 PP dr.
(1 - 7) (T do + + ph + 3 dl + +...)
= (1 - 7) (7d1 + 72 + 7 +...)
dz,7 - (1 - -dd
Therefore,
dx, 7P dx,y + (1 (1-7)d
(7Pa + (1
Accordingly, da,7 is the fixed point of an induced transition matrix given by PA. := yP, + (1 7)),1". This completes the reduction from the discounted to the undiscounted case.
B
PROOF OF THEOREM 4.
Note that
Dx B,d)= =
B,d: d B_d]
Following the definition the strictly integrally positive definite kernels, we have that D1 (d B,,d) 0 implies d - B&d = O, which in turn implies d d, by the uniqueness assumption of d,., We have thus proved the first claim.
For the second claim, define d = d - dx. Since d, - Brdd = O, we have
(x B, = k [dd B,d); (d - B,d']
k [id B,d (d, Brdx)); (d - B,d - (d, BBd,))]
= k [(ōw - Brów); (6w - BBddm))
Recalling that Bzd(x) En, Px ((( we have
(x (d) || d. = k (6 - B,dw); (6.. BBdw')
Σ k(0, (f Brd (5)) (z))
a.a
Σ k(x,)) dw( - Pa (a(oooo)bu (Lo(()) Pr((
Zo
12

---

Published as a conference paper at ICLR 2020
Define the adjoint operator of B..
Paf(z) = P=.((())f()))
Denote by P the operator applied on k(x, F) in terms of variable x, that is, Pak(s,
Ex Pa (c(2z))(('',)) This gives
Dx || Bxd)
Σ x²)
(w((x)- Σ Pa (p((olao)0000))) (v)(() ( - (P((((E))
20
50
Σ (x) (k(rr,)) -xkk(x))) - PP 8(7)
(2) (r,
completing the proof.
C PROOF OF THEOREM 4.2
First, note that the error can be decomposed as follows:
(x || Br & (2,
B2 + D (B || Brda)
< D& (dw.
[B ) + D2 (B,r dà B,
D (dw.
BRdw. ) DD 1,, dw. B,dw.) + D (B || Bxda)
(dw...
|| BBdw. ) + 2 sup Bx(Bndw |1 B,dw)
wEW
= D2 (dw.
|| (Bdd.)) +
where we define
7 Dye (Bxthun || Brddn)
Therefore, we just need to bound Z.
Denote by Bx (J= H, 11/l S 1} the unit ball of RKHS. Define ||Bx|| == sup SEB and R. (Bx) the expected Rademacher complexity of Bx of data size n. From classical RKHS theory (see Lemma C.2 below), we know that [ loo S Tk and Rr,(B) S Tk/ VT, where Tk ==
/supzex k(x,,x)) x²).
remains calculate Z sup D& (B,dho || Bxdw)). Recall from the definition of IDx that
Th Bxdd)) sup B 1 [f())) E. du [f())
fEB,
Recall that ((x,, + is set of transitions with xi ~ d. 1z),, where dx denotes the transition probability under policy Following the definitions of Byd, and Brdw, have
(x) w(x))1(x 21}
(x) = Σ w(xx)d Ix.))
Therefore,
Z = sup D& (B, de BBdww) weW
sup sup E B., [f(]]] EV di [f(x)) weW feB,
Σ
w(xx) (f(x*) - Exy (z+))
sup WEW. ==1
13

---

Published as a conference paper at ICLR 2020
where ~ d= 224) is an independent copy of 2 that follows the same distribution. Note that F. introduced only for the sample complexity analysis. Note that Z a random variable, and E|Z] denotes its expectation w.r.t random data {z;, -=rr We assume different (zi, 24)) are independent with each other. First, by McDiarmid inequality, we have
T2E
P(Z 2 [ +e) exp
|
This is because when changing each data point (xa,, xt),, the maximum change on Z is at most
2 |D |Bx]| /n. Therefore, have Z s [[Z] (log(11)) [I [| /n with proba- bility at least
Accordingly, we now just need to bound B[Z]:
E| = Ex
sup WEW.
w(x) (f(z²) - Ex(((EMEa))
< Ex,x
sup WEB,
1
wfx))(f f(tt)
= =Ex,8.o
sup WEW i=1
o, (f) f(z))
(because {a,} are i.i.d. Rademacher random variables)
S 2E
sup NEW,
2R,, (W & Bk),
where
w Bx = (f()g((z); f W, E Bk).
By Lemma C.I below, we have
E[2] < RW & Bx) S 4 Il + || (MV + R. (Bx)).
Combining the bounds, we have with probability 1 5,
8 (lo((1/)) || |B
22 < 4R, (W Bx) +
< + [|Ballac) (R.(W) + R., (Bx)) + 8log(1/8) |Bx
Plugging Lemma we have
8rk (1WI1 + + + | Vlo((180/8)
22 < 8 (1 rk) ()) R.) +
Vn
Assume Tmax
max([|Wlll rk). We have
27 < 16 rmax (M) 16r2 max + + v 8 (1/8)
Vn
Lemma C.1. Denote by || sup(lffl : f E W) the super norm of a function set W. Then,
R. Bxx) 5 2 ||
(W)) R., (Bx))
14

---

Published as a conference paper at ICLR 2020
Proof. Note that
f(x)g(z²)) = (f(z) + -( - g(x'))²
Note that x² is 2[ 1k LLipschiit on interval |- 1>>1 - -1 1I + 1[
Applying Lemma C.1 of Liu & Wang 2018), we have
(.. @ B&) - 2l + 1lB Bk),
where W + B& = (f(x)) + 9(x'): W, E Bk), and and
(W @ B&) = Evol
sup
Σ <((((z) + g(x())]
JEW.gE8k
I Euzl sup
Σ zi [x;();)] + E ssu Σ 2ng(1(4
JEW
gEBx
= RR, - R,,(Ba)
Remark The same result holds when w is defined as function of the whole transition pair (I,, x²), that is, w, = (x11
Lemma C.2. Let be the RKHS with a positive definite kernel k(x, x²) on domain X. Let Bx ( E Hx: |l/llxm $ 1} be the unil ball of HH, and rk- = /SuPEEx k(x, 2'). Then,
|B S Tk:
(Rk( vn
Proof. These are standard results in RKHS theory, and we give a proof for completeness. For ||Belloo we just note that for any J E B& and x E X,
f(x) (J, k(z, H4 S I1 [k(a, m - [|k(z, )1xx. = vk(u, S nk.
The Rademacher complexity can be bounded as follows:
(Bx) Ex,o
sup fEB,
Ear((a))
< Ex,o
sup fEB
f,
o,k((z)))
1=1
Hu
Ex,
o: ( :)
(rt
iml
Hu
1/2
< Ex
a a;k( .)
1/2
Ex
0:o ((o, 23)
n²
i===1
1/2
n
Ex
k (1tt, 23))
2
i=1
Tk
Vn n
15

---

Published as a conference paper at ICLR 2020
D MINI-BATCH TRAINING
The objective f(w) is not in form that is ready for mini-batch training. It is possible to yield better scalability with trick that has been found useful in other machine learning contexts (e.g., JJan et al. 2015). We start with transformed objective:
L(w) = log ((w)
log Σ Kij log Σ ii
Then,
VL = Ens ((W;ūū))
2 2E, Vi;
Eno the di
E1
Eis W Kij log (1;ūū})
2E, w; V log vi;
Env Wy Wi y Kav
Σ ui
= Egg V (og((ūnūū) - E. V log w:l,
where Basl-] and [.].] correspond to two properly defined discrete distributions defined on D2 and D, respectively. Clearly, V can now be approximated by mini-batches by drawing random samples from 2 or D to approximate Eij and E.
PSEUDO-CODE OF ALGORITHM
This section includes the pseudo-code of our algorithm that we described in Section
Algorithm 1 Black-box Off-policy Estimator based on MMD
Inputs: Dataset {ss, d, Ti, Isisnn of behavior policy тBEH, kernel function k, target policy parametric model (.)..
Output: Target policy value estimate P..
1:
Estimate important weights (wihisinn by solving the optimization problem in equation II return P=
2:
Σi Wyr's (see equation 6).
F BIAS- VARIANCE COMPARISON
In this section, we compare the performance of our approach from the bias and variance perspective. In partieular, focus the ModelWin MDP (Figure In order size on the performance of different estimators, we consider different number of trajectories of length For each setting, we have 200 independent runs and calculate the bias and variance of each method based on them. We compare our approach with Liu et al. (2018) and Nachum et al. (2019) that are two ofte-of-the-an methods in the off- off-policy estimation problem. Figure 4 shows the results of this comparison.
the impact of training data
As we can see, our method has smaller bias but larger variance compared to other approaches on this problem. As mentioned before, DualDICE (Nachum et al., 2019) does not cover the undiscounted reward criterion. Therefore, instead 7 = 1, we have used 7 0.9999 in the code shared by the authors. This induces some bias but reduces the variance of this method. To confirm this observation, we further decreased the 7 to 0.9 in DualDICE and observed that reducing ? in this algorithm increases the bias but reduces the variance at the same time.
The comparison to IPS of Liu et al. (2018) highlights the significance of an assumption needed by IPS: the data must be drawn (approximately) from the stationary distribution of the behavior policy. As the trajectory length in the experiment, this assumption is apparently violated, thus the high bias of IPS. In contrast, method does not rely on such assumption, is more robust.
16

---

Published as a conference paper at ICLR 2020
ModelWin
ModelWin,
-1.
-1.0
DusDICC (Cammmii:300)
Our Hechod
Log(Blas)
-2.0
IPS
2.44
-6
-2.
10
Trajectories
Trajectories
Figure 4: Bias and standard deviation of different methods for the ModelWin MDP (Fig. method has smaller bias but larger variance compared to other algorithms.
I
Our
Mountaincar
Cartpole
3.-
-1.6-
lag RMSE
-20
Our Methed Model based
-10
-22-
-15
-24
IPS
-2.6
-25
Behavior Policy
Behavior Policy
Figure 5: The RMSE of different methods w.r.t the target policy reward change the behavior policy. Our method outperform other approaches on different behavior policies.
G SENSITIVITY
Finally, in Figure we measure how robust our approach is to changing the behavior policy compared to other methods. In particular, we vary O that corresponds to the behavior policy to measure how the RMSE is affected. While ag is fixed 0.9, in each experiment we choose a1 from {0.7, 0.5, 0.3, 0.1). For each experiment, we use data from 50 trajectories (with TВEн 200) collected by the behavior policy and report results based on 20 Monte-Carlo samples. According to Figure [5] as aj diverges more from 022 the performance of all the methods degrade while our method is the least affected. It worth mentioning that for the Mountain Car problem and 01 0.1, the behavior policy close to random policy and hence the car has not been able to drive up to top of the hill. This means that all the methods have constantly received a reward of -1 during all the steps and hence the estimated on-policy reward has been 11 for all the methods well. Therefore, the RMSE of all four methods are equal in this case.
17


Reviews:
[{"review_id": "rkxhdccTFB", "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 to the off-policy evaluation problem in reinforcement learning, based on stationary state visitation. The proposed algorithm does not need to know the behavior policy probabilities, which provide a broader application scenario compared with previous work. It is based on directly solving the fixed point problem of the resulting target stationary distribution, instead of solving a fixed point problem about the stationary ratios.\n\nIn general, this paper is looking at an interesting problem with a lot of increasing focus these days. I think this paper contributes great idea and good theoretical analysis. I like the idea of matching the resulting target distribution instead of minimizing a loss over the ratio. However, several unclear places in the current version hurt the presentation of results. I would like to see them get improved and will increase my score accordingly if so.\n\nDetailed comments:\n\n1) The algorithm part could be presented more clearly. So far I did not see where the empirical operator \\hat{B} is formally defined. The word *empirical* is also confusing to me in \"B is approximated by empirical data\" because B is not an expectation, but an *integral* which has no *empirical* opposite of it. For the equations on top of page 5, shouldn't they be k[, ] about empirical operator instead of the expected operator since the RHS is already in sample-based form?\n\n2) Related with the last one, B has an integral. To approximate the integral, we only have one sample from the transition probability actually, and the sample state is not uniformly distributed. It needs some explanation of why that would not cause a problem to approximate the integral.\n\n3) The current loss function is invariant to the scale of w at all. Since the w is normalized, this is not a problem for the resulting estimator, ideally. However, that can be a numerical issue for float numbers. It's possible that the output from function approximator w goes to 0 or \\infty. Both cases can lead to NaN of the output/function approximator update eventually. I'd like to hear if the author has met this problem in the experiment or not, and how can that be fixed. \n\n4) I have to point out, as just a slight con of this paper, the technique used in this paper is not that much different from Liu et al 2018. Since it minimizes a loss function which is a supremum over an RKHS, and the resulting empirical loss also has a similar form. It's nice to see the author provide some details of making it work with mini-batch. These details are important for function approximator as NN.\n\nMinor point:\n - On page 12 the equations after \"We have by the definition of D_k\", I did not follow the second step of the equations.\n\nSuggestion:\nThis paper study the similar settings (behavior-agnostic OPE), using similar method (on the stationary distribution) came out several months ago: https://arxiv.org/pdf/1906.04733.pdf. I knew it's unfair to ask the author to compare it with a very recent prior/parallel work. However since they are in such a similar case, and they have code available, is it possible to directly compare with the result from their code? https://github.com/google-research/google-research/tree/master/dual_dice\n\n\n======= After rebuttal =======\nThe author's feedback clarified some of my concerns in the initial review. After reading the author's feedback and other reviews, I think this paper has enough show contribution to the related work. Some of my previous concerns (point 2 and 3) seems true for many related works in this area in general. I partly agree that it is not very fair to ask this paper to fix them. The updated version also presents the theory section in a more clear way. So I'd like to raise my score. I've no problem with acceptance, but I won't fully heart argue for acceptance.\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "rklAXTxaKr", "reviewer": "AnonReviewer1", "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": "Summary : \n\nThis paper proposes an approach for long horizon off-policy evaluation, for the case where the behaviour policy may not be known. The main idea of the paper is to propose an estimator for off-policy evaluation, that computes the ratio of the stationary state distributions (similar to recent previous work Liu et al.,) but when the behaviour policy may be unknown. This is an important contribution since in most practical off-policy settings, the behaviour policy used to collect the data may not necessarily be known. \n\n\nComments and Questions : \n\n\t- This is an important and novel contribution where the authors propose an approach for OPE that comes down to solving a fixed point operator. This is simlar to solving for fixed point Bellman operators, but where their problem can be formulated as a backward recursive problem. \n\t- The operator defined as in equation 3 is in terms of the backward view of time - this allows the operator to capture the visitation from the previous s,a to the current s. This is the backward flow operator with which a fixed point equation can be described. Although the authors note that similar operators have appeared in the literature before - their main contribution is in terms of using such operators for the OPE problem, which seems novel to me and is an interesting approach with potential benefits as demonstrated in this paper. \n\t- The core idea comes from equation 9 which tries to minimize the discrepancy between the empirical distribution and the stationary distribution. This can be formulated as an optimization problem, and the paper uses blackbox estimators, as described in section 4.2 for solving this problem.\n\t- The next interesting part of the paper comes from solving the optimization problem in equation 9 with Maximum Mean Discrepancy (MMD) - this is a popular approach that has recently become well-known, and the authors make use of it minimize the differences between the empirical and the stationary state distribution. \n\t- Section 4.2 appears a bit confusiing to me with some details missing - it would perhaps be useful if the authors could include more details for 4.2, especially with some explanations of how they arrived at the expression in equation 10. This would also make the paper more self-contained, for readers in the RL community perhaps not so well-read with literature on MMD.  Appendix C contains the detailed derivation, but more intuitive explanations might be useful for the context of the paper. \n\t- The proposed black box estimator seems quite useful as demonstrated in figures 2 and 3. Although the authors evaluate their approach of few simple domains - it would have been useful if there were more extensive experiments performed for OPE problems. This would be useful since from fig 2, it appears that the proposed method only outperforms in 3 out of 4 evaluated problems. \n\t- For experiments, it would also be useful to demonstrate the significance of not knowing the behaviour policy and what are the usefulness of it. The paper is motived in terms of unknown behaviour policies that generated the data - so few experiments that explicitly shows the benefit of it would perhaps strengthen the paper more. \n\t- I am curious to know more about the bias-variance trade-off of the proposed OPE estimator as well. Ie, does the proposed method introduce any bias, or has significance in terms of lower variance for the long horizon problem? Experimentally, would it be possible to demosntrate whether the approach has lower variance compared to existing baselines?\n\nScore : \n\n- Overall, I think the paper has useful contributions. It is a well written paper, but some additonal details in section 4.2 might be useful, especially on the appriach with MMD. Experimentally, I think there are some experiments missing and doing those can significantly strengthen the paper as well. The proposed method seems simple and elegant, and I would recommend for a weak acceptance of the paper.  \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "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": "H1xjTu5iYH", "reviewer": "AnonReviewer2", "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": "Summary\n\nThis paper proposes using a black-box estimation method from Liu and Lee 2017 to estimate the propensity score for off-policy reinforcement learning. They suggest that, even when the full proposal distribution is available (as is the case in much of the off-policy RL literature), that estimating the propensity score can allow for a much lower variance off-policy correction term. This reduced variance allows the proposed method to \"break the curse of horizon\" as termed by Liu 2018.\n\nReview\n\nThe proposed fixed point formulation for learning a parameterized off-policy state distribution allows for lower variance off-policy corrections decreasing the impact of the curse of horizon. This approach appears both theoretically sound and empirically well-supported.\n\nI am concerned with the consistency argument made in section 4.3. It appears from equation (10) and the final statement of theorem 4.1 that it is necessary to have two independent samples of x' given a single state x. In the general case, without access to the environment model, it is not possible to obtain two samples of x'. If the environment is continuing, then the probability of returning to state x to obtain a second sample is 0. Am I misunderstanding the requirements specified by the objective function in equation (10)? An additional concern with the consistency argument is that it appears to assume that the approximator for d_w can achieve 0 error according to the MMD. If d_pi is not representable by the approximator, which could reasonably be the case in more challenging domains, it is unclear from this analysis or empirical results what the behavior of the system will be. It is difficult to assess how large of an assumption this is for consistency claim; for difficult problems will d_pi never be representable, or is this a fairly low concern?\n\nThe empirical results look to have high enough variance in the final outcomes that it is difficult to consistently assess the performance of each algorithm (looking specifically at figure 3). However, the primary competitor algorithm is IPS which the proposed algorithm handily beats in three of the four problems. In the fourth problem, it is unclear that the competitor algorithm is winning, and could in fact be better only due to chance given the size of the respective error bars. It is worth noting that, because the parameter settings were tuned only for 50 trajectories, it is important to primarily assess performance based only on that point. It is likely that, given more trajectories to learn from, each algorithm would have chosen a smaller stepsize and effectively performed similarly.\n\nAdditional comments (did not affect score)\n\nI would be interested in seeing the scalability of this approach empirically. Given the additional parameterized function to learn, I am unsure if this method would scale reasonably to much larger problems. However, I recognize that the scalability question is largely outside the scope of this paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses an important and relevant problem in reinforcement learning: learning from off-policy data, taking into account the offsets in the visitation distribution of states. This has the promise of lowering variance even with long horizon roll-outs. Existing methods have required access to the behavior policy (or have required data from the stationary distribution). The novel proposed approach instead uses an alternative method, based on the fixed point of the "backward flow" operator, to calculate the importance ratios required for policy evaluation in discrete and continuous environments. 

In the initial version of the submission, several concerns were expressed regarding both the quality of the paper and clarity. The authors have updated the paper to address these concerns to the satisfaction of the reviewers, who are now unanimously in favor of acceptance. 
Decision: Accept (Poster)