Bregman Gradient Policy Optimization
Authors: Feihu Huang
Shangqian Gao
Heng Huang
Venue: ICLR 2022 Poster (2022)

Abstract: In the paper, we design a novel Bregman gradient policy optimization framework for reinforcement learning based on Bregman divergences and momentum techniques. Specifically, we propose a Bregman gradient policy optimization (BGPO) algorithm based on the basic momentum technique and mirror descent iteration. Meanwhile, we further propose an accelerated Bregman gradient policy optimization (VR-BGPO) algorithm based on the variance reduced technique. Moreover, we provide a convergence analysis framework for our Bregman gradient policy optimization under the nonconvex setting. We prove that our BGPO achieves a  sample complexity of $O(\epsilon^{-4})$ for finding $\epsilon$-stationary policy only requiring one trajectory at each iteration, and our VR-BGPO reaches the best known sample complexity of $O(\epsilon^{-3})$, which also only requires one trajectory at each iteration. In particular, by using different Bregman divergences, our BGPO framework unifies many existing policy optimization algorithms such as the existing (variance reduced) policy gradient algorithms such as natural policy gradient algorithm. Extensive experimental results on multiple reinforcement learning tasks demonstrate the efficiency of our new algorithms. 

Published as a conference paper at ICLR 2022
BREGMAN GRADIENT POLICY OPTIMIZATION
Feihu Huang"; Shangqian Gao", Heng Huang! Department of Electrical and Computer Engineering
University of Pittsburgh
Pittsburgh, PA 15261, USA huangfeihu20188ee 2mae com, shg84@pitt.edu, heng hwwng@pitt edu
ABSTRACT
In the paper, we design novel Bregman gradient policy optimization framework for reinforcement learning based on Bregman divergences and momentum tech- niques. Specifically, we propose a Bregman gradient policy optimization (BGPO) algorithm based the basic momentum technique and mirror descent iteration. Meanwhile, we further propose an accelerated Bregman gradient policy optimiza- tion (VR-BGPO) algorithm based the variance reduced technique. Moreover, we provide a convergence analysis framework for our Bregman gradient policy optimization under the nonconvex setting. We prove that BGPO achieves sample complexity of O(e*)) for finding e-stationary policy only requiring one trajectory each iteration, and our VR-BGPO reaches the best known sample complexity of (e)-)), which also only requires one trajectory at each iteration. In particular, by using different Bregman divergences, our BGPO framework uni- fies many existing policy optimization algorithms such as the existing (variance reduced) policy gradient algorithms such as natural policy gradient algorithm. Ex- tensive experimental results on multiple reinforcement learning tasks demonstrate the efficiency our new algorithms.
INTRODUCTION
Policy Gradient (PG) methods are class of popular policy optimization methods for Reinforce- ment Learning (RL., and have achieved significant successes in many challenging applications (Li) 2017) such robot manipulation (Deisenroth et al. 2013). the Go game (Silver et al.) (0117) and autonomous driving (Shalev-Shwartz et al.) 2016). In general, PG methods directly search for the optimal policy by maximizing the expected total reward of Markov Decision Processes (MDPs) in- volved in RL, where an agent takes action dictated by policy in an unknown dynamic environment over a sequence of time steps. Since the PGs are generally estimated by Monte-Carbe sampling, such vanilla PG methods usually suffer from very high variances resulted in slow convergence rate and destabilization. Thus, recently many fast PG methods have been proposed reduce variances in vanilla stochastic PGs. For example, Sutton et al. (000) introduced a bascline to reduce vari- ances of the stochastic PG. Konda & Tsitsiklis (2000) proposed an efficient actor-critic algorithm by estimating the value function to reduce effects of large variances. (Schulman et al.) 2016) pro- posed the generalized advantage estimation (GAE) to control both the bias and variance in policy gradient. More recently, some faster variance-reduced PG methods (Papini et al., (0188) Xuu et al.) 2019a Shen et al.) 2019 Liu et al., 2020; Huang et al., (020) have been developed based on the variance-reduucioon techniques in stochastic optimization.
Alternatively, some successful PG algorithms (Schulman et al. 2015; 2017) improve convergence rate and robustness of vanilla PG methods by using some penalties such Kullback-Leibler (KL) divergence penalty. For example, trust-region policy optimization (TRPO) (Schulman et al. 2015) ensures that the new selected policy is near to the old one by using KL-divergence constraint, while
proximal policy optimization (PPO) (Schulman et al.] 2017) clips the weighted likelihood ratio implicitly reach this goal. Subsequently, Shani al. 2020) have analyzed the global conver- gence properties of TRPO in tabular RL based on the convex mirror descent algorithm.
Liu et al.
"Feihu and Shanggian contributed equally.
1 "Correspnndigg Authors.

---

Published as a conference paper at ICLR 2022
Table 1: Sample complexities of the representative PG algorithms based on mirror descent algo- rithm for finding an c-stationary policy of the nonconcave performance function. Although [Lu eet al. (2019); (Shani et al.] (2020) have provided the global convergence of TRPO and PPO under some specific policies based on convex mirror descent, they still obtaín a stationary point of noncon- cave performance function. Note that our convergence analysis does not rely any specific policies.
Algorithm
Reference
Complexity
Batch Size
TRPO
Shani et al.
(2020)
OlE
O
Regularized TRPO
Shani et al.
(0020)
Ole
O
TRPO/PPO
Liu al. (2019)
Ole
Olc
VRMPO
Yang et al.
(2019)
O(c-2)
MDPO
Tomar et al. (2020)
Unknown
Unknown
BGPO
Ours
O
O(1)
VR-BGPO
Ours
O(e
0(1)
2019) have also studied the global convergence properties of PPO and TRPO equipped with over- parametrized neural networks based on mirror descent iterations. At the same time, Yang et al.) 2019) tried to propose the PG methods based on the mirror descent algorithm. More recently, mir- for descent policy optimization (MDPO) (Tomar et al. (020) iteratively updates the policy beyond the tabular RL by approximately solving trust region problem based on convex mirror descent algorithm. In addition, addition.,Agarval et al. (2019); Cen et al. (2020) have studied the natural PG methods for regularized RI.. However, Agarwal et al. (2019) mainly focuses on tabular policy and log-linear, neural policy classes. Cen et al. (2020) mainly focuses on softmax policy class.
Although these specific PG methods based on mirror descent iteration have been recently studied, which are scattered in empirical and theoretical aspects respectively, it lacks universal framework for these PG methods without relying on some specific RL tasks. In particular, there still does not exist the convergence analysis of PG methods based on the mirror descent algorithm under the nonconvex setting. Since mirror descent iteration adjusts gradient updates to fit problem geometry, and is useful in regularized RL (Geist et al. 2019), there exists important problem to be addressed:
Could we design a universal policy optimization framework based on the mirror descent algorithm, and provide its convergence guarantee under the non-convex setting! ?
In the paper, we firmly answer the above challenging question with positive solutions and propose an efficient Bregman gradient policy optimization framework based on Bregman divergences and mo- mentum techniques. In particular, provide convergence analysis framework of the PG methods based on mirror descent iteration under the nonconvex setting. In summary, our main contributions are provided as follows:
a) We propose an effective Bregman gradient policy optimization (BGPO) algorithm based on the basic momentum technique, which achieves the sample complexity of O(c-)) for finding c-stationary policy only requiring one trajectory each iteration.
b) We propose an accelerated Bregman gradient policy optimization (VR-BGPO) algorithm based on the veriance-reduced technique of STORM (Cutkosky & Orabona 2019). More- over, we prove that the VR-BGPO reaches the best known sample complexity of (c="))
c) We design a unified policy optimization framework based on mirror descent iteration and momentum techniques, and provide its convergence analysis under nonconvex setting.
In Table [ showss that sample complexities of the representative PG algorithms based on mirror descent algorithm. (Shani et al. (2020); Liu et al. (2019) have established global convergence of a mirror descent variant of PG under some pre-specified setting such as over-parameterizeed networks eLiu al. 2019) by exploiting these specific problems' hidden convex nature. Without these special structures, global convergence of these methods cannot be achieved. However, our framework does not rely on any specific policy classes, and our convergence analysis only builds on the general nonconvex setting. Thus, we only prove that our methods convergence to stationary points.
Geist et al. (2019;; Jin & Sidford (020):: Lan (202T); Zhan et al. (2021) studied a general theory of regularized MDPs based on policy space such as a discrete probability space that generally is discontinuous. Since both the state and action spaces S and A generally are very large in practice, the policy space is large. While our methods build on policy" parameter space that is generally continuous Euclidean space and relatively small. Clearly,
methods and theoretical results are more practical than the results in (Geist et al.) 22099] Jin & Sidford 2020 Lan 2021 Zhan et al. 2021). (Tomar al. 2020) also proposes mirror descent PG framework based on policy parameter
2

---

Published as a conference paper at ICLR 2022
space, but it does not provide any theoretical results and only focuses on Bregman divergence taking form of KL divergence. While our framework can collaborate with any Bregman divergence forms.
RELATED WORKS
In this section, we review some related works about mirror descent-based algorithms in RL and variance-reduced PG methods, respectively.
2.1
MIRROR DESCENT ALGORITHM IN RL
Due to easily deal with the regularization terms, mirror descent (a.k.a., Bregman gradient) algorithm (Censor & Zenios 1992 Beck & Teboulle, 2003) has shown significant successes in regularized RL, which is first proposed in (Censor & Zenios 1992) based on Bregman distance (divergence) (Breg- man 1967 Censor & Lent 1981). For example, Neu al. (2017) have shown both the dynamic policy programming (Azar et al. 2012) and TRPO (Schulman et al., 2015) algorithms are approx- imate variants of mirror descent algorithm. Subsequently, Geest al. (2019) have introduced general theory of regularized MDPs based on the convex mirror descent algorithm. More recently, Liu et al. 2019) have studied the global convergence properties of PPO and TRPO equipped with overparametrized neural networks based on mirror descent iterations. At the same time, Shani et al.) (2020) have analyzed the global convergence properties of TRPO in tabular policy based on the convex mirror descent algorithm. [Wang et al. (2019) have proposed divergence augmented policy optimization for off- off-policy learning based on mirror descent algorithm. MDPO (Tomar et al. 2020) iteratively updates the policy beyond the tabular RL by approximately solving trust region problem based on convex mirror descent algorithm.
2.2
REDUCED) PG METHODS
PG methods have been widely studied due to their stability and incremental nature in policy op- timization. For example, the global convergence properties of vanilla policy gradient method in infinite-horizon MDPs have been recently studied in (Zhang et al. (019)).
Diriqquently,Zaaanee et al. 2020 have studied asymptotically global convergence properties of the REINFORCE (Williams) 1992]. whose policy gradient is approximated by using single trajectory or a fixed size mini-batch of trajectories under soft-max parametrization and log-barrier regularization. To accelerate these vanilla PG methods, some faster variance-reduced PG methods have been proposed based on the variance-reduction techniques of SVRG (Johnson & Zhang 2013), SPIDER (Fang et al., 2018) and STORM (Cutkosky & Orabona 2019) in stochastic optimization. For example, fast S SVRPG (Papini 2018; Xu et 201 algorithm have been proposed based on SVRG. Fast HAPG (Shen 2019) and SRVR-PG (Xu et al., 2019a) algorithms have been presented by using SPIDER technique. Subsequently, the momentum-
ct al.
al.
PG methods, i.e., ProxHSPGA (Pham et al. 2020) and IS-MBPG (Huang et al. (2020), have been developed based variance-reduced technique of STORM/Hybrid-SGD (Cutkosky & Orabonal 2019 Tran-Dinh et al., 2019). More recently, (Ding
al.
2021 studied the global convergence momentum based policy gradient methods. (Zhang
et al.
2021 proposed a truncated stochastic incremental variance- reduced policy gradient (TSIVR.
PG) method to relieve the uncheckable importance weight assumption in above variance-reduucd PG methods and provided the global convergence of the TSIVR-PG under overparameterizaiton of policy assumption.
3
PRELIMINARIES
In the section, we will review preliminaries of Markov decision process and policy gradients.
3.1 NOTATIONS
Let [n] 21,2, n) for all n E N4. For vector Rdd let ||æ||] denote the & norm of and ||0/|| (Et /m.p) 1/p (p 1) denotes the p-norm of x. For two sequences {ax} and {ba). we denote O(be) if ag < Cb. for some constant C' >>> 0. B[X) and V[X) denote the expectation and variance of random variable X, respectively.
3.2 MARKOV DECISION PROCESS
Reinforcement learning generally involves a discrete time discounted Markov Decision Process (MDP) defined by tuple (8,A, Prr,7, Po)) S and A denote the state and action spaces of the
3

---

Published as a conference paper at ICLR 2022
agent, respectively. P(s'|s,a) : A A(S) is the Markov kernel that determines the transition probability from the state to s' under taking an action a E A. r(s, a) S x A [-R, R (R > 0) the reward function of and a, and Po p(so) denotes the initial state distribution. Y (0, is the discount factor. Let π S + A(A) be a stationary policy, where ((A) is the set of probability distributions on A.
Given the current state 8, E S, the agent executes an action o, E A following a conditional proba- bility distribution π (er]s)), and then the agent obtains reward rt r(s,, ar). At each time we can define the state-action value function (5t 0r) and state value function V*(sr) as follows:
0
Q" (8,, (4) =E 1.
>rr,d,, V (st) Bas,s
Σ \n-]] 1=0
1=0
We also define the advantage function A (St, a+) Q" (+) V*(s)) to find the optimal policy by maximizing the expected discounted reward
(s²). The goal of the agent is
max == Eso~po (so)].
(2)
Given a time horizon H, the agent collects a trajectory T = {st, Ge
H-1 under any stationary policy.
Then the agent obtains cumulative discounted reward r(r) Σ and action spaces S and A are generally very large, directly solving the problem (2) is difficult.
--- y'r(s;, az). Since the state
Thus, let the policy be parametrized mo for the parameter θ S Rd. Given the initial
distribution = p(sp). the probability distribution over trajectory т can be obtained
p(r(0) = p(00)
II
PP 04) (e)
t=0
Thus, the problem will be equivalent to maximize the expected discounted trajectory reward: max J(0) := (x())] AE
(4)
In fact, the above objective function (0) has a truncation error of ( compared the original anfnite-hhoizon MDP.
3.3 POLICY GRADIENTS
The policy gradient methods (Williams 1992, Sutton et al. 2000 are class of effective policy- based methods to solve the above RL problem 4). Specifically, the gradient of (()) with respect to 0 is given as follows:
J(()) = By-p(r19) V log (p(T10))r(T))-
(5)
Given a mini-batch trajectories B { In sampled from the distribution p(r(0), the standard stochastic policy gradient ascent update (k + 1)-th step, defined as
0k+1 0g + 1) Jss(() (0x),
where 77 >> is learning rate, and Jı Og) = 1 >
(TT Ta (0k) is stochastic policy gradient. Given
H = ( as in (Zhang et al. gradient of ((0), Le.. E[g(T(0)
2019 Shani et al. 2020). 9 is the unbiased stochastic policy
0), where
h
H
g(T
a log (a st)
Σ rrr(s, (1)). t=
1=0
Based on the gradient estimator in 77. we can obtain the existing well-known policy gradient esti- mators such as REINFORCE (Williams 1992), policy gradient theorem (PGT (Sutton et al. 2000)). Specifically, the REINFORCE obtains a policy gradient estimator by adding baseline deñindd as
H
H-1
g
V log ( sc))
> az) 1 6t).
2=
The PGT is a version of the REINFORCE, defined as
H-1#
((T = -
(F'(()), b,) Vo log (o(a), st).
(=0 j=t
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 BGPO Algorithm
1: Input: Total iteration K, tuning parameters (X, b, m,c) c} and mirror mappings { {1/1: j= k-
u-strongly convex functions;
2: Initialize: 0, E O and sample trajectory 7i from p(7(01), and compute un -
3: for k = ........ K do
4: Update 0k+1 = arg mingge { (un, 0) + Do (0, 0x));
5: Update Ok+1 0x + yp [0x0++ 0x) with f/s:
(m EEju7
6: Sample a trajectory T from p(T 02+1) and compute un+1 = -
+
BE+1) with BK+1 CTE
7: end for
8: Output: 0g chosen uniformly random from {0x]
BREGMAN GRADIENT POLICY OPTIMIZATION
In this section, we propose novel Bregman gradient policy optimization framework based on Breg- man divergences and momentum techniques. We first let f(0) = (O), the goal of policy-based RL is solve the problem: maxęge (())
= minege f0), we have f(()) (O))
Assume (x)) is continuously and v-strongly convex function, i.c., (æ y. Vb(x)
Ve(()) 2 v|| vll, 0, we define Bregman distance:
(y. 2² (b)) (xx) (Vv(s), 2)) Vx, y E Rd
(8)
Then given function h(z) defined on closed convex set X, we define proximal operator (a.k.a., mirror descent):
P (x) arg min (h(v) yEX
1 D)(u,))).
1
X
where À > Based on this proximal operator PM in Ghadimi et al. 2016 Zhang & He 2018
we can define a Bregman gradient function h(()) as follows:
(x) = { ( (x,
(10)
If (1x) = | and X' = Rd, x= is stationary point of h(x)) if and only if X. (x*)
Vh(x*))
=
0. Thus, this Bregman gradient can be regarded as generalized gradient.
4.1 BGPO ALGORITHM
In the subsection, we propose Bregman gradient policy optimization (BGPO) algorithm based on the basic momentum technique. The pscudo code of BGPO Algorithm is provided in Algorithm ||
In Algorithm| [ the step 4 uses the stochastic Bregman gradient descent (a.k.a,, stochastic mirror descent) to update the parameter 0. Let h(0)= (0, uz) be the first-order approximation of function f() at 9g. where uę is an approximated gradient of function (() at 0g. By the step 4 of Algorithm T and the above equality (IO). we have
( (0x) = \ (Op. 0x+1),
(11)
where À > Then by the step of Algorithm [ we have
a 02 1 (B&),
(12)
where 0 < 7hs < 1. Due to the convexity set Rdd and 02 E O, we choose the parameter Th (0, 1] to ensure the updated sequence {0t) in O
In fact, our BGPO algorithm unifies many popular policy optimization algorithms. When the mir- mappings (0) Y ||0l11 for Vk > 1, the update (12 will be equivalent to a classic policy gradient iteration. Then our BGPO algorithm will become a momentum version of the policy gra- dient algorithms (Sutton et al. 2000 Zhang al. 2019). Given (b) I|l11| and Px i.e.,
14 = g 0k), we have t (0x) = -g(TT 10x) and
a 0x XTTO(TA(OA).
(13)
5

---

Published as a conference paper at ICLR 2022
Algorithm 2 VR-BGPO Algorithm
1: Input: Total iteration K, tuning parameters (X, b, m,c) c} and mirror mappings { {1/1: j= k- u-strongly convex functions;
2: Initialize: 0, E O and sample trajectory 7i from p(7)01), and compute un -
3: for k = ........ K do
4: Update Bk+1 = arg mingge { (un, 0) + Do D (0, 0x));
5: Update Ok+1 0x + yn (0x++ 0x) with n/s: +i
6: Sample a trajectory Th+11 from p(T 1), and compute ux+1
+
Bk+1) [ux - ( 10x+1) + w(Tx+1 (x+1)g((k+ with Bu+1 = cn:
7: end for
8:
Output: 0g chosen uniformly random from (Ox [
When the mirror mappings (0) } F(O)) with F(O,) [VVO,, (s, a) ( VoTo,
(s, (
a))
the update (12) will be equivalent to natural policy gradient iteration. Then our BGPO will become a momentum version of natural policy gradient algorithms (Kakade) [201] Liu et al. 2020). Given F a/x = A F(xx)e, Bx = i.., uk = -g( 10x), we have x (0x) = - F(x))* g (x) and
0x+1 = 0₂ + Am F(0e)) g(Tx 0x),
(14)
where F(Ox)* denotes the Moore-Penrost pseudoinverse of the Fisher information matrix F(0x). )- When given the mirror mapping <hx (0) = Eses TT(() (og(m((s)) i.e., Boltzmann-Shannon en- tropy function (Shannon 1948) and θ {0 E TR E.es To(s) = 1}. we have D (0, 0x)
(T((To))), No, (+)) Eves (s(s) log (Fg] which the KI. divergence. Then our BGPO will
me(s)
become momentum version of mirror descent policy optimization (Tomar al. 2020).
4.2 VR-BGPO ALGORITHM
In the subsection, we propose a faster variance-reduced Bregman gradient policy optimization (VR-
BGPO) algorithm based on a variance-reducee technique. The pseudo code of VR-BGPO algorithm provided in Algorithm 2
Consider the problem (4) is non-oblivious that the distribution p(r(0) depends on the variable varying through the whole optimization procedure, we apply the importance sampling weight (Pap-
ini et al. 2018 Xu et al. 2019a) in estimating our policy gradient u4+1 defined as
p(Tx+1100
H-1
Te, (ar|se) II t=0
w (Tr++10k, 0k+1)) P[Tk+1104+1
M8a-1 (a. st)
Except for different stochastic policy gradients {ux} and tuning parameters {m/, 8e) using in Al- gorithms D and 2 the steps 4 and 5 in these algorithms for updating parameter 0 are the same. Interestingly, when choosing mirror mapping 4ix (0) 0 our VR-BGPO algorithm will reduce to non--oonnnnnn ada-aive version of IS-MBPG algorithm (Huang et 2020)
5 CONVERGENCE ANALYSIS
In this section, we will analyze the convergence properties of our BGPO and VR-BGPO algorithms. All related proof's are provided in the Appendix A Here we use the standard convergence metric
( ( (f)] used in (Zhag & He 2018 Yang et al. 2019) to evaluate the convergence Breg- man gradient- based (a.k.a., mirror descent) algortthms. To give the convergence analysis, we first give some standard assumptions.
Assumption 1. For function log (a)ss) its gradient and Hessian matrix are bounded, i.e., there exist constants Cy. Ch > such that Vo log no [a]s)]] S Cg. [[V? log no(a|s)] S Cn-
Assumption 2. Variance of stochastic gradient g(7 (0) is bounded, i.e., there exists constant >> 0. for all πe such that V(g(T(0) = []]g(T[0) (2) o?. Assumption 3. For importance sampling weight w(rl0r,0,) -(T)))))p((7(2) its variance is bounded, i.c., there exists a constant W > 0, it follows ((u(T 02)) $ W for any 0, 02 E Rd and t ~ p (2))

---

Theorem 1. Assume the sequence {0x 1em be generated from Algorithm 1 Let Tee [m+R))72 for Published as a conference paper at ICLR 2022
Assumption 4. The function (0) has upper bound in O i... supege J(0) < +o0.
Assumptions and 2 are commonly used in the PG algorithms (Papini et al., 2018 Xu et al. 2019alb). Assumption 3 is widely used in the study of variance reduced PG a algorithms (Papini et al. 2018 Xu et al., 2019a). In fact, the bounded importance sampling weight might be violated in some cases such as using neural networks as the policy. Thus, we can clip this importance sampling weights to guarantee the effectiveness of our algorithms as in (Papini et al. 2018). At the same time, the importance weights actually also have some nice properties. c.g., in soft- policy it is bounded by e 161=1 for all 01. 02 O. More recently, (Zhang et al. 2021 used simple truncated update to relieve this uncheckable importance weight assumption. Assumption 4 guarantees the feasibility of the problem (4). Note that Assumptions 2 and 4 are satisfied automatically given Assumption and the fact that all the rewards are bounded, i.e.. (r(s,)) I R for any E S and a E A. For So we have J R
example, due to (r(s,)) S R, we have [J(O) -
R I-
5.1 CONVERGENCE ANALYSIS OF BGPO ALGORITTH
In the subsection, we provide convergence properties of the BGPO algorithm. The detailed proof is provided in Appendix [A.T
b
all 1
pm3/2 1/2
>
1/2 SLA S c b, and m 2 max(b?, (cb)² we have
9L6
K
2M
2/2M
B
( (0x) S K1/2
K
K1/4
where M (1))
wAb DALD + vALE In(m + K).
ma²
Remark 1. Without loss of generality, let b= O1), m 0(1) and X = O(), we have M O(n(m + K)) Ö(1) Theorem / shows that the BGPO algorithm has convergence rate of Ō (( Let K-
we have K Ō(E=t). Since the BGPO algorithm only needs one trajectory to estimate the stochastic policy gradient at each iteration and runs K iterations, it has the sample complexity of 1 K ((e-a) ( for finding e-stationary point.
5.2 CONVERGENCE ANALYSIS OF VR-BGPO ALGORITHM
In the subsection, we give convergence properties the VR-BGPO algorithm. The detailed proof provided in Appendix A.2
Theorem 2. Suppose the sequence 1K
be generated from Algorithm 2 Let Tee (m+R)=73 for
all k 2 0. 0.0 < A
2m3 b O, CE
20L2x²
m 2/3
and m 2 max (2, (cb)², (b) 2/33)
SLb
363
have
2 2/22mm2/6
2V2M'
Σ
E (V (B&)l
(15)
KL/2
K1/3
k=1
where M' J J(O)( + 12 bud
2
20t62 812X2
L = L2 2G2 G CgR/ 7) and C.n
H(HHC) + CW)(W 1).
Remark 2. Without loss of generality, let = 0(1, m = 0(1) and X = 0(1), we have M = O(I((m + K)) Ô(1. Theorem 2 shows that the VR-BGPO algorithum has convergence rate of Ō( ((x17)) Let K-3 < e, have K = (6-). Since the VR-BGPO algorithm only needs one trujectory to estimate the stochastic policy gradient at each ieeration and runs K iterations, reaches a lower sample complexity of K Ö(c ((c-3)oor for finding an e-stationary point.
EXPERIMENTS
In this section, we conduct some RL tasks to verify the effectiveness of our methods. We first study the effect of different choices of Bregman divergences with our algorithms (BGPO and VR- BGPO), and then compare our VR-BGPO algorithm with other state-of-the-art methods such as TRPO (Schulman et al. 2013), PPO (Schulman et al. 2017), ProxHSPGA (Pham et al. 2020).
VRMPO (Yang et al. 2019), and MDPO (Tomar et al. 2020). Our code is available at https: 7/qithub. com/ gawsh/BGPOOOOO
7

---

Published as a conference paper at ICLR 2022
(a) CartPole-vl
(b) Acrobat-v1
(c) MountainCarContinn
Figure 1: Effects of two Bregman Divergences: 4 noor and diagonal term (Diag).
8010
900C
(a) CartPole-vl
(h) Acrobat-vl
(c) CauntainCarComtiuuuua
Figure 2: Comparison between BGPO and VR-BGPO on different environments.
6.1 EFFECTS OF BREGMAN DIVERGENCES
In the subsection, we examine how different Bregman divergences affect the performance of our algorithms. In the first setting, let mirror mapping (x) | (p 2 1) with different p
to test the performance our algorithms. Let eg(v) = (E yı ) the conjugate mapping of tha (I)), where p-1 + q- = 1, P.q > 1. According to (Beck & Teboulle (2003). when θ = Rdd the update of 0x-1 in our algorithms can be calculated by 0A-1 = V (V t/ (0x) + Auu), where (ob( and (U;) are p-norm link functions, and (a)n(zy)) = sign(z,)]æ, 1"= sign(y;)
Vot( =
|
P-2
" and j is the coordinate index of and y. In the second setting, we apply diagonal Ilvll
term the mirror mapping (>x(x)) 1 MEæ, where Mà is diagonal matrix with positive values. In the experiments,
generate Ha diag(Ver + a), Uk Buk-1 (1 Du and
> 3 E (0, 1), as in Super-Adam algorithm (Kingma & Ba 2014; Huang et al. 2021). Then we have Dab, (u, 2) 1 (v - x)² (v y x). Under this setting, the update of 0 can also be analytically solved 0x+1 = AH uk.
To test the effectiveness of two different Bregman divergences, we evaluate them on three classic control environments from gym Brockman al. (2016): CartPole-vl, Acrobat-vl, and NountainCarComiimuuu--00 In the experiment, categorical policy is used for CartPole and Acrobot environments, and Gaussian policy is used for MountainCar, Gaussian value functions are used in all settings. All policies and value functions are parameterized by multilayer perceptrons (MLPs). For fair comparison, all settings use same initialization for policies. We run each setting five times and plot the mean and variance of average returns. For 4, norm mapping, we test three dif- ferent values of (1.50, 2.0, 3.0). For diagonal mapping, we set 3 = 0.999 and a 10-8, We set hyperparameters (b. m, e) be the same. still needs to be tuned for different p to achieve relatively good performance. For simplicity, mapping, and we use BGPO-I, to represent BGPO with fn-morm mapping. Details about the setup of environments and hyperparameters are provided in the Appendix
BGPO-Diag represent BGPO with diagonal
From Fig. I we can find that BGPO-Diag largely outperforms BGPO-I, with different choices of p. The parameter tuning of BGPO-I, is much more difficult than BGPO-Diag because each requires an individual À to achieve the desired performance.
6.2 COMPARISON BETWEEN BGPO AND VR-BGPO
To understand the effectiveness of variance reduced technique used in our VR-BGPO algorithm, we compare BGPO and VR-BGPO using the same settings introduced in section. 6.1 Both algorithms use the diagonal mapping for dh, since it performs much better than I,-norm. From Fig. 2 given in the Appendix C we can that VR-BGPO can outperform BGPO in all three environments.
8

---

Published as a conference paper at ICLR 2022
TRRO
(a) Pendulum-v2
(b) DoublePendulum-v2
(c) Walker2d-v2
(d) Swimmer-v2
(c) Reacher-v2
(f) HalfCheetah-v2
Figure 3: Experimental results of our algorithms and other baseline algorithms on six environments.
In CartPole, both algorithms converge very fast and have similar performance, and VR-BGPO is more stable than BGPO. The advantage of VR-BGPO becomes large in Acrobot and MountainCar environments, probably because the task more difficult compared to CartPole.
6.3 COMPARE TO OTHER METHODS
In this subsection, we apply our BGPO and VR-BGPO algorithms to compare with the other meth- ods. For our BGPO and VR-BGPO, we use diagonal mapping for sh. For VRMPO, we follow their implementation and use 1--norm for th. For MDPO, e the negative Shannon entropy, and the Bregman divergence becomes KL-divergence.
To evaluate the performance these algorithms, we test them on six gym (Brockman et al. 2016) environments with continuous control tasks: Inverted- DoublePendulum--22 Walker2d-v2, Reacher- v2 and HalfCheetah-v2. We use Gaussian policies and Gaus-
v2, Swimmer-v2, sian value functions for all environments, and both of them parameterized by MLPs. To ensure fair comparison, all policies use the same initialization. For TRPO and PPO, we use the implementa- tions provided by garage (garage contributors, 2019). We carefully implement MDPO and VRMPO following the description provided by the original papers. All methods include our method, are implemented with garage (garage contributors 2019) and pytorch (Paszke et al. 2019). We run all algorithms ten times on each environment and report the mean and variance of average returns. Details about the setup of environments and hyperparameters are also provided in the Appendix C
From Fig, 3 we can find that our VR-BGPO method consistently outperforms all the other meth- ods. Our BGPO basically reaches the second best performances. From the results of our BGPO, we can find that using a proper Bregman (mirror) distance can improve performances of the PG methods. From the results of our VR-BGPO, we can find that using proper variance-reduced tech- nique further improve performances of the BGPO. ProxHSPGA can reach some relatively good performances by using the variance reduced technique. MDPO can achieve good results in some environments, but VRMPO only outperforms PPO and TRPO in Reacher and InvertedDoubllePenddllum The unde- sirable performance of VRMPO is probably because it uses lp norm for vh, which requires careful tuning of learning rate.
not outperform PPO or TRPO in Swimmer and InvertedDDubleeenduule
CONCLUSION
In the paper, we proposed a novel Bregman gradient policy optimization framework for reinforce- ment learning based on Bregman divergences and momentum techniques. Moreover, we studied convergence properties of the proposed methods under the nonconvex setting.
ACKNOWLEDGMENT
This work was partially supported by NSF IIS 1845666, 1852606, 1838627, 1837956, 1956002, OLA 2040588.

---

Published as a conference paper at ICLR 2022
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradi- ent methods: Optimality, approximation, and distribution shift, arXiv preprint arXiv: 1908.00261 2019.
Mohammad Gheshlaghi Azar, Vicenç Gómez, and Hilbert J Kappen. The Journal of Machine Learning Research, 13(1):3207-3245, 2012.
Kappen Dynamic policy programming.
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Lev M Bregman. The relaxation method of finding the common point of convex sets and its applica- tion to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217, 1967.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
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.
Yair Censor and Arnold Lent. An iterative row-action method for interval convex programming. Journal of Optimization theory and Applications, 34(3):321-35,, 1981.
Yair Censor and Stavros Andrea Zenios. Proximal minimization algorithm of Optimization Theory and Applications, 73(3):451-466 1992.
Journal
Corinna Cortes, Yishay Mansour, and Mchryar Mohri. Learning bounds for importance weighting. In Advances in neural information processing systems, pp. 442-450, 2010.
Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction in non-convex sgd.
In Advances in Neural Information Processing Systems, pp. 15210-15219, 2019.
Marc Peter Deisenroth, Gerhard Neumann, Jan Peters, et al. A survey policy search for robotics. Foundations and Trends@ in Robotics, 2(1-2):1-142, 2013.
Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global convergence of momentum-based policy gradient. arXiv preprint arXiv:2 10. 101 16, 2021.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path-integrated differential estimator. In Advances Neural Information Processing Systems, pp. 689-699, 2018.
The garage contributors. Garage: A toolkit for reproducible reinforcement learning research. httpp:://itthii thugt com..cco/rr. r wo kgroopggaaaage. 2019.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. theory of regularized markov decision
processes. In Thirty-sixth International Conference on Machine Learning, 2019.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth- ods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2): 267-305, 2016.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-based policy gradient meth- ods. In International Conference on Machine Learning, pp. 4422-4433, PMLR, 2020.
Feihu Huang, Junyi Li, and Heng Huang. Super-adam: Faster and universal framework of adaptive gradients. Advances in Neural Information Processing Systems, 34, 2021.
Yujia Jin and Aaron Sidford. Efficiently solving mdps with stochastic mirror descent, Interna- tional Conference on Machine Learning, pp. 4890-4900 PMLR, 2020.
10

---

Published as a conference paper at ICLR 2022
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In NIPS, pp. 315-323, 2013.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14:1531-1538, 2001.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:14/2.6988) 2014.
Vijay Konda and John N Tsitsiklis. Actor-critic algorithms. In Advances in neural information processing systems, pp. 1014, 2000.
Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.00/335, 2021.
Yuxi Li. Deep reinforcement learning: An overview. arXiv preprint arXiv: /701.07274, 2017.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang- Neural proximal/trust region policy optimiza- tion attains globally optimal policy, arXiv preprint arXiv: 10306, 2019.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33, 2020.
Gergely Neu, Anders Jonsson, and Vicenç Gómez. unified view of entropy--egularized markov decision processes. arXiv preprint arXiv: 2017.
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. 35th International Conference on Machine Learn- ing. volume 80, pp. 4026-4035, 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances Neural Information Processing Systems, pp- 8024-8035, 2019.
Nhan Pham, Lam Nguyen, Dzung Phan, Phuong Ha Nguyen, Marten Dijk, and Quoc Tran-Dinh. A hybrid stochastic policy gradient algorithm for reinforcement learning. In International Confer- ence on Artificial Intelligence and Statistics, pp. 375-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, 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In International Con- ference on Learning Representations (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017.
Shai Shalev- Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 1610.0361. 2016.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized mdps. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5668-5675 2020.
Claude Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-423 1948.
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International Conference Machine Learning, pp. 5729-5738, 2019.

---

Published as a conference paper at ICLR 2022
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-3355 -599 2017.
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 informa- tion processing systems. pp. 1057-1063, 2000.
Manan Tomar, Lior Shani, Yonathan Efroni, and Mohammad Ghavamzadeh. Mirror descent policy optimization. arXiv preprint wrXiv:2055.09814 2020.
Quoe Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. Hybrid stochastic gradi- ent descent algorithms for stochastic nonconvex optimization. arXiv preprint arXiv: arXiv:1905.05920, 2019.
Qing Wang, Yingru Li, Jicchao Xiong, and Tong Zhang. Divergence-augmentee policy optimization. In Advances in Neural Information Processing Systems, pp. 6099-61 2019.
Ronald J Williams. Simple statistical follwng algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-25 256,, 1992.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In Proceedings of the Thirty-Fifth Conference Uncertainty in Artificial Intelligence, pp. 191, 2019a.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. arxiv preprint 1atp::9990006.11. 2019b.
Long Yang, Gang Zheng, Haotian Zhang, Yu Zhang, Qian Zheng, Jun Wen, and Gang Pan. Policy optimization with stochastic mirror descent. arXiv preprint arXiv: 10462, 2019.
Wenhao Zhan, Shicong Cen, Baihe Huang, Yuxin Chen, Jason D) Lee, and Yuejie Chi. Policy mirror descent for regularized reinforcement learning: A generalized framework with linear con- vergence. arXiv preprint 105. 2021.
Junyu Zhang, Chengzhuo Ni. Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the con- vergence and sample efficiency of variance-reduced policy gradient method. arXiv preprint arXiv:2102.08607, 2021.
Junzi Zhang, Jongho Kim, Brendan O'Donoguue, and Stephen Boyd. Sample efficient reinforce- ment learning with reinforce. arXiv preprint 2:Xi:20110111344 2020.
Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Başar. Global convergence of policy gradient methods to (almost) locally optimal policies. arXiv preprini arXiv: 190.00888, 2019.
Siqi Zhang and Niao He. On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization, arXiv preprint arXiv:1806.00 04781, 2018.
12

---

Published as a conference paper at ICLR 2022
A APPENDIX
In this section, we study the convergence properties of our algorithms. We first provide some useful lemmas.
Lemma 1. (Proposition 4.2 in Xu et al. (2019b)) Suppose g is the PGT estimator. Under
Assumption 1, we have
1) g(+(0) is I--ipschitt.diffeennttll i.., (l((:(0))= < L| 0211 01, 02 E e. where L = C/RR((1
7) -->);
2) (0) is L-smooth, i.e. [()2 S L;
3) g()(0) is bounded, i.c., [0)( S G for all 0 E θ with G Cg -7)2.
Lemma 2. (Lemma 6.1 in Xu et al. (2019a)) Under Assumptions 1 and 3, let w(T g(r(0x-1)/9((10b) we have
=
[[w[T(x=11)) 0x)] S C2 110 0x-1
(16)
where C / (2HH + CWWW + +1)
Lemma 3. (Lemma in Ghaadimi et al. (016)) Let X C Rd be closed convex set, and Φ X R be a convex function but possibly nonsmooth, and Dap : x X + Bregman divergence related to the v-strongly convex function v.. Then define
x = arg min {(9,2) 2) + Du(2,)) + o(z)}, E X ZEX
(17)
Px A) = 1 (xx--*) =x*),
(18)
where 9
RR X 0 and (=(2,)) v1(2) (vb(x) + (Vb(z), z)). Then the following
statement holds
(g, Px(xI,gAA)) 2 vIIPx(E, 1) + [ -x)))
(19)
Ghadimi er 2016 xx and at be given 17 with g re- placed by 91 and 92 respectively, Then let Px (I, 91, A) and Px(x,, g2, A) be defined in 18 with x replaced by xt and z respectively. we have
Lemma (Proposition
(1, - Px(x 92, A)ll < 11 g2ll-
(20)
Lemma's 5. (Lemma I in (ortte et al. 2010 Let w(x) Q()) be the importance weight for dis-
P(x)
tributions P and Q The following identities hold for the expectation, second moment, and variance of)
[[w(x)] = V[u(x)] d2(P)
d2(P))
(21)
where (p(1) = (PPIQ), and D(PIIQ) is Rényi divergence between distributions P and Q.
Lemma 6. Suppose that the sequence (0x K be generated from Algorithms 1 or Let Mi S
and 0 < X A 2Lm then we have
- < Tk (f())) - 1111 1/7/
110+11 - 02112.
(22)
2X
Proof. According to Assumption and Lemma 1 the function ((0) is L-smooth. Then we have
L
f(0x+1) S f(Ox) + (Vf())), 0x+1 0k) + 11xt1 0x112
(23)
2
Li
=((0)) + mи (Ox) 0x+1- - -Ox) +
11x+ - 0x
2
L
= =(((s) + 7hh (V.(a)) uu, 0u.1 O2) + mh (uR, Oa 0n) +
10
0x
2
13

---

Published as a conference paper at ICLR 2022
where the second equality is due to 8k+1 0x + m/ (bx+bk+1 0s)) By the step 4 of Algorithm | or have 0k+1 arg minsee {uus 0) + Dv, (0, oz)) - By using Lemma with e(-) O, we have
(uk: x (0x 0k+1)) )) 2 vl (0p 0x+1)11
(24)
Thus, we can obtain
(ug, 8xt1 - 0x) - 1/ - 110+11 - 8 1x11².
(25)
According to the Cauchy- Cauchy-Schwarz Schwarz inequality and Young's inequality, we have
(VS(0s) - uk, Ox+1 0x) - [[v)(0s) - ux [11100++++ - -0x1
(()()) ux 1/4 100+1 0x11.
(26)
42
Combining the inequalities 23
25
with (26 we obtain
Lofk ||0 - 0xll
f(0x+1) - f(0x) + mI (V uk, au+1
Ok) + m. nuR Okt1
0k) +
2
1(0a) + A [V
uxl12
110x+1
0xl1
UTJk
110 ++ 0x11 ? Lufi
11
0x 11
V
4X
= f(xx) + T&A
I (0x)
u
110x+1
0xl1
VT
Ln
)102-1 0
V
2X
4X
2
S 1(0a))
+
A
[
uM
VTR
110x+1
0xl1
(27)
V/
2X
where the last inequality is due to 0 < X S
ZLME
A.1 CONVERGENCE ANALYSIS BGPO ALGORITIIM
In this subsection, we analyze the convergence properties of BGPO algorithm.
Lemma 7. Assume the stochastic policy gradient uk+1 be generated from Algorithm 7 given 0 <
Bx < 1, we have
(( - -4++1 1 (1- BE+ E u4 +
12 - 0xl1 + 12
B
Proof. By the definition of uk+1 in Algorithm
!
we have
uk+1 2i - (x+10(T4+100+44))
(28)
Since ff(x)) = (Ox) for all 2 1, we have
B
+1) (0x+1)
u+++1 1
El (J({))) 4k VJ v.((L))) - (18+1-
-w)+1-u))1 uz)l
E|| (O())) uk VJ((++1) +J 3K4IUK + 1B (x+1))1
[ 3x+ 1) (-vJ((O)) - un) + ++ + +0x())+00++1))
+ (1 - - (.](+++1) + V.((A)))11
(1 (1-3k-1) 9 (lIV
VJ(0 VJ(00)] + B2 ( -(Tx)>>0)))(
< (1 - 3 [1 (1
+ ux + 11-1) 8
[ - -..C)))))))-(()1)))))
+ + E V J g(T 10x+
<1 11-3A-)E 1112
B[|VJ(0,+1) -
VJ(0.)] E -9(0099(T=(l)) -((x++100++)))
BR-1
<11 1 VJ + 1 +
L2E|| - 0x11 + 8 [ - 9(
Bo+1
11-3A-EE mu 12
L
2 11
0x11 + 024100
(29)
Bx41
14

---

Published as a conference paper at ICLR 2022
where the fourth equality holds by Brg 1~p(r 0x (l9((T++100++1) vJ((x+1);; the first inequality
holds by Young's inequality; the second inequality is due to 0 Bg+1 such that (1 1-3++1 (1+
(k+1) = 1 8x+1 - 5k++1 + -B++1 I 1 8 and (1 - Bb+1) (1 + pe-1 S + B2+1 BL
the last inequality holds by Assumption 2.
Theorem 3. Assume the sequence [0x) be generated from Algorithm 1 Let mm Im+ for 1/2
all 2 < 1,0xA5
> 0. SL
m²//2 b.
and m 2 max{b², (cb)² J. we have
9
K
2 2/2m/144
2/2M
E
(0.)). (0+) S
K1/2
K1/4
where M = ((0)
DALb
o²
+
ma² vALb
In(m + K).
Proof. Since (m=+R)177 is decreasing on k, we have S 1/0 m < 1 for all k 2 0. At
the same time, let m 2 (cb)?, we have 8k-1 = cTK I CMj = m1/2 I 1. Consider m 2 (cb)?, we
1/2 have e c b
Since 0 < A < pm 1/2
um 1/2
I pm1 y I " for all A: 2 0. 2Lm
7L6 we have À S
9l6
2LD
2Lno
According to Lemma we have
V MA+1 {((=)((2))) - 11.12
2 1,2 1/ ( 10x+1 0x11 B 1
S - Ba+1 18 (0p) -u +
3x+1
2L
- (0x) - us
Th B..1((
0.41 - 0x 2-222200100) + 21R00
SLA E V ((0))) - ux +
Lv
m1 - 0x11 + mnko0
(30)
4X
62
where the first equality is due to 8k+1 eıj and the last equality holds by SLA S c S m/2
b
Next we define Lyapunov function 42 = ((( + ((()) 1x11 for any 2 1. Then we have
4b = =(( + 1 (1V ux+1/1 [lV)((b)) ux 12]
+ k++1
Ana E v((w) 1211 17k
8ATT E E (Ox)) uul1
1110k+1
0x11
2x
Ell0k41 - 02 + mnmo²
VTR
4X
Lb2
mn
< 4 E ((x))) - 12
2
m= - 22 +
(31)
4x
Lb2
where the first inequality follows by the Lemma and the above inequality 330
15

---

Published as a conference paper at ICLR 2022
Summing the above inequality (31 over is from to K, we can obtain
nh E
V
f(On)
1=l1 +
n-lllo0-11 0x119]
4A
mo² K
< $1 - x++11 +
Σ Lba
The
k=1
1 1 f((k((+1) uk
mo²
K
=((1) f(0k+1)+ + ff(1)) u1ll
ux=1
Lb
ma²
S ](0++))- J((i)) [V((0,) 1( +
1/3
LB?
x²
mo²
K
S J - J(0))
+
dk + k
L
x²
mo²
J ((0)
ln(m + K),
(32)
1
L
where the last second inequality holds by Assumptions 2 and 4. Since 7% is decreasing, we have
K
E B((L)(
uxll + 412 B| 1x
K
4v2
k=1
J
((O1)
o² mo²
In(m + K)
KvALπK
J I(O1).
o²
mo²
(m + K)1/2
In(m + K)
(33)
vbb
vALb
vALb
K
Let M J'-J((1)
mo² PAth
In(m
K), the above inequality
33
reduces to
vbb
vALh
1
M
(0ak)) uxl1 +
11 0011 S
(m K)1/2.
(34)
K
4x2
K
According to Jensen's 's inequality, we have
1
1
E
[((k)))
uxll +
22 110 0xlll
2v
K
[(((k)) - 1x +
4x2 110 - -2x11)) 1/2
1
K
4
k=1
V2M
V/Mm!/4
V2M
(m +
K/4
(35)
K1/2
K1/2
K1/4
where the last inequality is due the inequality (a b) have
1/4 b1/4 for all a, 2 0. Thus
2/2Mm
2/2M
(f())) uxll + } 10 -8xll 5
(36)
K1/2
K1/4
By the step of Algorithm
we have
8 (i (0a) = (e(O,, ue, A)
(0: 02+1).
1
(37)
16

---

Published as a conference paper at ICLR 2022
At the same time, in Ghadimi et al. (2016), we define
A( (0x) Po(Os. A)(( = 11(0x -0%1))
(38)
where
1
0
min (VV 0) DEB
Dev (0, (v,0)).
(39)
K+
X
According to the above Lemma 4 have 1
A.iux. (0x) B (. (0x)ll 1
- v((+)))
Then we have
|
1 Am 03 (0k)l + | X.1ux .0 (0x) BY 11 (0x)]
(xx (04)l + luk v.((0)]]
1
R 110k+1 0ull + 1 VS(O))I--
(40)
By the above incqualities (36) and (40) we have
K
2/2Mm 1/4
2/2M
E
(Pa)
(41)
K
K1/2
K1/4
A.2 CONVERGENCE ANALYSIS OF TR-BGPO ALGORITHM
In this subsection, we will analyze convergence properties of the VR-BGPO algorithm.
Lemma 8. Assume that the stochastic policy gradient u,+1 be generated from Algorithm given
0 < BB < 1, we have
||| - (1-+ 12 + 4422m2110 0x11 + 2.32+102
where L = CG2 and C.u / H(HHC CW + +1.
Proof. By the definition of u4+1 in Algorithm] 2 we have
uk+1 - us
1u 1x+11((Te) ((0T)1110++1)))))00110 + (1 (- (00(((-(TT))))) g(T6:1 - w(Tx+ Oz+ (9(TT+1100))
Since v.((+++)) = - ((((k+))) we have
11 u ((()) + + vJ((R++)) VJ((O2) + (u++1 -
(42)
E(I)) + us + vJ(02+1) VJ(O2) Bx+14z 1 -tet
+ (1 - -+++)) 10++) 10T 0411)0000000119(000001 (x)) 1
E][(1 - 1) (.) +u) (V000) 1
- (1 || - -V vJJ()))
(1 1) + (VJ(Ok+)) -JJ(E))))
<(1 3xx
2( - bx+1) || (VJ (V))))))((((() VJ((x)))1
S (1 -- g
w(T++1 1r., 6x (04+))(77+1
=T:
17

---

Published as a conference paper at ICLR 2022
where the forth equality holds by 100 10
J((+++1) and
(rpe:=p((1()= (0((=)))) (g(7+++ ond last inequality follows by Young's ' inequality; and the last inequality holds by Assumption 2,
(02+00001))))) - w(Tx+1 1 10,, 0x+1 ())+()((()))))))) [x)] = ()(+++))) vJ(0)): the sec-
and the incquality BBlls - _ E||c| - (EKs)) s 1llss and 0 < Bu+1 S 1.
Next, we give an upper bound of the term Ti as follows:
Ti - E (T
w((x++ 00, 0x+1))44000) ()(
= El]g(Te-1100+1) g(Tx+1 10x) + g (0+) - u 0x+1 1 10x]11
S 2BBlg((7+1100+1) - -( |0x)| 21 w(T++ 10 Ox+ ()))))))((((+1110)0 10=)
S 22L ||x2|00+11 - 02 26 ( B4, 0x+
2T, 1|x+1 0x ( 02, 0k+1))
s 2 2G
0
(43)
where the second incquality holds by Lemma and the third equality holds by Lemma 5 and the last inequality follows by Lemma
Combining the inequalities (42 with 43 let L L2 + CG we have
E|| (((+4)))+1)) - 111 (1
+ EE V f(0)) uxl1² + 28 2 + +4t.3110++1 - 0xx12
0²
= (1 +1 E V ((x)) u2l1 + 2 + +4i2 m 12110xt - 11.
Theorem 4. Suppose the sequence
{0x ) be generated from Algorithm 2 Let TJ [m+2)773 for
b
all k 2
2m-/3
b
>
0,
2
+
2012
SCs
m2/3
and m 2 max (2, (cb)², ( )2/3)
5Lb
36
V
we have
K
2V2M'm226 2/6
2V2M
B
\ ((0)).0) (0+) S
(44)
K
KL/2
K1/3
k=1
where M' J(0)
m 2
di'i 8L=x2 and i L2 + +2G
brd
168 L2X
Proof. Since 7p (m+ k is decreasing and 2 b3. we have ?e S 1Ju m/5 I 1. Due
b
to L VL2 + 2G 0
2 L. we have 0 < X I cm 1/3
S
um 1/3 P_ S 2mm for any l: 2 O.
5Lb
2Lb 2mm
Consider 0 < 7 I 1 and m 2 (cb)², we have Bx+1 cgj <
df
I 1. At the same time, we have
m273
m 2/3 62
According to Lemma 8 we have
1
E ((k++)) u6+11 21
E| ((ak)
ux11
77
BE41
E (Ox=)) ux + 20
+ mf.2m - 0x.12
1k
7
n
1
E V (0ee) - 1111 + 26 2200 + 4f.2 10 - 0x
cTT
7)-1
1
b ((m + +x))+
- (m + k: 1)
cm V 1111 222 + 4f. nx 10 - 0
2
363 7k cn ) V ((x)) ux 2| + 202 + 4i'ms 18 0
(45)
where the last inequality holds by the following inequality
(m + k)} (m + k 1
3(m + k: - 1)2/3
3 m 2 + k) k)2/3
2/3
22/3
22/3
12
22/3
2
3(m + k)2/3
312
(m k32/33
362
2
<
352
nk.
(46)
18

---

Published as a conference paper at ICLR 2022
where the first inequality holds by the concavity of function f(z) x!/3, Le.. (x + y) 1 x + 324/3 the second inequality is due m 2 2, and the last inequality is due to 0 7 1. have
2062>²
Let c 2 363
2111 1 ((O))((0) -uxl2
V [(0R+1) -2
-
20
Th
F
((0k)
ux + 222 + 4f.3 m1100++ 0x11?
(47)
v2
Here simultaneously consider
2
2DL2x²
2/3 b²
and
0
A S
v/8 sLb
we have
36
2
20
200
22m2233
4m
m2233
+
+
+
(48)
353
D2
303
25 v²
313
562
b²
Then we have 2
(2))
Next we define Lyapunov function S2g [[[((k)) According to Lemma 6 we have
Vf((p)
ux for any 1.
162
24+1 94 = f(06+1) f(0x) +
V
(EIIV(((++1))
- 22+1112
1
E f((b)) -2x12
16Î2> AK
7
V vf(()) ussl²²
VRR
10a41 0x112
5Ame
E f((kk) - u
2x
4v
MERmA0²
1/T
E 10++1 0x
4X
Amik
ver
E (0x))
- mx
Bll0++1 - 0x
(49)
4v
4A
gi2X
where the first inequality is due to the above inequality (47 Thus, we can obtain
(((a) - u + 4v
VTk
E
0
0a11 s Sh 2x+1 +
(50)
4A
-i²>
Taking average over k = 1,2, K on both sides of 50 have
K
XIIk
E
V
(0kk)
1x
UIJ
Bllōet1
1x
T
4v
4A
k=1
f(0:) f(0K+1)
1
v((())
un 11
vllVf(kk+))
UK+1
1 K
5
K
16Ê2noXK
8i.₂> x
k=1
J(0k+1) - -((1))
vO²
K
n2
Σ
K.
16L2
K
kml
J - ((01)
DO²
1
(51)
K
85.2
where the second inequality is due u1 -g( 01), VS(0i) (J((0) and Assumption 1, and the last inequality holds by Assumption 2. Since nh is decreasing, i.e., 7x > 1
- for any
19

---

Published as a conference paper at ICLR 2022
0 k S K, we have
((0)) uxll+
B110x+1
0x 0x
412
J J(01)
o²
K
KAλNK
16L
KλTK
8Î22
R=1
J J(01)
m 022 16hI.22211 K
202
k ba
dk
KUNTK
8f222K
m +
J J(01)
m m2/302
Co221
In(m + K)
K Кλпк
16b x K 1/1/002
-(61)
c0022
(m KK1/3
(52)
byd
1662
81
K
where the second inequality holds by Σm= dk < f
dk = 6² Jtt (m + ddk.
Let M' -(0))
+
m//3
+
d'026
the above inequality 52 reduces to 8i2x2*
bud
1662
1
K
1
M' S
(0x))) umll? +
1 0x
(m + K)1/3. K
(53)
K
412
According to Jensen's 's inequality, we have
((kk) - uell + 2/x11 111+++1 - 0xll]
K
2v
22
K
E
V (((e)) - 1x 2
+
1
1100+1 0xx113)) 1/2
K
4x2
k=1
V2M
m/
22M'
(m K/
(54)
K1/2
K1/2
K1/3
where the last inequality is due to the inequality (a (a+bb) (b & a 1/6 + 1/6 for all a, 22 1. Thus we have
B unll + + 11 -0u1] <
2 2/
2/2M'
(55)
K
K1/2
K1/3
Then by using the above inequality 40).
obtain
K
2V2M'm 2/6
2/2M'
B th
(6,)
(56)
K1/2
K1/3
B ACTOR-CRITIC STYLE BGPO AND VR-BGPO ALGORITHMM
In the experiments, we use the advantage-basee policy gradient estimator:
H
s(T(0) V log ( (st, ast,
(57)
t=
20

---

Published as a conference paper at ICLR 2022
Algorithm 3 BGPO Algorithm (Actor-Critie Style)
1: Input: Total iteration K, tuning parameters (X, b, m.c) c) and mirror mappings { ) u-strongly convex functions;
2: Initialize: 01 O, of O" and sample trajectory Ti from p(7(01), and compute un -g(1((1);
3: for k k. do
4: # Update the policy network
5: Update Dk+1 = arg mingee { (uz, 0) + 1 Da (0, 0x));
6: Update 0k+1 = 02 + m (0x+1 0x) with T7 (m++)1/2
7: # Update the value network
8:
Update 0++1 by solving the subproblem (58);
9: # Sample new trajectory and compute policy gradients
Sample trajectory Tk+1 from p(T (T(0k+)), and compute ux+1 -Be+19(Te-110k=1)
Bk+1) ug with Pk+1 CTK
end for Output: 0g chosen uniformly random from (0% ) 1==1
12:
Algorithm 4 VR- Algorithm (Actor- (Actor-Critic Style)
Input: Total iteration K, tuning parameters {A, b, m, c} and mirror mappings { ) are v-strongly convex functions;
2: Initialize: 0, O, 0g O" and sample a trajectory тı from p(r[01). and compute in 11):
3: for k = K do
4: # Update the policy network
5:
Update Oc+1 arg minsge { (ug, 0) + D (0, 0x)):)
6:
Update 0k+1 = 02 + mı (0x+++1 0%) with The ()173
7:
# Update the value network
8:
Update h++1 by solving the subproblem 58
9: # Sample new trajectory and compute policy gradients
Sample trajectory Tk+1 from p(r (k+1),, and compute ux+1 = - with Bu+1 c
BK+1) Ug g (0++)) w=Tx+110ks
11: end for
Output: 0g chosen uniformly random from [0x]
where A(E O C Idd denotes parameters of the policy network, and A a) is an estimator of the advantage function a (s, a). In using advantage-based policy gradient, we also need the state- value function (s). Here, we use value network Ve- approximate the state-value function V= (s). Specifically, we solve the following problem to obtain the value network:
F-1
min L(A") 9"E6"
= Σ
(s:) (s:))
(58)
t=0
where (E O C Rdd) denotes parameters of the value network, and 7r (s) an estimator of the state-value function VT (s), which is obtained by the GAE Schulman al. (2016). Then we use the GAE to estimate A based value network Vge. We describe the actor-critic style BGPO and VR-BGPO algorithms in Algorithm 3 and Algorithm 4 respectively.
C DETAILED SETUP OF EXPERIMENTAL ENVIRONMENTS AND HYPER- PARAMETERS
In this section, provide the detailed setup of experimental environments and saper-parameters. We first provide the detailed setup of our experiments and Tab. We use ADAM optimizer optimize value functions for all methods and settings, which is common practice. The impor-
21

---

Published as a conference paper at ICLR 2022
Environments
CartPole-vI
Acrobat-v1
MountainCar-vD
Horizon
100
500
500
Value function Network sizes
32 x 32
32 x 32
32 x 32
Policy network sizes
8 x
8 x
64 x 64
Number of timesteps
x 10
x 10
7.3 x 10
Batchsize
50
100
100
TR-BGPO/BGPO {b, m.c)
{1.5, 2.0, 25)
[1.5. 2.0, 25]
[1.5,2.0 25] (0.016, 0.001) x 10
BGPO-I, (Ap-1.5, 2p-2.0, 3
{0. 00.0064, 0.0016, 0.0008)
(0.016, 0.001) x 10
BGPO-Diag/VR Bet///V----P---iie BGPO-Diag&
x 10
Value l'unction learning rate
2.5 10-3
2.5 10-3
2.5 10
Table 2: Setups of environments and syper-parameters for experiments in section 6.2 and section 6.3.
The learning rate of value functions are the same for all methods.
Environments
Pendulum-v22
DouhlePendsllm-222
Walker2d-v22
Swimmer-v2
Keacher-vV2
HallCheetali-22
Horizon
500
300
500
500
500
500
Value function Network sizes
x
x
x
32 32
x
x
Policy nerwerk sizes
64 x 64
64 x 64
64 x 64
64 x 64
64 x 64
64 x 64
Number timesteps
5
107
Batchsize
100
100
100
100
100
100
VR-RGPO m)
2.0,
10 2.0,26)
[1.50, 2.0, 25)
(1.50, 2.0.26 26)
(1,50, 2.0, 25)
2.0, 25)
VR-BGPO
1 10
10
5 10
5 10
10
TRPO/PPO learning
2.5 x 10-3
2.5 10ma
10-3
2.5 10-3
2.5 10-3
2.5 10-3
MDPO learning rule
3.x
3.x 10
3.x 10
3 10
3.x 10-3
3 10-3
VRMPO learning rate
10
3
10
2 10
5
5 10
function learning rate
10
2.5
2.5
Table 3:
Setups of environments and hyper-parameters for experiments in section 6.4. The learning rate value functions are the same for all methods.
tance sampling weight used for VR- algorithm is clipped within [0.5, 1.5]. The momentum term 3g is set to less or equal than one (6g- = min(3 1.0) through the whole training process.
BGPO and VR-BGPO algorithms involve hyper-parameters {A, b, m, c}, which may bring addi- tional efforts for hyper-parameter tuning. However, the actual hyper-paramett tuning is not so hard, set of (b, m., c} for 9 environments. The strategy of typer-parameter tuning is
and we only to separate the four hyper-parameters into two parts. The first part is (b, m, cJ, which mainly decide when the momentum how fast the policy is learning. To further reduce the complexity of hyper-parameter parameter tuning, we always set m 2. By grouping syper-parameteryy we only consider and how B% changes, which largely simplifies the process of hyper- parameter tuning.
3x actually affects (3x < 1.0) updates. The second part, X, only affects
22


Reviews:
[{"review_id": "mURsuEYl9hf", "reviewer": "Reviewer_mQZe", "summary": "", "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": "My concern about this paper mainly lies in its lack of novelty both in the algorithm design and the theoretical analysis. First of all, mirro policy gradient with Bregman divergence regularizer was already proposed in other papers. For example, the algorithm proposed in the current work is almost the same as that in the following paper:\nYang L, Zheng G, Zhang H, Zhang Y, Zheng Q, Wen J, Pan G. Policy optimization with stochastic mirror descent. arXiv preprint arXiv:1906.10462. 2019 Jun 25.\n\nThe difference of the current paper with the above one lies in the variance reduction techniques. Yang et al uses the SPIDER estimator, while the current paper uses the STORM estimator proposed in Cutkosky and Orabona (2019). Moreover, even the adaptation of STORM from nonconvex optimization to policy optimization was already studied in a recent paper: Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-based policy gradient methods (2020). Therefore, combining these methods with a mirror descent update do not seem to have enough contributions for the publishment of this paper. \n\n\n==after the author's response==  \nI thank the authors for their detailed response on the differences of the submission from closely related work. Given these comments and discussions, I am willing to raise my score to accept this paper.", "summary_of_the_paper": "This paper studies the convergence of policy gradient algorithms with constraints. They modify the vanilla policy gradient with Bregman divergence as a regularizer. The authors also propose a new variance reduced policy gradient methods based on the STORM estimator in nonconvex optimization. \n\n\n", "summary_of_the_review": "This paper has limited novelty in both algorithm design and theoretical analysis. It is also highly similar to existing papers from several perspectives.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "RVcAwxV71YR", "reviewer": "Reviewer_pxbY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "The paper discusses the momentum and STORM version of the mirror descent PG method, which is a relatively new result. The analysis and the presentation of the results are clear and well-organized. Although the result can be expected since both STORM and mirror descent, as well as their numerous variants, are well-studied, the discovery of this paper does imply the convergence of several important special cases of the PG method, including the NPG and Super-Adam version of PG. So I think this is a good paper. ", "summary_of_the_paper": "The authors consider the optimization problem of an MDP. They designed two policy gradient algorithms based on the mirror descent method, which are named BGPO and VR-BGPO. The BGPO algorithm is a momentum mirror descent method that finds an $\\epsilon$-stationary policy with $O(\\epsilon^{-4})$ samples. The VR-BGPO algorithm is a STORM-type variance reduced mirror descent method that finds an $\\epsilon$-stationary policy with $O(\\epsilon^{-3})$ samples. The analysis is nicely organized and the authors also provide a couple of experiments to verify their theoretical findings.  ", "summary_of_the_review": "The main comments are provided in the main review part. Here I will add a few comments. \n\n1. The authors have used \"mirror descend\" several times in the paper, please unify terminology and use \"mirror descent\".\n\n2. Because the second algorithm proposed by the author is a STORM type variance reduced mirror descent PG method, the authors should also mention the work by Yuhao Ding Junzi Zhang & Javad Lavaei: \\emph{On the Global Convergence of Momentum-based Policy Gradient}. The algorithms of this paper also apply the STORM technique.  For the same reason, the following work by Nhan H. Pham et al. \\emph{A Hybrid Proximal Stochastic Policy Gradient Algorithm} should also be cited. \n\n3. Regarding equation (4), the author should mention that the objective function with a horizon $H$, there is a truncation error of $\\frac{\\gamma^H}{1-\\gamma}$ compared to the original infinite-horizon MDP. \n\n4. Regarding Assumption 2 and Assumption 4, the author should mention that both of them are satisfied automatically given Assumption 1 and the fact that all the rewards $r(s,a)$ are bounded. \n\n\n5. Regarding Assumption 3, the authors should also mention that the importance weights can be bounded theoretically (instead of an uncheckable assumption) by using the truncated gradient step instead of a gradient step. See the work of Junyu Zhang et al. \\emph{On the convergence and sample efficiency of variance-reduced policy gradient method}. The importance weights actually as some nice properties,   for soft-max policy it is bounded by $e^{c||\\theta_1-\\theta_2||}$, in Gaussian policy it is bounded as $e^{c||\\theta_1-\\theta_2||^2}$. So a simple truncated update is enough to control this value. \n\n6. There are still a few typos/gramma errors in the paper, for example, in the first row of contribution (a), the \"based the\" should be \"based on the\". The authors should carefully check the spelling and gramma in the revision. \n\n7. Regarding the experiments, the authors compared with several different algorithms. However, there is a small issue w.r.t. the selected algorithms. \n\nVR-BGPO: variance reduction (VR) + mirror descent (MD)\n\nVR-MDPO: VR + MD\n\nMDPO: VR only\n\nTPO & PPO: no VR, no MD\n\nFrom these comparisons, I'm not able to see if the MD really works. The authors should also compare with algorithms such as Prox-HSPGA, (A hybrid stochastic policy gradient algorithm for reinforcement learning) which applies STORM technique while not using mirror descent. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8WE9LtvZ5Tf", "reviewer": "Reviewer_s4n4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "In general, the paper is well written with some minor grammar issues. The developed BGPO and VR-BGPO are simple and easy to implement. The derived convergence results match the state-of-the-art one. Numerical results illustrate the effectiveness of the proposed algorithms. However, we still have some concerns as follows:\n\n1) My understanding is that the proposed algorithm is pretty general. Why does the work only focus on policy gradient rather than general gradient? What is the unique property that has been used here to guarantee theoretical results compared to the traditional stochastic gradient methods?\n\n2) Why do the compared algorithms shown in Table 3 need a large batch size (i.e., $\\epsilon$ dependent) while the proposed one only requires constant batch size?\n\n3) I agree that VR-BGPO is better than BGPO. But BGPO is not simulated in Figure 3?  \n\nSome other minor issues:\n\nPGT is not explicitly definied.", "summary_of_the_paper": "This work proposes a Bregman gradient policy optimization framework for RL. Two specific algorithms are proposed, which are BGPO and VR-BGPO, where VR-BGPO is an accelerated version of BGPO. The authors provide the convergence rates results for these two algorithms and show their efficiency through multiple numerical simulations.", "summary_of_the_review": "Overall, I believe that there are some merits of this work regarding the simplicity of the implementation of the algorithms, theoretical justification of the convergence rates, and numerical instances of verifying the efficiency of BGPO and VR-BGPO.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a policy gradient algorithm based on the Bregman divergence and momentum method. While one reviewer was initially concerned about the technical novelty of the paper given some existing works, after the author's response and paper revision, the reviewers are all convinced and have reached a consensus to accept this paper. Thus I recommend acceptance.
Decision: Accept (Poster)