Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
Authors: Pan Xu
Felicia Gao
Quanquan Gu
Venue:  (2020)
Keywords: Policy Gradient
Reinforcement Learning
Sample Efficiency

Abstract: Improving the sample efficiency in reinforcement learning has been a long-standing research problem. In this work, we aim to reduce the sample complexity of existing policy gradient methods. We propose a novel policy gradient algorithm called SRVR-PG, which only requires $O(1/\epsilon^{3/2})$\footnote{$O(\cdot)$ notation hides constant factors.} episodes to find an $\epsilon$-approximate stationary point of the nonconcave performance function $J(\boldsymbol{\theta})$ (i.e., $\boldsymbol{\theta}$ such that $\|\nabla J(\boldsymbol{\theta})\|_2^2\leq\epsilon$). This sample complexity improves the existing result $O(1/\epsilon^{5/3})$ for stochastic variance reduced policy gradient algorithms by a factor of $O(1/\epsilon^{1/6})$. In addition, we also propose a variant of SRVR-PG with parameter exploration, which explores the initial policy parameter from a prior probability distribution. We conduct numerical experiments on classic control problems in reinforcement learning to validate the performance of our proposed algorithms.

Published as a conference paper at ICLR 2020
SAMPLE EFFICIENT POLICY GRADIENT METHODS WITH RECURSIVE VARIANCE REDUCTION
Pan Xu, Felicia Gao, Quanquan Gu Department of Computer Science University of California, Los Angeles Los Angeles, CA 90094, USA panxuêcs, ucla. edu,
edu, qguêcs ucla edu
ABSTRACT
Improving the sample efficiency in reinforcement learning has been a long- standing research problem. In this work, we aim reduce the sample complexity of existing policy gradient methods. We propose a novel policy gradient algo- rithm called SRVR-PG, which only requires 0 episodes to find an e- approximate stationary point of the nonconcave performance function J(0) (i.e., o such that || [() S f). This sample complexity improves the existing result (11/5 for stochastic variance reduced policy gradient algorithms by factor of ((/))//)) In addition, we also propose a variant of SRVR-PG with parameter exploration, which explores the initial policy parameter from prior probability distribution. We conduct numerical experiments on classic control problems in reinforcement learning validate the performance of our proposed algorithms.
INTRODUCTION
Reinforcement learning (RL) (Sutton & Barto 2018) has received significant success in solving various complex problems such learning robotic motion skills (Levine al.) 2015). autonomous driving (Shalev-Shwartz et al.) 2016) and Go game (Silver et al. 2017D. where the agent progres- sively interacts with the environment in order to learn a good policy to solve the task. In RI., the agent makes its decision by choosing the action based on the current state and the historical rewards it has received so far. After performing the chosen action, the agent's state will change according to some transition probability model and new reward would be revealed to the agent by the envi- ronment based on the action and new state. Then the agent continues to choose the next action until reaches terminal state. The aim of the agent is maximize its expected cumulative rewards. Therefore, the pivotal problem in RL is to find good policy which is function that maps the state space the action space and thus informs the agent which action to take each state. To optimize the agent's 's policy in the high dimensional continuous action space, the most popular approach is the policy gradient method (Sutton al. 2000 that parameterizes the policy by an unknown parameter Rd and directly optimizes the policy by finding the optimal O. The objective function J(Ø) is chosen be the performance function, which is the expected return under a specific policy and is usually non-concave. Our goal is to maximize the value of (() by finding a stationary point 0* such that [O) [|2 O using gradient based algorithms.
Due to the expectation in the definition of J()), it is usually infeasible to compute the gradient exactly. In practice, one often uses stochastic gradient estimators such as REINFORCE (Williams) 1992), PGT (Sutton et al. 2000) and GPOMDP (Baxter & Bartlett 2001) to approximate the gradi- ent of the expected return based on a batch of sampled trajectories. However, this approximation will introduce additional variance and slow down the convergence of policy gradient, which thus requires a huge amount of trajectories to find good policy. Theoretically, these stochastic gradient (SG) based algorithms require O(1/e2) trajectories (Robbins & Monro, 1951) find e-approximate stationary point such that E| ((())))) < In order to reduce the variance of policy gradient algorithms, Papini al. (2018) proposed stochastic mariance-reducee policy gradient (SVRPG)
10(-) notation hides constant factors.

---

Published as a conference paper at ICLR 2020
Table I: Comparison on sample complexities of different algorithms to achieve |[
Algorithms
Complexity
REINFORCE (Williams 1992
0(1/e²)
PGT (Sutton et al. 2000)
0(1/e²)
GPOMDP (Baxter & Bartlett 2001
0(1/e)
SVRPG (Papini al. 2018
0(1/e)
SVRPG (Xu et al. 2019)
0(1/6/3)
SRVR-PG (This paper)
0(1/212)
algorithm by borrowing the idea from the stochastic variance reduced gradient (SVRG) (Johnson & Zhang 2013 Allen-Zhu & Hazan 2016 Reddi al. 2016a) in stochastic optimization. The key idea is to use so-called semi-stochastic gradient to replace the stochastic gradient used in SG methods. The semi-stochastic gradient combines the stochastic gradient in the current iterate with snapshot of stochastic gradient stored in an early iterate which is called a reference iterate. In prac- tice, SVRPG saves computation gradient methods. Papini et al.] (2018) also proved that SVRPG converges to an c-approximate sta- tionary point 0 of the nonconcave performance function (0) with [E[] (J) trajectories, which seems to have the same sample complexity as SG based methods. Recently, the sample complexity of SVRPG has been improved to 0(1/5//3) by a refined analysis (Xu et al. 2019), which theoretically justifies the advantage of SVRPG over SG based methods.
trajectories and improves the performance of SG based policy
after (11/²²)
This paper continues on this line of research. We propose a Stochastic Recursive Variance Reduced Policy Gradient algorithm (SRVR-PG). which provably improves the sample complexity of SVRPG. At the core of our proposed algorithm is a recursive semi-stochastic policy gradient inspired from the stochastic path-integrated differential estimator (Fang al. 2018), which accumulates all the stochastic gradients from different iterates to reduce the variance. We prove that SRVR-PG only takes ( trajectories to converge to an e-approximate stationary point f of the performance function, i.e., [ (() [12) e. We summarize the comparison of SRVR-PG with existing policy gradient methods in terms of sample complexity in Table I Evidently, the sample complexity of SRVR-PG is lower than that of REINFORCE, PGT and GPOMDP by a factor of (1/cl/22, and is lower than that of SVRPG (u et al. 2019) by a factor of ((1/c1/6)
In addition, integrate algorithm with parameter-basse exploration (PGPE) method (Schnke et al. 2008 2010), and propose a SRVR-PG-PE. algorithm which directly optimizes the prior prob- ability distribution of the policy parameter 0 instead of finding the best value. The proposed SRVR-PG-PE enjoys the same trajectory complexity as SRVR-PG and performs even better in some applications due to its additional exploration over the parameter space. Our experimental results on classical control tasks in reinforcement learning demonstrate the superior performance of the proposed SRVR-PG and SRVR- algorithms and verify our theoretical analysis.
1.1 ADDITIONAL. RELATED WORK
We briefly review additional relevant work to ours with focus policy gradient based methods. For other RL methods such as value based (Watkins & Dayan 1992 Mnih et al. 2015) and actor- critic (Konda & Tsitsiklis 2000 Peters Schaal, 2008a; Silver et 2014) methods, we refer the
reader Peters& & Schaal (0088)) Kober et a2013) Sutton & Barto 2018) for complete review.
To reduce the variance of policy gradient methods, early works have introduced unbiased baseline functions (Baxter & Bartleti 2001] Greensmith et al.] 2004 Peters & Schaal,, (008b) to reduce the variance, which can be constant, time-dependent or state-dependent. [Schulman et al. (2015b) proposed the generalized advantage estimation (GAE) to explore the trade-off between bias and variance of policy gradient. Recently, action- -eiionddeeeneent baselines are also used in Tucker et al. 2018); Wu et al. (2018) which introduces bias but reduces variance at the same time. Sehnke et al. 20088 2010) proposed policy gradient with parameter- based exploration (PGPE) that explores in the parameter space. It has been shown that PGPE enjoys much smaller variance (Zhao et al.
2

---

Published as a conference paper at ICLR 2020
2011 The Stein variational policy gradient method is proposed in Liu et al. (2017) 7) See Peters &
Schaal (2008b); Deisenroth et al. (2013) Li (2077) for a more detailed survey on policy gradient.
Stochastic variance reduced gradient techniques such as SVRG (Johnson & Zhang 2013 Xiao &
Zhang 2014), batching SVRG (Harikandch et al. 2013), SAGA (Defazio et al. 2014 and SARAH
2017) were first developed in stochastic convex optimization. When the objective function is honconvex (or nonconcave for maximization problems), nonconvex SVRG (Allen-Zhu
Nggueen et al.
& Hazan 2016: Reddi al. (0T66) and SCSG (Lei al. 2017 Li & Li 2018) were proposed and proved to converge to a first-order stationary point faster than vanilla SGD [Robbins & Monro 1951) with no variance reduction. The tfae-of-the-ar art stochastic variance reduced gradient methods for nonconvex functions are the SNVRG (Zhou et al., (2188) and SPIDER (Fang et al. (2018) algorithms, which have been proved to achieve near optimal convergence rate for smooth functions.
There are yet not many papers studying variance reduced gradient techniques in RL. Du et al. (2017) first applied SVRG in policy evaluation for fixed policy. Xu al. (2017) introduced SVRG into trust region policy optimization for model-free policy gradient and showed that the resulting algo- rithm SVRPO is more sample efficient than TRPO. Yuan et al. (219) further applied the techniques in SARAH (Nguyen et al., 2017) and SPIDER (Fang al. 2018) to TRPO (Schulman et al., 2a)5a). However, no analysis on sample complexity (i.c., number of trajectories required) was provided in the aforementioned papers (Xu al. 2017 Yuan et al., 2019). We note that recent work by [Shen et al. (019) proposed a Hessian aided policy gradient (HAPG) algorithm that converges to the sta- tionary point of the performance function within 0(H12/ /E3/2) trajectories, which is worse than our result by a factor of (12)²) where H is the horizon length of the environment. Moreover, they need additional samples to approximate the Hessian vector product, and cannot handle the policy in a constrained parameter space. Another related work pointed out by the anonymous reviewer is Yang & 'Zhang (2019), which extended the stochastic mirror descent algorithm (Ghadimi et al. (016) in the optimization field policy gradient methods and achieved O(H2/ ((H2/22 sample complexity. Af- ter the ICLR conference submission deadline, Yang & Zhang (2019) revised their paper by adding a new variance reduction algorithm that achieves O(H² / sample complexity, which is also worse than our result by factor of (
Apart from the convergence analysis of the general nonconcave performance functions, there has emerged a line of work (Cai et al. 20199 Liu al. 2019, Yang et al., 2019 Wang al., 20T9) that studies the global convergence of (proximal/trust-egionn policy optimization with neural network function approximation, which applies the theory of overparameterized neural networks (Du al., 2019b a Allen-Zhu et al. 20199; Zou et al. 2019: Cao & Gul 2019) to reinforcement learning.
Rd and || denotes the spectral norm of a matrix A E Rexd We write an (b,,) if a, < Cb, for some constant C >> 0. The Dirac delta function 6()) satisfies 6(0) +os and 8(z) 0 if * 0. Note that 8(x) satisfies 1 6(x)dx= = 1. For any a > O, we define the Rényi divergence Rényi et al. 1961 between
Notation || denotes the Euclidean norm of vector
distributions and Q as
1
P((x)
(P(I1) a
log,
P(x)
dæ,
Q(x)
which is non-negative for all 0. The exponentiated Rényi divergence is (PII)) (PI())
BACKGROUNDS ON POLICY GRADIENT
Markoy Decision Process: A discrete-tima Markov Decision Process (MDP) is tuple M = (S,A, A, P, P.r,y,p) S and A are the state and action spaces respectively. P( a) is the tran- sition probability of transiting to state s' after taking action a at state Function r(s,a) x A + [-R, R. emits a bounded reward after the agent takes action a at state 8, where R > 0 is a constant. 7 (0, 1) is the discount factor. p is the distribution of the starting state. A policy at state s is a probability function x <[ass) over action space A. In episodic tasks, fol- lowing any stationary policy, the agent can observe and collect sequence of cate-action pairs T = {Sp, ag $1, .,...., $1 --, s1 1r),, }, which is called a trajectory or episode. is called the trajectory horizon episode length. In practice, we can set H to be the maximum value among all
3

---

Published as a conference paper at ICLR 2020
the actual trajectory horizons have collected. The sample return one trajectory т is defined the discounted cumulative reward R(r) -Ei= r"r(s,, an)-
Policy Gradient:
Suppose the policy, denoted by Te, is parameterized by an unknown parameter Rd. We denote the trajectory distribution induced by policy me as p(r(0). Then
H-1
p(T p(so)
II h=
Ta 88. P(sh+ 0s).
(2.1)
We define the expected return under policy me as J(0) = 10) [R()) which is also called the performance function. To maximize the performance function, eter 0 by iteratively running gradient ascent based algorithms. i.e., 0x+1 = 0 + (fxx) where
update the policy param-
n 0 is the step size and the gradient (B) is derived as follows:
/ r
( (
VoJ(O)
10) Vo log (T)))))(()))
(2.2)
However, it is intractable calculate the exact gradient in (2.2) since the trajectory distribution p(T(0) 0) is unknown. In practice, policy gradient algorithm samples a batch of trajectories {Ti};=1 to approximate the exact gradient based on the sample average over sampled trajectories:
N V (ologp(T]0)R[(1
J
(2.3)
N
At the k-th iteration, the policy is then updated by 0x+1 0% + Ve (Ox). According to know that Ve log P(T; 0) is independent of the transition probability matrix P. Recall the definition of RT)) we can rewrite the approximate gradient follows
2.1
N
Vo)(O)
V log (chlst)
Σ h=0
rrr(sh
==
def ((:
(2.4)
where {sh a s ai. ................................ "1 a ) for all i 1,..., N and ()) is unbiased gradient estimator computed based on the i-th trajectory т;- The gradient estimator in (2.4) is based on the likelihood ratio methods and is often referred (Williams 1992). Since V log (a|s)] = O, we can add any constant baseline 6, to the reward that independent of the current action and the gradient estimator still remains unbiased. With the observation that future actions do not depend on past rewards, another famous policy gradient theorem (PGT) estimator (Sutton et al. 2000) removes the rewards from previous states:
the REINFORCE gradient estimator
#-1
0(T =
Vo log To (af
Σ
r'r(st
(2.5)
h=0
where by is constant baseline. It has been shown (Peters & Schaal 2008b) that the PGT estimator equivalent to the commonly used GPOMDP estimator (Baxter & Bartlett 2001) defined as follows:
#
h Σ 1=0
g(T, 0)
Σ h=D
Ve log To (afls)) (p" at,) bn).
(2.6)
All the three gradient estimators mentioned above unbiased (Peters & Schaal 2008b). It has
been proved that the variance of the PGT/GPOMDP estimator is independent of horizon H while the variance of REINFORCE depends on H polynomially (Zhao et al.) 2011 Pirotta et al. 2013). Therefore, we will focus on the PGT/GPOMDP estimator in this paper and refer to them inter- changeably due their equivalence.

---

Published as a conference paper at ICLR 2020
3 THE PROPOSED ALGORITHM
The approximation in 2.. using a batch of trajectories often causes a high variance in practice. In this section, we propose novel variance reduced policy gradient algorithm called stochastic recursive variance reduced policy gradient (SRVR-PG), which is displayed in Algorithm [ Our SRVR-PG algorithm consists of S epochs. In the initialization, we set the parameter of a reference
policy to be 0 Po. At the beginning of the s-th epoch, where s = O,..., S - 1, we set the initial policy parameter 0z+1 to be the same as that of the reference policy 0". The algorithm then samples N episodes {T:) from the reference policy Tg. to compute a gradient estimator vo - 1/N E (T:)00),, where g(T: (*) is the PGT/GPOMDP estimator. Then the policy is immediately update as in of Algorithm |
Within the epoch, the f-th iteration, SRVR-PG samples B episodes { based on the current policy To We define the following recursive semi-stochastic gradient estimator:
1 E (T
x+
B 5
++1 + V--1
(3.1)
where the first term is a stochastic gradient based on B episodes sampled from the current policy, and the second term is stochastic gradient defined based on the step-wise important weight between the current policy T and the reference policy Tg.. Take the GPOMDP estimator for example, for a behavior policy To, and a target policy Ta the step-wise importance weighted estimator is defined as follows
H
In (T) 01)
Σ h=0
worh (T
Σ Vo, log To, (a/1s/) 7" 7 ab)),
(3.2)
where wo: (r 002, 01) IT To (an|s))/ 1//5s//T (an(sh) ) is the importance weight from p(TA (0:1)(0+1))))))
to p(TA ( and is truncated trajectory {(a, // from the full trajectory It is easy to (g))
verify that (e= (T,)0:)] 01)] = Br=-(r10=) (T(T))
The difference between the last two terms in (3.1) can be viewed control variate to reduce the variance of the stochastic gradient. In many practical applications, the policy parameter space is subset of TRd. i.e., 0 @ with θ Rdd being convex set. In this case, need to project the updated policy parameter onto the constraint set. Base on the semi-stochastic gradient (3.1) update the policy parameter using projected gradient ascent along the direction of v; T 0-+1 Pe (0 ?);+ where 17 0 is the step size and the projection operator associated
with θ is defined as
1 u112), (0) = argmin | ul/3 = argmin (Ie + by
(3.3)
u
uERd
u O and ( too otherwise. > 0 is any finite real value and is chosen as the step size in our paper. It is easy to see that 1 (-) is nonsmooth. At the end of the s-th epoch, we update the reference policy as ga-1 g=+1 where ge+1 the last iterate of this epoch.
where (u) is the set indicator function θ, i.e., l
The goal of our algorithm is to find point 0 θ that maximizes the performance function J(Ø) subject to the constraint, namely, maxage (0) = (J))) 1 (0)} The gradient norm [[)[())]| is not sufficient to characterize the convergence of the algorithm due to additional the constraint. Following the literature on nonsmooth optimization (Reddi et al., 2016b;; Ghadimi et al., 2016 Nguyen et al. 2017 Li & Li 2018: Wang al. 2018), use the generalized first-order stationary condition: ( 0, where the gradient mapping Gr is defined as follows
1 (Po VVJ()) 0).
0,(00) = 1)
(3.4)
We can view Gn as a generalized projected gradient at 0. By definition if O = Rd we have (0) = VJ((). Therefore, the policy is update is displayed in Line 10 in Algorithm [ where
5

---

Published as a conference paper at ICLR 2020
Algorithm Stochastic Recursive Variance Reduced Policy Gradient (SRVR-PG)
Input: number epochs S, epoch size m, step size 77, batch size N, mini-batch size gradient estimator g. initial parameter 0 On E O
2: for . S
do
3: 05+1 = A
4: Sample N trajectories {Ti} from p(-10-)
5: vo = (0) : 1/N Ei imi
6: 0f+1 -0 +1vv
7:
for 1....,m- do
8:
Sample B trajectories {T,) from p(-10;+1)
vi v プド= (9( (Ty 0x+²)) Iw (T, 1))
9:
10:
0111 = Pe ( + +,v+1)
11: end for
12: 0++1 0=+1
13:
end for
14:
return Pow. which is uniformly picked from {01) It= m 1=1:=00....
prox is the proximal operator defined in (3.3 Similar recursive semi-stochastic gradients to 3.1 were first proposed in stochastic optimization for finite-sum problems, leading to the stochastic re- cursive gradient algorithm (SARAH) (Nuuyen et 2017 2019) and the stochastic path- ant-inteerrate differential estimator (SPIDER) (Fang et al. 2018: Wang et al. 2018). However. our gradient es- timator in (3.1 is noticeably different from that in Nguyen et al. (2017); Fang al. (2018) Wang et al. (201 8); Nguyen et al. (219)) due to the gradient estimator I (T ( defined in (3.2 that is equpped with step-wise importance weights. This term is essential to deal with the non-stationarity of the distribution of the trajectory Specifically, {Ty}
sampled from policy Te: while the
PGT/GPOMDP estimator g(- 1(-10;#1) is defined based on policy Top according to (2.6). This in-
consistency introduces extra challenges in the convergence analysis SRVR-PG. Using importance weighting, we can obtain
E B (T
( [ = E. ( [0( (0t)))
which eliminates the inconsistency caused by the varying trajectory distribution.
is worth noting that the semi semi-stochastic gradient in (3.1) also differs from the one used in SVRPG (Papini et al. 2018 because we recursively update V; using v from the previous iteration, while SVRPG uses reference gradient that is only updated at the beginning of each epoch. More- over, SVRPG wastes N trajectories without updating the policy the beginning each epoch, while Algorithm updates the policy immediately after this sampling process (Line 6). which saves computation practice.
We notice that very recently another algorithm called SARAPO Yuan et al. 2019) is proposed which also uses a recursive gradient update in trust region policy optimization (Schulman et al. 2015a). Our Algorithm]] I differs from their algorithm at least in the following ways: (1) our recursive gradient vi defined in (3.I) has an importance weight from the snapshot gradient while SARAPO does not; (2) are optimizing the expected return while Yuan et al. (2019) optimizes the total advantage over state visitation distribution and actions under KullbackLeibler divergence constraint; and most importantly (3) there is no convergence or sample complexity analysis for SARAPO.
4
MAIN THEORY
In this section, we present the theoretical analysis of Algorithm] I We first introduce some common assumptions used in the convergence analysis of policy gradient methods. Assumption 4.1. Let (a(a)s be the policy parameterized by 6. There exist constants G, M > 0 such that the gradient and Hessian matrix of log To (als)) with respect 0 satisfy
|| Vo log [o(a)))] s G,
V2 log (a(s)))) s M,
for all A and E S.

---

Published as a conference paper at ICLR 2020
The above boundedness assumption is reasonable since usually require the policy function to be twice differentiable and easy to optimize in practice. Similarly, in Papini et al. (2018). the au- thors assume that 80, log (a)s)) and 0² 80,00, log To (a)s) are upper bounded elementwisely, which
a
actually stronger than Assumption 4.1
In the following proposition, we show that Assumptior 4. directly implies that the Hessian ma- trix of the performance function V²J(0) is bounded, which is often referred to the smoothness assumption and is crucial in analyzing the convergence of nonconvex optimization (Reddi et al. 2016a Allen-Zhu Hazan 2016).
Proposition 4.2. Let g( be the PGT estimator defined in 2.5 Assumption 4.1 implies:
(I). ( - 90 < L| 02|12 vO,, 02 E Rd, where the smoothness parameter is 2G2 7)
L
(2). (0) is L-smooth, namely [V) L: (3) (g 0)1l2 S Cg for all 0 E Rd, with Cg GR/(1 7)
Similar properties are also proved in Xu al. (2119) However, in contrast their results, the smoothness parameter L and the bound on the gradient norm here do not rely on horizon H. When H = 1/(11))) and y sufficiently close to 1, we can see that the order of the smoothness parameter is (1)))) which matches the order O H2 2 (01//(1111) y)) in Xu et al. (201)). The next assumption requires the variance of the gradient estimator bounded.
Assumption 4.3. There exists constant & > 0 such that (ar(g(T))) <²² for all policy me.
In Algorithm 1 we have used importance sampling to connect the trajectories between two different iterations. The following assumption ensures that the variance of the importance weight is bounded, which is also made in Papini al. (0188; Xu al. (2019).
Assumption 4.4. Let ,,, 02) p( 11))p((110 02). There is constant W < such that for each policy pairs encountered in Algorithm [
Var(w(r|01, 02)) s W, V01,02 Rd, p(-102).
4.1 CONVERGENCE RATE AND SAMPLE COMPLEXITY OF SRVR-PG
Now ready to present the convergence result of SRVR-PG stationary point:
Theorem 4.5. Suppose that Assumptions 4.1 and 4.4 hold. In Algorithm I we choose the step size such that
size 1j & 1/(4L) and epoch size m and
72mmn (2G /M + 1)(W + +17
B >
(1 71-
Then the generalized projected gradient of the output of Algorithm satisfies
8(J(0") ((O)) 10 1e (0))
6 N
E [ (0...)
+
Sm
where 0* argmax J(Ø).
Remark 4.6. Theorem 4.5 states that under proper choice of step size, batch size and epoch length, the expected squared gradient norm of the performance function at the output of SRVR-PG is the order of
o (1 N )1+11)
5m
Recall that the number of epochs and m is the epoch length SRVR-PG, so Sm is the total number of iterations of SRVR-PG. Thus the first term ((1((mm)) characterizes the convergence rate of SRVR-PG. The second term (1/NN) comes from the variance of the stochastic gradient used in the outer loop, where N is the batch size used in the snapshot gradient v in Line 5 of SRVR-PG. Compared with the O(1 ((1/(5m) 1/N 1/B) convergence rate in Papini et al. (0188)
7

---

Published as a conference paper at ICLR 2020
analysis avoids the additional term O(1/B) that depends on the mini-batch size within each epoch.
Compared with Xu et al. (2019), our mini-batch size B is independent of the horizon length H. This enables us to choose a smaller will show in the next corollary, this improvement leads to lower sample complexity.
size while maintaining the same convergence rate. As
Corollary 4.7. Suppose the same conditions as in Theorem 4.5 hold. Set step size 1j = 1/(4T,,
the batch size parameters N O(1/e) and B = O(1/e !72) respectively, epoch length
0(1/64/2) and the number of epochs as S (11/ (1))) Then Algorithm outputs a point oon that satisfies B G, (m 11 < within ( trajectories in total.
Note that the results in Papini al. (2018); Xu et al. (2019) are for ( < while our result in Corollary 4.7 more general. In particular, when the policy parameter is defined on the whole space Rd instead of θ result reduces to the case for [ I since θ R" and G, (0) = ( In Xu et al. (2019), the authors improved the sample complexity of SVRPG (Papini et al., 2018) from O(1/c²) to ((1/c5/3) by a sharper analysis. According to Corollary 4.7 SRVR-PG only needs ((1/68/2) number of trajectories to achieve [[VaJ(0)]3 I which is lower than the sample complexity of SVRPG by a factor of O(1/c1/0). This improvement is more pronounced when the required precision is very small.
4.2 IMPLICATION FOR GAUSSIAN POLICY
Now, we consider the Gaussian policy model and present the sample complexity of SRVR-PG in this setting. For bounded action space C R. Gaussian policy parameterized by defined as
((s) a)²
(als) ) = exp
(4.1)
2m
20²
where o² is a fixed standard deviation parameter and Φ S + Rd is mapping from the state space to the feature space. For Gaussian policy, under the mild condition that the actions and the state feature vectors are bounded, we can verify that Assumptions 4.1 and 4.3 hold, which can be found in Appendix D It is worth noting that Assumption 4.4 does not hold trivially for all Gaussian distributions. In particular, Cortes et al. (2010) showed that for two Gaussian distribu- tions ne, (als) N(J, of) and (als)) ~ N N(12, oz).. ). if 02 >> v2/2011 then the variance of w[T(O, 02) ) is bounded. For our Gaussian policy defined in (4.1) where the standard deviation o² fixed, we have a > 22/2o trivially hold, and therefore Assumption 4.4 holds for some finite
constant W according to (2.1).
Recall that Theorem 4.5 holds for any general models under Assumptions 4.
4.3 and 4.4 Based
on the above arguments, know that the convergence analysis in Theorem 4.5 applies Gaussian
policy. In the following corollary, we present the sample complexity of Al Algorithm policy with detailed dependency on precision parameter 6, horizon size H and the discount factor 7-
[ for Gaussian
Corollary 4.8. Given the Gaussian policy defined in (4.1 suppose Assumption 4.4 holds and we ( < MM. for all s E S, where C., Ma. > 0 are constants. If
have |a| < C2 for all a E AA and ||
we set step size as 7 O(1 ))) ), the mini-batch sizes and epoch length as N 0(1-2)-36-11
B O(11 7) - 1/2) and m O - 2) 2e-1/)), then the output of Algorithm satisfies
E[I|g,, (0mm)) ]13] I c after ((1/((1= - (3)33))3)))))) trajectories total.
Remark 4.9. For Gaussian policy, the number of trajectories Algorithm | needs find an approximate stationary point, i.e., [E]]],,, (O.uz) faster than PGT and SVRPG. Additionally, we explicitly show that the sample complexity does not depend on the horizon H, which is in sharp contrast with the results in Papini et al. (2018) Xu et al. (2019). The dependence on 1/(1 - 7) comes from the variance of PGT estimator.
< is also in the order of O which
5 EXPERIMENTS
In this section, we provide experiment results of the proposed algorithm on benchmark reinforce- ment learning environments including the Cartpole, Mountain Car and Pendulum problems. In all
8

---

Published as a conference paper at ICLR 2020
x30
x12
Avrgrage Roturn
Aveerage Return
Nuwrrage Retum
-3.1
4.5-
0.8
-0.0
0.5
-0.3
-2.
-33
UnOREo SURPS
GrOND
-12
3150
1875
2500
750 Numbar Tajectorks
2507
05
Number Tajectories
Number Tajectories
(a) Cartpole
(b) Mountain Car
(c) Pendulum
1.0
5
Aver Return
0.8
22
Average Return
Average Raturnn
-0.4
-0.5
0.a
0.5-
-0.5
0.4
0.2
-33
-12
5 103
0.0
676
1250
1875
2006
-15
750
1000
2253
3300
0.5
35
1.0
2.
Number of Trajectories
Number of Trajectories
Number of Traectories
(d) Cartpole
(e) Mountain Car
(f) Pendulum
Figure I: (a)-(c): Comparison of different algorithms. Experimental results are averaged over 10 repetitions. (d)-(f): Comparison of different batch size B on the performance of SRVR-PG.
the experiments, we use the Gaussian policy defined in (4.1) J. In addition, we found that the proposed algorithm works well without the extra projection step. Therefore, we did not use projection in our experiments. For baselines, we compare the proposed SRVR-PG algorithm with the most relevant methods: GPOMDP (Baxter & Bartleti 2001) and SVRPG (Papini al. 2018). For the learning rates 77 in all of our experiments, we use grid search to directly tune 77. For instance, we searched n for the Cartpole problem by evenly dividing the interval [10-5, 10-1] into 20 points in the log- space. For the batch size parameters N and B and the epoch length m. according to Corollary 4.7, we choose = O(1/c), B = O(1/cl/2) and thus m = O(1/c1/2). where >> is a user-defined precision parameter. In our experiments, we set N = Co/e, = C1/c1/2 and m = C2/e and tune the constant parameters Co. C1, C2 using grid search. The detailed parameters used in the experiments are presented in Appendix
We evaluate the performance of different algorithms in terms of the total number of trajectories they require to achieve a certain threshold of cumulative rewards. We run each experiment repeatedly for 10 times and plot the averaged returns with standard deviation. For a given environment, all experiments are initialized from the same random initialization. Figures ((a) [(b) and [(c) show the results on the comparison of GPOMDP, SVRPG, and our proposed SRVR-PG algorithm across three different RL environments. It is evident that, for all environments, GPOMDP is overshadowed by the variance reduced algorithms SVRPG and SRVR-PG significantly. Furthermore, SRVR-PG outperforms SVRPG in all experiments, which is consistent with the comparison on the sample complexity of GPOMDP, SVRPG and SRVR-PG in Table
Corollaries 4.7 and suggest that when the mini-batch size B in the order of O(VN), SRVR-PG achieves the best performance. Here N is the number of episodes sampled in the outer loop of Al- gorithm and is the number of episodes sampled each inner loop iteration. To validate our theoretical result, conduct sensitivity study to demonstrate the effectiveness of different batch sizes within each epoch of SRVR-PG on its performance. The results on different environments are displayed in Figures ((d)
Iee) and ((f) respectively. To interpret these results, take the Pendu- lum problem as an example. In this setting, we choose outer loop batch size N of Algorithm T to be N 250. By Corollary 4.8 the optimal choice of batch size in the inner loop of Algorithm is
B CVN, where C. > 1 is constant depending on horizon H and discount factor 7. Figure

---

Published as a conference paper at ICLR 2020
shows that B = 50 3/N yields the best convergence results for SRVR-PG Pendulum, which validates our theoretical analysis and implies that larger batch size B does not necessarily result in improvement in sample complexity, batch size B pushes SRVR-PG to behave more similar to GPOMDP. Moreover, by comparing with the outer loop batch size N presented in Table for SRVR-PG in Cartpole and Mountain Car envi- ronments, we found that the results in Figures I(d) and [(e) are again in alignment with our theory. Due to the space limit, additional experiment results are included Appendix E
each update requires more trajectories, but smaller
CONCLUSIONS
We propose a novel policy gradient method called SRVR-PG, which is built on a recursively updated stochastic policy gradient estimator. We prove that the sample complexity of SRVR-PGI is lower than the sample complexity of the state-of-the-art SVRPG (Papiní et al. 2018 Xu et al., 2019) algorithm. We also extend the new variance reduction technique to policy gradient with parameter based ex- ploration and propose the SRVR-PG-PE algorithm, which outperforms the original PGPE algorithm both in theory and practice. Experiments on the classic reinforcement learning benchmarks validate the advantage of our proposed algorithms.
ACKNOWLEDGMENTS
We would like thank the anonymous reviewers for their helpful comments. We would also like to thank Rui Yuan for pointing out an error on the calculation of the smoothness parameter for the performance function the previous version. This research was sponsored in part by the National Science Foundation 11S-1904183, IIS- 19061699999999 and Adobe Data Science Research Award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
REFERENCES
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International Conference on Machine Learning, pp. 699-707, 2016.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-
parameterization. In International Conference on Machine Leurning, pp. 242-252, 2019.
Jonathan Baxter and Peter L Bartlett. Infinite-horizon policy-gradient estimation. Journal of Artifi- cial Intelligence Research, 15:319-350, 2001.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning con- verges to global optima. In Advances in Neural Information Processing Systems, 2019.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint 1rXiv:1902.01338 2019.
Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in Neural Information Processing Systems, pp. 442 442-450, 2010.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, pp. 1654, 2014.
Mare Peter Deisenroth, Gerhard Neumann, Jan Peters, et al. survey on policy search for robotics. Foundations and Trends in Robotics, 2(1-2):1-142, 2013.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 20
Simon S Du, Jianshu Chen, Lihong Li. Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1049-1058. JMLR. org, 2017.
10

---

Published as a conference paper at ICLR 2020
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019b. URL
net/ ott.:p/awwaaaeee..eooooooraaaaaa /tt.:/orrnnii111l11sss
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 686-696, 2018.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth- ods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2): 267-305, 2016.
Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning Journal of Machine Learning Research, 5(Nov):1471-1550, 2004.
Reza Harikandeh, Mohamed Osama Ahmed, Alim Virani, Mark Schmidt, Jakub Konečný, and Scott Sallinen. Stopwasting my gradients: Practical svrg. In Advances in Neural Information Process- ing Systems, pp. 2251-2259, 2015.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances Neural Information Processing Systems, pp- 315-323, 2013.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. The International Journal Robotics Research,
2013.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information
Processing Systems, pp. 1008-1014, 2000.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via scsg methods. In Advances in Neural Information Processing Systems, pp. 2348-2358, 2017.
Sergey Levine, Nolan Wagener, and Pieter Abbeel. Learning contact-rich manipulation skills with guided policy search. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 156-163. IEEE, 2015.
Yuxi Li. Deep reinforcement learning: An overview. CoRR, abs/1701.07274, 2017. URL http:
7/arxiv. srexiv.erg/abst.. 07274
Zhize Li and Jian Li. simple proximal stochastic gradient method for nonsmooth nonconvex
optimization. In Advances in Neural Information Processing Systems, pp. 5569-5579, 2018.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proximal/trust region policy opti- mization attains globally optimal policy. In Advances Neural Information Processing Systems, 2019.
Yang Liu, Prajit Ramachandran, Qiang Liu, and Jian Peng. Stein variational policy gradient. CoRR, 0s//1004.0299 2017. URL httlht/pp///xiii org/ abs/1704 02399
Alberto Maria Metelli, Mattco Papini, Francesco Faccio, and Marcello Restelli. Policy optimization via importance sampling. In Advances in Neural Information Processing Systems, pp. pp. 5447-5599, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Marc G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference Machine Learning-Volee Volume 70, pp. 2613-2621. JMLR. org, 2017.
Lam M Nguyen, Marten Dijk, Dzung T Phan, Phuong Ha Nguyen, Tsui-Wei Weng, and Jayant R Kalagnanam. Optimal finite-sum smooth non non-convex optimization with sarah. CoRR, 0bs/1191_00744 2019. URL http:////wwaa...ra/////11..1111 07648

---

Published as a conference paper at ICLR 2020
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance- reduced policy gradient. In International Conference on Machine Learning, pp. 4023 4023-4032, 2018.
Jan Peters and Stefan Schaal. Natural actor-critic. Neurocomputiing, 71(7-9):1180-113 1190, 2008a.
Jan Peters and Stefan Schaal. Reinforcement learning of motor skills with policy gradients. Neural Networks, 21(4))682-697, 2008b.
Matteo Pirotta, Marcello Restelli, and Luca Bascetta. Adaptive step-size for policy gradient meth- ods. In Advances in Neural Information Processing Systems, pp. 1394-1402, 2013.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning, pp- 314-323, 2016a.
Sashank Reddi, Suvrit Sra, Barnabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in Neural Information Processing Systems, pp. 115-1153, 20.
Alfréd Rényi et al. On measures entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume I: Contributions to the Theory of Statistics. The Regents of the University of California, 1961.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathemat- ical Statistics, pp. 400-407, 1951.
John Schulman, Sergey Levine, Pieter Abbeel, Michael I Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, volume 37, pp. 1889- 1897, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Picter Abbeel. High- dimensional continuous control using generalized advantage estimation. CoRR, abs/1506.024.. 2015b. URL httppss//aaaxi..orrrbbbo////////
02438
Frank Sehnke, Christian Osendorfer, Thomas Rückstießß Alex Graves, Jan Peters, and Jürgen Schmidhuber. Policy gradients with parameter-based exploration for control. In International Conference on Artificial Neural Networks, pp. 387-396. Springer, 2008
Frank Sehnke, Christian Osendorfer, Thomas Rückstieß, Alex Graves, Jan Peters, and Jürgen Schmidhuber. Parameter-exploring policy gradients. Neural Networks, 23(4):551-559, 2010.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinorcmment learning for autonomous driving. CoRR, abs/1610.03225, 2016. URL URLLattp://axxiv.oot
abs/ /eee/1600..m 03295
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International Conference Machine Learning, pp. 5729-5738, 2019.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International Conference Machine Learning, 2014.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):35,, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Infor- mation Processing Systems, pp. 1057-1063, 2000.
12

---

Published as a conference paper at ICLR 2020
George Tucker, Surya Bhupatiraju, Shixiang Gu, Richard Turner, Zoubin Ghahramani, and Sergey Levine. The mirage of action-dependent baselines in reinforcement learning. In International Conference Machine Learning, pp. 5022-5031, 2018. 2018.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates convergence. arXiv preprint 1909.0100000110000 2019.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. CoRR, abs/1810.10699, 2018. URL
http://arxiv. org/ abs /1s10 10690
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):27--292 1992.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning. 8(3-4):229-2555) 1992.
Cathy Wu, Aravind Rajeswaran, Yan Duan, Vikash Kumar, Alexandre M Bayen, Sham Kakade, Igor Mordatch, and Pieter Abbeel. Variance reduction for policy gradient with action-dependent factorized baselines. In International Conference on Learning Representations, 2018. URL net For.rorddddlldtss-----
httpss://ppenrew/
Lin Xiao and Tong Zhang, A proximal stochastic gradient method with progressive variance reduc- tion. SIAM Journal on Optimization, 24(4):2057-200 2075,5 2014.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In International Conference on Uncertainty in Artificial Intelligence, 2019.
Tianbing Xu, Qiang Liu, and Jian Peng. Stochastic variance veechastii vaiimneeeerrctttioooo for policy gradient estimation. CoRR, abs/1710.06034 2017. wwt.httpp/aarxx..o////////00.000
Long Yang and Yu Zhang. Policy optimization with stochastic mirror descent. arXiv preprint arXiv:1906. 10462, 2019.
Zhuoran Yang, Yongxin Chen, Mingyi Hong, and Zhaoran Wang. On the global convergence of actor-critie: A case for linear quadratic regulator with ergodic cost. In Advances in Neural Infor- mation Processing Systems, 2019.
Huizhuo Yuan, Chris Junchi Li, Yuhao Tang, and Yuren Zhou. Policy optimization via stochas- tic recursive gradient algorithm, 2019. URL htttps://openree// wwt.:eet//foooe iid=
352A9977
Tingting Zhao, Hirotaka Hachiya, Gang Niu, and Masashi Sugiyama. Analysis and improvement of policy gradient estimation. Advances in Neural Information Processing Systems, pp. 262-270, 2011.
Tingting Zhao. Hirotaka Hachiya, Voot Tangkaratt, Jun Morimoto, and Masashi Sugiyama. Efficient sample reuse in policy gradients with parameter-based exploration. Neural computation, 25(6): 1512-1547, 2013.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduced gradient descent for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 3922-3933, 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. Machine Learning, 2019.
13

---

Published as a conference paper at ICLR 2020
A EXTENSION TO PARAMETER-BASE EXPLORATION
Although SRVR-PG is proposed for action-based policy gradient, can be easily extended to the policy gradient algorithm with parameter-based exploration (PGPE) (Sehnke al. 2008). Unlike action-based policy gradient in previous sections, PGPE does not directly optimize the policy param- eter O but instead assumes that it follows a prior distribution with hyper-parameter p: 0 p g). The expected return under the policy induced by the hyper-paramenn parameter is formulated as follows
J ((0))))((10)(()ddrrdd
((p)
(A.1)
PGPE aims to find the p(0lp) is stochastic and can provide sufficient exploration, we can choose To (a(as)) 5(a Lgg (s)) to be deterministic policy, where 8 is the Dirac delta function and μa(-) is deterministic function. For instance, a linear deterministic policy is defined as (a(as) = ō(a OT s) (Zhao et al., 2011 Metelli et al., 2018). Given the policy parameter 0, trajectory is only decided by the initial state distribution and the transition probability. Therefore, PGPE is called a parameter -easee bbased exploration approach. Similar the action-based policy gradient methods, we can apply gradient ascent find p" In the k-th iteration, we update Pk by pk+1 P + p>J The exact gradient of J (p) with respect p given by
p" that maximizes the performance function Jpp). Since
V P
log p p)R
To approximate (p). we first sample N policy parameters {0:} from p(Olp). Then we sample one trajectory Tú for each 0, and use the following empirical average to approximate V P
(
1 Σ
v log ((00(())pp)
Σ ( a/) = Σ g(T.p))
(A.2)
where y E [0, 1) is the discount factor. Compared with the PGT/GPOMDP estimator in Section 2 the likelihood term vp p(O. in (A.2) for PGPE is independent of horizon H.
Algorithm D can be directly applied to the PGPE setting, where we replace the policy parameter with the haper-perameter p. When we need to sample N trajectories, we first sample N policy pa- rameters (0.) from p)0 Since the policy is deterministic with given 0, we sample one trajectory from each policy p(T 0.). The recursive semi-stochastic gradient is given by
v
4 g (
1 B
Σ
(T
v.-1
(A.3)
where 9 (T,lP; ) is the gradient estimator with step-wise importance weight defined in the way as in (3.)). We call this variance reduced parameter- basee algorithm SRVR-PG-PE, which is displayed
in Algorithm 2
Under similar assumptions on the parameter distribution p(O)p), as Assumptions 4.1 4.3 and 4.4 we
can easily prove that SRVR-PG-PE converges to a stationary point of (pp) with O 2/2)) sample assume the policy parameter 0 follows the distribution p())p) and
complexity. In particular, we update our estimation of p based on the semi-stochastic gradient in (A.3). Recall the gradient & (p) derived in (A.2). Since the policy in SRVR-PG-PE is deterministic, we only need to make the boundedness assumption on p(0 In particular, we assume that
1. IV log p || and | log log p)]p2 are bounded by constants in a similar way to As- sumption 4.1
2. the gradient estimator g(T(p) = Vp
EH ~ 0%) has bounded variance; 3. and the importance weight w(T, I +11 (000pP t1) has bounded vari- ance in a similar way to Assumption
We slightly abuse the notation by overloading J as the performance function defined on the hyper- parameter p.
14

---

Published as a conference paper at ICLR 2020
Then the same gradient complexity (11/22/2) for SRVR-PG-PE can be proved in the same way as the proof of Theorem |45 and Corollary 4.7 Since the analysis is almost the same as that of SRVR-PG, omit the proof of the convergence of SRVR-PG-PE. In fact, according to the analysis in iZhao et al. (2011); Metelli et al. (2018), all the three assumptions listed above can be easily verified under Gaussian prior for 0 and linear deterministic policy.
Algorithm 2 Stochastic Recursive Variance Reduced Policy Gradient with Parameter-basee Explo- ration ISRVR-PG-PE
1: Input: number epochs epoch size m, step size 17, batch size N, minimiiniaa mini-batch size B, gradient estimator 9, initial parameter Pm = p0 Pu
2: for = O.....S do
3: p pp
4: Sample N policy parameters { from pl (pa)
5: Sample one trajectory тИ from each policy Te.
6: vo - pp'')) = Em (TT("")
7: P = Po +
8:
for l......,,
do Sample B policy parameters (0,) from p(-lp;"" Sample one trajectory Tj from each policy ne
9:
11:
v + Dj= (e(T)lei+)) Iw (T, (1())=1))
12: P+ = P. + I
end for
14:
end for
15:
return Pour. which is uniformly picked from (pi)e= m=:0...
B PROOF OF THE MAIN THEORY
In this section, we provide the proofs the theoretical results for SRVR-PG (Algorithm]) [ Before start the proof of Theorem 44.5 we first lay down the following key lemma that controls the variance of the importance sampling weight
Lemma B.1. For any 01, O2 E I&d, let worh (T10 0.) p , 0n (.)// 11/)/p(m))) (1/pp(//.00))) (22). where t a truncated it holds that
trajectory of F up to step h. Under Assumptions 4.1 and 4.4
Var(won (T|01, 02)) < C. 0 021
where C. = h + M)W +)..
Recall that in Assumption 4.4 we assume the variance of the importance weight is upper bounded by constant W. Based this assumption, Lemma B. further bounds the variance of the importance weight via the distance between the behavioral and the target policies. As the algorithm converges, these two policies will be very close and the bound in Lemma B.1 could be much tighter than the constant bound.
Proof of Theorem
4.5
By plugging the definition the projection operator in 3.3 into the update
rule 0++11 Pel
ny; ) we have
0 argmin 1/(2m) 0x+ 1
(vi') .).
(B.1)
neRd
Similar to the generalized projected gradient 9,, defined in 3.4 define Ø to be (stochas- tie) gradient mapping based the recursive gradient estimator
1 - = - (e 0;+1) = -P (0: + +1v+t) - 0,+1)
(B.2)
The definition of T differs from (0, only in the semi-stochan gradient term vž+!, while the latter uses the full gradient VJ( Note that le(.) is convex but smooth. We
15

---

Published as a conference paper at ICLR 2020
assume that p E à (1e(0,+1) is sub- sub--gradeet of 1=(+). According to the optimality condition of
B.I. we have p + ( 1-1 0c+1) vt+ 0. Further by the convexity of (le).)), we have
1 (0 < 1e (p. 0 - 0.
= -1( (1/n(0 0: 1 v2 ++ 0.f1 - - 0,t1).
(B.3)
By Proposition 4.2 (0) is Lsmooth, which by definition directly implies
0::1 - 0 _ 1 0,+1 1
J (( 2 (
+ (V
For the simplification of presentation, let us define the notation $(0) = J(0) - (0). Then ac- cording to the definition of Le we have argmaXper* (0)) argmaXge (()) = 0- Combining the above inequality with (B.3). we have
0 ( 2 (0 (VJ(O)))) vith 0ct1 0c+2)
[
L
1111 0 112
11
2
+ (VJ(0 - vēt .n0tt1 +
00
112
112
L
1 0,+111 11
2
2 *(0++1) 7 (0 v1
+1
112
-
|10 - 0, 0,t111 112
+( // (0: - -v;
2
- 11
1
L
|1001
0,t1112
4nj
2 (00+t1) - -- "(( - -v,+'
1 (0t+1))2
"
7 |0, -
1 L
0, 0.+11 1|20
(B.4)
4
4n
where the second inequality holds due to Young's inequality and the third inequality holds due to the fact that (0,+))1 - 21| + (, - 3 Denote 0::1 = prox,, le (0,+1 + J(0++ )). By similar argument in (B.3) we have
(0 < - (1/n(0:71 0,+1) vith (+] 0
ll ele (0 S 1e -4/m)0))0) - (V ), 0 0
Adding the above two inequalities immediately yields |0: 0 S // / - v 1|2
which further implies (0, - < [(](())))) vi" 112. Submitting this result into B.4.. we obtain
(0 2 (0(+1)
31
VJ - v? 112 "
G. (0x
4
g
1
+
10
0 1
(B.5)
4n
2
We denote the index set of {r in the t-th inner iteration by B, Note that
|| v 1|
(J(O:+1) v + (T,(T
-
B
jEB
|J(O:+T) ) + 1
(gw +
B
JEB,
- ()(())))
1
(gw (T, 0
B
8EB
2 jEB.
(J --J( IN (T 1 (1+h) (J(O -
16

---

Published as a conference paper at ICLR 2020
[J(0 v
(B.6)
Conditional on 0,+1 taking the expectation over B, yields
E| ((( 0 VJ(O;=)) viti) 0.
Similarly, taking the expectation over 0,+1 and the choice of B, yields E (V]((t)))) I (T) V 0.
Combining the above equations with (B.6), we obtain
E J - +
((((tt+)) - v)(( + Σ
(ew - -
=
B
JEB,
+ + (
Σ
E VJ VJ(O + oo - =T
B
JEB
+ E BJ - v
(B.7)
Σ JEB
(T
- ||2 [J(0 1
(B.8)
is due to the fact that El|x1 + ... + x. 12 E||x 2l ... + E| ll for in- dependent zero-mean random variables, and (B.8) holds due to the fact that x X is due
where B.7
E|x Ex] I E For the first term, we have (1g
g(7) 0,
S
Now (T 1 o(T
+ -|
0.+1| by triangle inequality and Proposition 4.2
B[] (T, 10 - ( 1
E
(wo: - -1)
V log To (a)1st)
70hh ( on))
2
t=
12
E
(Wo.h 1)
Vo log no (a
7 ( a/h)
C2G + M)W + 1) 0,+ 11 122G2arR
h=0
22 M)W + 1 |0
0.
2
(B.9)
(1
where in the second equality we used the fact that E[V log To (a|s |]] = 0, the first incquality is due
to Lemma B.1 and in the last inequality we the fact that カ= high 7 11y2 + 11 +
1)/(1 >) for hy << 1. Combining the results in B.g and B.9
get
Cg
E WJ
1 <
0
111
v
0
V +1 - vo 112
(B.10)
B
which holds for t = 1...., m 1, where C+2- = 2ARG (202 W + +1h/(11 7). According
to Algorithm| I and Assumption 4.3 we have
E ( - 1 N
(B.11)
Submitting the above result into B.5 yields
ExB ( (0:+1) 2 Ex (0:+ +
7 1 (0: 11 +
1
| 0: 0
4n
2
17

---

Published as a conference paper at ICLR 2020
C 4B
3n
EN
10
0
(B.12)
4N
for 1 = 1,..., m 1.Recall Line
6 in A Algorithm
where we update 0 with the average of a
mini-batch of gradients v 1/N have
N
g 0*) Similar to B.3 by smoothness of J(0),
==
((0++1) 2 10)+
31
V.((O)+)) v 11 (0tt
4
1
L
00
0.+11 1
4nj
Further by B.11.. holds that
( 2 E 2 (0
3np²
+
17
Gy (0
(1) -
10
11 (B.13)
4N
8
4n
Telescoping inequality (B.12) from / = 1 to m
1 and combining the result with (B.13). we obtain
7 m
3mmg
EN,B (((++1)) }] 2 EN [ (0
Ev [, ()
4N
m
0 0g 0,+1112
4nj
C
m-
ENNB
10pt1 0-1111
2B
t=
3mn5?
2 EN, (00+t))]
N g (0c+1)
4N
t=
1
L 3m
0
0,+ 1|
(B.14)
4n
2B
we choose step size 17 and the epoch length B such that
1
B
3nC G2n (2G2 + M)( +1y
1 5 4L
(B.15)
m
M(1-7) 7)
and note that 05+1 +1
00, 0=-1
1
0+
then
B.
leads to
m Σ
3mmg2
EN T (0+t) EN (
Ev
(B.16)
4N
Summing up the above inequality over = ......5 yields
S-1m-1
3Smng²
Ellls, (0; (0; < E(
E
(0))
4N
-=0
which immediately implies
S(E| E + (0"))
6g2
8(2(0*) ((Oo))
6g
Smmm
mm5m
This completes the proof.
Proof of Corollary 4.7 Based on the convergence results in Theorem
order to ensure
E
< c, we can choose S, m and such that
8(J(0)) - J(0o))
6E
7m5m
2
N
2
18

---

Published as a conference paper at ICLR 2020
which implies Sm O(1/c) and N O(1/e). Note that we have set O(B). The total number stochastic gradient evaluations Tg we need is
Tg = SN + SmB 0
N
B
= =
(
1
Be
c3/2
where we 1/61/2.
C PROOF OF TECHNICAL LEMMAS
In this section, we provide the proofs the technical lemmas. We first prove the smoothness of the performance function J()).
Proof of Proposition 4.2
Recall the definition of PGT in 2.5 We first show the Lipschitzness of as follows:
g( 0) with baseline
H
H-1
Vg(T
V log To (an)ss))
Σ
rr(ss oo)
1=h
R
V log loggoaaaallll
1-7
1=0
MR
< (1 ?
where we used the fact that < < < 1. When we have a nonzero baseline bn we can simply scale it with 7 and the above result still holds up to constant multiplier.
Since the PGT estimator is an unbiased estimator the policy gradient VeJ we have VgJ(0) = E, (r(g(r()) and thus
VOJ(0) |(T + / p(T 0)g(7 V log log 0)dr
= E, -
log p(T())
(C.1)
We have already bounded the norm of the first term by MR/(1 - ? Now we take a look at the second term. Plugging the equivalent definition of gT (2.6) yields
E ( log ((]
#-1
b
Ve log (ar(s))
rr an) Vo Vo log lllglll())0))00oo) -((1)))))
H-1
4-1
Vo log (a(()))))
h Mr(h. ah)
Vo log (a((l)))) p(T(0)dr
r'=0
V log (a((
('r(sh) an)
Ve log To (a (e) p((())dr,
(C.2)
==0
where the second equality is due to VoP(s ar) = 0, and the last equality is due to the fact that for all t' > h holds that
Σ Vo log TO (acl)s))) an Vo log (o p(T[0)dr = 0.
Therefore, we have
#-1
E
S E,
ΣΣ h=0
G R x (h (h+1)G
19

---

Published as a conference paper at ICLR 2020
R-1
Σ
G2
+
K=D
R
71-
Putting the above pieces together, we can obtain
MR
+ 2G == L,
(2)()) S (1 (1-7)3 7)3 (1 7)3
which implies that (()) s-smooth with I= M MR/(1 7) 2G R/(R2/11 7)) Similarly, we can bound the norm of gradient estimator as follows
Vo log (a (sh) 3a R(1 7
GR
1 1-7
71-7)2²
which completes the proof.
Lemma C.1 (Lemma 1 in Cortes al. (2010)) Let ((x) P(<)/((())) be the importance weight for distributions P and Q. Then E(w) [[ = dz(P)])), where d2(Pl])) 2D(())) and (2(l))Q) is the Rényi divergence between distributions P and Q. Note that this immediately
implies Var(w) = d2((1)())
Proof of Lemma B. According to the property of importance weight Lemma C.I
we know
Var(wo:k (T o +)) d2 (P(Th) 0 Ilp(Tr [lP((T.0(+1) 0t++))
To simplify the presentation, denote 0 0 and 0₂ 0,+1 in the rest of this proof. By definition, we have
d2(p(Tn (1)(ml)0:lllp(T, 02)) = f p(TT p(TT dr - dr.
p(Tn 02)
Taking the gradient of d2(p(Tm ( 10)01ll(mppm))))) (2)) with respect to 0,, we have
Ve, de 02))
dr.
In particular, if set the value of 0, be 0 O2 in the above formula of the gradient, we get
Ve, (0l(p(Tx/01)llpm/n (2)) 0.- - V pl (o, 11) (e, = 0.
Applying mean value theorem with respect to the variable 01, we have
d2(p(T, (1)))((p = 1/2(0: 02)) T Vada(p(tal))leecmeee.)
02),
(C.3)
where 0 = 10 (1-t)02 for some t [0, and we used the fact that de (p(Tr (z)) |p(T) 02)) 1. To bound the above exponentiated Rényi divergence, we need to compute the Hessian matrix. Taking the derivative of
(2)) with respect to 0 further yields
Vo logp( () log 0) P(Th O)2 dr
p(T 02)
+
VoP(TA 0)((TA 0)P(TA 02) 0z dr.
(C.4)
Thus we need to compute the Hessian matrix of the trajectory distribution function, i.c., which can further be derived from the Hessian matrix of the density function.
Vip(T.))..
log (( ()) Vop((n () 00) + p(T) (VVap))
(C.5)
20

---

Published as a conference paper at ICLR 2020
Submitting (C.3 into (C.4)
yields
4 Vo 1o P( 10) dr p(T 02)
(3dd(p(T, p( 02))
2 / V log 0) P(T) 00) dr
p(Th 02)
2
1) [4 pTh 0) + V log (2
02)
- G4
02)
< 2h(2h + M) +1,,
where the second inequality comes from Assumption 4.1 and the last inequality due to Assumption
4.4 and Lemma C.I Combining the above result with (C.3) we have
Var(wa:t (r (r)0", oc+1)) d2 (p(Tn (0)mm,m0
S C. 0= 0.+1112
where C. = M(22G2 + M)( + 1).
D PROOF OF THEORETICAL RESULTS FOR GAUSSIAN POLICY
In this section, we prove the sample complexity for Gaussian policy, According to we can calculate the gradient and Hessian matrix of the logarithm of the policy.
V log (e((s) (a - T (()))((s)
4 (o(as) (s))
(D.1)
o²
is easy to see that Assumption 4.1 holds with = Ms/o and M M2/0². Based on this
observation, Proposition also holds for Gaussian policy with parameters defined as follows
RC.Mo 22 7)3 and Cg 0² 7)2
RM
(D.2)
The following lemma gives the variance ç? of the PGT estimator, which verifies Assumption 4.3
Lemma D.1 (Lemma 5.5 in Pirotta et al. 2013)). Given a Gaussian policy Ta s)
~
NO d(s), o²), if the (r(s,a) I R and [Ø(8) 2 S Mo for all S,a E A and R, Mo
are constants, then the variance of PGT estimator defined in (2.5) can be bounded as follows:
R2M2 (1 (1-7)202
2H
7H
Var(g(r(0) < 8²
HT2H 2
Proof of Corollary that |||l ((e ou))
4.8
The proof will be similar to that of Corollary e, we can set
4.7 By Theorem
4.5
to ensure
8(J(0") J(O)))
6E
2
N
2
Plugging the value of g in Lemma For the first equation, have S evaluations T required by Algorithm is
D.1 into the second equation above yields N (1--1(1-))))) (mme))). Therefore, the total number of stochastic gradient
001
T = SN + SmB = o mme
B n7
+
So good choice of batch size and epoch length m will lead to Bm = N. Combining this with the requirement of B in Theorem 4.5
LN ni
NnC.
and B
21

---

Published as a conference paper at ICLR 2020
Note that C, 24RG MW 11/1111)))) Plugging the values of G.N N and L into the above equations yields
B B=0
m
(1-7)
The corresponding sample complexity
1
=o 0
(1 (1 (1-7)483/2
This completes the proof for Gaussian policy.
E ADDITIONAL DETAILS ON EXPERIMENTS
Now, provide more details of our experiments presented in Section We first present the param- eters for all algorithms we used in all our experiments in Tables 2 and 3 Among the parameters, the neural network structure and the RL environment parameters As mentioned in Section [) the order of the batch size parameters of our algorithm are chosen ac- cording Corollary 4.7 and multiply them by a tuning constant via grid search. Similarly, the orders of batch size parameters of SVRPG and GPOMDP are chosen based on the theoretical re- sults suggested by Papini al. (2018); Xu et (2019). Moerover, the learning rates for different methods are tuned by grid search.
shared across all the algorithms.
We then present the results of PGPE and SRVR-PG-PE on Cartpole, Mountain Car and Pendulum in Figure 2 In all three environments, our SRVR-PG-PE, algorithm shows improvement over PGPE worth noting that in all these environ-
(Sehnke et al. 2010) terms of number of trajectories. ments both PGPE and SRVR-PG-PE seem solve the problem very quickly, which is consistent with the results reported in (Zhao et al. 2011 2013 Metelli et al. 2018). Our primary goal this experiment is show that proposed variance reduced policy gradient algorithm be easily extended to the PGPE framework. To avoid distracting the audience's attention from the variance reduction algorithm the sample complexity, do not thoroughly compare the performance of the parameter based policy gradient methods such as PGPE and SRVR-PG-PE, with the action based policy gradient methods. We refer interested readers to the valuable empirical studies of PGPE based algorithms presented in Zhao et al. [201 2013): Metelli et al. (0018).
"10'
1.3
1.0
0.0
Average Retum
Average Retum
0.6-
Average
0.2
PGP
-00
PGPE
-62
Number Trajectories
Number of Trajecttoiis
Number of Trajectories
(a) Cartpole
(b) Mountain Car
(c) Pendulum
Figure 2: Performance SRVR-PG-PER compared with PGPE. Experiment results are averaged over 10 runs.
22

---

Published as a conference paper at ICLR 2020
Table 2: Parameters used in the SRVR-PG experiments.
Parameters
Algorithm
Cartpole
Mountain Car
Pendulum
NN size
64
64
8x8
NN activation function
Tanh
Tanh
Tanh
Task horizon
100
1000
200
Total trajectories
2500
3000
x 10
GPOMDP
0.99
0.999
0.99
Discount factor
SVRPG
0,999
0.999
0,995
SRVR-PG 0.995
0.999
0.995
GPOMDP 0.005
0.005
0.01
Learning rate 7)
SVRPG
0.0075
0.0025
0.01
SRVR-PG
0.005
0.0025
0.01
GPOMDP
10
10
250
Batch size
SVRPG 25
250
SRVR-PG
25
10
250
GPOMDP
Batch size B
SVRPG
10
5
50
SRVR-PG
5
50
GPOMDP SVRPG
Epoch size m
3
2
SRVR-PG
3
Table 3: Parameters used the SRVR-PG-PE experiments.
Parameters
Cartpole
Mountain Car
Pendulum
NN size
64
8x8
NN activation function
Tanh
Tanh
Tanh
Task horizon
100
1000
200
Total trajectories
2000
500
1750
Discount factor 7
0.99
0,999
0.99
Learning rate 7)
0.01
0.0075
0.01
Batch size N
10
5
50
Batch size B
5
10
Epoch size m
2
2
23


Reviews:
[{"review_id": "rJxxBuwItB", "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\nThe paper proposed a policy gradient method called SRVR-PG, which based on stochastic recursive gradient estimator. It shows that the complexity is better than that of SVRPG. Some experiments on standard environments are provided to show the efficiency of the algorithm over GPOMDP and SVRPG.   \n\nComments:\n\n1) I think you may ignore the highly-related work: Yang and Zhang, \"Policy Optimization with Stochastic Mirror Descent\", June 2019. Since both papers are highly-related, I would suggest the author(s) have some discussions to differentiate two papers. \n\n2) Could you please provide the reasons why you are only choosing two methods (GPOMDP and SVRPG) to compare? There are many policy gradient algorithms such as A3C, A2C, ... which have not mentioned or discussed in this paper. Are they completely different here? Is there no way to compare the performance among them with SRVR-PG? \n\n3) I am not sure if you are using the right word \"novel\" to describe your method. Basically, you adopt the existing estimator based on SARAH/SPIDER in optimization algorithms into RL problems. I do not think the word \"novel\" is proper here since it is not something total new. Notice that, the complexity result achieved in this paper is also matched the one for SARAH/SPIDER/SpiderBoost in nonconvex optimization. \n\n4) There are some discussion on choosing a batch-size in the experimental part. However, I do not see the discussion on the learning rate. The choice of parameters for GPOMDP and SVRPG may also need to be discussed. \n\n5) In Papini et al., 2018, for the experiment part, they use a snapshot policy to sample in the inner loop, and use early stopping inner loop. Moreover, they also check variance to recover the backup policy when it is blowup. Do you apply any trick to your experiments? I wonder if your numerical experiments are totally followed on your theory. \n\nMinor comments: \n- Redundancy \")\" in \\eta*S*m in Theorem 4\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper 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": "r1xTId76KH", "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": "This paper studies the theory of sample efficiency in reinforcement learning, which is of great importance and has a potentially large audience. \n\nThe strong points of the paper:\n1. This paper proposed a new algorithm stochastic variance reduced policy gradient algorithms. This paper establishes better sample complexity compared with existing work. The key part of the proposed algorithm for variance reduction is to have step-wise importance weights to deal with the inconsistency caused by varying trajectory distribution.  \n2. This paper provides experimental results verifies the efficiency and effectiveness of the proposed algorithm. \n3. In addition, parameter-based exploration extension is discussed in the appendix, which enjoys the same order of sample complexity under mild assumptions and gives better empirical performance. \n4. This paper is easy to follow. In particular, there are a lot of discussions comparing this work with existing work. \n\nThe weak points of the paper:\n1. In section 3, it is not quite clear how the reference policy is defined, and the \\theta^s is not clearly defined when s >= 1.\n2. In the main part of the paper, the discussion in Remark 4.6 and the following Corollary 4.7 is not quite clear.\n\n\nSome minor comments of the paper:\n1. In introduce page 3, We note that a recent work by .... by a fator of H. --> Here H should be defined as the Horizon. \n2. There is one additional parenthesis in Theorem 4.5.  \n3. In  Corollary 4.7, T is not defined. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJe3Ea2AYr", "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": "The authors propose a new stochastic reduced variance policy gradient estimator, which combines a baseline GPOMDP estimator with a control variate integrating past gradients by importance re-weighting. The authors establish the sample complexity of gradient descent using the proposed estimator, and further demonstrate its effectiveness through some simple empirical results.\n\nI believe this paper is a good contribution for ICLR. The result is relevant and interesting, and extends recent ideas around reduced-variance policy gradient estimators. The paper is overall easy to read, and presents its ideas clearly. Some detailed comments:\n\n- The wording of theorem 4.5 and corollary 4.7 could be somewhat clarified. In particular, I did not see \\Phi defined in the main text, and given its definition in the appendix, I believe theorem 4.5 could be stated simply in terms of J, avoiding any additional notation. Similarly, corollary 4.7 could be stated somewhat more clearly, and in particular, the choice of S should be made explicit. In the appendix, I could not find a definition for \\phi.\n\n- The empirical results presented are interesting, although I wish they were more comprehensive. In particular, it would be valuable to more exhaustively evaluate the impact of the hyper-parameters N, B and m. The authors should also clarify how the current values were chosen. Given that the theoretical results also apply to projected gradient descent, it would be interesting to see empirical results in that case.", "extra_scores": {"experience_assessment": "I have read many 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 did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a policy gradient estimator that is based on stochastic recursive gradient estimator. It provides a sample complexity result of O(eps^{-3/2}) trajectories for estimating the gradient with the accuracy of eps.
This paper generated a lot of discussions among reviewers. The discussions were around the novelty of this work in relation to SARAH (Nguyen et al., ICML2017), SPIDER (Fang et al., NeurIPS2018) and the work of Papini et al. (ICML 2018). SARAH/SPIDER are stochastic variance reduced gradient estimators for convex/non-convex problems and have been studied in the optimization literature.
To bring it to the RL literature, some adjustments are needed, for example the use of importance sampling (IS) estimator. The work of Papini et al. uses IS, but does not use SARAH/SPIDEH, and it does not use step-wise IS.

Overall, I believe that even though the key algorithmic components of this work have been around, it is still a valuable contribution to the RL literature.

Decision: Accept (Poster)