On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
Authors: Junyu Zhang
Chengzhuo Ni
Zheng Yu
Csaba Szepesvari
Mengdi Wang
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Reinforcement Learning
Policy Gradient Method
Variance Reduction
Gradient Truncation

Abstract: Policy gradient (PG) gives rise to a rich class of reinforcement learning (RL) methods. Recently, there has been an emerging trend to augment the existing PG methods such as REINFORCE by the \emph{variance reduction} techniques.  However, all existing variance-reduced PG methods heavily rely on an uncheckable importance weight assumption made for every single iteration of the algorithms. In this paper, a simple gradient truncation mechanism is proposed to address this issue. Moreover, we design a Truncated Stochastic Incremental Variance-Reduced Policy Gradient (TSIVR-PG) method, which is able to maximize not only a cumulative sum of rewards but also a general utility function over a policy's long-term visiting distribution.  We show an $\tilde{\mathcal{O}}(\epsilon^{-3})$ sample complexity for TSIVR-PG to find an $\epsilon$-stationary policy. By assuming the \emph{overparameterization} of policy and exploiting the \emph{hidden convexity} of the problem, we further show that TSIVR-PG converges to global $\epsilon$-optimal policy with $\tilde{\mathcal{O}}(\epsilon^{-2})$ samples. 

On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
Junyu Zhang
Department of Industrial Systems Engineering and Management National University of Singapore
Singapore, 119077 junyuzênus edw.ee
Chengzhuo
Department of Electrical and Computer Engineering Princeton University Princeton, NJ, 08544
chengzhuo ni@princetoon edu
Zheng Yu
Csaba Szepesvari
Department of Electrical and Computer Engineering Princeton University Princeton, NJ, 08544
Department of Computer Science
University of Alberta Edmonton, Alberta, Canada T6G 2E8
zhengy@princeton.co edu
szepesvaduallerta.cc ca
Mengdi Wang
Department of Electrical and Computer Engineering
Princeton University Princeton, NJ, 08544
mengdiw@prinneeonn.ce edu
Abstract
Policy gradient (PG) gives rise to rich class of reinforcement learning (RL) methods. Recently, there has been an emerging trend accelerate the existing PG methods such REINFORCE, by the variance reduction techniques. However, all existing variance-reduced PG methods heavily rely on an uncheckable importance weight assumption made for every single iteration of the algorithms. In this paper, simple gradient truncation mechanism proposed to address this issue. Moreover, design a Truncated Stochastic Incremental Bariance-Reducee Policy Gradient (TSIVR-PG) method, which able to maximize not only a cumulative sum of rewards but also general utility function distribution. We show an Ō(E-3) sample complexity for TSIVR-PG PG to find an e-stationary policy. By assuming the overparameterization of policy and exploiting the hidden convexity of the problem, we further show that TSIVR-PG converges global e-optimal policy with ((e= samples.
policy's long-term visiting
Introduction
In this paper, investigate the theoretical properties of Policy Gradient (PG) methods for Rein- forcement Learning (RL) In view of RL as a policy optimization problem, the PG method
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

parameterizes the policy function and conduct gradient ascent search to improve the policy. In this paper, we consider the soft-max policy parameterization
exp(v(s.a:0)) 0)}
Top (als) = En exp(v(s,a';0))
where (8, a) is state-action pair and & is some smooth function. Potentially, one can set the function d to be some deep neural network with weights 0 and input a). The main problem considered in this paper is the policy optimization for a general utlity function:
max R(TT) ;- F()*)),
where is a general smooth function, and A denotes the unnormalized state-action occupancy measure (also referred to as the visitation measure). For any policy and initial state distribution E.
+00
X (T(s,a) Σ
x IP ((
s, at 8, ~ ~t).
where y stands for the discount factor and P denotes the probability of a certain event. When F is linear, the problem reduces to the standard policy optimization problem where the objective is to maximize a cumulative sum of rewards. When F nonlinear, problem ( goes beyond standard Markov decision problems: examples include the max-entropy exploration []6]. risk-sensitive RL 50] certain set constrained RL [27]. and so on.
In the standard cumulative-retumt case (i.e., F is linear), numerous works have studied PG methods
in various scenarios, see e.g. 47 58 22 21 37 38 23). When directly optimizing over the policy space without any parameterization. the policy mirror descent (PMD) method [23 achieves an Ö(c-2) sample complexity to find an Octiomml solution. However, for the more practical parameterized policy optimization, the authors' best knowledge, the most recent variant of PG
methods, using the SARAH/Spider stochastic variance reduction technique [13] 29), find a local
e-stationary policy using
( samples 48 33]. This poses contrast with the known Ó( ?)
sample complexity results that can be achieved by various value-based methods 42 and are provably matching
In this paper, we attempt to close this gap and prove Ō(c-3) sample complexity bound for a PG method. Most importantly, when comes to PG estimation, the application the variance reduction technique typically relies on certain off-policy PG estimator, resulting in the difficulty of distribution shift. We notice that none of the existing variance-reduced PG methods attempt to address this challenge. Instead, they directly make an uncheckable assumption that the variance of the importance weight is bounded for every policy pair encountered in running the algorithm, see c.g. B1 49 33 In this paper, we propose simple gradient truncation mechanism to fix this issue.
eeormation-theoreee lower bounds [2 3 4
Next, let us go beyond cumulative return and consider policy optimization for general utility where F may be nonlinear. However, much less is known in this setting. The nonlinearity of F invalidates the concept of Q-function and value function, leading to the failure of policy gradient theorem [44] To overcome such difficulty, [1]] showed that the policy gradient for the general utilities is the solution to a min-max problem. However, estimating a single PG is highly nontrivial this case. is still unclear how to make PG methods to use samples in a most efficient way.
In this paper, we aim investigate the convergence and sample efficiency of the PG method, using episodic sampling, for both linear F' (i.c., cumulative rewards) and nonlinear F' (i.c., general utility). Observe that problem (2) is an instance of the Stochastic Composite Optimization (SCO) problem 45 46 min f [[ which involves an inner expectation that corresponds to the occupancy measure x= Motivated by this view point, we attempt to develop stochastic policy gradient method with provable finite-sample efficiency bounds.
Main results. Our main results are summarized below.
We propose the TSIVR-PG algorithm to solve problem 2 via episodic sampling. It provides a conceptually simple stochastic gradient approach for solving general utility RI.
We provide a gradient truncation mechanism to address the distribution shift difficulty in variance-reduced PG methods. Such difficulty has never been addressed in previous works.

---

We show that TSIVR-PG finds an e-stationary policy using ((e-9) samples if F and & are general smooth functions. When F is concave and & satisfies certain overparameterization condition, we show that TSIVR- P- obtains a gloal c-optimal policy using Ō samples.
Technical contribution. Our analysis technique is also of independent interest in the relating areas.
For stochastic composite optimization (SCO), most existing algorithms require estimating the Jacobian matrix of the inner mapping, which corresponds to VgA* in our setting. This is in practice prohibitive if the Jacobian matrix has high dimensions, which is exactly the case our problem. Unlike SCO algorithms such as 24 54 53 etc.J, our analysis enables us to avoid the Jacobian matrix estimation.
For the stochastic variance-reduced gradient methods, our analysis implies convergence of SARAH/Spider methods to global optimality and a new ((=-²) sample complexity for nonconvex problems with "hidden convexity" structure, which has not been studied in the optimization community yet.
2
Related Works
Policy gradient gives rises rich family of RL algorithms, such REINFORCE and many of its variants [47 5 38), as well as extensions such as the natural policy gradient methods [20] 32], the
actor-critic methods 22 21 28 the trust-region policy optimization [37 57 39] and the proximal
policy optimization method [38 25 etc. In this paper we mainly focus on REINFORCE-Ype
methods, where many of them need Ö(c=A) samples to find an c-stationary solution, including the vanilla REINFORCE (77. as well its variants with baseline [58 43 and GPOMDP (3), etc. By incorporating the stochastic variance reduction techniques, the sample efficiency of PG methods can be further improved. In [31] the SVRG [19] variance reduction scheme is adopted and O(e sample complexity is achieved, which is later improved to O(e-10(()) by 48). With additional Hessian information, (40] achieved an O(e complexity. By utilizing a more efficient SARAH/Spider (29 13 variance reduction scheme, people able achieve ((e-3) sample complexity without second-order information [48 33 We would like to comment that these results only for finding c-stationary (rather than near-optimal) solutions, and all of them requires an uncheckable condition on the importance weights in every iteration.
Recently, for cumulative reward, series of works have started to study the convergence of policy gradient method to global optimal solutions [ 56 6 26 7 9 (55). In particular, [51] exploited the hidden convexity property of the MDP problem and established the convergence to global optimality for general utility RL problem, as long as the policy gradient can be computed exactly.
Our approach is related to the stochastic composite optimization (SCO) 45 46 For the general
composition problem, there have been numerous developments, including momentum-base and multi-time-ssale algorithms
46 15 and various composite stochastic variance-reduced algo- rithms 224 [7 52 54). Our approach is also inspired by variance reduction techniques that were 1 29 ; and were later on extended to In particular, we will utilize
A5
initially used for stochastic convex optimization, see [19 36
the stochastic nonconvex optimization problems 2 the SARAH/Spider scheme
[ 30].
Problem Formulation
where S is a finite state space, A is a finite action space, y E (0, is a discount factor, and F is some general utility function. For each state s E S, transition to state s' occurs when selecting an action E A following the distribution P(-la, s). For each state E S, policy gives distribution π (-1ss) over the action space A. Let ę be the initial state distribution and let the unnormalized state-action occupancy measure A be defined by (3). we define the general utility function F as a smooth function the occupancy measure, and the goal of the general utility MDP to maximize F(X*). With the policy me being parameterized by (I). propose to solve problem (2), which is
Consider an MDP with a general utility function, denoted as MDP(S,
max R(Fo) == F (ATM).
3

---

For notational convenience, we often write X(0) instead of x Such utility function is very general and includes many important problems RL. We provide a few examples where F are concave.
Example 3.1 (Cumulative reward). When F )) = (r, ) for some T &RIIIIAA, Then we recover the standard cumulative sum of rewards: R(TT) = B[[ 7² (r(sss, (1),,aa)))))) To, 80 {]]
Vs E S be the state occupancy measure, which is the margin of XT over S. Let F(.) be the entropy function, then we recover the objective for maximal entropy exploration [6): ((TT)))T)) = = -.EE n=* (8) log 1²0 (s).
Example 3.2 (Maximal entropy exploration). Let p=a = (1 --2
Example 3.3 (RL with Set Constraint). Let z(8;, az) E TR& be vector feedback received in each step. The cumulative feedback u( == E Ei=o ?² z(5t, az)(sa ~ E, To) X for some matrix M E Radx|s |AI, 127) proposed a sel-constrained RI. problem which aims to find a policy a S.I. u(T) U for some convex set U. This problem can be formulated as instance of (2) by letting
F() be the negative squared distance: R(mo) = min [| u(
4 The TSIVR-PG Algorithm
In this section, we propose a Truncated Stochastic Incremental Sariance-Reduced Policy Gradient (TSIVR-PG) method, which is inspired by techniques of gradient truncation mechanism is proposed provably control the importance weights in off-policy sampling.
variance reduction and off off-policy estimation.
4.1 Off-Policy PG Estimation
Policy Gradient First, let derive the policy gradient of the general utility. Let V (r) be the cumulative reward under policy ge. initial distribution & and reward function r. By Example 3.1 v (r) (A(0), r), the chain rule and policy gradient theorem
44 indicates that
+o0
V VOV* (r) [v>(0)]] Tr Tr=T-Bae -= Eg
Σ
r(t,a ae)
Vo log To(aelss))]
where VoA(0) is the Jacobian matrix of the vector mapping X(0). That is, policy gradient theorem actually provides a way for computing the Jacobian- product for the occupancy measure. Following the above observation and the chain rule, we have
voR(TT)=
[Vo)(0)] [Vo\(1]=[Vo((
VxF(X(0) = (TV
Therefore, we can estimate the policy gradient using the typical REINFORCE long as we pick the "quasi-reward function" as r := V F()())). To find this quasi-reward, we need to estimate the state-action occupancy measure x()) (unless F' is linear).
Importance Sampling Weight Let = {so, do, 81, (1,01 ... SH-1. 1, - be length- H trajectory generated under the initial distribution and the behavioral policy Te, For any target policy Te,, define the importance sampling weight as
11 TT, (an|sh)
( (1,
0 Osts H
(S)
The =o, (an
It is worth noting that such importance sampling weight is inevitable in the stochastic variance reduced policy gradient methods, see [31 48, 49 33 25). In these works, the authors usually directly assume Var(wæ-1 02)) < W for all the policy pairs encountered in every iteration of their algorithms. However, such assumption is too strong and is uncheckable.
Based on the above notation of behavioral and target policies, long the importance sampling weights, we present the following off- pof-co occupancy and policy gradient estimators.
Off-Policy Occupancy Measure Estimator Denote the vector with (s, a)-th entry being 1 while other entries being 0. We define the following estimator for A(O2)
#-1
(,(70,, 02, =
x we (7) 02) exaor
(6)

---

When 82 01, (2) = 1 and (T)01, 02) becomes the on on-policy (discounted) empirical distribution, for which we the simplified notion X(T (2) == (T 82).
Off-Policy Policy Gradient Estimator Let r E RISAA be any quasi-reward vector. We aim to estimate the Jacobian-vector product [Va)(02)] for target policy Toz by
(T 02,
Σ >a w.(F(01,02) r(),,a)) 00
Vo log Ta, (acl
When 82 = 01 (7 82) 1 and [m.(1 02 r) becomes the on-policy REINFORCE estimator with quasi-reward function In this case, we use the simplified notion O(T 02, r) = Iw (T Oz. r).
Estimators (T|0,,,, and Tw (F 02, are almost unbiased. details, ||Eraar, (T 01, 02)]
see details in Appendix Therefore the bias due to truncation is almost negligible if H is properly selected.
and | (T (1, 02 r),r)] [V>](22]
4.2 The TSIVR-PG Algorithm
To achieve the Ö(--2) sample complexity, we propose an epoch-wise algorithm called Truncated Stochastic Incremental Suriance-Reduced PG (TSIVR-PG) Algorithm. Let 6 be the starting point of the i-th epoch, TSIVR-PG constructs the estimators for \(6)), quasi-reward V F(F((( and the policy gradient V (A((6))) by
1/ ((T1)) o VxF(X)) and gó
Σ TEN,
T(T r()-
(8)
TEN.
where N₁ is of N independent length- H trajectories sampled under Tag
When j 2 1,
2/
1 Σ
(N(T10))
(3))) A5-11 ry vxF(11)
(9)
B
TEB
1
9)
(T10), TEB
Σ
F. (110), (3)))))))))))) -
(10)
B
where B) is set of B independent length-Hf H trajectories sampled under Tgz. and we default == rd- Specifically, I.e 10, r 2 is used instead of (T 00;, 0: -::1::3-- r31) for independence issue. The details of the TSIVR-PG algorithm stated in Algorithm
Algorithm 1: The TSIVR-PG Algorithm
Input: Initial point 0f = 0o: batch sizes N and B; sample trajectory length H; stepsize ry; epoch length m;; gradient truncation radius 6.
2 for Epoch i 1, 2, ....dd do for Iteration j 0,
do
j = 0 then
Sample N trajectories under policy Tag of length H, collected Ng.
Compute estimators Al. rú and gó by (8) Default r²_ := rú-
else
Sample B trajectories under policy To: with length H, collected as By.
Compute estimators Xj, rý and 9 by and (O)..
10
Update the policy parameter by truncated gradient ascent step:
{0] + +
if < 8, otherwise.
0/41
(1I)
0
+ 8 9 ||lg|||
11
Set 00+
8: Bi
5

---

It is worth noting that the truncated gradient step is equivalent to a trust region subproblem:
1
0 J+1 argmax F(X(03)) (g). 03)
110 0311
(12)
l|e -0-0:116
2nj
where the approximate Hessian matrix is simply chosen as (11)
Sample Efficiency of TSIVR-PG
In this section, we analyze the sante-sample performance of TSIVR-PG. We first show that TSIVR-PP finds an e-stationary solution with Ō(E samples. Given additional assumptions, we show that TSIVR-PG finds global c-optimal solution with Ō()= samples.
5.1 Convergence Towards Stationary Points
Since we focus on the soft-max policy parameterization where To(als) E. exp (xp( we make the following assumptions the parameterization function 1 and the utility F.
exple(s.a:0)
Assumption 5.1. (8, a) is twice differentiable for all and a. There Fe, Tup > S.1.
max sup Voobss a; 0) s lv and .EB,aEA
max sup (, s Lh,
(13)
sEB,aEA
where || stands for L2 norm and spectral norm for vector and matrix respectively.
Assumption 5.2. F a smooth and possibly nonconvex functiion There exists Ex,00 > 0 such that [V)F(A I (x,00 And there exist constants Lx LA O.t. it holds for v), X' that
[[))(()) - VAF(X) & Ixll> X1|2
and [(V) V>F(X)) & LA XI11-
Based the above assumptions, have the following supporting lemmas.
Lemma 5.3. Given Assumption 5.7 aand 5.2] the following results hold:
(i). For any policy parameter and any state-action pair (s, a), the following inequalities hold:
[ log no(a|s)]] S 2bg. [[ log Te(a|s)] < 2(L + -Zy). and ([ S 26y-6..0
(1-7)*
(ii). For any policy parameters 01 and 0z it holds that 1| xm ||| I
26
-10 0211
(1-1}²
Als. + 8f. [I-
24 (L
(iii). The objective function F X(-) is La-smooth, with Lg
(1-9)"
To measure the convergence, propose to the gradient mapping defined as follows:
(, 0 - 7
0 + n-. where 0+ =
if lg S 6, otherwise
6 8 g/lllll
where = vgF(A(0)). We remark that, (e] is more suitable for the ascent analysis of the truncated gradient updates, compared with the commonly used F that (0) (A((O)) if [0)] < 8 and ||))(( is bounded for any 6. Based such observation, we have the following lemma to validate the choice of the proposed stationarity measure.
Note
Lemma 5.4. For any random vector 0, (O) S implies ((((O)) S 0(6-1.e)
Based on the notion of Gy we characterize the per-iteration ascent as follows.
Lemma 5.5. Let the iterates be generated by Algorithm 7 Then it holds that
((X(0 "IG, 2n
Lo)1
0511 (
2L (V))()(())
This suggests us to bound mean Secun-squared-enee El| V (()()))) 1/ 1). For this purpose, we need to bound the importance sampling weight, by utilizing the soft-max form of policy parameterization (I)
Lemma 5.6. For any behavioral policy iT, and target policy Te, parameterized by ( the impor- tance weight satisfies [T]01, 0z) exp (2(t + 1) 021l). for v0 s H -

---

Since TSIVR-PG only uses importance weights for two consecutive iterations 8jj 03-1 while forcing |00) 0j_1 Só by the truncated gradient step (1I), we have ( (-)) (xxp2) w.p. 1. As we will see later, the effective horizon H only has a mild magnitude of ( truncation radius only need to satisfy d = -
the for Vi < -
4b s.t. Wh
0(1), ; -1)
Consequently, combining Lemma 5.3 5.6 and Lemma B.1 of [48] gives the following result.
Lemma 5.7. Let policy Te be parameterized by ① with function satisfying Assumption 5.7 Suppose behavioral policy ne, and target policy тe, satisfy ||0] - 82ll I 8, then
([1, 02)] =1 and Var (we(T)01, 02)) - (t (t+ + +1 110 0211? where T sampled under policy no,, and (t) t( (t 2) + +2 (Ettv 2 + +1).
As a result, we can bound the mean-squaeee squa---quard--rrorr of the 93 as follows.
Lemma 5.8. For the PG estimators gj. we have
Ci + C27 2 +
C3 B
E [lo] - VOF(N(MN
S
Σ p=1
-1000-1-00111 + A.B [10]] - -0]13]
E
03 [10
for some constants C,,.., C 0. case j = O, we default ΣØ= 0.
The expression of constants C²'s are complicated, we provide their detailed formula in the appendix.
If we set H ( log(1/<) and 8 S 2HE then C, only depends polynomially on the Lipschitz constants, log(c-1) and (1 -1-1. Combining Lemma 5.5
5.8 and 5.4 gives Theorem 5.9
Theorem 5.9. For Algorithm I we choose = 2 llog(1/e) 5 2He = -mm= m= B= N==
7 = T+CC++ zL.. After running the algorithm for T = c epochs and output Oou from {0) - mm1 uniformly at random, we have El[|g,, (f ))l S O(c). The total number of samples T' ((m - B)B + N) x H = (E.-)))) By Lemma 5.4 we also have V (((00ntt)) - O(e).
5.2 Convergence Towards Global Optimality
Next, we provide a mechanism to establish the convergence of TSIVR-PG to global optimality. For this purpose. we introduce the hidden convexity of the general utility RL problem. In addition the smoothness of F (Assumption 5.2). we further assume its concavity, formally stated as follows.
Assumption 5.10. Function a concave function of the state-action occupancy measure.
Let L be the image of the mapping X(0). Then the parameterized policy optimization problem 2 can be rewritten as an equivalent uccupancy optimization problem:
maxş F()(0))
max F(u).
(14)
When the policy parameterization is powerful enough to represent any policy, the image is convex polytope, see e.g. (10). Since F is concave, the occupancy optimization problem is a convex optimization problem. In this case, if the mapping X(-) is invertible (see (5T), we may view the original problem (2) as reformulation of a convex problem by change of variable: 0 = X (p). We call this property "hidden convexity". However, requiring X(-) to be invertible too restrictive, and doesn't it even hold for simple soft-max policy with (b(s, , 0) = t.o where multiple 0 correspond to a same policy. Therefore, we adopt a weaker assumption where (i). mo can represent any policy (ii). a continuous inverse X (-) can be locally defined over a subset of O.
Assumption 5.11. For policy parameterization of form ( 9 overparanetrizes the set of policies in the following sense. (i). For any O and X(0), there exist (relative) neighourhoods 0 e Us B(8 8) and x(0) E Vx(0) C X(B(0, 6)) s.t. (Al,)(.) forms bijection between Us and VxØy where (X (.).))))))))))) ( the confinement of onto Ug. We assume (N1))) is Ln-Lipschitz continuous for any 0. (ii). Let πT- be the optimal policy. Assume there exists small enough, s.t. (1 -))(()))))))))))) =>(0-)
Vx for Ve <τ, ē, VO.
Based on Assumption 5.11 replace Lemma 5.5 with the following lemma.
7

---

Lemma 5.12. For VE < E &with È defined in Assumption 5.11 it holds for all iterations that
F(X(0)) F(((0)))) s (1-c) (F(X(()) (F(X()))-((((())))
(15)
+ (Lg + 2n) (1 - 7)2 (2 - 103111111-1111
1 26
1 Lg [99 VoF(A(()))12
The analysis of Lemma 5.12 is very different from its nonconvex optimization counterpart (Lemma 5.5). Next, we derive the sample complexity of the TSIVR-PG algorithm given Lemma a 5.8
and
Theorem 5.13. For TSIVR-PG method (Algorithm D. let E) be the larget accuracy. If we choose H, m. B, N and 6 according to Theorem 5.9 and we let the stepsize to be small enough s.I.
n S CLo+ then after at most T loga (c epochs, E [) -F(((r)) & Oc)).
The total number of samples taken is T x ((m - 1)B + N) x H 0
6 Numerical Experiments
6.1 Maximizing Cumulative Reward.
In this experiment, we aim to evaluate the performance of the TSIVR-PG algorithm for maximizing the cumulative sum of reward. As the benchmarks, we also implement the SVRPG 44),, the SRVR- PG [48], the HSPGA [3), and the REINFORCE [47] algorithms. Our experiment is performed on benchmark RL environments including the FrozenLake, Acrobot and Cartpole that are available from OpenAl gym [8) which is a well-known toolkit for developing and comparing reinforcement learning algorithms. For all the algorithms, their batch sizes are chosen according to their theory. In details, let e be any target accuracy. For both TSIVR-PG and SRVR-PG, we set N = Oee-))
B = m = HSPGA, we set B = ( -1), other parameters are calculated according to formulas in (33) given B. For REINFORCE, we set the batchsize to be N = O ²). The parameter e and the stepsize/learning rate are tuned for each individual algorithm using grid search. For each algorithm, we run the experiment for multiple times with random initialization of the policy parameters. The curve is obtained by first calculating the moving average of the most recent 50 episodes, and then calculate the median of the return over the outcomes of different runs. The upper and lower bounds of the shaded area are calculated as the and 1/ quantiles over the outcomes. We run the experiment for 10 times for the Frozenl .ake environment and 50 times for the other environments. The detailed parameters used the experiments are presented in the Appendix.
For SVRPG, we set N = )) B =
and m = ((E=) For
FrozenLake The FrozenLake8x8 enviromment is tabular MDP with finite state and action spaces. For this environment, the policy parameterized with (s, a; 0) 0.a.
Cartpole and Acrobot Both the Cartpole environment and the Acrobot environment are environ- ments with discrete action space and continuous state space. For both environments, we use neural network with two hidden layers with width 64 for both layers to model the policy.
Result We plot our experiment outcomes in Figure 6.1 The experiments show that given enough episodes, all of the algorithms are able to solve the tasks, achieving nearly optimal returns. And as expected, the REINFORCE algorithm takes the longest time to find the optimal policy. While the other algorithms yield a faster convergence speed, the TSIVR-PG algorithm consistently outperforms the other benchmark algorithms under all of the environments, showing the advantage of our method.
6.2 Validating the Ō(c-2) Sample Complexity
Besides the comparison between different benchmark algorithms,, we also perform validation experiment showing that for certain environments, the convergence rate of TSIVR-PG is close the theoretical guarantee. Because the parameters N, B, m are dependent on the target accuracy c, in this section we adopt a different way to set up these parameters: We first set a fixed epoch E, and perform experiments using different values of the parameter N. The parameter B and m are set according to our choice of N by B the average score of the last few episodes, which is then averaged over 10 independent runs. Again, use the FrozenLake8x8 environment to do the experiment. Because FrozenLake8x8 is a tabular
= VN. The performance of the algorithm output is calculated as
8

---

060
The performance eurves of TSIVR-PG and benchmark algorithms under different environ- ments. The curve is the median return over multiple and the shaded areas calculated the and 1 quantiles of the experiment outcomes.
Figure 1:
environment whose transition and reward function can be easily obtained from the document, can calculate it's optimal value simply by value iteration, which takes 0.41 46 when we choose y = 0.99. In this way, calculate the gap between the algorithm return and the optimal value, and get log-log figure w.r.t. the gap and the number episodes calculated by E(N + Bm)- = 2EN.
Result The result is shown in the first sub-figure of Figure 6.3 where the blue curve is the gap between the average return experiment outcome and the optimal value and the shaded area the range of one standard deviation of the logarithm value. In addition, we add orange dotted line to the convergence curve, whose slope takes value -0.496, which nearly matches the O(e thcoretical bound (slope -..5).
6.3 Maximizing Non-linear Objective Function
The TSIVR-PG algorithm is designed not only to solve typical RL problems, but also able to solve broader class of problems where the objective function is a general concave function. Unfortunately, none of the benchmark algorithms proposed the previous section have the ability to solve this kind choose another benchmark algorithm,
of problem. To evaluate the performance of our algorithm, which is the MaxEnt algorithm [16]. In the experiment, we use FrozenLake8x8 environment since it's more tractable to compute À for discrete state space. We set the objective function as
F(A)
Σ log #ES
Σ aEA
Xsaa + t
where a is fixed small constant. We choose 0.125 in our experiment. The orders of N, B, are set in the same way as those in section 6.1. For the MaxEnt algorithm, note that in the original paper, the nonlinear objective function assumes the input value is the stationary state distribution d", but the input value can easily be changed into our À without changing the steps of the algorithm much. The result is illustrated in Fig. 6.3 From the result, may that algorithm consistently outperforms the benchmark.
7 Broader Impact
There has been an emerging trend of applying stochastic variance reduction technique to enhance the performance of the policy gradient methods. However, all the existing variance-reduced policy gradient methods depend on an ingorithm-dependen assumption that is made to every single iteration running the algorithm, which actually may not be satisfied by many of these algorithms. We propose simple yet effective mechanism to fix such dilemma for applying the SARAH/Spider variance reduction scheme in policy gradient methods. Our analysis can also be applied other schemes such as STORM and Hybrid SARAH-SGD. Beyond that, we also show how the hidden convexity and overparameterization of the RI problem can help stochastic vericede-reduced policy gradient methods to converge to global optima and yield better sample complexity.

---

Lonvergence Curve Follcy Valuee for FrczenLake
Chance of PAA for ProzenLa
Fisted
-45
-.0
-102
-2.5
-112
-3.0
Max
10.0 10.3
21.0
11.3
12.0
2002
2000
3000
4200
5000
8000 5000
7000
Epis0des
Figure 2: Left: Empirical Evaluation of the Convergence Rate of TSIVR-PG. The optimality gap achieved by TSIVR-PG decreases as the sample size increases, nearly matching the c - sample com- plexity theory (orange line). Right: Performance Curve ofTSIVR- PP and MaxEnt for Maximizing Non-linear Objective Functions. The curve is the median return over 10 runs and the shaded areas are calculated as the and & quantiles of the experiment outcomes.
8 Limitation
To compute the policy gradient for the general utility function, one needs to compute gradient of the function with respect to the state-action occupancy measure. Although for many instances, including standard cumulative sum of reward (Example 3.1)p and set constrained RL (Example (3.3). estimating the occupancy measure is not necessary. There are many instances where estimating the occupancy measure is unavoidable. Due to the curse of dimensionality, the need for estimating the occupancy measure is a potential limitation if the state and action spaces are continuous and high-dimensional. One potential solution is to incorporate function approximation for the occupancy measure, in a similar style of the Q-function approximation in the actor-critic method. We leave this for future development.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference on Learning Theory, pages 64-66. PMLR, 2020.
[2] Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pages 699-707, 2016.
[3] Mohammad Gheshlaghi Azar, Rémi Munos, Mohammad Ghavanzadeh, and Hilbert Kappen. Reinforcement learning with a near optimal rate of convergence. 2011.
[4] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning. (133:325-349 2013.
[5] Jonathan Baxter and Peter Bartlett. Seinite-hhoizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15:319-350, 2001.
[6] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv: 190600/99 2019.
[7] Jalaj Bhandari and Daniel Russo. A note on the linear convergence of policy gradient methods. arXiv preprint arXiv:2007. / 2020.
[8] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint 1.X.vv1606.015.00 2016.
10

---

[9] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558, 2020.
[10] Yichen Chen, Lihong Li, and Mengdi Wang. Scalable bilinear pi learning using state and action features. arXiv preprint arXiv: 10328, 2018.
[11] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradi- ent method with support for non-strongly convex composite objectives. Advances in neural information processing systems,
1654, 2014.
[12] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of muchine learning research, 7(6), 2006.
[13] Cong Fang. Chris Junehi Li, Zhouchen Lin, and Tong Zhang. Spider: convex optimization via stochastic path- -itternteertted differential estimator. In Advances in Neural Information Processing Systems, pages 689-699, 2018.
Near-optimal non-
[14] Maryam Fazel, Rong Ge, Sham M Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. arXiv preprint arXiv: 100000039, 2018.
[15] Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang. A single timescale stochastic approximation method for nested stochastic optimization. SIAM Journal on Optimization, 30(1):960- 9700009979,000 2020.
[16] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Machine Learning, pages 2681-2691. PMLR, 2019.
[17] Zhouyuan Huo, Bin Gu, Ji Liu, and Heng Huang. Accelerated method for stochastic composition optimization with nonsmooth regularization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[18] Sashank J Reddi, Suvrit Sra, Bamabas Poczos, and Alexander Smola. Proximal stochastic methods for nonsmooth nonconvex fnite-sum optimization. Advances in neural information processing systems, 29:1 145-1153, 2016.
[19] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-323, 2013.
[20] Sham M Kakade, natural policy gradient. Advances neural information processing systems, 14:1531-1538, 2001.
[21] Vijay R Konda and John N Tsitskliis Actor-critic algorithms. In Advances in neural information processing systems, pages 1008-1014, 2000.
[22] Vijaymohan R Konda and Vivek S Borkar. Actor-critic-type learning algorithms for markov decision processes. SIAM Journal on control and Optimization, 38( (1)::994113, 1999.
[23] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint 10Xiv:2102.00/35, 2021.
[24] Xiangru Lian, Mengdi Wang, and Ji Liu. Finite-sum composition optimization via variance reduced gradient descent. In Artificial Intelligence and Statistics, pages 1159-1167. PMLR. 2017.
[25] Boyi Liu, Qi Cai. Zhuoran Yang. and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. In Advances in Neural Information Processing Systems, pages (0565-10576) 2019.
[26] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global conver- gence rates of softmax policy gradient methods. arXiv preprint arXiv:2005.06639,, 2020.
11

---

[27] Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert E Schapire. Reinforcement learning with convex constraints. In Advances in Neural Information Processing Systems, pages 14093-14102, 2019.
[28] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928-1937, 2016.
[29] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. arXiv preprint arXiv: vtXivv/703.001 100.000 2017.
[30] Lam M Nguyen, Marten van Dijk, Dzung T Phan, Phuong Ha Nguyen, Tsu Weng, and Jayant R Kalagnanam. Finite-sum smooth optimization with sarah. arXiv preprint arXiv:1901.0764B5 2019.
[31] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. arXiv preprini arXiv:/806.0888 806660668,, 2018
[32] Jan Peters and Stefan Schaal. Natural actor-critic. Neurocomputing, 7 71(7-9):1100-119) 2008.
[33] Nhan H Pham, Lam M Nguyen, Dzung T Phan, Phuong Ha Nguyen, Marten van Dijk, and Quoc Tran-Dinh. A hybrid stochastic policy gradient algorithm for reinforcement learning. arXiv preprint arXiv:2003.00 000300 2020.
[34] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference machine learning, pages 314-323, 2016.
[35] Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Fast incremental method for nonconvex optimization. arXiv preprini 103.01660 2016.
[36] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162((-2):83 112, 2017.
[37] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pages 1889-1897, 2015.
[38] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford. and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint wrXiv:1707.0634/ 2017.
[39] Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 34, pages 5668-5673 2020.
[40] Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International Conference on Machine Learning, pages 5729-5738, 2019.
[41] Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving discounted markov decision process with generative model. arXiv preprint arXiv: 1806.0444909 2018
[42] Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving markov decision processes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770-787. SIAM, 2018.
[43] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[44] 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 information processing systems, pages 1057-1063, 2000. 2000.
12

---

[45] Mengdi Wang, Ethan X Fang, and Han Liu. Stochastic compositional gradient descent: algo- rithms for minimizing compositions of expected-value functions. Mathematical Programming. 161(1-2):4194449 2017.
[46] Mengdi Wang. Ji Liu, and Ethan X Fang. Accelerating stochastic composition optimization. The Journal of Machine Learning Research, 18(1):3721-3743, 2017.
[47] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229-22) 1992.
[48] Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. arXiv preprint arXiv:1909,0860 08610, 2019.
[49] Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty Artificial Intelligence, pages 541-551. PMLR, 2020.
[50] Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Cautious reinforcement learning via distributional risk in the dual domain. arXiv preprint arXiv:2002.12475, 2020.
[51] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Varia- tional policy gradient method for reinforcement learning with general utilities. arXiv preprint arXiv:2007.02/55 151, 2020.
[52] Junyu Zhang and Lin Xiao. A composite randomized incremental gradient method. In Interna- tional Conference on Machine Learning, pages 7454-7444 0464-7462,.0 2019.
[53] Junyu Zhang and Lin Xiao. Multi-level composite stochastic optimization via nested variance reduction. arXiv preprint orXiv:/900) 1468, 2019.
[54] Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. In Advances in Neural Information Processing Systems, pages 9078-9088, 2019.
[55] Junzi Zhang, Jongho Kim, Brendan O' O'Donoguue, and Stephen Boyd. Sample efficient rein- forcement learning with reinforce. arXiv preprint wrxiv:2010.11364 2020.
[56] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv preprint 1906::/906.88:00 2019.
[57] Mingming Zhao, Yongfeng Li, and Zaiwen Wen. A stochastic trust-region framework for policy optimization. arXiv preprint arXiv:/911.1 1640, 2019.
[58] Tingting Zhao, Hirotaka Hachiya, Gang Niu, and Masashi Sugiyama. Analysis and improvement of policy gradient estimation. Neural Networks, 26:118-121 129, 2012.
13


Reviews:
[{"review_id": "qOVuOVoZ3la", "reviewer": "Reviewer_6pHy", "summary": "There is a lot of interest in studying policy gradient type of algorithms for solving the RL problem recently.  This paper develops a variance reduced policy gradient method, where the objective function can be some general utility function instead of just being the cumulative reward. A sample complexity of $\\mathcal{O}(\\epsilon^{-3})$ was established under some mild conditions, and it was further improved to $\\mathcal{O}(\\epsilon^{-2})$ under a convexity assumption and a so-called over-parametrization assumption. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is nicely written. One comment about the structure in Section 5. I understand that the results in Section 5 are presented linearly. However, as a reader, I prefer to first read the main theorem, and then its proof or proof sketch.\n\nWhen the objective function is the cumulative reward, the sample complexity of policy gradient (or natural policy gradient) was established in the literature, which is $\\mathcal{O}(\\epsilon^{-2})$ (Lan, G. (2021). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.00135.). However, in this setting, the proposed algorithm in this paper requires the overparametrization assumption to establish the $\\mathcal{O}(\\epsilon^{-2})$ sample complexity. Is this assumption really necessary or it is an artifact of the proof?\n\n----------------------------------After Feedback----------------------------------\n\nThank the author for their feedback. I do not have further concerns and I am going to keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No Societal Impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "pRflneNqIPF", "reviewer": "Reviewer_gxo4", "summary": "In this paper, the authors propose a new policy gradient algorithm called TSIVR-PG for the policy optimization for a general utility function. They adopt a gradient truncation mechanism in TSIVR-PG to get rid of the uncheckable importance weights assumption which is frequently used in previous literatures. They establish convergence rate to stationary points, and global convergence results with additional assumptions. Moreover, they conduct experiments and compare with other previous methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-written, highlights their contribution clearly, and has a detailed discussion on related works. I’m glad to see that convergence of the algorithm does not rely on the importance weight assumption that is indeed problematic sometimes. I think the contribution on the theory side is significant. Besides, the empirical evaluation is promising and makes this paper more solid.\n\nConcerns:\n\n(1) I’m wondering if Assump. 5.11 is still too strong? Are there any policy function classes examples that can (approximately) satisfy that assumption?\n\n(2) I'm kind of worried about whether the choice of B and m is fair enough without grid search because the constant in the $O(\\cdot)$ also matters and making sure the alignment of $\\epsilon$ may not be enough, especially B and m are small in these experiments. I wonder if the authors have some remarks on that? \n\nBut considering that the main contribution of this paper is on the theory side, this is not an important issue.\n\n\nMinor Issues:\nLine 168: a redundant \\theta after “\\theta^+=”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "JJPdWp-oO9I", "reviewer": "Reviewer_sR2P", "summary": "This paper proposed an algorithm TSIVR-PG, which can provably control the importance weights, while other methods rely on uncheckable ones when it comes to variance reduction in off-policy estimation. To support the idea, derivations are given in Section 5 to theoretically prove the convergence of this model, and experiments in Section 6 also support its effectiveness.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work incorporates a simple gradient truncation mechanism into importance weights control for variance reducing, which addresses the restrictive assumption issues that other methods suffer. The mathematical derivation of convergence seems solid. The work seems good to me, however, there could be several points that could further improve the overall quality of this paper, as follows:\n1. Some symbols are used without an explicit statement when first mentioned in this paper,  e.g.,  $\\gamma$ and $\\mathbb{P}$ in equation 3.\n2. In the denominator part of equation 5, the position of $h$ and $t$ is supposed to be exchanged.\n3. Above line 169, a redundant $\\theta$ is added in the definitive equation of $\\theta_{+}$.\n4. In equation 13, the character $L_{h}$ is supposed to be $L_{\\psi}$.\n5. Inconsistent format, e.g., the figures in Section 6 are not referred to in a correct fashion in the main manuscript.\t(Labeled as Fig. 1 but referred to as Fig. 6.1)\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Though this method is applicable to discrete space small-sized problems, it is still not clear why the continuous space problems and neural networks are not taken into accounts. Besides, there are several points that are not explained clearly and may cause limitations on understanding.\n1. In Eq. 10, why the update of $g_j$ has to use $r_{j-1}$, what if $r_{j}$ is used in Eq. 10 given that $r_j$ can be updated/obtained according to Eq. 9 ？\n2.  The total numbers of samples used in Theorem 5.9 and 5.13 are obtained according to algorithm 1.  I can follow Theorem 5.13 but get confused about Theorem 5.9. Could you please explain more about how the total number of samples is obtained in Theorem 5.9?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "2jST0x2AyUX", "reviewer": "Reviewer_vT8s", "summary": "This paper investigates a novel truncation mechanism to perform variance reduction in policy gradient methods without the uncheckable importance weight assumption widely used in the literature. This technique is analyzed in depth in theory and supported with strong numerical experiments.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "First, I would like to thank the authors for their work: It is a very-well written and clear paper with relevant motivations (clear introduction), well-explained related work and fine overall structure. I really enjoyed reading this paper.\n\n- Originality: \nThe idea behind TSIVR-PG is originial and there are solid contributions. This paper presents a new truncation mechanism for policy gradient methods which extends several convergence results known so far in restricted settings. The related work is adequately cited and clearly describes how the current paper differs from it.\n\n- Quality: \nTechnically strong, highly general results, advanced techniques. The different examples of the problem formulation are convincing. The numerical experiments strongly support the theoretical claims.\n\n- Clarity: \nThe paper is very well written with fine overall structure making it easy for the reader to grasp all the main ideas.\nThe mathematical proofs are well polished.\n\n- Significance: \nThe results are quite important as they extend and relax several assumptions made so far in policy gradient methods.\n\n- Typos:\nabstract \"overparameterizaiton\"\nl.113 tuncation mechanism [is] proposed\nl.293 beyongd", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a novel truncation mechanism for variance reduction in policy gradient methods. This truncation mechanism allows one to dispense of the importance weight assumption. The paper then develops a complexity theory both for reaching stationary points and global optima (under additional convexity assumptions). All the reviewers agreed that this is an importance contribution, that the theory is sound and well written, and that the additional numerical experiments insightful. 
Decision: Accept (Spotlight)