Momentum-Based Policy Gradient with Second-Order Information
Authors: Saber Salehkaleybar
Mohammadsadegh Khorasani
Negar Kiyavash
Niao He
Patrick Thiran
Venue: Accepted by TMLR ()

Abstract: Variance-reduced gradient estimators for policy gradient methods have been one of the main focus of research in the reinforcement learning in recent years as they allow acceleration of the estimation process. We propose a variance-reduced policy-gradient method, called SHARP, which incorporates second-order information into stochastic gradient descent (SGD) using momentum with a time-varying learning rate. SHARP algorithm is parameter-free, achieving $\epsilon$-approximate first-order stationary point with $O(\epsilon^{-3})$ number of trajectories, while using a batch size of $O(1)$ at each iteration. Unlike most previous work, our proposed algorithm does not require importance sampling which can compromise the advantage of variance reduction process. Moreover, the variance of estimation error decays with the fast rate of $O(1/t^{2/3})$ where $t$ is the number of iterations. Our extensive experimental evaluations show the effectiveness of the proposed algorithm on various control tasks and its advantage over the state of the art in practice.

Published in Transactions on Machine Learning Research (04/2024)
Momentum-Based Policy Gradient with Second-Order Infor- mation
Saber Salehkaleybar
Leiden Institute of Advonced Computer Science
Leiden University
Sadegh Khorasani
sudegh..Hoorusami@@llp....k
School of Computer and Communication Sciences
EPFL
Negar Kiyavash
College of Management of Technology
EPFL
Niao He
niao.he ethe. cc
Deportment of Computer Science
ETH Zurich
Patrick Thiran
patrick. théran &eeff..c
School of Computer and Communication Sciences
EPFL
Reviewed OpenReview: opennrvve/ennr.viee.u net/ ttr/formm? id= 2bURaH6RM
Abstract
Varience-reduced gradient estimators for policy gradient methods have been one of the main focus of research in the reinforcement learning in recent years they allow acceleration of the estimation process. We propose variance-reduced policy-gradient method, called SHARP, which incorporates second-order information into stochastic gradient descent (SGD) using momentum with a time-varying learning rale. SHARP algorithm is parameter-free, achieving e-approximate first-order stationary point with O number of trajectories, while using a batch size of (1) at cach itcration. Unlike most previous work, our proposed algorithm does not require importance sampling, which can compromise the advantage of variance reduction process. Moreover, the variance of estimation error decays fast rate of (1//2/33) where t is the number of iterations. Our extensive experimental evaluations show the effectiveness of the proposed algorithm on various control tasks and its advantage over the state of the art icectice.
1 Introduction
Reinforcement Learning (RL) has achieved remarkable success in solving various complex tasks in games Silver et al. 2017). autonomous driving (Shalev-Shwartz al. 2016), and robot manipulation (Deisenoohh ct al. 2013). among other fields. In the RL setting, an agent tries to learn the best actions by interacting with the environment and evaluating its performance based on reward signals. More specifically, in Markov Decision Processes (MDPs), the mathematical formalism for RL, after taking an action, the state changes according transition probability model and reward signal received based on the action taken and the current state. The main goal of the learner is to find policy that maps the state space the action space, maximizing the expected cumulative rewards the objective function.

---

Published in Transactions on Machine Learning Research (04/2024)
Policy gradient methods (Sutton et al. 2000) are often used for training policies in MDPs, especially for high-dimensional continuous action space. In policy gradient methods, the policy is parameterized by an unknown parameter 0 and it is directly optimized using the stochastic first-order gradient of cumulaatve rewards as it is infeasible to compute the gradient exactly. REINFORCE (Williams) 1992). PGT (Sutton et al. 2000). and GPOMDP (Baxter & Bartlett 200T) are some classical methods that update the policy by applying a stochastic gradient ascent step. These methods generally require a large number of trajectories due to the large variance of gradient estimates, stemming from randomness of transitions over trajectories.
In the RL literature, several methods have been proposed to reduce the variance in policy gradient methods. For instance, Sutton et al. (2000) proposed to consider a bascline in order to reduce variance of gradient estimation. Konda & Tsitsiklis (2000) presented an actor-critic algorithm that estimates the value function and uses it to mitigate the effect of large variance. [Schllaan et al. (2016) proposed GAE to control both bias and variance by exploiting temporal difference relation for the advantage function approximation. More recent work such as TRPO (Schulman et al. 2015) considers a Kullback-Leibler (KL) divergence penalty term in order to ensure that the updated policy remains close to the current policy PPO (Schulman el. al.) 2017) that uses clipped surrogate objective function to achieve the same goal. In practice it has been shown that these algorithms have better performance compared with vanilla policy gradient method.
Most stochastic gradient based policy methods need O(e-²) trajectories in order to achieve e-approximate first-order stationary point (e-FOSP) of the objective function J(0), i.e, J S e (Ghadimi & Lan 2013 Shani et al.) 2020). In recent years, there have been several attempts to reduce the variance of policy gradient by adapting variance reduction techniques proposed previously in a supervised learning context (a list of previous work is given in Section 4.. These methods can achieve sample complexity of O(c-3) in the RL setting and this rate is optimal in stochastic optimization under some mild assumptions the objective function and stochastic gradients (Arjevani et al.) 2020). On the one hand, in supervised learning problems, the objective function is oblivious, in the sense that the randomness that selects the loss function does not depond on the parameters that are to be optimized. On the other hand, in the RL sctting, the distribution over trajectories is non-stationary and changes over time as the parameters of policy are updated. To resolve this issue, most previous work use importance sampling techniques, which may degrade the effectiveness of the variance reduction process (Yang et al., 2022). Morcover, to analyze the convergence rate of these methods, strong assumption the variance of importance sampling weights is made, which may not hold in the RL setting. Most importantly, these methods often need huge batch sizes, which is highly undesirable in practice.
In this paper, we propose the Stochastic Hessian Aided Recursive Policy gradient (SHARP) algorithm, which incorporates second-order information into SGD with momentum. Our main contributions are summarized as follows:
Under some common regularity assumptions on the paramcterized policy, SHARP reaches c-FOSP with a sample complexity of O(E-3). Moreover, our algorithm does not use importance sampling techniques. As a result, we can relax the strong additional assumptions on importance sampling weights, which are customary in the literature.
The batch size of SHARP is 0(1) and it does not require checkpoints, thanks to the use of a second-order term in the updates and time-varying learning rate and momentum weight.
SHARP is parameter-free in the sense that the initial learning rate and momentum weight do not depend the parameters of the problem. Morcover, the variance of the cstimation crror decays with rale of 0(1/12/5), where / is the number of ilerations.
Our experimental results show that SHARP perforrs the state of the art on various control tasks, with remarkable performance in more complex environments.
The rest of this paper is organizod as follows: In Section 2 we define the problem and provide some notations and background on variance reduction methods in supervised learning. In Section B we describe the proposed algorithm, SHARP, and analyze its convergence rate. In Section 4 we give a summary of previous work
2

---

Published in Transactions on Machine Learning Research (04/2024)
and discuss how SHARP differs from them. In Section 5 evaluate the performance of SHARP against the related work experimentally. Finally, we conclude the paper in Section G
2
Preliminaries
2.1 Notations and problem definition
Consider a discrete-time MDP M = {S 7.P) that models how an agent interacts with given environment. and A are state space and action space, respectively. P(s'ls, a) denotes the probability of transiting to stale 8 from s after laking action a. The reward function R returns reward r(s, a) when action is taken in state s. Parameter Y E (0, denotes the discount factor and p the distribution of starting state. The actions are chosen according policy æ where T(ass) is the probability of taking action a for given state Here, we assume that the policy is parameterized with vector 0 Rd and use shorthand notation To for (a(ss))
For a given time horizon H, according to policy the agent observes a sequence of state-action pairs T == (5p, 4o, ... $H-1,aH-11 called a trajectory. The probability observing a trajectory t for a given policy wy
H-1
p(r(mo) p(so) II
P(sn-1lsh (o (an|sh)-
(1)
h=0
The discounted cumulative reward for a trajectory t defined as R(T) = Σ#1 >r((n, an) and the expected return for policy Te is:
O(0)= Er [R(T]].
The main goal in policy-based RL is to find 0" = arg max, J(0). As in many applications, [() is non-convex and we settle instead for obtaining c-FOSP such that E[[[JJ(A]II s c. It can be shown that:
H-1
J((()) = Σ
(T) To (analss))
(3)
where (T( E 7"r(s,, Therefore, for any trajectory 7, 9(:; = unbiased estimator of (O))). The vanilla policy gradient updates 0 as follows:
En=o
is
+ 8 (g(=;))
(4)
where 77 is the learning rate.
The Hessian matrix of (() can be written follows Shen et al. 2019
v2 = (VV
(5)
where T(0,)) = H-1 H-1 0=
Σ
1=
y (st a.) log No (4n
For given trajectory B(r;0)
=
VV( logp(T|TT)
V (0;;T) is an unbiased estimator of the Hessian matrix.
2.2 Variance reduced methods for gradient estimation
Variance reduced methods for estimating the gradient vector were originally proposed for the stochastic optimization setting:
min (e0p(e) GER
(6)
where a sample is drawn from distribution p(z) and [(; is commonly assumed to be smooth and non- convex function of 0. This setting mainly considered in supervised learning contexts where corresponds the parameters of the training model and 2 = (a. y) is the training sample, with æ the feature vector of the sample and y the corresponding label. In this setting, the distribution p(2) is invariant with respect parameter 0.
3

---

Published in Transactions on Machine Learning Research (04/2024)
A Algorithm 1 Common framework in variance reduction methods for 0.... ,T do
(f(0,,
t (mod Q),
(7)
Beheekk
se Beheckk
ht
h +
(VS(0,, (0 v)((-=):)),
otherwise.
(8)
B
ZEB
3: Pc-1 f- 8g - 1/h
4: end for
Return 9, with t chosen randomly from {0.... ,T -
The common approach for reducing the variance of gradient estimation is to reuse past gradient vectors. The pseudo-code for this general framework for variance reduction is given in Algorithm [ After every pre-determined number of iterations Q, there is a checkpoint to obtain an unbiased estimate of the gradient, denoted by he, at the current parameter 0e by taking batch of samples Beheck- Between any two consocutive checkpoints, the gradient. at the parameter Or is estimated according to equation g by taking a batch of samples B drawn from p(z). The above framework appeared in several previous variance reduction methods in stochastic optimization such as SARAH Nguuyen et al. 2017) and SPIDER (Fang et al. 2018 Zhang (202)) discusses how to choose the size of batches and the parameters Q and In fact, there is a trade-off between 17 and [ Tf a small batch size is used, then is also required to be small. The two extremes are
BoiderBoost (Wang et al. 2019) (B = 0( 1), = (())) and SARAH (Nguyen et al., 2017) ([B) = O(1,,
7 = O(c). Very recently, Li
2021) proposed PAGE, where each iteration t, either batch of samples
is taken with probability Pt update the gradient or the previous estimate of the gradient is used with a small adjustment, with probability p-p
In the context of RL, sample = corresponds to a trajectory т. Unlike supervised learning, the distribution of these trajectories depends on the parameters of the policy that generates them. Therefore, in the second term in the sum in equation S namely ff( x (i.c., the trajectory T in the RL context) is generated according policy Tæ, while 0.-1 is the parameter of the policy at the previous ileration. In the RL setting, importance sampling technique is commonly used account for the distribution shift follows:
h ---111 + Σ g(00))) -wrrr))w((((r,ee.)oor (1)00
with the weights w(r]0;, 0,-1) TT me, (a, (8x)
As we shall see in Section 4 nearly all variance reduction approaches RL employing the general framework of Algorithm [ use an importance sampling technique. This could significantly degrade the performance of the approach as the gradient estimates depend heavily on these weights (Yang et al., 2022). Besides, these variance reduction methods often need giant batch sizes at checkpoints, which not practical in the RL setting. Finally, the hyper-parameters of these approaches must be selocted carcfully they often use non-adaptive learning rales. To resolve the issue of requiring huge batch-sizes, in the context of stochastic optimization, a variance reduction method called STORM (Cutkosky & Orabona. 2019) was proposed with the following update rule:
- -t) ff,, 2)) +(1 (1- (v)(0(() vf(0--1,))) o1+1 +- 0, -/hh
(10)
where 2, is the sample drawn at iteration t and a and 77 are the adaptive momentum weight and learning rate, respectively. Compared with SGD with momentum, the main difference STORM is the correction term Vf(0,, f((-1122 2) in equation 10 Cutkosky & Orabona (2019) showed that by adaptively updating 04 and nn based the norm of stochastic gradient in previous iterations, STORM can achieve
4

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm The SHARP algorithm
Input: Initial point Go, parameters av, No; and number of iterations T
1: Sample trajectory To with policy Te.
2: Up < [ 06)
3: 0, - 0 + 1/0 Tool
in
do 4: for t = 1. ... .
5: Sample by ~ (0,
6: 0g + byO, + (1- b,)0.-1
Sample trajectories Te and 7 with policies Te, and Top respectively
8: Te
no 2/a, 0g +
22/3
0g
- (1 (1) B(T (0) - 01 0(-1)) + (T)
10: P--1 + O2 + le [لll
11: end for
12: Return 0, with t chosen randomly from {0, T -1 1}
the same convergence rate previous methods without requiring checkpoints nor huge batch size. Later, parameter-free version, called STORM+ (Levy et al., 2001), has been introduced using new adaptive learning rate and momentum weight. However, to adapt these methods in the RL setting, we still need to use importance sampling techniques because of the term (f(0,-1, xt) Recently, (Tran & Cutkosky (2022) showed that the correction term can be replaced with a second-order term f(0, 2))( - 0.-1) by making the additional assumption that the objective function second-order smooth. Besides, the above Hessian vector product can be computed in O(Hd) (similar to the computational complexity of obtaining the gradient vector) by executing Pearlmutter's algorithm (Pearlmutter 1994).
3 The SHARP Algorithm
In this section, we propose the SHARP algorithm, which incorporates second-order information into SGD with momentum and we provide convergence guarantee. SHARP is described in Algorithm ? At each iteration we draw sample b, from a uniform distribution in the interval [0. 1] (line 5) and next obtain 6 the linear combination of 0z-1 and 0g with coefficients 1 b, and b, (line 6). In line 7, we sample trajectories Ti and of according to policies Ho, and Toz, rospectively. Afterwards, we update the momentum weight a and the learning rate N7 (line 8) and then compute the estimate of gradient time t, i.e., Ut, using the Hessian vector product BiT;; (0. 6t-1) (please refer to Section 2.1 for the definition of B(r;0)) and stochastic gradient g(T;: 0.) (linc 9). Finally update 9₂ based
normalized version of in line 10.
Note that in each iteration, we compute one Hessian vector product, which can be done with the same computational complexity of obtaining the gradient vector using Pearlmutter's algorithm (Pearlmutter 1994). Therefore, the computational cost of SHARP per itcration is in the same order as the one for first-order methods such as REINFORCE (Williams 1992).
Remark 1 By choosing point uniformly at random on the line between 0,-1 and O,, we can ensure that B(T;;0)) (0-1)) is an unbiased estimate of (0)) -1046--JJJ0 (0(0z))) (see equation 22 in Appendix A). As we mentioned before, in the contert of stochastic optimization, Tran & Cutkosky (2022) used the second-order term (2I(0,,
which is biased as the Hessian vector product evaluated at the point 0,. As result, in order provide the convergence guarantee, it is further assumed that the objective function is second-order smooth in [Tran& & Cutkosky, 2022).
Remark 2 To give on intuition why the second-order term is helpful in the update in line 9, consider the following error term:
U2 VJ(OO)
(11)
5

---

Published in Transactions on Machine Learning Research (04/2024)
We rewrite the above error term follows:
c (1- (1-aa)(vl-11 V.((.)) B(T; (0) 0c-1)) + + J.())).
(12)
Now, for moment, suppose that B[un-1] = F(V (with total expectation on both sides). Then, Biut-1 (O,) + BT 02) -
(13)
casily show by induction that according to above As uo is unbiased estimate of gradient at 0u, equation, Elvx] = [O.)] for any 2 0.
In the next part, we provide thcoretical guarantee on the convergence rate of SHARP algorithm.
3.1 Convergence Analysis
In this part, we analyze the convergence rate of Algorithm under bounded reward function and some regularity assumptions on the policy Tg.
Assumption 1 (Bounded reward) For Vs E S, Va E A, [R(s a)l < Ro where Ro > 0 is some constant.
Assumption 2 (Paramcterization regularity) There cxist constants G, L such that for any Rd and for any
(a) | log To [a]s)]] < G, (b) V log To (a|s)) S L.
Assumptions and convergence of policy gradient methods. Under these assumptions, the following upper bounds be derived on [[]]g(r;0) ( and B(r; J(0]
common in the RL literature (Papini al. 2018 Shen el. al. 2019 analyze the
Lemma 1 (Shen et al. (2019)) Under Assumptions and
Bllg((;;)) - V.](O)] S 2 B[] - v²J(0) 12| S
(14)
G where 03 [I-3]a and o
(1-7)²
Based on these bounds, we can provide the following guarantee on the convergence rate of SHARP algorithm. All proofs are provided the appendix.
Theorem 1 Suppose that the initial momentum weight ao E =2/33, 1] and initial learning rale roo > 0. Under
Assumptions 1 and Algorithm guarantees that:
T
8VC + 9C
60
E
VJ(()]l
<
(15)
T
T1/3
T2/3
1=1
where C' 330 (48803/88/// /ao + (6ag + 1/a0)03)) //2 2) and CJ Ro/ 7))
Corollary 1 The right hand side of equation 15 is dominated by the first term. If we set no in the order of /B then the namber of trajectories for achieving e-FOSP would be O (a1))aa) ) where we assume that the time horizon H. is set in the order of 1/(1 7)
Remark 3 Let rewrite equation
12 follows:
a1)--1 + +aU a.

---

Published in Transactions on Machine Learning Research (04/2024)
where U.- (g( v(())) and W, B(T (0) 02-1) (VJ((B)) (7J(0))-V(((--). As g( 0,) and B (0, - 02-1) are unbiased estimates of (0+)) and ((())) - -VJ(O-1)), respeclively, we have RR[U 0 and [[W;] = 0, which in turn implies that E1(Er-1, [[((-11, Wa]] 0. After some simple manipulations
(see Appendir A for more details), we have
B[]le]]]]] s (1 10--0-
20 [I U. + 2 w.ll
Now, according to Lemma any trajectory T [Shen et al.
we know that 3] - og. Moreover, it can be shown that [B(r; S aB for 2019). Therefore, ||Wall S 2 110 - 0r-1ll- Moreover, the normalized update of SHARP yields that 110 8 nf-1- Hence,
B||le| 11] - 20203 + 80 Boh-
As aa and ne have the same dependency on t, along the iterations of the SHARP algorithm, the following inequality holds for any
B|||,119] =| (1- +(
(16)
Therefore, the variance of the estimation ervor decays with rate ((1/t2/a) (see Appendir B for the proof). To the best of our knowledge, eristing variance reduction methods only guarantee the decoy of curvulative variance. This appealing property of SHARP is largely due to the use of unbiased Hessian-aided gradient estimator and normalized gradient descent. Moreover, as byproduct of these desirable properties, our convergence analysis turns out to be more simple, compared to existing work (Culkosky & Orabona 2019 Tran & Culkosky, 2022). This could be of independent interest for better theory of variance-reduced methods.
Remark 4 The SHARP algorithm is porameter-free in the sense that og and no are constants that do not depend on other parameters in the problem. Therefore, for any choice of 2/3 < au S 1 and tju > 0, we con guarantee convergence to e-FOSP with the sample complezity of ((E However, in practice, it is desirable to tune these constants to have smaller constants in the numerators of convergence rates in equation 15 For inslance, might be large in some RL sellings and we control the conslant in the first term on the right hand side of equation 15 by tuning njo- It is noteworthy that STORM+ is also parameter-free, but it requires adaptive learning rate and momentum weight that depend on stochastic gradients in previous iterations.
Remark 5 Regarding the dependency on e, in the contert of stochastic optimization, Arjevant et al. (2200) have shoun that under some mild assumplions on the objective function and stochastic gradient, the rale of O(1/e)) is optimal in order to obtain e- E-FOSP, and connot be improved with stochastic p-th order methods for p p22 2.
4 Related Work
In recent years, several variance-reduced methods have been proposed in order to accelerate the existing PG methods. Papini et al. (2018) and Xu et al. (2020) proposed SVRPG algorithm based on SVRG (Johnson & Zhang 2013), with sample complexity O(1/e*) and (11/20/3), respectively. This algorithm requires
importance sampling techniques as well the following additional assumption for guaranteeing convergence to e-FOSP:
Bounded variance of importance sampling weights: For any trajectory т, it is assumed that:
p(T) p(T
Var
SW,
v0, R
(17)
where W < 0o is constant.
The above assumption fairly strong as the importance sampling weight could grow exponentially with horizon length H (Zhang et al. 2021). In order to remove importance sampling weights, Shen et al. (2019)
7

---

Published in Transactions on Machine Learning Research (04/2024)
Method
SC
[B3]
check
Checkpoint
18
Further Assump.
SVRPG
Xu et al.
2020
0 2073
0 ((733)
0
Needed
Needed
Assump. in equation 17
HAPG
Shen et al.
2019)
((2)
0
Needed
Not needed
SRVR-PG
Xu et al.
2019
(
0 (
o
Needed
Needed
Assump. in equation 17
HSPGA
Pham et al.
2020
((1)
Not needed
Needed
Assump. in equation 17
MBPG
Huang et al.
2020
((
((1)
Not needed
Needed
Assump. equation 17
VRMPO
Yang et al.
2022
(
(
(
Needed
Not needed
VR-BGPO
(Hang et al.
2022)
(
((1)
Not Needed
Needed
Assump. in equation 17
PAGE-PG
(Gargiani et al.
2022.
(
O(1)
(
Needed
Needed
Assump. in equation 17
This paper
((+)
((1)
Not needed
Not needed
Table 1: Comparison of main variance-redueed policy gradient methods to achieve e-FOSP based on sample
complexity (SC), batch size ([B)), batch size at checkpoints ([Behook)). )), and the need for checkpoints, importance sampling (IS), and additional assumptions.
proposed the HAPG algorithm, which uses second-order information and achieves better sample complexity of O(1/e)). However, it still needs checkpoints and large batch sizes of |B| O(1/e), and |Beheok| = 0(1/²).
In Table ! we compare the main periaacce-redueed policy gradient methods achieving e-FOSP in terms of sample complexity and batch size In this table, after HAPG (Shen al. 2019), all the proposed variance reduction methods achieve a similar sample complexity. The orders of batch sizes are also the same in HAPG. Xu et al. (219)) proposed SRVR-PG, and used stochastic path-integunn inthhinteerated differential estimators for variance reduction. This algorithm uses important sampling weights and the required batch sizes are in the order of [B] = (11/VE) and |Bcheckl = O(1/c). Later, Pham et al. (2020) proposed HSPGA by adapting the SARAH est imator for reducing the variance of REINFORCE. HSPGA still needs importance sampling weights, but the batch size reduced to O(). Huang et al. (020 proposed three variants momentum based policy gradient (called MBPG), which are based on the STORM algorithm (Cutkosky & Orabona 2019). Thus, the required batch size is (1), similarly to STORM. However, it still needs use importance sampling weights. (Zhang et al. 2020 used similar update for the estimate of stochastic gradient the in SHARP for Frank- Wolfe type algorithms in the context of constrained optimization. Later, Zhang al. (2021) proposed TSIVR-PG with gradient truncation mechanism in order to resolve some issues pertaining to the use of importance sampling weights. In their convergence analysis, they are restricted to soft-max policy with some specific assumptions on the parameterization functions. More recently, two mothods using mirror-descent algorithm based on Bregman divergence, called VR-BGPO (Huang et al. 2022 and VR-MPO Yang al. 2022) have been proposed, achieving e-FOSP if the mirror map in Bregman divergence is the 12-norm. Very recently, based PAGE (Li et al., 2021), ) Gargiani al. (0022) proposed the PAGE-PG algorithm which takes batch of O(c-2) samples for updating the parameters with probability pt reuse the previous estimate gradient with a small adjustment, with probability pr. The proposed algorithm requires importance sampling weights and thus the additional assumption in equation 17 to guarantee convergence to e- c-FOSP with a sample complexity of (c)-3).
Please that the sample complexity also depends the other parameters such as horizon length H and discount factor 7. Here, we just. mention the dependency of sample complexity on e.
8

---

Published in Transactions on Machine Learning Research (04/2024)
There are few recent work on the global convergence of policy gradient methods. For instance, Liu et al. 2020 showed global convergence of policy gradient, natural policy gradient, and their variance reduced variants, in the case of positive definite Fisher information matrix of the policy. Chung et al. (2021) studied the impact of basclines on the learning dynamics of policy gradient methods and showed that using a bascline minimizing the variance can converge to a sub-oplimal policy. Recently, Diig et al. (2022) studied the soft-max and the Fisher non-degenerate policies, and showed that adding a momentum term improves the global optimality sample complexities of vanilla PG methods by ((e-1.5) and Ö(E-)), respectively.
The main methods discussed above are summarized in Table D For each method, we mention whether it needs checkpoints and/or importance sampling weights P All of them require Assumptions and In the last columm, additional assumptions besides these two are listed for each method.
Comparing the sample complexity of the SHARP algorithm with previous work, note that all the algorithms (including SHARP) under SVRPG in Table | achieve rates of O(1/c) or Ó(1/2).. Without any further assumption, SHARP is the only method that requires no checkpoints, no importance sampling weights, and has batch size of the order of O1)) As we will see in the next section, besides these algorithmic advantages, it has remarkable performance compared to the state of the art in various control tasks.
5 Experiments
In this section, we evaluate the performance of the proposed algorithm and compare it with previous work for control tasks in MuJoCo simulator [Tooorov et al. 2012) which is physical engine, suitable for simulating robotic tasks with good accuracy and speed in the RL setting. We implemented SHARP in the Garage library Igarage contributors 2019) as it allows for maintaining and integrating it in future versions of Garage library for casier dissemination. We utilized a Linux server with Intel Xeon CPU E5-2680 v3 (24 cores) operating at 2.50GHz with 377 GB DDR4 of memory, and Nvidia Titan X Pascal GPU. The implementation of SHARP is available supplementary material.
We considered the following four control tasks with contimouu action space: Reacher, Walker, Humanoid, and Swimmer. In Reacher, an arm with two degrees of freedom aims at reaching a target point in a two-dimensional plane. A higher reward is attained if the arm gets closer to the target point. In Walker, a humanoid walker tries to move forward in a two dimensional space, ie., it can only fall forward or backward. The state contains velocitics of different parts of body and joint angles and the actions represent how move legs and foot joints. The reward signal is based on the current velocily of the agent. In Humanoid, a three-dinensional bipedal robot is trained to walk forward as fast as possible, without falling over. The state space is 376-dimensional, containing the position and velocity of each joint, the friction of the actuator, and contact forces. The action space is a 17-dimensional continuous space. Finally, in Swimmer, the agent is in two-dimensional pool and the goal is to move as fast as possible in the right direction.
We compared the SHARP algorithu with PG methods that provide theoretical guarantees for converging to an approximate FOSP; PAGE-PG (Gargiani et al.J 2022). IS-MBPG (Huang et al. 2020) which is based STORM, HAPG (Shen et al.) 2019) which does not require TS weights, and VR- BGPO (Huang et al.
2022) which is mirror descent based algorithm. We also considered REINFORCE (utton et al. 2000) as baseline algorithm. There are some other approaches in the literature with theoretical guarantees such as VRMPO (Yang et al., (0222,, and STORM-PG (Yuan et al. 2020) but the official implementations are not publicly available and our request to access the code from the authors remained unanswerod.
For each algorithm, we used the same set of Gaussian policies parameterized with neural networks having two layers of 64 neurons each. Baselines and environment settings (such as maximum trajectory horizon, and reward intervals) were considered the same for all algorithms. We chose a maximum horizon of 500 for Walker, Swimmer, and Humanoid and 50 for Reacher. More details about experiments are provided in A Appendix E
2To he more precise, although PAGE-PG, has no fixed checkpoints, it takes a batch of ((e-2) to get an unbiased estimate of the gradient with prohability Pe- Therefore, in this sense, requires checkpoints.
9

---

Published in Transactions on Machine Learning Research (04/2024)
800
700
600
500
Average
Average
800
-00
SHARP
300
REINFORCE
200
-40
I5-MBPG
PAGE-PG
100
VR-BGPO
0
System probes (a) Reacher
System probes
(b) Walker
175
300
Aveeaage fetum
Avrerage Return
125
300
79
100
System
probes
(c) Humanoid
(d) Swimmer
Figure 1: Comparison of SHARP with other variance reduction methods on four control tasks.
In the literature, has been observed that most PG methods are quite sensitive parameter initialization or random seeds (Henderson al. 2018). Hence, it might be challenging in some cases reproduce previous rosults. Moreover, it is not clear how to compare methods in terms of performance (c.g., the average episode return) and robustness (such as the standard deviation (STD) of return) al the same time.
To resolve the above issues, we considered the performance-rouusteess (PR) metric proposed in (Khorasani ct al. 2023), capturing both the average return and STD of return of an algorithm. In particular, for any algorit A, afler observing state-actions pairs (which we call system probes), the lower bound of the confidence interval 90 percent of average return over n runs of the algorithm (denoted by (CI,(n, t)) is computed The PR metric is defined by averaging LCIA(R, over all system probes f -,..... as follows:
1 PRA(n)= T
(.C.(,,
(18)
where 7' is maximum number of system probes.
We used grid search to tune the typer-parameee SHARP), the search space for each lyper-parameter was chosen based on the one from the original papers. For each configuration of the byper-parameters, we ran each algorithm A, five times and computed (R) We selected the configuration which maximized PR (5) and then reported (1,(10) of each algorithm for the selected configuration based on 10 different runs in Table 2 SHARP achieved the highest PR in all environments compared with the other algorithms. In Appendix D we also reported the PR metric by considering the upper bounds of confidence intervals instead of lower bounds (i.e., the "best-case" performance
all the considered algorithms. For the algorithms (except
3 As recommended (Agaraal al. 2021), for 10 available runs, we used percentile bootstrap compute 90% confidence interval with 2000 number hootstrap samples.
10

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Comparison of SHARP with other variance-reduced methods in terms of PR. In each environment, the highest PR is in bold.
Reacher
Walker
Humanoid
Swimmer
HAPG
-25.30
94.95
137.59
68.22
IS-MBPG
-22.45
175.58
164.55
26.75
PAGE-PG
-18.67
243.63
335.24
17.65
REINFORCE
-30.31
51.03
140.06
17.84
VR-BGPO
-16.15
313.42
393.90
37.92
SHARP (our algorithm)
-10.97
323.63
415.92
141.42
rather than the "worst-case" performance). Still, SHARP outperforms other algorithms in all environments. This is also evident from Figure where the confidence interval of SHARP fairly tight.
We considered the confidence interval of the performance (average return) to show the sensitivity of an algorithm to random sceds. As can be seen in Figure ! SHARP not only achieves the highest average return after 10 million system probes but also has a relatively small confidence interval.
6 Conclusion
We proposed a variance-reduced policy-gradient method, which incorporates second-order information, i.e., Hessian vector product, into SGD with momentum. The Hessian vector product can be computed with an efficiency that is similar to that of obtaining the gradient vector. Therefore, the computational complexity per iteration of the proposed algorithm, SHARP, remains in the same order as first-order methods. More importantly, using the second-order correction term enables us obtain an estimate of the gradient and completely bypass importance sampling. Morcover, the batch size is O(1) and there is no need for checkpoints, which makes the algorithm appealing in practice. Under some regularity assumptions on the parameterized policy, we showed that it achieves e-FOSP with sample complexity of O(e-). SHARP is parameter- free in the sense that the initial learning rate and momentum weight do not depend on the paramcters of the problem. Experimental results show its remarkable performance various control tasks, especially some complex environments, such as Humanoid, compared to the state of the art.
Acknowledgments
This research was in part supported by the Swiss National Science Foundation under NCCR Automation, grant agreement 51NF40 -50540 and Swiss SNF project 0000212003355//1
11

---

Published in Transactions on Machine Learning Research (04/2024)
References
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Marc Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In Advances in Neural Information Processing Systems, volume 34, pp. 29304 29320, 2021.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridharan. Second- order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pp. 242-299. PMLR, 2020.
Jonathan Baxter and Peter L Bartlett. stfnite-horizon policy- golicy-gradient estimation. Journal of Artificial Intelligence Research, 15:319-350 1500, 2001.
Wesley Chung, Valentin Thomas, Marlos C Machado, and Nicolas Le Roux. Beyond variance reduction: Understanding the true impact of baselines policy optimization. In International Conference on Machine Learning, pp. 1999 2009. PMLR, 2021.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, volume 32, 2019.
Mare Peter Deisenroth, Gerhard Neumann, Jan Peters, et al. A survey on policy search for robotics. Foundations and Trends in Robotics, 2(1-2):388 403,, 2013.
Yuhao Ding, Junzi Zhang, and Javad Lavaci. On the global optimum convergence of momentum-based policy gradient. In International Conference on Artificial Intelligence and Statistics, pp. 1910-1934 PMLR, 2022.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Adnances in Newral Information Processing Systems, volume 31, 2018
The garage contributors. Garage: A toolkit for reproducible reinforcement learning rescarch. https 2019.
Matilde Gargiani, Andrea Zanelli, Andrea Martinelli, Tyler Summers, and John Lygeros. Page-pg: A simple and loopless variance-rectuced policy gradient method with probabilistic gradient estimation. In International Conference on Machine Learning, 2022.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. M Journal on Oplimization, 23(4):2341 -2668, 2013.
Peter Henderson, Riashat Islam, Philip Bachman, Joelle Pineau, Doina Precup, and David Meger. Deep reinforcement learning that matters. In Proceedings of the AAAT Conference Artificial Intelligence, volume 32, 2018.
Foihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-bbssed policy gradient methods. In International Conference on Machine Learning, pp. 4422 4433. PMLR, 2020.
Feihu Huang, Shangqian Gao, and Heng Huang. Bregman gradient policy optimization. In International Conference on Learning Representations, 2022.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, pp. 315-323, 2013.
Sadegh Khorasani, Saber Salchkaleybar, Negar Kiyavash, Niao Hc, and Matthias Grossglauser. Efficiently escaping saddle points for non-convex policy optimization. arXiv preprint arXiv:2311.08914 2023.
Vijay R Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, pp. 1008 1014, 2000.
Kfir Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive sgd with momentum for nonconvex optimization. Tn Advances in Neural Information Processing Systems, 2021.
12

---

Published in Transactions on Machine Learning Research (04/2024)
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pp- 6286 6295. PMLR, 2021.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (varianco-roduced) policy gradient and natural policy gradient methods. In Advunces in Nearul Information Processing Systems, 2020.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference Machine Learning, pp. 2613 2621. PMLR, 2017.
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reducced policy gradient. In International Conference on Machine Learning, pp- pp. 4026-4035. PMLR, 2018.
Barak Pearlmutter. Fast exact multiplication by the hessian. Newral Computation, 6(1):147-600, 1994.
Nhan Pham, Lam Nguyen, Dzung Phan, Phuong Ha Nguyen, Marten Dijk, and Quoe Tran-Dinh. A hybrid stochastic policy gradient algorithm for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 374-385. PMLR, 2020.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897. PMLR, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. In Internation Conference on Representation Learning, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. Xiv preprinl or Xrxx:1777.0033 2017.
Shai Shalev-Shwarlz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. Xrxiv preprint 1510.6610.033 2016.
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 Conference on Artificial Intelligence, volume 34, pp. 5668 4668-5675, 5675, 2020.
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International Conference on Machine Learning, pp. 5738. PMLR, 2019.
David Silver, Julian Schrittwieser, Karen Simonyan, loannis 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(767)):354- 359, 2017.
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement lcarning with function approximation. In Advances in Neural Information Processing Systems, pp. 1057-1063, 2000.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 LEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-32 5033. IEEE, 2012.
Hoang Tran and Ashok Cutkosky. Better sgd using second-order momentum. In Advances in Newral Information Processing Systems, volume 35, pp. 3530 3541, 2022.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. Tn Advances in Neural Information Processing Systems, pp. 2406 2406-2416, 2416, 2019.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229 2222, 1992.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. In International Conference Learning Representations, 2019.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance-reduced
policy gradient. In Uncertainty in Artificial Intelligence, pp. 541 551. PMLR, 2020.
Long Yang, Yu Zhang, Gang Zheng, Qian Zheng, Pengfei Li, Jianhang Huang, and Gang Pan. Policy optimization with stochastic mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 8823 8831, 2022.
Huizhuo Yuan, Xiangru Lian, Ji Liu, and Yuren Zhou. Stochastic recursive momentum for policy gradient methods. Xiv preprint ar Xiv: 04302, 2020.
Junyu Zhang, Chengshuo Ni, Csaba Szepesvari, Mengdi Wang, al. the convergence and sample efficiency of variance-reduced policy gradient method. In Advances in Neural Information Processing Systems, volume 34, pp. 2228-2240, 2021.
Liang Zhang. Variance reduction for non-conver stochastic optimization: General analysis and new applications. Master's thesis, ETH Zurich, 2021.
Mingrui Zhang, Zebang Shen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One sample stochastic folle-wolle. In International Conference on Artificial Intelligncce and Statislics, pp. 4012 4023. PMLR, 2020.
14

---

Published in Transactions on Machine Learning Research (04/2024)
A Proof of Theorem
Let us define G, = 2t (.().). Then, based the update in line 9 of Algorithm 2
have:
4= - (1 + as Up + (1 - -,
(19)
where U2 (g(T1; 0.) ((.))) and W; B( 07) 0 -VJ(())-VV-----)) Let H4 be the history
up to lime 4, i.e., He (On, To. 7I, bi,
TI, 6
Tr, b,, -²'
By taking the square l2 norm of both sides of the above equation,
||el|1 (1
20 (0) + 20. (U) WT) 2(1 (4-1-,,
(20)
$ (1 - ( 2 |
20 ax) (a) Wz),
where we used Young's incquality in the first incquality for the following term: 20 (v) (O(U,,W)) Wi) S (1 ax.) + Now, by laking expectations both sides,
- Bi|l S (1 11 -
20 a: (c,,, - - Wi)
(a)
(21)
20 - a: [B[ 2(1 ( Wo)]
(1 -1- az ) 20 2 W.1l
(a) follows for all 12 0.
(b) follows because the following two terms are zero. First, [E( Ut} = EEB(((-,, 0 as 6t-1 is determined given H4-1 and E = since g(T;; 0,) an unbiased estimation of v.((B,). Second,
(ct-1 W.)] (e
W. W,
= because
E[W,HH4-]] =
- VJ((O-1))
Es, -10 - vJ((0-1))
(c) Es, (²)(0)) - -.000---00)))-------000000 -V/0))
(22)
J(b(( + (1 b)0:- 0.-1) (VJ(0.) VJ(()-1)) 0,
(c) is due to the fact that for a given 8% B(T 0?) an unbiased cstimation of V²J(B,).
() The integral follows since f = b,0, + (1 - 6.)8.-1 with b, uniformly distributed in [0, 1]. and its value is V((())) (0......
Now, from equation 21 we have:
El 11 (0)
2
[B[]]e Bl]le [|]e 11' + - W;ll + 20102
at
(23)
[B[lle - - -(]lee + 80 vi- 20
(a) We the bound in Lemma
i.e., B||[U,|19] < oz.
15

---

Published in Transactions on Machine Learning Research (04/2024)
(b) It has been shown that [[]( S dg for any trajectory and 0 E R (Shen et al 2019). Therefore,
|[)]] [B(;))() cB. Hence, ()))) is Lipschitz with constant and we have:
[Wlll < [B(rT; (0) 0t-1)1 [V)() - VJ(O,-1)
< |B( 00)1 - 01- + 0B 01-1ll
(24)
B 0 11-1
where the first inequality is due to the Lipschitzness of (J))), and the second inequality results from the bound on [[B(T(:0p) 01]1-
Summing the both sides of equation 23 from t 1 to T, have:
E
c
1
E
B
Bllle.11
+80
11-1
2
20
(25)
Q1
04-1
a₁
0g
(I)
(II)
(III)
First note that [|]|eol|/\/a S o//00. Now, we bound the other terms in the right hand side of the above inequality:
(I): For the coefficient in the sum, we have: 1/at+1 - 1/a, ((t + 1)2/3 - f2/3 S 21 21 1/3 /(30)) 2/-10/ 2/ (3ao) where we used the gradient inequality for the concave function f(z) 22/3, Therefore, this term can be bounded by: (2/(3oo)) DT= TT
(II: 1-1/0 n6/ / (1
1123// s no o0l1 22/3 1i s 61/T Joo-
(M)): Ei= 0r 00 Σ 1-23 <
T1/3
Plugging these bounds in equation
25 we get:
||
s
1/3
(26)
t=
where C 300 (4180) + +o2)/og + 6ogo2)/(300 - 2).
The previous inequality yields that:
T-1 <
T-1
T
vC
Bllle
E
??
<
BP
<
(27)
T
T
T
T1/3
where used Jensen's inequality in the second inequality above.
16

---

Published in Transactions on Machine Learning Research (04/2024)
Now, if we average from t= 0 T 1 in equation
32 in Lemma 2
and then take expectations, have:
T-1
30 2T
T-1
J(0++1) J(Oe)
E
K
B|llel||
+
+
T
T
T
8
G0 6%
3
T
(( J(O.)
+ E
T1/3
T2/3
T
1/t
t=
8VC
6
3
((OT)
](00)
1
E
J(0.)
T1/3
T2/3
T
1r--1
710
9/-1
m
SVC
B
C5(T
-1)2/3
CJ
-=- 7
(28)
E
J(0+)
71/3
T2/3
T
770
700
8VC
B%
3
Cy(( 1)2/33
CJ
+
E
Σ CJ
T1/3
T2/3
T
170
170
172
Te-1
(9)
8VC
G0
3
CJ(TT - 1)2/3
CJ
C5(T Cr(T -
]
+E
71/3
T2/3
1/0
1/0
1/0
SVC
9Cg
T1/3
T2/3
7//3//3
(a) We used the bound in equation
27 for the first term and ET-1 17: S 4no
(b) [J(]] [By=as [R(T)]] = [ET~T
Σ H-1 ~M an)ll S ET E 7 l (r(, an)l S | -7)]
Ro/(1 - -)) Hence, we have: [J(0) I C2 for all 0 E Ied where CJ == Ro/ (1 7).
(c) Due to ETS 1/n-- 1/n--1 1/ 1/mo (T- 1)2/3/1o
B Proof of Remark 3
According to equation 21 we have:
Bllke1191 s (1 -.) 80 + 20,00
(29)
Let us define Z. =- [[]]] Then, we can rewrite the above equation as follows:
Cz 6, (1- 44/3¹
(30)
where C2 = 8 x 2//3 + 20j03 Now, by induction, we will show that: Z, S C2/ where C" C2/(an 2/3). It can be casily seen that for the base case Z1, this statement holds. Now, for the induction step, suppose that Z₁-1 S C22((t - 1)2/3 for some 2 2. Then, from above equation, we have:
Cz (a) C0Oz - 20
14/3 v 12/3(1 - 1)2/3
CnC2
Cz
(1
1)(2/3
12/3(1
1)2/3
11/3
(6)
CrO
Cz
C
(t - 11223
/2/3
12/3 (t 1)2/3
44/
(31)
(1
a0
C²
Cz < C
12/3
(1 (1- 1-///3
11/3 12/3
(c)
(1 Zi-1 + Cz
C22
<
14/3
f2/3
(d)
C²
Z, <
22/3
17

---

Published in Transactions on Machine Learning Research (04/2024)
where (a) is due to definition of Cz: (b) is based on using gradient inequality for the concave function
((=) = =2//3, L... f2/3 (1 - 1)2/3 < 2/3(1 - 1)) (c) is according to induction hypothesis, and (d) is due to
equation 30
C
Supplemental Lemma
Lemma 2 Suppose that 0g 's are generated by executing Algorithm 2
Let G == - VJ((,). Then, at any
time t, we have:
|V(0,.)| & 8||eel1 + Bd (J(0 J(O,))
(32)
From -gssmoothness of J(,)) Shen et al. 2019 we have:
J(0,41) J(0.) (VJ(O.), 10:11-000 -0,)
OB
00+1 0.l12
2
(33)
= VJ(()):
1/2
σB
||wll|
Regarding the first term above, we consider two cases, whether [VJ(e,II 2 2//c.|| or not. For the former case, we have:
[VJ (VJ(()).
J(O.): Vp
[VJ((O,) + Gell
[())(
(().) + +ell
[0)](
(34)
2(IIV + (<.l)
[VJ().I)
3
M [VJ(O.I
8
|leall
3
3
where the first incquality, we used the bound (VJ(()), () 2 [[VJ(()]] -VV)(1))1 For the latter case,
(((O)), 2i [wlll
2
|[V
(35)
3
3
[[,)(
8lleell
3
3
Plugging the bound on (VJ(O.), v ///// equation
33
we get:
10 - > [O.0I)II
8|leel|
2
2 1/5
3
3
(36)
30
||VJ( < 811e=]|
- 7
2
Comparison Using Another Variant of PR Metric
In this section, we report another variant PR metric that takes into account the upper bounds of confidence intervals instead of the lower bounds. As can be seen in Table 3. SHARP still outperforms other algorithms in all environments considering the new variant of PR metric.
18

---

Published in Transactions on Machine Learning Research (04/2024)
Table 3: Comparison SHARP with other variance-reduced methods terms of PR metric (The upper bounds of confidence intervals are considered reporting PR metric).
Reacher
Walker
Humanoid
Swimmer
HAPG
-23.05
127.94
230.48
88.31
IS-MBPG
-20.78
296.85
309.51
30.32
PAGE-PG
-17.25
259.36
402.20
25.05
REINFORCE
-28.65
136.37
222.97
28.40
VR-BGPO
-15.92
346.41
406.22
39.77
SHARP (our algorithm)
-10.23
440.70
441.27
172.42
E Details of Experiments
We used the default implementation of linear feature baseline from Garage library. The employed linear feature baseline is linear regression model that takes observations for each trajectory and extracts new features such as diffcrent powers of their lengths from the observations. These extracted features are concatenated to the observations and used to fit the parameters of the regression with least square loss function. In the experiments, we used linear baseline for all the environments and methods.
In our reporting, each iteration i, we generated trajectories according to the current policy until we collected 10k system probes. Then, computed the average return based the collected trajectories and considered this value for 10k x system probes.
In the following table, we provide the fine-tuned parameters for each algorithm. Batch sizes are considered the same for all algorithms. The discount factor is also set to 0.99 for all the runs.
19

---

Published in Transactions on Machine Learning Research (04/2024)
Reacher
Walker
Humanoid
Swimmer
Max horizon
50
500
500
500
Neural network sizes
64 x 64
64 x 64
64 x 64
64 x 64
Activation functions
Tanh
Tanh
Tanh
Tanh
IS-MBPG ir
0.9
0.3
0.75
0.3
IS-MBPG
100
12
5
12
IS-MBPG
200
20
2
25
REINFORCE step-size
0.01
0.01
0.001
0.01
SHARP
1.5
5
5
4.5
SHARP Tlo
0.1
1
0.6
0.15
PAGE-PG pr
0.4
0.4
0.6
0.6
PAGE-PG step-size
0.01
0.001
0.0005
0.001
HAPG step-size
0.01
0.01
0.01
0.01
HAPG
10
10
10
VR-BGPO Ir
0.8
0.75
0.8
0.75
VR-BGPO
25
25
25
25
VR-BGPO w
1
1
1
VR-BGPO lam.
0.0005
0.0005
0.0025
0.0005
Table 4: Selected hyper-parane parametrs for different methods.
20

---

Published in Transactions on Machine Learning Research (04/2024)
In the following table, provide the sets of considered values for hyperparameter tuning for each algorithm.
Set
IS-MBPG Ir
(0.1, 0.2, 0.3, 0.4, 0.55, 0.65, 0.75, 0.85, 0.9}
IS-MBPG
{5, 12, 20, 25, 50, 80, 100}
IS-MBPG w
{2, 5, 10, 15, 25, 50, 100, 200}
REINFORCE step-size
{0.0005, 0.001, 0.01, 0.05, 0.1}
SHARP ag
(1, 1.5, 2, 3, 3.5, 4.5, 4, 5}
SHARP 7/
(0.1, 0.15, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}
PAGE-PG Pt
{0.2, 0.4, 0.5, 0.6, 0.7, 0.9)
PAGE-PG step-size
(0.0005, 0.001, 0.01, 0.05, 0.1}
HAPG step-size
{0.0005, 0.001, 0.01, 0.05, 0.13
HAPG Q
{5, 7, 10, 15, 20}
VR-BGPO ir
{0.6, 0.7, 0.75, 0.8, 0.85 0.9, 0.95}
VR-BGPO
{15, 25, 35, 45, 50}
VR-BGPO
(1, 3, 5, 10}
VR-BGPO lam
{0.0005, 0.001, 0.0015, 0.002, 0.0025)
Table 5: Sets of typer-parameters for different methods.
21


Reviews:
[{"review_id": "kEPo32A9Qn", "reviewer": "Reviewer_H6Lx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1) The proposed method is clearly explained. The authors also made a nice literature review that is helpful to read the advantages of the proposed method. \n\n(2) The proposed method introduces a middle-point policy to get an unbiased gradient difference. Due to such second-order information, there is no need of checking points for sampling batches. \n\n(3) The learning parameters do not reply on problem parameters, which makes the proposed method more practical. \n\nWeaknesses:\n\n(1) The sample complexity is sub-optimal.  \n\n(2) Some assumptions can be strong, such as Assumption 2, although it is often assumed in literature.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a new variance-reduced policy gradient method by use of the second-order information. This new method improves existing methods by removing the requirement of importance sampling and careful checkpoint. The authors prove sublinear rate to obtain an near-optimal stationary point. Experiments are also provided to show the effective performance of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, the result is nicely presented. Here are a few questions for consideration.  \n\n- In SHARP, is the choice paramters $(\\eta_t,\\alpha_t)$ in same order optimal? \n\n- What's the policy parametrization used in experiments? How do you check the assumption made on the policy?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BDbF00TBcH", "reviewer": "Reviewer_wm5y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I think this is a good paper. It makes a distinct and solid contribution to the literature on variance-reduced policy gradient methods. The theory appears to be good given the existing literature surrounding this topic, and it achieves competitive rates under very mild conditions. The experiments show convincingly that the method outperforms the baselines considered. I don't have an explicit weaknesses to bring forth, but I do have some questions/suggestions. Perhaps these can be incorporated to further strengthen the paper.\n\nQuestions:\n\n- Which the experiment baselines are 'parameter-free' and which ones aren't? How do you choose the hyperparameters for the ones that are not? It maybe helpful to highlight this in that section.\n- You compared to REINFORCE, but not more modern algorithms like PPO and TRPO. Why not? It seems like it would be informative to the reader to see the difference been PPO (a go-to PG method) and this, even though the theoretical guarantees may not be as strong.\n- What are the computational trade-offs between this algorithm and the others discussed in the related work and used as baselines? The proposed method includes a second-order calculation, which can be prohibitive for larger models.\n- I believe the page limit is 12, correct? I thought it might be helpful to include a sketch of the proof or at least highlight some of the core ideas that allow the analysis to through (beyond the algorithmic ones already discussed). What do you think?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of policy gradient optimization in reinforcement learning. The propose a new algorithm, with the primary purpose of delivering theoretical guarantees, that achieves a fast convergence rate to a stationary point. This is done with a variance reduction method that uses second order information and without further assumptions than what is typical. It is also done without importance-weighting, which is a common practical limitation. The algorithm is also shown to outperform peer methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KHYJVD3TVe", "reviewer": "Reviewer_BZdM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Main Argument\n\nRecommendation: weak reject\n\nI am concerned that there is not a sufficient empirical justification for the SHARP algorithm. A significant amount of details about the empirical study are missing -- details that are needed for a more thorough, complete evaluation. Below I will comment on my major concerns.\n\nFirst, the paper does not outline the hyperparameter ranges that were tuned over for any algorithm. This information is vital in order for a successful evaluation of the empirical study. Were approximately the same number of hyperparameter settings tuned over for all algorithms? If some algorithms had more hyperparameter settings tuned over, they likely had an advantage over the other algorithms, as there were more avenues by which performance could be improved for such algorithms. \n\nSecond, I am unsure of the performance robustness (PR) metric that is reported for performance. This PR metric is basically the average lower bound of a 90% confidence interval over average return for each timestep in an agent-environment interaction. Because this metric only considers a lower bound, it hides a significant amount information, especially information about whether confidence intervals are overlapping. Here is equation 18 from the paper:\n\n$$\nPR_{A}^{\\text{min}}(n) = \\frac{1}{T} \\sum_{t=1}^{T} LCI_{A}(n, t)\n$$\n\nWe can also consider another metric:\n\n$$\nPR_{A}^{\\text{max}}(n) = \\frac{1}{T} \\sum_{t=1}^{T} UCI_{A}(n, t)\n$$\n\nwith $UCI_{A}(n, t)$ the upper bound of a 90% confidence interval over average return for $n$ runs of algorithm $A$. Why was this mteric not also reported? It would help to better gauge algorithm performance, especially when comparing algorithms.\n\nIt could be the case that for two algorithms $A$ and $B$ that $PR_{A}^\\text{min}(n) > PR_{B}^\\text{min}(n)$ but that $PR_{A}^\\text{max}(n) < PR_{B}^\\text{max}(n)$. In such a case, algorithm $B$ has a lower estimate of \"worst-case\" performance but a higher estimate of \"best-case\" performance, meaning that algorithm $B$ could really outperform $A$ on the problem. We don't have sufficient information to determine this. The $PR_A^\\text{min}$ metric hides this information (and more). Further, I am unsure that comparing lower bounds of confidence intervals can sufficiently show that one algorithm is necessarily better than another. Why not provide the average lower and upper bounds for this confidence interval, as I have outlined above?\n\nFurthermore, considering table 2, the $PR_{SHARP}^\\text{min}$ value is not much higher than that of many of the other algorithms (especially on Humanoid and Walker), which seems to indicate that the confidence intervals which were used to generate these numbers do indeed overlap.\n\nTo compute the $PR_A^\\text{min}$ metric, a confidence interval over average return is constructed over $n$ runs of the algorithm for each system probe. A system probe is simply a (state, action) pair. How was the average return computed for this (state, action) pair, since only a reward is available at this time? Is the episodic return used for the episode corresponding to the system probe under consideration?\n\nThird, even if I was confident about the aforementioned metric, the paper is not clear about how confidence intervals are constructed. The paper mentions that 90% confidence intervals are used to compute the values in table 2, but there is no indication about what kind of confidence interval is used. I assume that t-distributed confidence intervals were used since this is what is common (please correct me if I am wrong). In this case, I am not confident that the distributional assumptions of the confidence interval are satisfied, and the reported confidence intervals may therefore be overly optimistic. Likely, 10 runs is not enough to satisfy the normality assumptions of such confidence intervals. This would also exacerbate the issue with table 2 that I mentioned above. Would it be possible to attain a significant number of more experimental runs (e.g. >=20 total)? Further, a likely better estimate of confidence could be obtained with confidence intervals which make no distributional assumptions about the data [1]. Does Figure 1 also use the same confidence intervals as reported in table 2? \n\nNext, why were the default values not used for the maximum episode horizon for Walker, Swimmer, and Humanoid? The default values for each of these environments are significantly higher than what was used in the empirical study (default is 1000 timesteps). This design choice makes the results reported in the paper hard to compare with existing results in the literature which tend to use the default episode cutoffs. Further, reducing episode cutoffs can make these problems easier.\n\nFinally, a number of things are not clear in the paper. First, $B(\\tau_t^b, \\theta_t^b)$ is used before it is clearly defined. Second, in _Remark 1_, why is it important to have an unbiased estimate of $\\nabla J(\\theta_t) - \\nabla J(\\theta_{t-1})$? Where does this difference in gradients come from? Is it related to equation 10? I am assuming this difference in gradients is from some theoretical result in Tran & Cutkosky's (2022) paper [2], but it is not clear why an unbiased estimate of this value is important. Equation 8 in Algorithm 1 is not clear. Are both gradient terms included in the sum?\n\n# Small Things\n\nHere are a list of small things which **did not affect the scoring of the paper** but can help to make the paper stronger:\n- There are multiple grammatical errors in the paper. For example:\n     - \"In RL context\" -> \"In the RL context\"\n     - \"In RL setting\" -> \"In the RL setting\"\n     - \"In (Zhang et al., 2020)\" - > \"Zhang et al. (2020) state that...\"\n     - \"distribution of starting state\" -> \"distribution of starting states\"\n     - \"IS-MBPG... which is based on STROM\" -> I think this should be \"STORM\".\n     - \"metric proposed in (Khorasani et al., 2023)\" -> \"Khorasani et al. (2023) propose the metric...\" \n- In many different places, vague terms are used. For example, at the beginning of the second paragraph in the introduction, it is stated that \"Policy gradient methods are often used for obtaining good policies\". What is a \"good policy\"? \n- I found the first paragraph of the introduction hard to follow. There were multiple undefined terms in this paragraph as well (or terms were used before they were defined). For example, what are the \"best actions\"? \n- I believe this is a typo, but in the last sentence of the paper it is claimed that SHARP attains remarkable performance on HalfCheetah. Yet, these results were never shown.\n\n# References \n\n[Cédric Colas, Olivier Sigaud, Pierre-Yves Oudeyer. How Many Random Seeds? Statistical Power Analysis in Deep Reinforcement Learning Experiments. 2018.](https://arxiv.org/abs/1806.08295)\n\n[Hoang Tran, Ashok Cutkosky. Better SGD using Second-order Momentum. 2022.](https://arxiv.org/abs/2103.03265)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "# Summary\n\nThis paper presents a new algorithm called _Stochastic Hessian Aided Recursive Policy gradient_ (SHARP). The SHARP algorithm incorporates second-order, Hessian information into stochastic gradient descent (SGD) with momentum in order to reduce the variance of the policy gradient estimator. SHARP is able to reach first order stationary points (FOSP) without importance sampling and with relatively low sample complexity.  Unlike some other popular variance reduction methods for policy gradient algorithms, SHARP does not require large batch sizes or gradient checkpointing.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Requested Changes\n\nIn order to secure my recommendation for acceptance, all the issues I listed in my _Main Argument_ would have to be addressed. This includes (but is not limited to):\n1. Using confidence intervals for which all assumptions are satisfied.\n2. The confidence intervals in (1) should not overlap and be high confidence estimates (>= 90% confidence) with many random seeds.\n3. Reporting full confidence intervals, rather than only the average lower bound, while maintaining similar conclusions\n\nTo make the paper better, the issues in the _Small Things_ section above could be addressed. This is not critical for securing my recommendation for acceptance.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the proposed algorithm SHARP is both theoretically sound and appears to perform well in experiments on some MuJoCo tasks. The reviewers are generally positive about the contributions of the paper. Therefore, I recommend acceptance.

I encourage the authors to further revise the paper based on the reviewers' suggestions in the camera ready version. For example, the authors may consider having more runs for computing the bootstrap confidence intervals, as raised by Reviewer BZdM.
Decision: Accept (poster)