GenDICE: Generalized Offline Estimation of Stationary Values
Authors: Ruiyi Zhang*
Bo Dai*
Lihong Li
Dale Schuurmans
Venue:  (2020)
Keywords: Off-policy Policy Evaluation
Reinforcement Learning
Stationary Distribution Correction Estimation
Fenchel Dual

Abstract: An important problem that arises in reinforcement learning and Monte Carlo methods is estimating quantities defined by the stationary distribution of a Markov chain. In many real-world applications, access to the underlying transition operator is limited to a fixed set of data that has already been collected, without additional interaction with the environment being available. We show that consistent estimation remains possible in this scenario, and that effective estimation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and empirical distributions, derived from fundamental properties of the stationary distribution, and exploiting constraint reformulations based on variational divergence minimization. The resulting algorithm, GenDICE, is straightforward and effective. We prove the consistency of the method under general conditions, provide a detailed error analysis, and demonstrate strong empirical performance on benchmark tasks, including off-line PageRank and off-policy policy evaluation.

Published as a conference paper at ICLR 2020
GENDICE: GENERALIZED OFFLINE ESTIMATION OF STATIONARY VALUES
Ruiyi Zhang Bo Dai Lihong Lia, Dale Schuurmans
Duke University, "Google Research, Brain Team
ABSTRACT
An important problem that arises in reinforcement learning and Monte Carlo methods is estimating quantities defined by the stationary distribution of a Markov chain. In many real-world applications, access to the underlying transition opera- tor is limited to a fixed set of data that has already been collected, without addi- tional interaction with the environment being available. We show that consistent estimation remains possible in this challenging scenario, and that effective esti- mation can still be achieved in important applications. Our approach is based on estimating a ratio that corrects for the discrepancy between the stationary and em- pirical distributions, derived from fundamental properties of the stationary distri- bution, and exploiting constraint reformulations based on variational divergence minimization. The resulting algorithm, GenDICE, is straightforward and effee- tive. We prove its consistency under general conditions, provide error analysis, and demonstrate strong empirical performance on benchmark problems, including off-line PageRank and off- off-policy policy evaluation.
INTRODUCTION
Estimation of quantities defined by the stationary distribution of a Markov chain lies at the heart of many scientific and engineering problems. Famously, the steady-state distribution of a random walk on the World Wide Web provides the foundation of the PageRank algorithm (Langville & Meyer, 2004]. In many areas of machine learning, Markov chain Monte Carlo (MCMC) methods are used to conduct approximate Bayesian inference by considering Markov chains whose equilibrium dis- tribution is desired posterior (Andrieu et al., 2002). An example from engineering queueing theory, where the queue lengths and waiting time under the limiting distribution have been exten- sively studied (Gross et al. 2018). As we will also below, stationary distribution quantities of fundamental importance in reinforcement learning (RL) (e.g.. Tsitsiklis & Van Roy 1997).
Classical algorithms for estimating stationary distribution quantities rely on the ability to sample next states from the current state by directly interacting with the environment (as in on-line RL or MCMC), or even require the transition probability distribution to be given explicitly (as in PageR- ank). Unfortunately, these classical approaches are inapplicable when direct access to the environ- ment is not available, which often the case practice. There are many practical scenarios where collection of sampled trajectories is available, having been collected off-line by an external mech- anism that chose states and recorded the subsequent next states. Given such data, we still wish to estimate stationary quantity. One important example is off- off-policy policy evaluation in RL, where we wish to estimate the value of a policy different from that used to collect experience. Another ex- ample is off-line PageRank (OPR), where seek to estimate the relative importance of webpages given a sample of the web graph.
Motivated by the importance of these off-line scenarios, and by the inapplicability of classical meth- ods, we study the problem of off-line estimation of stationary values via a stationary distribution corrector. Instead of having access the transition probabilities only access to a fixed sample of state transitions, where states have been sampled from an unknown distribution and next-states are sampled according the Markov chain's 's transition operator. The
next-state sampler, assume
Equal contribution.
Work done while interning Google.

---

Published as a conference paper at ICLR 2020
off-line setting is indeed more challenging than its more traditional on-line counterpart, given that one must infer an asymptotic quantity from finite data. Nevertheless, we develop techniques that still allow consistent estimation under general conditions, and provide effective estimates in prac- tice. The main contributions of this work are:
We formalize the problem of off-line estimation of stationary quantities, which captures wide range of practical applications.
We propose novel stationary distribution estimator, GenDICE, for this task. The resulting algo- rithm is based on new dual embedding formulation for divergence minimization, with carefully designed mechanism that explicitly eliminates degenerate solutions.
We theoretically establish consistency and other statistical properties of GenDICE, and empir- ically demonstrate that it achieves significant improvements on several behavior-agnostic off- policy evaluation benchmarks and an off-line version of PageRank.
The methods we develop in this paper fundamentally extend recent work in off- off-policy policy evalu- ation (Liu et al., 2018: Nachum et al. 2019) by introducing a new formulation that leads to a more general, and as we will show, more effective estimation method.
2 BACKGROUND
We first introduce off-line PageRank (OPR) and off-policy policy evaluation (OPE) as two motivat- ing domains, where the goal is to estimate stationary quantities given only off-line access to a set of sampled transitions from an environment.
Off-line PageRank (OPR) The celebrated PageRank algorithm (Page et al. 1999) defines the ranking of web page in terms of its asymptotic visitation probability under a random walk on the (augmented) directed graph specified by the hyperlinks. If we denote the World Wide Web by directed graph G (V, E') with vertices (web pages) E V and edges (hyperlinks) (u, u) E E, PageRank considers the random walk defined by the Markov transition operator v - u:
(1) where |o] denotes the out-degree of vertex e and E 1) is a probability of "teleporting" to any page uniformly. Define de (v) := (s: = v/so- ~ No. vi < t, 81+1 -P(sss))). where μu the initial distribution over vertices, then the original PageRank algorithm explicitly iterates for the limit
P (ulju) = (1-n)
[o] (n,))E E + |²]
lim; lim (v)
if
d (v)
(2)
(1
i (0.
The classical version of this problem is solved by tabular methods that simulate Equation [ How- ever, we are interested in more scalable off-line version of the problem where the transition model is not explicitly given. Instead, consider estimating the rank of a particular web page e' from a large web graph, given only sample D {(v, w) from a random walk on G as specified above. We would still like to estimate ((v') based on this data. First, note that if one knew the distribution by which any vertex v appeared in D, the target quantity could be re-expressed by a simple importance d(u)
ratio d (v') Evwp
p(u) |u=v] Therefore, if one had the correction ratio function
(v) d(v)
p(")'
an estimate of d (t") can easily be recovered via d (v') R p (v') (v'), where á (v') is the empirical probability of o' estimated from D. The main attack on the problem we investigate is to recover a good estimate of the ratio function
Policy Evaluation An important generalization of this stationary value estimation problem arises in RL in the form of policy evaluation. Consider a Markov Decision Process (MDP) M = (S, A, A.P. R. 7: Mo) (Puterman) 2014), where a state space, notes the transition dynamics, R is reward function, E (0. 1] is a discounted factor, and Po is the initial state distribution. Given policy, which chooses actions in any state s according to the prob- ability distribution T--19), trajectory 3 = (So, do...,......... 81,88,,1) ai,,,,,,,................ ..) is generated by first sampling the initial state $o ~ Ho, and then for 2 0. a; ~ (.(]):). F2 ~ R(s,, a:), and 8141 ~ P(. a.). The value of a policy is the expected per-step reward defined as:
an action space, P (s'1s, a) de-
Average: R(T)= == limy- T Ei_
Discounted: R,(T) := (1 (1->) (3)
In the above, the expectation is taken with respect to the randomness in the state-action pair P (s')s, a) π (a'ls') and the reward R (sy, ).). Without loss of generality, we assume the limit exists for the average case, and hence R(x) is finite.
2

---

Published as a conference paper at ICLR 2020
Behavior-agnostic Off-Policy Evaluation (OPE) An important setting of policy evaluation that often arises in practice is to estimate Ry (α) or R (4) given fixed dataset D {(s a, r, s ~ (s')ss, a) p (s, a), where p (s. a) is unknown distribution induced by multiple unknown behavior policies. This problem is different from the classical form of OPE, where it is assumed that a known behavior policy Fe is used to collect transitions. In the behavior-agnostic scenario, however, typical importance sampling (IS) estimators ..gg.Prrccup et al., 2000) do not apply. Even if one can assume D consists of trajectories where the behavior policy can be estimated from data, known that that straightforward IS estimators suffer variance exponential in the trajectory length, known as the "curse of horizon" (Jiang & Li 2016 Liu et al. 2018).
Let dā (s, a) IP (sg 5, 4r al ~V Po, Vi < t,a, ~ π (-18),, 8141 ~ P(-(8;; 4)). The station- ary distribution can then be defined as
limr 74I Ex di (s, = lim, oo df (5,a) (1 11-78 >)) Er 7'dī (s,a) With this definition, R(T) and R., (m) can be equivalently re-expressed as < (s.0)
if =
m (s.
(4)
if E (0.
(T) == Epg [R (s. a) = Ep
R (s, a)
(5)
p(..a)
Here once again that if we had the correction ratio function (s.a) (..a)
p(s.a straightfor-
ward estimate of R. R,(T)) could be recovered via (T) [T (s, a) R (s, a)]. where á (s, a) is an empirical estimate of p (s,a), In this way, the behavior-agnostic OPE problem can be reduced to estimating the correction ratio function т, as above.
We note that Liu al. (2018) and Nachum et al. (011)) also exploit Equation 5 to reduce OPE to stationary distribution correction, but these prior works are distinct from the current proposal in different ways. First, the inverse propensity score (IPS) method of Liu al. (2018) assumes the transitions are sampled from a single behavior policy, which must be known beforehand; hence that approach is not applicable in behavior-agnostic OPE setting. Second, the recent DuaIDICE algo- rithm (Nachum et al., 2019) is also a behavior-agnostic OPE estimator, but its derivation relies on a change-of-variable trick that is only valid for 7 1. This previous formulation becomes unstable when + 1, as shown in Section 6 and Appendix E The behavior-agnostic OPE estimator we derive below in Section B is applicable both when 7 and y E (0, 1). This connection is why we name the new estimator GenDICE, for GENeralized stationary DIstribution Correction Estimation.
3 GENDICE
As noted, there are important estimation problems in the Markov chain and MDP settings that can be recast as estimating stationary distribution correction ratio. We first outline the conditions that characterize the correction ratio function upon which we construct the objective for the GenDICE estimator, and design efficient algorithm for optimization. We will develop our approach for the more general MDP setting, with the understanding that all the methods and results can be easily specialized to the Markov chain setting.
3.1 ESTIMATING STATIONARY DISTRIBUTION CORRECTION
The stationary distribution p. defined in Equation 4 can also be characterized via n (s',, ,d) - (1 4o (8') (d'ls)) + (a' (d's')) (s'ss, ds da, ((3,a')
(6)
(Tow)otta)
At first glance, this equation shares a superficial similarity to the Bellman equation, but there is fundamental difference. The Bellman operator recursively integrates out future (s', a') pairs to characterize a current pair (s, a) value, whereas the distribution operator T defined in Equation operates in the reverse temporal direction.
When 7 < 1, Equation always has a fixed-point solution. For = 1, in the discrete case, the fixed- point exists as long as T is ergodic; in the continuous case, the conditions for fixed- pointt existence become more complicated (Meyn & Tweedie (012) and beyond the scope of this paper.
The development below is based on a divergence D and the following default assumption. Assumption (Markoy chain regularity) For the given target policy n, the resulting state-action transition operator T has unique stationary distribution y that satisfies D(T pulpp)) = 0.
3

---

Published as a conference paper at ICLR 2020
In the behavior-agnosse setting consider, one does not have direct access to P for element- evaluation or sampling, but instead is given a fixed set of samples from P (s'[s, s, a) (s, a) with
respect some distribution (s,, a) over 5 x A. Define T Th to be mixture of M and Tn i.e., let
To ((s''a') (s) = (1 - 7) po (8') (a' 88)) + y a (a' (s')s P
(s.
(7)
To Tp((sraa))
Obviously, conditioning on a,,') one could easily sample a' ~ (a'ls') to form (s, s', s',a') ~ To ((s', a'), (s, a)); similarly, a sample (s',a') ~ μo (s') π (a'ls') could be formed from s'. Mixing such samples with probability Y and 1 - respectively yields a sample (s, a, a') ~ Th ((s', a') (s, a)). Based on these observations, the stationary condition for the ratio from Equa- tion can be re-expressed in terms of T.mm
p (s'. (s' (1 7) pa (s') (d'ls) + (a'ls')
(s, (s. ds da,
(8)
where r" (s,a) := p(s.a)
p(s,a) is the correction ratio function we seek to estimate. One natural approach
to estimating 7" is to match the LHS and RHS of Equation 8 with respect to some divergence D (-I1-)
over the empirical samples. That is, we consider estimating T by solving the optimization problem
min D (T -llp- 7). -20
Although this forms the basis of our approach, there are two severe issues with this naive formulation that first need to be rectified:
i) Degenerate solutions: When 1, the operator T 1, is invariant to constant rescaling: if T' = =T T then CT T,= o (er") for any 2 0. Therefore, simply minimizing the divergence D (T==1,,00 o Tpp 7) cannot provide a desirable estimate of r". In fact, in this case the trivial solution 7" (s, a) = 0 cannot be eliminated.
ii) Intractable objective: The divergence
(Thh,o -llp- r) involves the computation of 7:140 т, which in general involves an intractable integral. Thus, evaluation of the exact objective is intractable, and neglects the assumption that we only have access samples from T and are not able to evaluate it at arbitrary points.
We address each of these two issues in a principled manner.
3.2 ELIMINATING DEGENERATE SOLUTIONS
To avoid degenerate solutions when = 1, we ensure that the solution is a proper density ratio; that is, the property E = == (+) 2 0, Ep [r] = 1} must be true of any that is ratio of some density to p. This provides an additional constraint that we add to the optimization formulation
min (Tri,po o -Tlpp [lpp-7 T),, s.t., Ep [r] = 1. +20
(10)
With this additional constraint, it obvious that the trivial solution 7 (s, a) infeasible point of Eqn (10). along with other degenerate solutions (8, a) er* (s, a) with c = 1.
eliminated as an
Unfortunately, exactly solving an optimization with expectation constraints very complicated in general (Lan & Zhou, 2016). particularly given nonlinear parameterization for т. The penalty method (Luenberger & Ye 2015) provides a much simpler alternative, where a sequence of regular- ized problems are solved
min J (T) = D (Tr ollpp -npp))) -) + (E, [7] 1)² r20
(11)
with À increasing. The drawback of the penalty method is that it generally requires À to ensure the strict feasibility, which is still impractical, especially in stochastic gradient descent. The infinite may induce unbounded variance in the gradient estimator, and thus, divergence in optimization.
However, by exploiting the special structure of the solution sets to Equation [I] we can show that, remarkably, is unnecessary to increase X.
Theorem For E (0, 1] and any À > 0, the solution to Equation is given by (s, a(s.a)
p(s,a)
The detailed proof for Theorem I is given in Appendix A.I By Theorem I we can estimate the
desired correction ratio function
by solving only one optimization with an arbitrary > 0.
4

---

Published as a conference paper at ICLR 2020
3.3 EXPLOITING DUAL EMBEDDING
The optimization in Equation involves the integrals (T оT) and Ep [T] [T] inside nonlinear loss functions, hence appears difficult solve. Moreover, obtaining unbiased gradients with naive approach requires double sampling (Baird, 1995). Instead, we bypass both difficulties by applying a dual embedding technique (Dai et 2016 2018). In particular, we assume the divergence D is in the form of an f-divergence (Nowozin et al. 2016
Do ((T OT) |lp -) == fp p. (s) (T)
ds da
pT((aaa)
where ④ (-) : R R is convex, lower-semicontinuon function with Φ (1) O. Plugging this into J (r) in Equation 11 we can easily check the convexity of the objective
Theorem For an f-divergence with valid & defining Dz, the objective J (T) is convex W.E.I. т.
The detailed proof is provided in Appendix A.2 Recall that a suitable convex function can be represented o (x) m f f o0 (f), where 6 is the Fenchel conjugate of (-). In particular,
have the representation 2 max, ux ju² which allows us re-express the objective
( (t)=fp=-) (s',a') maxy
(T pirislaa))
6* (f) ds''a' + X max,
u (E [r] 1) - (12)
Applying the interchangeability principle (Shapiro et al., 2014 Dai et al. 2016 one can replace the inner max in the first term over scalar f to maximize over function f [-,
A A
min 220 JRE
max
J (T, f) (1 (1-7) Exo [f (s, a)] + TBBT, [T (s, a) [s',a')]
- Ep |T (s, o² (s, a))] + A Ep |ur (s.a) - u) - (13)
This yields the main optimization formulation, which avoids the aforementioned difficulties and well-suited for practical optimization discussed in Section 3.4
Remark (Other divergences): In addition to f-divergence, the proposed estimator Equation is compatible with other divergences, such as the integral probability metrics (IPM) (uüller 1997 Srrpperumuuur et al., 2009), while retaining consistency. Based the definition of the IPM, these divergences directly lead to min-max optimizations similar to Equation 13 with the identity func- tion o² (.) and different feasible sets for the dual functions. Specifically, maximum mean discrep- ancy (MMD) (Smola et al., (006) requires Ilfll < 1 where Hr denotes the RKHS with kernel k; the Dudley metric (Dudley] 2002) requires If S. 1 where Il == II + II f 12: and Wasserstein distance (Arjovsky al. 2017) requires [V S 1. These additional requirements on the dual function might incur some extra difficulty in practice. For example, with Wasserstein distance and the Dudley metric, we might need to include an extra gradient penalty (Gulrajani al.) 2017). which requires additional computation to take the gradient through gradient. Meanwhile, the consistency of the surrogate loss under regularization is not clear. For MMD, we can obtain a closed-form solution for the dual function, which saves the cost of the inner optimization (Gretton) et al. 2012), but with the tradeoff of requiring two independent samples in each outer optimization update. Moreover, MMD relies on the condition that the dual function lies in some RKHS, which introduces additional kernel parameters to be tuned and in practice may not be sufficiently flexible compared to neural networks.
3.4 A PRACTICAL ALGORITHM
We have derived a consistent stationary distribution correction estimator in the form a min-max saddle point optimization Equation 13 Here, we present a practical instantiation of GenDICE with a concrete objective and parametrization.
We choose the x2 divvergee, which is an diveergee with o (z) =(x 1)² and d' (y) =y 2 The objective becomes
Juz (T. f) = (1 (1-11 7) E [f (s, a)) + + (s,,),
Ep |T (s, (s. (f + A Ep jut (s) u] 5 (14)
There two major reasons for adopting x² diveegeen::
i) In the behavior- agnossic OPE problem, mainly use the ratio correction function for estimating Ep [ (s, a) R (s. a)), which is an expectation. Recall that the error between the estimate and ground-truth can then be bounded by total variation, which is lower bound of -iveeregee.
5

---

Published as a conference paper at ICLR 2020
ii) For the alternative divergences, the conjugate of the K L--divereence involves exp (+), which may lead to instability in optimization; while the IPM variants introduce extra constraints on dual function, which may be difficult to be optimized. The conjugate function of x² diveeeegee en- joys suitable numerical properties and provides squared regularization. We have provided an empirical ablation study that investigates the alternative divergences in Section 6.3
To parameterize the correction ratio T and dual function f we use neural networks, T (s,a)= = nnw, (s, a) and f [s, a) = nnw, (s,a), where wy and wy denotes the parameters of r and respec- tively. Since the optimization requires T to be non-negative, we add an extra positive neuron, such as exp (.), log (1 + exp (.)) or (-)² at the final layer of m.,, (s.a). We empirically compare the different positive neurons Section 6.3
For these representations, and unbiased gradient estimator V (wy (T, f) can be obtained straightforwardly. as shown in Appendix This allows us to apply stochastic gradient descent to solve the saddle-point problem Equation 14 in scalable manner, as illustrated in Algorithm
THEORETICAL ANALYSIS
We provide a theoretical analysis for the proposed GenDICE algorithm, following a similar learning setting and assumptions (Nachum et al. 2019).
Assumption The target stationary correction are bounded, ||~ S SC < oc.
The main result summarized in the following theorem. formal statement, together with the proof, is given in Appendix C
Theorem 3 (Informal) Under mild conditions, with learnable F and H. the error in the objective
between the GenDICE estimate, 7, to the solution (s,0) a) p(a,a)
u(s,a) is bounded by
J [ = (Eappro (F, H) VN -
where E [+] is w.r.f. the randomness in D and in the optimization algorithms, Copt is the optimization error, and Capprox (F, H) is the approximation induced by (F, H() for parametrization of f)-
The theorem shows that the suboptimality of GenDICE's solution, measured in terms of the objective function value, can be decomposed into three terms: (1) the approximation error capproz which is controlled by the representation flexibility of function classes; (2) the estimation error due to sample randomness, which decays at the order of 1/ \/V; and (3) the optimization error, which arises from the suboptimality of the solution found by the optimization algorithm. As discussed in Appendix C in special cases, this suboptimality can be bounded below by a divergence between f and T", and therefore directly bounds the error in the estimated policy value.
There is also a tradeoff between these three error terms. With more flexible function classes (e.g., neural networks) for F and H. the approximation error capprox becomes smaller. However, it may increase the estimation error (through the constant in front of 1/vN) and the optimization error (by solving a harder optimization problem). On the other hand, if F and H are linearly parameterized. estimation and optimization errors tend to be smaller and can often be upper-bounded explicitly in Appendix C.3 However, the corresponding approximation error will be larger.
RELATED WORK
Off-policy Policy Evaluation Off-policy policy evaluation with importance sampling (IS) has has been explored in the contextual bandits (Strehl al. 2010;; Dudík al. 2011 Wang et al. 2017], and episodic RL settings (Murphy et al. 2001 Precup et al. 2001). achieving many empirical successes (e.g.. Sttrhl et al. 2010; Dudik et al. 2011] Bottou et al.J 2013). Unfortunately, IS- based methods suffer from exponential variance in long- hong-horizon problems, known as the "curse of horizon" (Liu et al.) 2018). A few variance-reduction techniques have been introduced, but still cannot eliminate this Fundamental issue (Tiang & Li 2016 Thomas & Brunskill [016]] Guo et al.) 2017). By rewriting the accumulated reward as an expectation w.r.t. a stationary distribution, Liu et al. 20188; Gelada & Bellemare (2019) recast OPE as estimating correction ratio function. which significantly alleviates variance. However, these methods still require the off-policy data to be collected by single and known behavior policy, which restricts their practical applicability. The only published algorithm in the literature, to the best of our knowledge, that solves agnostic-behavion behavior off off-policy evaluation is DuaIDICE (Nachum et al. 2019). However, DuaIDICE was developed for

---

Published as a conference paper at ICLR 2020
discounted problems and its results become unstable when the discount factor approaches 1 (see below). By contrast, GenDICE can cope with the more challenging problem of undiscounted reward estimation in the general behavior-agnostic setting.
Note that standard model-based methods (Sutton & Barto 1998). which estimate the transition and reward models directly then calculate the expected reward based the learned model, are also applicable to the behavior-agnostic setting considered here. Unfortunately, model-based methods typically rely heavily on modeling assumptions about rewards and transition dynamics. In practice, these assumptions do not always hold, and the evaluation results can become unreliable.
Markov Chain Monte Carlo Classical MCMC (Brooks al. 2011] Gelman al. 2013) aims at
sampling from μ² by iteratively simulting from the transition operator. It requires continuous inter- action with the transition operator and heavy computational cost to update many particles. Amor- tized SVGD (Wang& & Liu 2016) and Adversarial MCMC (Song et al. [017 [i et al. (011)) alleviate this issue via combining with neural network, but they still interact with the transition operator di- rectly, i.e., in on-policy setting. The major difference of our GenDICE is the learning setting: we only access the off- off-policy dataset, and cannot sample from the transition operator. The proposed GenDICE leverages stationary density ratio estimation for approximating the stationary quantities, which distinet it from classical methods.
Density Ratio Estimation Density ratio estimation is fundamental tool in machine learning and much related work exists. Classical density ratio estimation includes moment matching (Gretton al. 2008), probabilistic classification (Bickel al., 2007). and ratio matching (Nguyen et a 2008 Sugiyama et al. (2008; Kanamori et al.) 2009). These classical methods focus on estimating the ratio between two distributions with samples from both of them, while GenDICE estimates the density ratio to stationary distribution of transition operator, from which even one sample is difficult to obtain.
PageRank Yao & Schuurmans 2013) developed a reverse-time RL framework for PageRank via solving a reverse Bellman equation, which is less sensitive to graph topology and shows faster adap- tation with graph change. However, Yao & Schuurmans (2013) still considers the online manner, which is different with our OPR setting.
6 EXPERIMENTS
In this section, we evaluate GenDICE on OPE and OPR problems. For OPE, we use one or multiple behavior policies to collect a fixed number of trajectories at some fixed trajectory length. This data used to recover a correction ratio function for a target policy π that is then used estimate the average reward in two different settings: i) average reward; and ii) discounted reward. In both settings, we compare with model-based approach and step-wise weighted IS (Precup et al. 2000). We also compare to Liu et al. (2018) (refereed to as "IPS" here) in the Taxi domain with learned behavior policy"] We specifically compare to DualDICE (Nachum et al. 2019) in the discounted reward setting, which is a direct and current oftte-of-thh-art baseline. For OPR, the main comparison is with the model-based method, where the transition operator is empirically estimated and stationary distribution recovered via exact solver. We validate GenDICE in both tabular and continuous cases, and perform an ablation study to further demonstrate its effectiveness. All results are based on 20 random seeds, with mean and standard deviation plotted. Our code is publicly available at ht https: http:://gttub.. com/ zhangry868 G/eeenDGGeGnD
6.1 TABULAR CASE
Offline PageRank on Graphs One direct application of GenDICE is off- PageRank (OPR). We test GenDICE on Barabasi-Albert (BA) graph (synthetic), and two real-world graphs, Cora and Citeseer. Details of the graphs are given in Appendix [ We use the log K T-diiergeeece between estimated stationary distribution and the ground truth as the evaluation metric, with the ground truth computed by an exact solver based on the exact transition operator of the graphs. We compared GenDICE with model-based methods in terms of the sample efficiency. From the results in Fig- ure D GenDICE outperforms the model-based method when limited data is given. Even with 20k samples les for a BA graph with 100 nodes, where a transition matrix has 10k entries, GenDICE still
We used the released implementation of TPS Liu et al. 2018 from https: thub. com/2t95/
infinite- hhrei zon-off-- -yt--poolyyysseee insaimationn
7

---

Published as a conference paper at ICLR 2020
shows better performance in the offline setting. This is reasonable since GenDICE directly esti- mates the stationary distribution vector or ratio, while the model- based method needs to learn an entire transition matrix that has many more parameters.
Off-Policy Evaluation with Taxi We use a similar taxi domain as in Liu et al. (2018), where grid size of 5 x 5 yields 2000 states in total (25 x 16 x 5, corresponding to 25 taxi locations, 16 passenger appearance status and 5 taxi status). We set the target policy to a final policy π after running tabular Q-learning for 1000 iterations, and set another policy # after 950 iterations as the base pol- icy. The behavior policy is mixture controlled by as Th = (1 - 0x)x + a. For the model-based method, r tabular representation for the reward and transi-
tion functions, whose entries are estimated from behavior data. For IS and IPS, we fit a policy via behavior cloning to estimate the policy ratio. In this specific setting, our methods achieve better results compared to IS, IPS and the model-based method. Interestingly, with longer hori- zons, IS cannot improve as much as other methods even with more data, while GenDICE consistently improve and achieves much better results than the baselines. DualDICE only works with y 1. GenDICE is more stable than DuaIDICE when y 1), while still showing competitive performance for smaller discount factors 7
Figure 1: Stationary Distribution Estimation on BA and real-world graphs. Each plot shows the log KL- divergence of GenDICE and model- based method towards the number of samples.
becomes larger (close to
Sociat Rosed
Ieperianc Sempling
Da
P5
Gardiic isan!
100
y
1-0
y 3.929
MSE
-3
-30
41
338
Truncated Longtn
Truncorted Length
Descount Factory
0,993
3.0
0.0
Mlding Rato
Hbxing Rato
Figure 2: Results on Taxi Domain. The plots show log MSE of the tabular estimator across different trajectory lengths, different discount factors and different behavior policies (x-axis).
6.2 CONTINUOUS CASE
We further test our method for OPE on three control tasks: a discrete-control task Cartpole and two continuous-control tasks Reacher and HalfCheetah. In these tasks, observations (or states) are continuous, thus we use neural network function approximators and stochastic optimization. Since DualDICE (Nachum al. 2019) has shown the state-of-the-ee thethhe performance on discounted OPE, we mainly compare with it in the discounted reward case. We also compare to IS with a learned policy via behavior cloning and neural model-based method, similar the tabular case, but with neural network as the function approximator. All neural networks are foed-forward with two hidden layers of dimension 64 and tanh activations. More details can be found in Appendix D
Due to limited space, we put the discrete control results in Appendix D and focus on the more challenging continuous control tasks. Here, the good performance of IS and model-based methods in Section 6. quickly deteriorates as the environment becomes complex, i.e., with a continuous action space. Note that GenDICE is able to maintain good performance in this scenario, even when using function approximation and stochastic optimization. This is reasonable because of the difficulty of fitting to the coupled policy-environnen
dynamics with a continuous action space. Here we also empirically validate GenDICE with off-policy data collected by multiple policies.
As illustrated in Figure 3 all methods perform better with longer trajectory length or more trajecto- ries. When a becomes larger, i.e., the behavior policies are closer to the target policy, all methods performs better, as expected. Here, GenDICE demonstrates good performance both on average- reward and discounted reward cases in different settings. The right two figures in each row show the log MSE curve versus optimization steps, where GenDICE achieves the smallest loss. In the discounted reward case, GenDICE shows significantly better and more stable performance than the
8

---

Published as a conference paper at ICLR 2020
strong baseline, DuaIDICE. F shows better performance of GenDICE than all baselines in the more challenging HalfCheetah domain.
Mode Rood
Imperianc tampliy
Dea OCC
Beecher, 2m0,90
ym 90
p=0.99
5m0.33
a-10.0 0.33, 0.86)
10
22
100
1060
CAA Bahanoer
20000 42993 Gp00 RC393120230
Trenctorns
Lengt
Reather ye1.0
pet
yet
pe0.33
angh 0.00)
122
30000 FOW
13/00d
Figure 3: Results on Reacher. The left three plots the first row show the log MSE of estimated av- erage per-step reward over different numbers of trajectories, truncated lengths, and behavior policies
(MI and M2 mean off-policy set collected by multiple behavior policies with a [0.0, 0.33] and = [0.0, 0.33, 0.66). The right two figures show the loss curves towards the optimization steps. Each plot in the second row shows the average reward case.
Imporiance Sempiing
DuvOrCE
y010
Lange
Truncred Lengt
Figure 4: Results on HalfCheetah. Plots from left to the right show the log MSE of estimated average per-step reward over different truncated lengths, numbers of trajectories, and behavior policies in discounted and average reward cases.
6.3 ABLATION STUDY
Finally, we conduct an ablation study on GenDICE study its robustness and implementation sen- sitivities. We investigate the effects of learning rate, activation function, discount factor, and the specifically designed ratio constraint. We further demonstrate the effect of the choice of divergences and the penalty weight.
Effeets of the Learning Rate mator, and stochastic optimization, it is necessary to show sensitivity to the learning rate with {0.0001, 0.0003, 0.001, 0.003). with results in Figure 5 When & = 0.33, ie., the OPE tasks are relatively easier and GenDICE obtains better results all learning rate settings. However, when a = 0.0, ie., the estimation becomes more difficult and only GenDICE only obtains reasonable results with the larger learning rate. Generally, this ablation study shows that the proposed method is not sensitive to the learning rate, and is easy to train.
Since we are using neural network as the function approxi-
Activation Function of Ratio Estimator We further investigate the effects of the activation func- tion on the last layer, which ensure the non-negative outputs required for the ratio. To better un- derstand which activation function will lead to stable trainig for the neural correction estimator, we empirically compare using i) (-)2: ii) log(1 1 + exp(-)); and iii) exp(.). In practice, we use the (-)² since it achieves low variance and better performance in most cases, as shown in Figure
Effects of Discount Factors We vary 7 E {0.95, 0.99, 0.995, 0.999, 1.0} to probe the sensitiv- ity of GenDICE. Specifically, we compare to DualDICE, and find that GenDICE is stable, while DuaIDICE becomes unstable when the y becomes large, as shown in Figure 6 GenDICE is also more general than DualDICE, as it can be applied to both the average and discounted reward cases.
Effects of Ratio Constraint In Section B we highlighted the importance of the ratio constraint. Here we investigate the trivial solution issue without the constraint. The results in 6 strate the necessity of adding the constraint penalty, since a trivial solution prevents an accurate corrector from being recovered (green line in left two figures).

---

Published as a conference paper at ICLR 2020
10001
08982
5.00
Souddee peidt vil
Hoater
Tectee grdE se1
Secter
Peather jo
+3008
2003
2008
of
#: Cape
Figure 5: Results of ablation study with different learning rates and activation functions. The plots show the log MSE of estimated average per-step reward over training and different behavior policies.
GerOIcE popeerts
CenOCCE jeif peratoo
Sancher Jo
-04
2000 10730 0000
2302 0303
10003
Depoart 3.00
3080
Dscouu Rodoe
Figure 6: Results of ablation study with constraint penalty and discount factors. The left two figures show the effect of ratio constraint on estimating average per-step reward. The right three figures show the log MSE for average per-step reward over training and different discount factor 7.
Effects the Choice of Divergences We empiri- cally test the GenDICE with several other alternative di- vergences, e.g., Wasserstein-1 distance, Jensen-She -hasnn-Shannon divergence, LLddivergenc,, Hellinger divergence, and MMD. To avoid the effects of other factors in the estima- tor, e.g., function parametrization, PageRank task on BA graph with 100 nodes and 10k of- fline samples. All the experiments are evaluated with 20 random trials. To ensure the dual function to be 1- 1-Lipchitz, we add the gradient penalty. Besides, we use a learned Gaussian kernel in MMD, similar to Li et al.] (2017). As we can see in Figure aaa), the GenDICE estimator is com- patible with many different divergences. Most of the di- vergences, with appropriate extra techniques to handle the difficulties in optimization and carefully tuning for extra parameters, variants of GANs (Lucic et al., 2018). However, K L--iveegeeece is an outlier, performing notice- ably worse, which might be caused by the ill-behaved exp() in its conjugate function. The x²- divergence and JS-divergence are better, which achieve good performances with fewer parameters be tuned.
focus the offline
(a)
(b)
Figure 7: Results of ablation study with (a) different divergence and (b) weight of penalty x. The plots show the log LL-Divergence of OPR on Barabasi-Albert graph.
achieve similar performances, consistent with phenomena in the
Effects of the Penalty Weight The results of different penalty weights À are illustrated in Fig- 7(b). We vary the À E [0.1, 5] with --vdiverge Within a large range X, the performances of the proposed GenDICE are quite consistent, which justifies Theorem [ The penalty multiplies with A. Therefore, with increases, the variance of the stochastic gradient estimator also increases, which explains the variance increasing in large À in Figure b)). In practice, À is reasonable choice for general cases.
7 CONCLUSION
In this paper, we proposed a novel algorithm GenDICE for general stationary distribution correction estimation, which can handle both the discounted and average stationary distribution given multiple behavior-agnosee samples. Empirical results on off-policy evaluation and offline PageRank show the superiority of proposed method over the existing state-of-the-an methods.
ACKNOWLEDGMENTS
The authors would like to thank Ofir Nachum, the rest of the Google Brain team and the anonymous reviewers for helpful discussions and feedback.
10

---

gan. arXiv preprint Published as a conference paper at ICLR 2020
REFERENCES
Christophe Andrieu, Nando de Freitas, Arnaud Doucet, and Michael I. Jordan. An introduction to MCMC for machine learning. Machine Learning, 50(1-2):5-43, 2002.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71(1):89-129, 2008.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. frXiv:1701.07875 2017.
Wasserstein
Francis R. Bach. Breaking the curse of dimensionality with convex neural networks. CoRR. abs/1412.8690, 2014.
Leemon Baird. Residual algorithms: reinforcement learning with function approximation. In Proc. Intl. Conf. Machine Learning, pp. 30-37. Morgan Kaufmann, 1995.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Discriminative learning for differing training and test distributions. In Proceedings of the 24th international conference on Machine learning, pp. 81-88. ACM, 2007.
Léon Bottou, Jonas Peters, Joaquin Quinonero-Candela, Denis Xavier Charles, D. Max Chicker- ing, 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.
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of markov chain monte carlo. CRC press, 2011.
Bo Dai, Niao He, Yunpeng Pan, Byron Boots, and Le Song. Learning from conditional distributions via dual embeddings. CoRR, abs/1607.04555 2016.
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 35th International Conference on Machine Learning (ICMI., pp. 1133-1142, 2018.
Miroslav Dudik, 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.
R. M. Dudley. Real analysis and probability. Cambridge University Press, Cambridge, UK, 2002.
Carles Gelada and Marc G 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.
Andrew Gelman, John B Carlin, Hal S Stern, David B Dunson, Aki Vehtari, and Donald B Rubin. Bayesian data analysis. Chapman and Hall/CRC, 2013.
A. Gretton, K. Borgwardt, M. Rasch, B. Schoelkopf, and A. Smola. A kernel two-sample test. JMLR, 13:723-773, 2012.
Arthur Gretton, Alexander J. Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Dataset shift in machine learning. In J. Qui nonero-Candela, M. Sugiyama, A. Schwaighofer, and N. Lawrence (eds.), Covariate Shift and Local Learning by Distribution Matching, pp. 131-160. MIT Press, 2008
Donald Gross, Carl M. Harris, John Shortle, and James M. Thompson. Fundamentals of Queueing Theory. Wiley Series in Probability and Statistics. Wiley, 5th edition, 2018.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Im- proved training of wasserstein gans. In Advances in Neural Information Processing Systems, pp- 5767-5777, 2017.
11

---

Published as a conference paper at ICLR 2020
Zhaohan Guo, Philip S Thomas, and Emma Brunskill. Using options and covariance testing for long horizon off-policy policy evaluation. In Advances in Neural Information Processing Systems, pp. 2492-2501, 2017.
D. Haussler. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik- Chervonenkis dimension. J. Combinatorial Theory (A), 69(2):117-232, 1995. Was University of CA at Santa Cruz TR UCSC-CRI-91-41.
Nan Jiang and Lihong Li. Doubly robust off oof-colicy value evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 652-661, 2016.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprini 102.:0690,,,06/8, 2019.
Takafumi Kanamori, Shohei Hido, and Masashi Sugiyama. A least-squares approach to direct im- portance estimation. Journal of Machine Learning Research, 10(Jll):391-1445) 2009.
Guanghui Lan and Zhiqiang Zhou. Algorithms for stochastic optimization with expectation con- straints. arXiv preprint 1604. 2016.
Amy N. Langville and Carl D. Meyer. Deeper inside PageRank. Internet Mathematics, 2004.
Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Finite-sample analysis of least- squares policy iteration. Journal of Machine Learning Research, 13(000):3041-3074 2012.
Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabas Poczos. Mmd gan: To- wards deeper understanding moment matching network. In I. Guyon. U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Curran Associates, Inc., 2017.
Processing Systems 30, pp. 2203-2213
Chunyuan Li, Ke Bai, Jianqiao Li, Guoyin Wang, Changyou Chen, and Lawrence Carin, Adversarial learning of sampler based on an unnormalized distribution. arXiv preprint arXiv:190I.006. 2019.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:
2015.
Qihang Lin, Mingrui Liu, Hassan Rafique, and Tianbao Yang. Solving beakly-convex-weakly concave saddle-point problems weakly-monotone variational incquality. arXiv preprint arXiv:1810.1003 10207, 2018
Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nomconvex-concave minimax problems. CoRR, abs/1906.00331. 2019.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of borizon: Infinite- horizon off-policy estimation. In Advances in Neural Information Processing Systems 3/ (NIPS), pp. 5361-5371, 2018
Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are gans created equal? a large-scale study. Advances in neural information processing systems, pp. 700-709, 2018.
David G. Luenberger and Yinyu Ye. Linear and Nonlinear Programming. Springer Publishing Company, Incorporated, 2015. ISBN 5319188410, 9783319188416.
Sean Meyn and Richard L. Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1rXiv:/312.500 2013.
12

---

Published as a conference paper at ICLR 2020
A. Müller. Integral probability metrics and their generating classes of functions, Advances in Applied Probability, 29(2):429 443, 1997.
Susan A Murphy, Mark van der Laan, James Robins, and Conduct Problems Prevention Re- search Group. Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 2001.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Schavior-agnosta estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, 2019.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. on Optimization, 19(4):1774-1009 January 2009. ISSN 1052-6234.
X.L. Nguyen, M. Wainwright, and M. Jordan. Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization. In Advances in Neural Information Processing Systems 20, pp. 1089-1096. MIT Press, Cambridge, MA, 2008
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan:
Training generative neural samplers using variational divergence minimization. In Advances neural information processing systems, pp. 271-279, 2016.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
Doina Precup, S. Sutton, and S. Singh. Eligibiliit traces for off-policy policy evaluation. In Proc. Intl. Conf. Machine Learning, pp. 759-766. Morgan Kaufmann, San Francisco, CA, 2000.
Doina Precup, Richard S. Sutton, and Sanjoy Dasgupta. Off-policy temporal-difference learning with funtion approximation. In Proceedings the 18th Conference Machine Learning (ICML), 2001.
pp.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Shai Shalev-Shwards and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA, 2014. ISBN 1107057132, 9781 107055135.
Alexander Shapiro, Darinka Dentcheva, al. Lectures stochastic programming: modeling and theory, volume 16. SIAM, 2014.
A. Smola, A. Gretton, and K. Borgwardt. Maximum mean discrepancy. In Proc. Annual Conf. Computational Learning Theory, 2006. submitted.
Jiaming Song, Shengjia Zhao, and Stefano Ermon. A-nice-me: Adversarial training for meme. In Advances in Neural Information Processing Systems, pp. 5140-5150, 2017.
B. Sriperumbudur, K. Fukumizu, A. Gretton, B. Schoelkopf, and G. Lanckriet. On integral probabil- ity metrics, é-divergences and binary classification. Technical Report 1tXx::0001.269844 arXiv, 2009.
Alex Strehl, John Langford, Lihong Li, and Sham Kakade. Learning from logged implicit explo- ration data. In Advances in Neural Information Processing Systems, pp. 2217-2223 2010.
M. Sugiyama, S. Nakajima, H. Kashima, P. von Bünau, and M. Kawanabe. Direct importance estimation with model selection and its application to covariate shift adaptation. In Advances in Neural Information Processing Systems 20, pp. 1433-1440, Cambridge, MA, 2008
Richard S Sutton, Csaba Szepesvári, Alborz Geramifard, and Michael P Bowling. Dyna- style planning with linear function approximation and prioritized sweeping. arXiv preprint arXiv: /2X6.3/20..2288 2012.
13

---

Published as a conference paper at ICLR 2020
R.S. Sutton and A.G. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.
Philip Thomas and Emma Brunskill. Data-efficient off off-policy policy evaluation for reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pp. 2139-2148, 2016.
John Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42:674-690 690, 1997.
Dilin Wang and Qiang Liu. Learning to draw samples: With application to amortized mle for generative adversarial learning. arXiv preprint arXiv:1611.01725 2016.
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off-policy evaluation in contextual bandits. In ICMI, 2017.
Hengshuai Yao and Dale Schuurmans. Reinforcement ranking. arXiv preprint arXiv:1303.5988, 2013.
B. Yu. Rates of convergence of empirical processes for mixing sequences. Annals of Probability, 22(1):94-116, 1994.
14

---

Appendix
A PROPERTIES OF GENDICE
For notation simplicity, we denote = (s)a) S A and P (+'l=) (a'ls") P (s')s,a). Also define || == (),)), (a) p (x) dr. We make the following assumption ensure the existence of the stationary distribution. Our discussion is all based on this assumption.
Under the target policy, the resulted state-action transition operator T has unique stationary distribution in terms of the divergence (-Il-).
Assumption 1
If the total variation divergence is selected, the Assumption requires the transition operator should be ergodic, as discussed Meyn & Tweedie (212))
A.1 CONSISTENCY OF THE ESTIMATOR
Theorem For arbitrary X > O, the solution the optimization Equ 11 is u(s.a)
p(a.a) for E (0, 1].
Proof For y E 10, there is not degenerate solutions to D ((T) (T OT) 1lp T). The optimal
2 solution is a density ratio. Therefore, the extra penalty (E)((t) [T (x)] - 1)² does not affect the optimality for v\ 0.
When 7 = 1, for AA > 0, recall both ((TH, TT) [|p- 7) and (Ep(a) [T (x)] - 1) are non- j(z) negative, and the the density ratio p(r) leads to zero for both terms. Then, the density ratio is solution to (7). For any other non-negative function T (x) 2 0, if it is the optimal solution to (T), then, we have
(z') / p (x'|z) ( (x) dz, (15)
D ((TF, T)) 11pp 7) 0 p(x')(aa') (TH (x)
(Bp(a) [r (x)] 1) 1)² = Ep(x) F (x) = 1.
(16)
We denote μ (x) = p (x) 7 (z), which is clearly density function. Then, the optimal conditions in Equation 15 limply
u u(x') ( f p (x' (d'(z) p (x) dz,
or equivalently, y is the stationary distribution of T. We have thus shown the optimal (x) is the target density ratio.
p(z)
p(w)
A.2 CONVEXITY OF THE OBJECTIVE
Proof Since the & is convex, we consider the Fenchel dual representation of the f-divergence Do ((T оT) 1lp (ip.T). i..
Do ((TP 7:00 TT) [|p. T) max {T,
fEn--R
= (1 - 7) Epor [f (x)] + (BT,(a,))) [T (x) Ep(z) (x) (f)). (17)
It is obviously (T, is convex in for each then, D& ((T), T) 1|p is convex. The term (E, (7) - 2 is also convex, which concludes the proof.
15

---

Published as a conference paper at ICLR 2020
Algorithm 1 GenDICE (with function approximators)
Inputs: Convex function and its Fenchel conjugate 6¹, off-policy data {(s()) al)) ,(0) s()) Mir initial state $0 ~ Mo., target policy distribution correc-
tor new, (:..), I.r, (, constraint scalar u, learning rates Wr. II The number of iterations K,
batch size B.
for t = I...., K do
Sample batch {(s(0) a0)) (()) {(0) from D.
n Sample batch { i==1 from Ag.
Sample actions a'(() (s) for i = ,,..., B.
Sample actions d T(5))) (1) ), for -....,,
Compute empirical loss J2a (T, u, f) = (1 - -7) -7) [f (s, a)] + ,BT (s)
EE (s, (f (8, + f (8, a)) + A [Ep (5,a) ul u2
Update W4 wi 7/ Vo, J
Update Wy - W + n1 V Jx2.
Update
The V "Jy2.
end for Return n.w..
B
ALGORITHM DETAILS
We provide the unbiased gradient estimator for V Vu..w.y, J (T, f) in Equ 14 below:
1
Jx (T, u. =,T, Vu, T (s (s' Ep Vw, (s,a) f (s. 1 (s,
+duEp V T (s.
(18)
Vadya (T, A (Ep IT (8, a) 11 1]]--)
(19)
V J (T, = (1 7) E po /w, I (s, + BB, [T as Vuy [((,
(20)
-Ep (s)a) (1+ 21+25(,, (s, Vw, (s,
Then, we have the psuedo code which applies SGD for solving Eqn [14]
C PROOF OF THEOREM 3
For convenience, we repeat here the notation defined in the main text. The saddle-point reformula- tion of the objective function of GenDICE is: J () (1 7)) Epg [J (<')] BB, |T f
1 [2 - Epp(s) |T (x) 6" (ʃ (x)) + X (Epcz) [uT (x) 1 u]
2
To avoid the numerical infinity in Do (-11-), we induced the bounded version
J ( = max [T, u, f) D (TF o r) |pp 7) 2 (Ep(z) [r (x)] -00]-11) 1)²
I1/I SC,a
in which DC 6 (-11-) still a valid divergence, and therefore the optimal solution 7" is still the sta-
tionary density ratio m(w)) We denote the J (r, nt f) as the empirical surrogate of (T, μ4, f) on
p(z).
samples D (zx,z),² Tigmo (I,x') with the optimal solution in (H,F, as ( 7¹ 83)
Furthermore, denote
#i = arg min / (T) TEN
T² = arg min J (T)
TESXA-+R
16

---

Published as a conference paper at ICLR 2020
with optimal ,f',"), and
(T) max J (T. U,);
JEF,uER
(T) JEF,uER
uT,
max
We apply some optimization algorithm for J (T, u, f) over space (H, IR), leading to the output (t.ūff)
Under Assumption + E Tul S (C + 1)}. We choose the o* (-) k-Lipschitz continuous, then, the J [TT, f) is Cp.
2. we need only consider || I C, then, the corresponding dual u = Ep (7)
max
|| p, (1 11-1) 7)
How
+x) II (x)) dr |u], and
k C, 1)
P
p.30
Lipschitz continuous function w.r.t. (f, u) with the norm [I ((f, u) Ca.C.A == (C + X + 1) + maxiel- (-Ø -ipscciip continuous function w.r.t 7 with the norm |||| p,1 == f Ir (x)] (x) dr.
We consider the error between & and r* using standard arguments (Shalev-Shwartz Ben-David 2014
Bach 2014), i.e.
d(f,r") = J (r")
-
The discrepancy d (T,T*) [T) 0 and d (T, = 0 if and only p- is stationary distribution of T in the weak sense of D (-11-).
Remark: In some special cases, the suboptimality also implies the distance between f and r" Specifically.for > if the transition operator pa can be represented pa QAQ where Q denotes the (countable) eigenfunctions and A denotes the diagonal matrix with eigenvalues, the largest of which 1. We consider @ (-) as identity and f F == { span ( (2) [I.fll s the d r") will bounded from below by a metric between r and r" Particularly, we have
$1). then
D& ((T TT) I1p- T) = max E (T [T (x) f (x') - Ep() [T (z) f (x)] = ||5 P" T p.2
fEF
Rewrite 7 = a7* + C. where ( E span (2)-e), ), then
p o Cll Do ((T 7:00 TT) [Ip-7) 7) ||aT" - ap Or + + p p o clp.. = =Ils 1(--Pt
Recall the optimality of 7", ie., Do (TH - 11p (1pp--)) 0, we have
d(T,T") (7) || P o <l1p2 ||(T T") (P)
C.I ERROR DECOMPOSITION
We start with the following enror decomposition: d
(+T) + + (F
(7*).
For é1, we have
( = IZ)) L(F) - ( + T. [( - J (f+)
We consider the terms oye-by- By definition, we have
- = max J (7, u, f) max J (+, u, JEF
f
S Ope sup inf
E feEF (f u1) (f2,
(21)
Cupprox (F)
which is induced by introducing FF for dual approximation.
For the third term L (ft) (ftt,, have
L (ft) J (+++)= = max
J (F f)
max J (+t u, f) S 0.
JEF,uEU
J.uEU
17

---

Published as a conference paper at ICLR 2020
- (f+)) For the term -
-f-) = L(F) - +2 (f%) L (f%)
Eopt
(T) -Z(r) + Eopt
sup
TEM
sup
max
J (T, - max
J (T, (T,,,,)) + Eopt
rEH JEF
JEF,uEU
< sup sup
-J
Eopt
rEH JEF,uEU
= 2. Gest + Copt.
(22)
J (T, - [ uT,
where we define Cest == SUPrER.EEF.WEE Therefore, we can now bound 61 as
61 S CT Sappproo (F) 2east + Copt.
For 62, we have
62
J
J (+x) ( + ( (Tx) ( (Ti) J (TH) J (7*).
We consider the terms from right to left. For the term J (T+) - JJ (T"), we have
J J(r'=
(fh. 12, f3) (T', " fz + J (7", a", fr I - (("
50
= =J W f3) - J P3) $ Co.c. sup inf || - T2 12ll
a TEN
Capproo (H)
which induced by restricting the function space H. The second term nonpositive, due to the optimality of (u²", f*). The final inequality comes from the fact that J (T, u, f) is Co.CA Lipschitz w.r.t. T. For the term L (f% - J (Ti)). by definition
((TH) - (Ti) FEFUNEU
max
fT
max f.eEt
50.
For the term (ft) (Tx), we have
L (f() L (Tx) L (fn) - (ft) + +L - (rre)) +I (Ti) (Tie)
20
2 sup TEH
((r) -(7)
(T, (T,
= 2 sup
rEH.fEF,wEt
2 Eest-
where the second term is nonpositive, thanks to the optimality of *x. Finally, for the term J (+#) J (TH), using the same argument in Equation 21 we have
(f*) J (T+) S Cpe,e, Spp.ec,aappra (F).
Therefore, we can bound E2 by
E2 < C..prxaaprro (7) + .p (F) + Dcest-
In sum, have
d(frr') S 4east + Eopt + 2Cpp Fappppre (F) + Co. (H). In the following sections, we will bound the east and Copt.
C.2 STATISTICAL ERROR
In this section, we analyze the statistical error
J (T, ff ( [r.
Cest
sup eeE
18

---

Published as a conference paper at ICLR 2020
Tp (x, x²), which has been studied by previous authors (c.g.. Sutton et al. 2012: Nachum et al. 2019). However,
We mainly focus the batch RL setting with i.i.d. samples D
i=1
discussed in the literature (Antos al., 2008; Lazaric al. 2012 Dai al. 2018 Nachum
et al. 2019), using the blocking technique of Yu 1994). the statistical error provided here can be generalized 8-mixing samples in single sample path. We omit this generalization for the sake of expositional simplicity.
To bound the Easts we follow similar arguments by Dai al. (2018): Nachum et (019) via the covering number. For completeness, the definition is given below.
The Pollard's tail inequality bounds the maximum deviation via the covering number of function class:
Lemma 4 PPollard (2012) Let G be a permissible class of 2 - [-M, M) functions and {2s) i=1 are i..dd samples from some distribution. Then, for any given 0, N
1
Σ ((Z)) -(()))((((2)) E[((2)] >e) < 8E Ni
9, (2))))]]
-NNe
sup gEg
exp 512M2
N
8
The covering number can then be bounded in terms of the function class's pseudo-dimension:
Lemma 5 (Haussler (1995), Corollary 3) For any set X, any points x!:N E XN any class F of functions on taking values in [0, M) with pseudo-dimension D < co, and any >> 0,
(2cM Dy
Ni (e, Se +1
The statistical eπтог Eest can be bounded using these lemmas.
Lemma 6 (Stochastic error) Under the Assumption 2 if Φ² is k-Lipschitz continuous and the psuedo-dimension of H and are finite, with probability at least 1 we have
log N + log
Eest O
N
Proof The proof works by verifying the conditions in Lemma computing the covering number.
Denote the ft (x, x') (1 (a)
(z)) (x) -u X u²
we will apply Lemma 4 with
12 = (x), hHx
We check the boundedness of hç.u.f (x), Based Assumption 2 only consider the H
and u E U bounded by C and C 1. We also rectify the || = C. Then, we can bound the |
max - -6" (6) + (1 + + + XC2 (EE--C.)
$
+ +11100
(C+ -C.Co + X2C +1) M, where Co -axx -0" (1). Thus, by Lemma have
J u, J
sup FEH.fEF.uEU
P
sup FEN
Σ
hç.u, (Z+) - E [hc.a.f]
i=1
<
C Ni
g
G. (2, (
exp
512M?
-Ne2
(23)
19

---

Published as a conference paper at ICLR 2020
Next, we check the covering number of G. Firstly, bound the distance in g,
No .1 (Z,) har (2.)1
C C+ + M(C +1)
1 1+ GC 1C
m (x:) -2 (z;)) +
Σ
fi (x.) f2 (xS)
N
N
1=1
N
RC
1f1 (z4) fo (2.)) A 12C + 11 u2 Σ
N
which leads to
Ni [[C=+(B+++t44))C+)))(C3)
S W1 (,,H, (a:))= Ni C,F, (x)) Ni (c.F) NG (c.U).
For the set U = -------1 1, + 1]. we have,
2C +2
(c) S
Denote the pseudo-dimension of and F as DH and Dy, respectively, we have NV
Ni ( (3 21 + +3) (C + 1)) 6, {
22 +
4eC'
Du +2D
<e (Dx (Dx++))Dx+
e' e'
which implies
Mi 9, (1
C+1 e² (D# + 1) (Dz +1)²
32 (C( + (3) 2 + + x) (C + 1)) eC 1))
Dr+
< 20
C1
where D1 DH + D + and
C+1 3 (Dx + 1)) (32 23 (C (C+ e)) (C+1))
C
2C
Combine this result with Equation 23
we obtain the bound for the statistical error:
( Dr -Ne
[TT,, (T.u. < SC,
P
sup TE
exp
512M
(24)
Setting c
Cs (log N +oog })
with C2 = max (8C1) 1 512MD,,512M, 1). we have
N
!
D1
-Ne²
SC
exp
512M
5 6.
C.3 OPTIMIZATION ERROR
In this section, we investigate the optimization error
Eopt 7 (
Notice our estimator mintew max J JT,,u, u, f) is compatible with different parametrizations for (H, and different optimization algorithms, the optimization error will be different. For the general neural network for (T, f), although there are several progress recently (Lin et al. 2018 Jin et al., 2019 Lin et al. 2019) about the convergence to a stationary point or local minimum, remains largely open problem quantify the optimization error, which is out of the scope of this paper. Here, we mainly discuss the convergence rate with tabular, linear and kernel parametrization for (7, J).
20

---

Published as a conference paper at ICLR 2020
Particularly, consider the linear parametrization particularly, i.e., T ((x) - +h (x) with {wy, 4hr (x) 2 0} and (x) w V (x). With such parametrization, the J (T, u, f) is still convex-
concave w.r.t (w-: Wy, u).
We can bound the Eopt by the primal-dutt gap Egap'
Eop!
(f) - (fx)
max uf, u) - (
+(( + (H. vT,3)
-min J TCH T, ū.
fEFWEE
uf,
min J (T, r,ū,f)
max fEJ'uEU
TEH
Czop
With vanilla SGD, we have Egop 0
where T is the optimization steps (Nemirovski et al,
vT
2009). Therefore, Eopt = [Eops] =
where the E [-] is taken w.r.t. randomness SGD.
C.4
COMPLETE ERROR ANALYSIS
We now ready to state the main theorm in precise way:
Theorem 3 Under Assumptions and 7 the stationary distribution 1r exists, i.e., max To [f] E
(0" 10"
(f) O.
the Φ- (-) is k-Lipschitz continuous, lif C <
00, Vf E Fr, and the psuedo-dimense of H. and F are finite, the error between the GenDICE
estimate to 7 (x) p(z)
u(a) is bounded by
B[J(F) J
Capproz (F,H) +
Copt
where []] is w.r. the randomness in sample 'D and in the optimizution algorithms. copt is the optimization error, and Capprox (F, H.) is the approximation induced by (F, H) parametrization of f).
Proof We have the total error as
E [ (f) J (T') S 4E [Ceee] + E [Copt] + Capproz H)),
(25)
where Eapprox 2CT N.xx Tx
Eapproo (F) + Ca, Coppren (H). For Copt. we can apply the results for
SGD in Appendix
C.3
We can bound the [Eeat] by Lemma 6 Specifically, we have
[estt] = 8) C2 (log N + log !) + 5M -0
log N
N
by setting
VN
Plug all these bounds into Equation 25 we achieve the conclusion.
D EXPERIMENTAL SETTINGS
D.1 TABULAR CASE
For the Taxi domain, we follow the same protocol used in Liu et al. (0188) The behavior and tar- get policies are also taken from et al. (2018) (referred in their work as the behavior policy for a = 0). We use similar taxi domain, where grid size of 5 yields 2000 states in total (25 16 x5, cor- responding to taxi locations, passenger appearance status and 5 taxi status). We set our target policy the final policy n, after running Q-learning (Sutton & Barto 1998) for 1000 iterations, and
21

---

Published as a conference paper at ICLR 2020
set another policy क after 950 iterations as our base policy. The behavior policy is mixture policy controlled by a as π = (1 - a ,T + QTT,, L.e., the larger a is, the behavior policy is more close to the target policy. In this setting,
solve for the optimal stationary ratio exactly using matrix opera- tions. Since et al. (2018) perform a similar exact solve for |S] variables ju(s), for better compar- ison also perform our exact solve with respect to |S] variables T(s). Specifically, the final objec- tive of importance sampling will require knowledge of the importance weights u(a(s)/p(als).
For offline PageRank, the graph statis- ties are illustrated in Table [ and the de- gree statistics and graph visualization are shown in Figure 8 For the BarabasiAl- bert (BA) Graph, it begins with ini- tial connected network of mo nodes in the network. Each new node is connected m S. mo existing nodes with a probability that is proportional to the number of links
Table 1: Statistics of different graphs.
Dataset
Number of Nodes
Number of Edges
BA (Small)
100
400
BA (Large)
500
2000
Cora
2708
5/129
Citeseer
3327
4731
that the existing nodes already have. Intuitively, heavily linked nodes ("hubs') tend to quickly accu- mulate even more links, while nodes with only few links are unlikely to be chosen as the destina- tion for a new link. The new nodes have a 'preference' to attach themselves to the already heavily linked nodes. For two real-world graphs, it built upon the real-world citation networks. In our experiments, the weights of the BA graph is randomly drawn from a standard Gaussian distribution with normalization to ensure the property of the transition matrix. The offline data collected by random walker on the graph, which consists the initial state and next state in a single trajectory. In experiments, we vary the number of off off-policy samples to validate the effectiveness of GenDICE with limited offline samples provided.
Banazesi- Bresh
Sarabos Aber Grash
Citeseor
100
Dagien
Degren
25
Degne
Dagren
Figure& 8: Degree statistics and visualization of different graphs
D.2 CONTINUOUS CASE
We use the Cartpole, Reacher and HalfCheetah tasks as given by OpenAI Gym. In importance sam- pling, learn a neural network policy via behavior cloning, and use its probabilities for computing importance weights w. (a]s). All neural networks are feed-forward with two hidden layers of dimension 64 and tanh activations.
Discrete Control Tasks We modify the Cartpole task be infinite horizon: We use the same dynamics as in the original task but change the reward to be -1 if the original task returns a termi- nation (when the pole falls below some threshold) and otherwise. We train a policy on this task with standard Deep Q-Learning (Mnih et al. 2013) until convergence.
We then define the target policy π. as a weighted combination of this pre-trained policy (weight 0.7) and a uniformly random policy (weight 0.3). The behavior policy π for a specific 0 < a < 1 is taken be a weighted combination of the pre-trained policy (weight 0.55 + 0.15a) and a uniformly random policy (weight 0.45 - 0.15a). We train each stationary distribution correction estimation method using the Adam optimizer with batches of size 2048 and learning rates chosen using a hyperparameter search from {0.0001, 0.0003, 0.001, 0.003) and choose the best one as 0.0003.
Continuous Control Tasks For the Reacher task, we train deterministic policy until convergence via DDPG (Lillicrap et al., 2015). We define the target policy π as Gaussian with mean given by the pre-trained policy and standard deviation given by 0.1. The behavior policy no for specific 0- S a < 1 is taken to be a Gaussian with mean given by the pre-trained policy and standard deviation given by 0.4 0.3o. We train each stationary distribution correction estimation method using the
22

---

Published as a conference paper at ICLR 2020
Adam optimizer with batches of size 2048 and learning rates chosen using hyperparameter search from {0.0001, 0.0003, 0.001, 0.003) and the optimal learning rate found was 0.003).
For the HalfChectah task, we also train deterministic policy until convergence via DDPG (Lilli- crap ct al. 2015). We define the target policy π as a Gaussian with mean given by the pre-trained policy and standard deviation given by 0.1. The behavior policy % for specific 0 a < is taken to be a Gaussian with mean given by the pre-trained policy and standard deviation given by 0.2 0.1a. We train each stationary distribution correction estimation method using the Adam optimizer with batches of size 2048 and learning rates chosen using a hyperparameter search from {0.0001, 0.0003, 0.001, 0.003) and the optimal learning rate found was 0.003.
E ADDITIONAL EXPERIMENTS
E. OPE FOR DISCRETE CONTROL
On the discrete control task, we modify the Cartpole task to be infinite horizon: the original dy- namics is used but with modified reward function: the agent will receive -1 if the environment returns a termination (i.e., the pole falls below some threshold) and otherwise. As shown in Figure our method shows competitive results with IS and Model-Based in average reward case, but our proposed method finally outperforms these two methods in terms of log MSE loss. Specifically, it relatively difficult to fit a policy with data collected by multiple policies, which renders the poor performance of IS.
Carpule (a1
Corgule 235 CAR)
Carpale Jarpo C-L S
y=
3.90
0.00
3.50
0.90
1200
Corpol 13-030
Delpoc
Y:1.0
1.00
1.00
0.00
10000 20000 3X000 430000
100000
20000 30000 4000
10000 200000 300000 40000
13000 230006 300000
400030
0 130
Figure 9: Results on Cartpole Fach plot in the first row shows the estimated average step reward over training and different behavior policies (higher corresponds to behavior policy closer to the target policy; the same in other figures); MI:a = [0.0, 0.33]: M2: a = [0.0, 0.33, 0.66)
E.2 ADDITIONAL RESULTS ON CONTINUOUS CONTROL
In this section, we show more results on the continuous control tasks, iee. HalfCheetah and Reacher. Figure [0] shows the log MSE towards training steps, and GenDICE outperforms other baselines with different behavior policies. Figure II better illustrates how our method beat other baselines. and can accurately estimate the reward of the target policy. Besides, Figure 12 shows GenDICE gives better reward estimation of the target policy. In these figures, the left three figures show the performance with off- policy dataset collected by single behavior policy from more difficult to easier tasks. The right two figures show the results, where off-policy dataset collected by multiple behavior policies.
Figure 13 shows the ablation study results in terms of estimated rewards. The left two figures shows the effects of different learning rate. When a = 0.33, i.e., the OPE tasks are relatively easier, GenDICE gets relatively good results in all learning rate settings. However, when = 0.0, i.c., the estimation becomes more difficult, only GenDICE in larger learning rate gets reasonable estimation. Interestingly, can with larger learning rates, the performance becomes better, and when learning rate is 0.001 with a 0.0. the variance is very high, showing some cases the estimation becomes more accurate. The right three figures show different activation functions with different
23

---

Published as a conference paper at ICLR 2020
behavior policy. The square and softplus function works well; while the exponential function shows poor performance under some settings. In practice, we use the square function since its low variance and better performance in most cases.
bamping
-2.
-10
5X00
20030
1000 11g
2030
6000 1000
10000
of Sacee
F-l Prace
20
Reacher lawd p-0.90
Rescher 1o-0.06
S0-10.0 0.301
Reacher
-20
-20
-30
-12
2f Sups
of Saps
# Stipe
of Dago
# Shepe
Figure 10: Results on Reacher. Each plot in the first row shows the estimated average step reward over training and different behavior policies (higher corresponds to behavior policy closer to the target policy; the same in other figures).
Voeaa
Sampl
Gend (Emm
Codd
Poeiter (ood yo1
Nouth 13-0 3gg
Natcer Josf T
Pro-ter jo 5 0.55
0.
C4
0.0
43
-04
2008 #50s 6600 (000 1606
2030 1200) (800) 6K0 103030
2000 43030 210% M000 13000
2006
1000 (230 (200) 10000
22003
5000
1500 1000
033
2000 40000 G0000 10000 1200
2000 4200 80000 2200 2003 4203 MCD0 B300 1200
23003 #55.0 100000 00300 100000
Figure 11: Results on Reacher. Each plot in the first row shows the estimated average step reward over training and different behavior policies (higher a corresponds to behavior policy closer to the target policy; the same in other figures).
2.0
25
235
2.6
34
2.5
12
12
32
1.2
20000 40000 50830 38900333000
20006 45003 5300 89389100530
20000 40693 53000 30099100005
18000 4500E #B903 53006 200000
23003 43000 60083 83030189000
Figure 12: Results on HalfCheetah. Each plot in the first row shows the estimated average step reward over training and different behavior policies (higher a corresponds a behavior policy closer to the target policy.
E.3 COMPARISON WITH SELF-NORMALIZATION TRICK
The nelf-normalization trick used in (Liu et al. 2018) encodes the normalization constraint in т. while the principled optimization technique is considered in GenDICE. Further, the self- normalization trick will lead to several disadvantages theoretically, in both statistical and compu- tational aspects:
24

---

Published as a conference paper at ICLR 2020
High eegelt
und pr16)
4.1
9:200pps
1400
Figure 13: Results of ablation study with different learning rates and activation functions. The plots
show the estimated average step reward over training and different behavior policies.
i) will generally not produce an unbiased solution. Although [Da (G (8,, a) is an unbiased
estimator for E[r]. the plugin estimator
का Dto [(.a) will be biased for r(s.a)
T(s.a)
E[T]
ii) It will induce more computational cost. Specifically, the self-normalized ratio will be in the form r(s.a)
[29 (u.ate T(s.a) which requires go through all the samples in training set D even for just estimating one stochastic gradient, and thus, prohibitive for large dataset.
of
Empirically, self-normalization is the most natural and the first idea we tried during this project. We have some empirical results about this method in the OPR setting.
Despite the additional computational cost, it per- forms worse than the proposed regularization technique used in the current version of Gen- DICE. Table 2 shows comparison between self- normalization and regularization on OPR with x²- divergence for BA graph with 100 nodes, 10,000 of- fline samples, and 20 trials. We stop the algorithms the same running-time budget.
Table 2: Comparison between regularization and ceff-nommalization.
log KL-divergence
neff-normalizaiion
-4.26 + 0.157
regularization
-4.74 + 0.163
25


Reviews:
[{"review_id": "r1geCyJTKB", "reviewer": "AnonReviewer3", "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": "Main contributions:\nThis paper generalizes the recent state-of-the-art behavior agnostic off-policy evaluation DualDice into a more general optimization framework: GenDice. Similar to DualDice, GenDice considers distribution correction over state, action pairs rather than state in Liu et al. (2018), which can handle behavior-agnostic settings. The optimization framework (in equation (9)) is novel and neat, and the practical algorithm seems more powerful than the previous DualDice. As a side product, it can also use to solve offline page rank problem.\n\nClarity:\nThis paper is well established and written. \n\nConnection of theory and experiment:\nI have a major concern for the theory 1 about the choice of regularizer $\\lambda$. For infinite samples case, the derivation of theory 1 is reasonable since both term is nonnegative. However, in practice we will have empirical gap for the divergence term, thus picking a suitable $\\lambda$ seems crucial for the experiment. I think a discussion on $\\lambda$  for average case in experiment part should be added. And compared to Liu et al. (2018) which normalized the weight of $\\tau$ in average case, which one is better in practice?\n\nOverall I think this paper is good enough to be accepted by ICLR. The optimization framework can also inspire future algorithm using different divergence.", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyluc57aFB", "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": "In this paper the authors proposed a framework for off-policy value estimation under the scenario of infinite horizon RL tasks. The new proposed method utilize the variational representation of $f$-divergence, which quantifies the difference between $\\mathcal{T}\\tau$ and $\\tau p$, where $\\tau$ is the parametric density ratio between the unknown behavior policy data and the target policy. If only if $\\tau$ is the true density ratio, the loss $\\mathcal{D}_{f}(\\mathcal{T}\\tau || \\tau p) = 0$. \n\nCompared with prior work (Nachum et. al 2019), the new proposed framework can generalize the undiscounted case $\\gamma = 1$, and the derivation for the new algorithm is quite simple and easy to follow. The experimental results show the advantage of the proposed methods over baseline methods such as model-based, DualDice etc, for both discrete and continuous cases. Moreover, I have two specific questions:\n\n- The choice of $f$-divergence. Although the author mentioned the difficulty of using the dual representation of KL divergence, it would be nice to have an ablation study that shows the effectiveness of various $f$-divergence (Personally I think Jensen-Shannon Divergence may be also a good choice).\n\n-The authors should also have a discussion that similar idea can be generalized to more general  distribution metrics such as Integral Probability Metrics, specifically wasserstein-1 distance (similar to wasserstein-gan) or maximum mean discrepancy (Maybe it is unnecessary to conduct experiments, some discussion should be enough to clarify the relationship. I think there is a concurrent submission using MMD metrics).\n \n\nOverall I think this is a good paper and I recommend for acceptance. \n\nReference Papers:\n- Nowozin, Sebastian, Botond Cseke, and Ryota Tomioka. \"f-gan: Training generative neural samplers using variational divergence minimization.\" Advances in neural information processing systems. 2016.\n- Arjovsky, Martin, Soumith Chintala, and Léon Bottou. \"Wasserstein gan.\" arXiv preprint arXiv:1701.07875 (2017).\n- Nachum, Ofir, et al. \"DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections.\" arXiv preprint arXiv:1906.04733 (2019).\n- Anonymous, “Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning”, submitted to ICLR 2020.\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 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": "H1l3zHj6Yr", "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": "This paper proposes a new estimator to infer the stationary distribution of a Markov chain, with data from another Markov chain. The method estimates the ratio between stationary distribution of target MC and the empirical data distribution.  It is based on the observation that the ratio is a fixed point solution to certain operators. The proposed method could work in the behavior-agnostic and undiscounted case, which is unsolved by the previous method.\n\nThis paper tackles an interesting problem with an increasing number of studies in the reinforcement learning community and gives a practical algorithm with strong empirical justification, as well as theoretical justification. I think this paper should be accepted.\n\nDetailed comments:\n1) This paper provides experiment results in multiple domains, including two continuous control domains which are more complex than experiments in previous OPE methods. The paper also provides many details about the learning dynamics and ablation studies, which is very useful for the reader to understand the result of the paper.\n2) The theoretical result is as same strong as previous work DICE and DualDICE, under similar assumptions.\n3) I appreciate this paper formalizes the two difficulties of degeneration and intractability, and then explain how those are addressed in a principled way. Degeneration is important and is at least ignored in two similar works on this topic.", "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": {}}]

Author rebuttal:

Meta-review: The authors develop a framework for off-policy value estimation for infinite horizon RL tasks, for estimating the stationary distribution of a Markov chain. Reviewers were uniformly impressed by the work, and satisfied by the author response. Congratulations! 

Decision: Accept (Talk)