BREGMAN GRADIENT POLICY OPTIMIZATION
Year: 2021

Abstract:
In this 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 both the basic momentum technique and mirror descent iteration. At the same time, 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. Specifically, we prove that the BGPO achieves a sample complexity of O( −4) for finding -stationary policy only requiring one trajectory at each iteration, and the VR-BGPO reaches the best known sample complexity of O( −3) for finding an -stationary policy, which also only requires one trajectory at each iteration. In particular, by using different Bregman divergences, our methods unify many existing policy optimization algorithms such as the existing (variance-reduced) policy gradient algorithms and natural policy gradient algorithms. Extensive experimental results on multiple reinforcement learning tasks demonstrate the efficiency of our new algorithms.

heading: 1 INTRODUCTION
text: Policy Gradient (PG) methods are a class of popular policy optimization methods for Reinforcement Learning (RL), and have achieved significant successes in many challenging applications (Li, 2017) such as robot manipulation (Deisenroth et al., 2013), the Go game (Silver et al., 2017) 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) involved in RL, where an agent takes action dictated by a policy in an unknown dynamic environment over a sequence of time steps. Since the PGs are generally estimated by Monte-Carlo 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 to reduce variances of vanilla stochastic PG. For example, Sutton et al. (2000) introduced a baseline to reduce variances 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., 2015b) proposed 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., 2018; Xu et al., 2019a; Shen et al., 2019; Liu et al., 2020) have been developed based on the variance-reduction techniques in stochastic optimization.
Alternatively, some successful PG algorithms (Schulman et al., 2015a; 2017) improve convergence rate and robustness of vanilla PG methods by using some penalties such as Kullback-Leibler (KL) divergence penalty. For example, trust-region policy optimization (TRPO) (Schulman et al., 2015a) 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 to implicitly reach this goal. Subsequently, Shani et al. (2020) have analyzed the global convergence properties of TRPO in tabular RL based on the convex mirror descent algorithm. Liu et al. (2019) have also studied the global convergence properties of PPO and TRPO equipped with overparametrized 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, mirror descent policy optimization (MDPO) (Tomar et al., 2020) iteratively updates the policy beyond the tabular RL by approximately solving a trust region problem based on convex mirror descent
algorithm. In addition, Agarwal et al. (2019); Cen et al. (2020) have studied the natural PG methods for regularized RL. 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 a 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 an 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 momentum techniques. In particular, we provide a 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( −4) for finding -stationary policy only requiring one trajectory at each iteration.
b) We propose an accelerated Bregman gradient policy optimization (VR-BGPO) algorithm based on the variance-reduced momentum technique. Moreover, we prove that the VRBGPO reaches the best known sample complexity of O( −3) under the nonconvex setting.
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 1 shows thet 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-parameterized networks (Liu et 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 (2020); Lan (2021); Zhan et al. (2021) studied a general theory of regularized MDPs based on policy function space that generally is discontinuous. Since both the state and action spaces S and A generally are very large in practice, the policy function space is large. While our methods build on policy parameter space that is generally continuous Euclidean space and relatively small. Clearly, our methods and theoretical results are more practical than the results in (Geist et al., 2019; Jin & Sidford, 2020; Lan, 2021; Zhan et al., 2021). (Tomar et al., 2020) also proposes mirror descent PG framework based on policy parameter 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.

heading: 2 RELATED WORKS
text: In this section, we review some related work about mirror descent algorithm in RL and variancereduced PG methods, respectively.

heading: 2.1 MIRROR DESCENT ALGORITHM IN RL
text: 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 the Bregman distances (Bregman, 1967; Censor & Lent, 1981). For example, Neu et al. (2017) have shown both the dynamic policy programming (Azar et al., 2012) and TRPO (Schulman et al., 2015a) algorithms are approximate variants of mirror descent algorithm. Subsequently, Geist et al. (2019) have introduced a 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-policy learning based on mirror descent algorithm. MDPO (Tomar et al., 2020) iteratively updates the policy beyond the tabular RL by approximately solving a trust region problem based on convex mirror descent algorithm.

heading: 2.2 (VARIANCE-REDUCED) PG METHODS
text: PG methods have been widely studied due to their stability and incremental nature in policy optimization. For example, the global convergence properties of vanilla policy gradient method in infinite-horizon MDPs have been recently studied in (Zhang et al., 2019). Subsequently, Zhang et al. (2020) have studied asymptotically global convergence properties of the REINFORCE (Williams, 1992), whose policy gradient is approximated by using a 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 convex and non-convex optimization. For example, fast SVRPG (Papini et al., 2018; Xu et al., 2019a) algorithm have been proposed based on SVRG. Fast HAPG (Shen et al., 2019) and SRVR-PG (Xu et al., 2019a) algorithms have been presented by using SPIDER technique. Subsequently, the momentum-based PG methods, i.e., ProxHSPGA (Pham et al., 2020) and IS-MBPG (Huang et al., 2020), have been developed based on variance-reduced technique of STORM/Hybrid-SGD (Cutkosky & Orabona, 2019; Tran-Dinh et al., 2019). More recently, (Ding et al., 2021) studied the global convergence of 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-reduced PG methods and provided the global convergence of the TSIVR-PG under overparameterizaiton of policy assumption.

heading: 3 PRELIMINARIES
text: In the section, we will review some preliminaries of Markov decision process and policy gradients.

heading: 3.1 NOTATIONS
text: Let [n] = {1, 2, · · · , n} for all n ∈ N+. For a vector x ∈ Rd, let ‖x‖ denote the `2 norm of x, and ‖x‖p = (∑d i=1 |xi|p )1/p (p ≥ 1) denotes the p-norm of x. For two sequences {ak} and {bk}, we denote ak = O(bk) if ak ≤ Cbk for some constant C > 0. E[X] and V[X] denote the expectation and variance of random variable X , respectively.

heading: 3.2 MARKOV DECISION PROCESS
text: Reinforcement learning generally involves a discrete time discounted Markov Decision Process (MDP) defined by a tuple {S,A,P, r, γ, ρ0}. S and A denote the state and action spaces of the agent, respectively. P(s′|s, a) : S × A → 4(S) is the Markov kernel that determines the transition probability from the state s to s′ under taking an action a ∈ A. r(s, a) : S ×A → [−R,R] (R > 0) is the reward function of s and a, and ρ0 = p(s0) denotes the initial state distribution. γ ∈ (0, 1) is
the discount factor. Let π : S → 4(A) be a stationary policy, where4(A) is the set of probability distributions on A. Given the current state st ∈ S , the agent executes an action at ∈ A following a conditional probability distribution π(at|st), and then the agent obtains a reward rt = r(st, at). At each time t, we can define the state-action value function Qπ(st, at) and state value function V π(st) as follows:
Qπ(st, at) = Est+1,at+1,... [ ∞∑ l=0 γlrt+l ] , V π(st) = Eat,st+1,... [ ∞∑ l=0 γlrt+l ] . (1)
We also define the advantage function Aπ(st, at) = Qπ(st, at) − V π(st). The goal of the agent is to find the optimal policy by maximizing the expected discounted reward
max π
J(π) := Es0∼ρ0 [V π(s0)]. (2)
Given a time horizonH , the agent collects a trajectory τ = {st, at}H−1t=0 under any stationary policy. Then the agent obtains a cumulative discounted reward r(τ) = ∑H−1 t=0 γ
tr(st, at). Since the state and action spaces S and A are generally very large, directly solving the problem (2) is difficult. Thus, we let the policy π be parametrized as πθ for the parameter θ ∈ Θ ⊆ Rd. Given the initial distribution ρ0 = p(s0), the probability distribution over trajectory τ can be obtained
p(τ |θ) = p(s0) H−1∏ t=0 P(st+1|st, at)πθ(at|st). (3)
Thus, the problem (2) will be equivalent to maximize the expected discounted trajectory reward:
max θ∈Θ J(θ) := Eτ∼p(τ |θ)[r(τ)]. (4)
In fact, the above objective function J(θ) has a truncation error of O( γ H
1−γ ) compared to the original infinite-horizon MDP.

heading: 3.3 POLICY GRADIENTS
text: The policy gradient methods (Williams, 1992; Sutton et al., 2000) are a class of effective policybased methods to solve the above RL problem (4). Specifically, the gradient of J(θ) with respect to θ is given as follows:
∇J(θ) = Eτ∼p(τ |θ) [ ∇ log ( p(τ |θ) ) r(τ) ] . (5)
Given a mini-batch trajectories B = {τi}ni=1 sampled from the distribution p(τ |θ), the standard stochastic policy gradient ascent update at (k + 1)-th step, defined as
θk+1 = θk + η∇JB(θk), (6) where η > 0 is learning rate, and ∇JB(θk) = 1n ∑n i=1 g(τi|θk) is stochastic policy gradient. Given H = O( 11−γ ) as in (Zhang et al., 2019; Shani et al., 2020), g(τ |θ) is the unbiased stochastic policy gradient of J(θ), i.e., E[g(τ |θ)] = ∇J(θ), where
g(τ |θ) = (H−1∑ t=0 ∇θ log πθ(at, st) )(H−1∑ t=0 γtr(st, at) ) . (7)
Based on the gradient estimator in (7), we can obtain the existing well-known policy gradient estimators such as REINFORCE (Williams, 1992), policy gradient theorem (PGT) estimator (Sutton et al., 2000). Specifically, the REINFORCE obtains a policy gradient estimator by adding a baseline b, defined as
g(τ |θ) = (H−1∑ t=0 ∇θ log πθ(at, st) )(H−1∑ t=0 γtr(st, at)− bt ) .
The PGT is a version of the REINFORCE, defined as
g(τ |θ) = H−1∑ t=0 H−1∑ j=t ( γjr(sj , aj)− bj ) ∇θ log πθ(at, st).
Algorithm 1 BGPO Algorithm 1: Input: Total iteration K, tuning parameters {λ, b,m, c} and mirror mappings { ψk }K k=1
are ν-strongly convex functions;
2: Initialize: θ1 ∈ Θ, and sample a trajectory τ1 from p(τ |θ1), and compute u1 = −g(τ1|θ1); 3: for k = 1, 2, . . . ,K do 4: Update θ̃k+1 = arg minθ∈Θ { 〈uk, θ〉+ 1λDψk(θ, θk) } ; 5: Update θk+1 = θk + ηk(θ̃k+1 − θk) with ηk = b(m+k)1/2 ; 6: Sample a trajectory τk+1 from p(τ |θk+1), and compute uk+1 = −βk+1g(τk+1|θk+1) + (1− βk+1)uk with βk+1 = cηk; 7: end for 8: Output: θζ chosen uniformly random from {θk}Kk=1.

heading: 4 BREGMAN GRADIENT POLICY OPTIMIZATION
text: In the section, we propose a novel Bregman gradient policy optimization framework based on Bregman divergences and momentum techniques. We first let f(θ) = −J(θ), the goal of policy-based RL is to solve the problem: maxθ∈Θ J(θ) ⇐⇒ minθ∈Θ f(θ), so we have∇f(θ) = −∇J(θ). Definition 1. (Censor & Zenios, 1992; Zhang & He, 2018) Given a function h(x) defined on a closed convex set X , and the Bregman distance Dψ: Dψ(y, x) = ψ(y) − ψ(x) − 〈∇ψ(x), y − x〉, ∀x, y ∈ X , then we define a proximal operator Pψλ,h of function h(x),
Pψλ,h(x) = arg miny∈X { h(y) + 1 λ Dψ(y, x) } , (8)
where λ > 0, ψ(x) is a continuously-differentiable and ν-strongly convex function, i.e., 〈x − y,∇ψ(x)−∇ψ(y)〉 ≥ ν‖x− y‖, ν > 0.
Based on the proximal operator of Pψλ,h as in Zhang & He (2018); Ghadimi et al. (2016), we define the Bregman gradient as follows:
Bψλ,h(x) = 1
λ
( x− Pψλ,h(x) ) . (9)
If ψ(x) = 12‖x‖ 2 and X = Rd, x∗ is a stationary point of h(x) if and only if Bψλ,h(x∗) = ∇h(x∗) = 0. Thus, this Bregman gradient can be regarded as a generalized gradient.

heading: 4.1 BGPO ALGORITHM
text: In the subsection, we propose a Bregman gradient policy optimization (BGPO) algorithm based on the basic momentum technique. The pseudo code of BGPO Algorithm is provided in Algorithm 1.
In Algorithm 1, the step 4 uses the stochastic Bregman gradient descent (a.k.a., stochastic mirror descent) to update the parameter θ. Let h(θ) = 〈θ, uk〉 be the first-order approximation of function f(θ) at θk, where uk is a stochastic gradient of function f(θ) at θk. By the step 4 of Algorithm 1 and the above equality equation 9, we have
Bψkλ,h(θk) = 1
λ
( θk − θ̃k+1 ) , (10)
where λ > 0. Then by the step 5 of Algorithm 1, we have
θk+1 = θk − ληkBψkλ,h(θk), (11)
where 0 < ηk ≤ 1. Due to the convexity of set Θ and θ1 ∈ Θ, we choose the parameter ηk ∈ (0, 1] to ensure the updated sequence {θk}Kk=1 in the set Θ. In fact, our algorithm unifies many popular policy optimization algorithms. When the mirror mappings ψk(θ) = 12‖θ‖
2 for ∀k ≥ 1, then the update (11) is reduced to classic policy gradient algorithms (Sutton et al., 2000; Zhang et al., 2019; 2020). In the other words, given uk = −g(τk|θk) and ψk(θ) = 12‖θ‖ 2, we have Bψkλ,h(θk) = −g(τk|θk) and
θk+1 = θk + ληkg(τk|θk). (12)
Algorithm 2 VR-BGPO Algorithm 1: Input: Total iteration K, tuning parameters {λ, b,m, c} and mirror mappings { ψk }K k=1
are ν-strongly convex functions;
2: Initialize: θ1 ∈ Θ, and sample a trajectory τ1 from p(τ |θ1), and compute u1 = −g(τ1|θ1); 3: for k = 1, 2, . . . ,K do 4: Update θ̃k+1 = arg minθ∈Θ { 〈uk, θ〉+ 1λDψk(θ, θk) } ; 5: Update θk+1 = θk + ηk(θ̃k+1 − θk) with ηk = b(m+k)1/3 ; 6: Sample a trajectory τk+1 from p(τ |θk+1), and compute uk+1 = −βk+1g(τk+1|θk+1) + (1−
βk+1) [ uk − g(τk+1|θk+1) + w(τk+1|θk, θk+1)g(τk+1|θk) ] with βk+1 = cη2k;
7: end for 8: Output: θζ chosen uniformly random from {θk}Kk=1.
When the mirror mappings ψk(θ) = 12θ TF (θk)θ with F (θk) = E(s,a)∼Pθk (s,a) [ ∇θπθk(s, a)∇θπθk(s, a)T ] for ∀k ≥ 1, the update (11) is reduced to natural policy gradient algorithms (Kakade, 2001; Liu et al., 2020). Similarly, given uk = −g(τk|θk) and ψk(θ) = 1 2θ TF (θk)θ, we have Bψkλ,h(θk) = −F (θk)+g(τk|θk) and
θk+1 = θk + ληkF (θk) +g(τk|θk), (13)
where F (θk)+ denotes the Moore-Penrose pseudoinverse of the Fisher information matrix F (θk). When given the mirror mapping ψk(θ) = ∑ s∈S πθ(s) log(πθ(s)), i.e., Boltzmann-Shannon en-
tropy function (Shannon, 1948) and Θ = { θ ∈ Rd | ∑ s∈S πθ(s) = 1 } , we have Dψk(θ, θk) =
KL ( πθ(s), πθk(s) ) = ∑ s∈S πθ(s) log ( πθ(s) πθk (s) ) , which is the KL divergence. Thus, the update (11) is reduced to the mirror descent policy optimization (MDPO) (Tomar et al., 2020).

heading: 4.2 VR-BGPO ALGORITHM
text: In the subsection, we propose a faster variance-reduced Bregman gradient policy optimization (VRBGPO) algorithm based on a variance-reduced technique. The pseudo code of VR-BGPO algorithm is provided in Algorithm 2.
Consider the problem (4) is non-oblivious that the distribution p(τ |θ) depends on the variable θ varying through the whole optimization procedure, we apply the importance sampling weight (Papini et al., 2018; Xu et al., 2019a) in estimating our policy gradient uk+1, defined as
w(τk+1|θk, θk+1) = p(τk+1|θk) p(τk+1|θk+1) = H−1∏ t=0 πθk(at|st) πθk+1(at|st) .
Except for different stochastic policy gradients {uk} and tuning parameters {ηk, βk} using in Algorithms 1 and 2, the steps 4 and 5 in these algorithms for updating parameter θ are the same. Interestingly, when choosing mirror mapping ψk(θ) = 12‖θ‖
2, our VR-BGPO algorithm will reduce to a non-adaptive version of IS-MBPG algorithm (Huang et al., 2020).

heading: 5 CONVERGENCE ANALYSIS
text: In this section, we will analyze the convergence properties of the proposed algorithms. All related proofs are provided in the Appendix. Here we use the standard convergence metric ‖Bψkλ,〈θ,∇f(θk)〉(θ)‖ used in (Zhang & He, 2018; Yang et al., 2019) to evaluate the convergence Bregman gradient-based (a.k.a., mirror descent) algorithms. To give the convergence analysis, we first give some standard assumptions. Assumption 1. For function log πθ(a|s), its gradient and Hessian matrix are bounded, i.e., there exist constants Cg, Ch > 0 such that ‖∇θ log πθ(a|s)‖ ≤ Cg, ‖∇2θ log πθ(a|s)‖ ≤ Ch. Assumption 2. Variance of stochastic gradient g(τ |θ) is bounded, i.e., there exists a constant σ > 0, for all πθ such that V(g(τ |θ)) = E‖g(τ |θ)−∇J(θ)‖2 ≤ σ2. Assumption 3. For importance sampling weight w(τ |θ1, θ2) = p(τ |θ1)/p(τ |θ2), its variance is bounded, i.e., there exists a constant W > 0, it follows V(w(τ |θ1, θ2)) ≤ W for any θ1, θ2 ∈ Rd and τ ∼ p(τ |θ2).
Assumption 4. The function J(θ) has an upper bound in Θ, i.e., J∗ = supθ∈Θ J(θ).
Assumptions 1 and 2 are commonly used in the PG algorithms (Papini et al., 2018; Xu et al., 2019a;b). Assumption 3 is widely used in the study of variance reduced PG 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, e.g., in soft-max policy it is bounded by ec‖θ1−θ2‖ 2
for all θ1, θ2 ∈ Θ. More recently, (Zhang et al., 2021) used a simple truncated update to relieve this uncheckable importance weight assumption. Assumption 4 guarantees the feasibility of the problem (4). Note that Assumption 2 and Assumption 4 are satisfied automatically given Assumption 1 and the fact that all the rewards are bounded, i.e., |r(s, a)| ≤ R for any s ∈ S and a ∈ A. For example, due to |r(s, a)| ≤ R, we have |J(θ)| ≤ R1−γ . So we have J∗ = R1−γ .

heading: 5.1 CONVERGENCE ANALYSIS OF BGPO ALGORITHM
text: In the subsection, we provide convergence properties of the BGPO algorithm. The detailed proof is provided in Appendix A.1. Theorem 1. Assume the sequence {θk}Kk=1 be generated from Algorithm 1. Let ηk = b(m+k)1/2 for all k ≥ 1, 0 < λ ≤ νm 1/2
9Lb , b > 0, 8Lλ ν ≤ c ≤
m1/2
b , and m ≥ max{b 2, (cb)2}, we have
1
K K∑ k=1 E‖Bψkλ,〈∇f(θk),θ〉(θk)‖ ≤ 2 √ 2Mm1/4 K1/2 + 2 √ 2M K1/4 ,
where M = J ∗−J(θ1) νλb + σ2 νλLb + mσ2
νλLb ln(m+K). Remark 1. Without loss of generality, let b = O(1), m = O(1) and λ = O(1), we have M = O(ln(m + K)) = Õ(1). Theorem 1 shows that the BGPO algorithm has a convergence rate of Õ( 1
K1/4 ). Let K− 1 4 ≤ , we have K = Õ( −4). 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 = O( −4) for finding an -stationary point.

heading: 5.2 CONVERGENCE ANALYSIS OF VR-BGPO ALGORITHM
text: In the subsection, we give convergence properties of the VR-BGPO algorithm. The detailed proof is provided in Appendix A.2. Theorem 2. Suppose the sequence {θk}Kk=1 be generated from Algorithm 2. Let ηk = b(m+k)1/3 for all k ≥ 0, 0 < λ ≤ νm 1/3
5L̂b , b > 0, c ∈
[ 2
3b3 + 20L̂2λ2 ν2 , m2/3 b2
] and m ≥ max ( 2, b3, (cb)3, ( 56b ) 2/3 ) ,
we have
1
K K∑ k=1 E‖Bψkλ,〈∇f(θk),θ〉(θk)‖ ≤ 2 √ 2M ′m1/6 K1/2 + 2 √ 2M ′ K1/3 , (14)
where M ′ = J ∗−J(θ1) bνλ + m1/3σ2 16b2L̂2λ2 + c 2σ2b2 8L̂2λ2 , L̂2 = L2 + 2G2C2w, G = CgR/(1 − γ)2 and Cw =√
H(2HC2g + Ch)(W + 1).
Remark 2. Without loss of generality, let b = O(1), m = O(1) and λ = O(1), we have M = O(ln(m + K)) = Õ(1). Theorem 2 shows that the VR-BGPO algorithm has a convergence rate of Õ( 1
K1/3 ). Let K− 1 3 ≤ , we have K = ( −3). Since the VR-BGPO algorithm only needs
one trajectory to estimate the stochastic policy gradient at each iteration and runs K iterations, it reaches a lower sample complexity of 1 ·K = Õ( −3) for finding an -stationary point.

heading: 6 EXPERIMENTS
text: 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 VRBGPO), and then we compare our VR-BGPO algorithm with other state-of-the-art methods such as TRPO (Schulman et al., 2015a), PPO (Schulman et al., 2017), ProxHSPGA (Pham et al., 2020), VRMPO (Yang et al., 2019), and MDPO (Tomar et al., 2020).

heading: 6.1 EFFECTS OF BREGMAN DIVERGENCES
text: In the subsection, we examine how different Bregman divergences affect the performance of our algorithms. In the first setting, we let mirror mapping ψk(x) = ‖x‖p (p ≥ 1) with different p to test the performance our algorithms. Let ψ∗k(y) = ( ∑d i=1 |yi|q) 1 q be the conjugate mapping of ψk(x), where p−1 + q−1 = 1, p, q > 1. According to (Beck & Teboulle, 2003), when Θ = Rd, the update of θ̃k+1 in our algorithms can be calculated by θ̃k+1 = ∇ψ∗k(∇ψk(θk) + λuk), where ∇ψk(xj) and ∇ψ∗k(yj) are p-norm link functions, and ∇ψk(xj) = sign(xj)|xj |p−1
‖x‖p−2p , ∇ψ∗k(yj) =
sign(yj)|yj |q−1
‖y‖q−2q , and j is the coordinate index of x and y. In the second setting, we apply diagonal term on the mirror mapping ψk(x) = 12x TMkx, where Mk is a diagonal matrix with positive
values. In the experiments, we generate Hk = diag( √ vk + α), vk = βvk−1 + (1 − β)u2k, and α > 0, β ∈ (0, 1), as in Super-Adam algorithm (Kingma & Ba, 2014; Huang et al., 2021). Then we have Dψk(y, x) = 1 2 (y − x)
THk(y − x). Under this setting, the update of θ̃k+1 can also be analytically solved θ̃k+1 = θk − λH−1k uk. To test the effectiveness of two different Bregman divergences, we evaluate them on three classic control environments from gym Brockman et al. (2016): CartPole-v1, Acrobat-v1, and MountainCarContinuous-v0. 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 a fair comparison, all settings use the same initialization for policies. We run each setting five times and plot the mean and variance of average returns. For lp-norm mapping, we test three different values of p = (1.50, 2.0, 3.0). For diagonal mapping, we set β = 0.999 and α = 10−8. We set hyperparameters {b,m, c} to be the same. λ still needs to be tuned for different p to achieve relatively good performance. For simplicity, we use BGPO-Diag to represent BGPO with diagonal mapping, and we use BGPO-lp to represent BGPO with lp-norm mapping. Details about the setup of environments and hyperparameters are provided in the Appendix B.
From Fig. 1, we can find that BGPO-Diag largely outperforms BGPO-lp with different choices of p. The parameter tuning of BGPO-lp is much more difficult than BGPO-Diag because each p requires an individual λ to achieve the desired performance.

heading: 6.2 COMPARISON BETWEEN BGPO AND VR-BGPO
text: 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 ψ, since it performs much better than lp-norm. From Fig. 2, we can see that VR-BGPO can outperform BGPO in all three 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 is more difficult compared to CartPole.

heading: 6.3 COMPARE TO OTHER METHODS
text: In this subsection, we apply our BGPO and VR-BGPO algorithms to compare with the other methods. For our BGPO and VR-BGPO, we use diagonal mapping for ψ. For VRMPO, we follow their implementation and use lp-norm for ψ. For MDPO, ψ is the negative Shannon entropy, and the Bregman divergence becomes KL-divergence.
To evaluate the performance of these algorithms, we test them on six gym (Brockman et al., 2016) environments with continuous control tasks: Inverted-DoublePendulum-v2, Walker2d-v2, Reacherv2, Swimmer-v2, Inverted-Pendulum-v2 and HalfCheetah-v2. We use Gaussian policies and Gaussian value functions for all environments, and both of them are parameterized by MLPs. To ensure a fair comparison, all policies use the same initialization. For TRPO and PPO, we use the implementations 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 B.
From Fig. 3, we can find that our VR-BGPO method consistently outperforms all the other methods. 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 a proper variance-reduced technique can 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 it can not outperform PPO or TRPO in Swimmer and InvertedDoublePendulum. VRMPO only outperforms PPO and TRPO in Reacher and InvertedDoublePendulum. The undesirable performance of VRMPO is probably because it uses lp norm for ψ, which requires careful tuning of learning rate.

heading: 7 CONCLUSION
text: In the paper, we proposed a novel Bregman gradient policy optimization framework for reinforcement learning based on mirror descent iteration and momentum techniques. Moreover, we studied convergence properties of the proposed methods under the nonconvex setting.

heading: A APPENDIX
text: 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(τ |θ) is L-Lipschitz differential, i.e., ‖g(τ |θ1)−g(τ |θ2)‖ ≤ L‖θ1−θ2‖ for all θ1, θ2 ∈ Θ, where L = ChR/(1− γ)2;
2) J(θ) is L-smooth, i.e., ‖∇2J(θ)‖ ≤ L;
3) g(τ |θ) is bounded, i.e., ‖g(τ |θ)‖ ≤ G for all θ ∈ Θ with G = CgR/(1− γ)2. Lemma 2. (Lemma 6.1 in Xu et al. (2019a)) Under Assumptions 1 and 3, let w(τ |θk−1, θk) = g(τ |θk−1)/g(τ |θk), we have
V[w(τ |θk−1, θk)] ≤ C2w‖θk − θk−1‖2, (15) where Cw = √ H(2HC2g + Ch)(W + 1).
Lemma 3. (Lemma 1 in (Ghadimi et al., 2016)) LetX ⊆ Rd be a closed convex set, and φ : X → R be a convex function but possibly nonsmooth, and Dψ : X ×X → R is Bregman divergence related to the ν-strongly convex function ψ. Then we define
x+ = arg min z∈X
{ 〈g, z〉+ 1
λ Dψ(z, x) + φ(z)
} , ∀x ∈ X (16)
PX (x, g, λ) = 1
λ (x− x+), (17) where g ∈ Rd, λ > 0 and Dψ(z, x) = ψ(z) − ( ψ(x) + 〈∇ψ(x), z − x〉 ) . Then the following statement holds
〈g, PX (x, g, λ)〉 ≥ ν‖PX (x, g, λ)‖2 + 1
λ
[ φ(x+)− φ(x) ] . (18)
Lemma 4. (Proposition 1 in Ghadimi et al. (2016)) Let x+1 and x + 2 be given in (16) with g replaced by g1 and g2 respectively. Then let PX (x, g1, λ) and PX (x, g2, λ) be defined in (17) with x+ replaced by x+1 and x + 2 respectively. we have
‖PX (x, g1, λ)− PX (x, g2, λ)‖ ≤ 1
ν ‖g1 − g2‖. (19)
Lemma 5. (Lemma 1 in (Cortes et al., 2010)) Let w(x) = P (x)Q(x) be the importance weight for distributions P and Q. The following identities hold for the expectation, second moment, and variance of w(x)
E[w(x)] = 1, E[w2(x)] = d2(P ||Q), V[w(x)] = d2(P ||Q)− 1, (20)
where d2(P ||Q) = 2D(P ||Q), and D(P ||Q) is Rényi divergence between distributions P and Q. Lemma 6. Suppose that the sequence {θk}Kk=1 be generated from Algorithms 1 or 2. Let 0 < ηk ≤ 1 and 0 < λ ≤ ν2Lηk , then we have
f(θk+1)− f(θk) ≤ ηkλ
ν ‖∇f(θk)− uk‖2 − νηk 2λ ‖θ̃k+1 − θk‖2. (21)
Proof. According to Assumption 1 and Lemma 1, the function f(θ) is L-smooth. Then we have
f(θk+1) ≤ f(θk) + 〈∇f(θk), θk+1 − θk〉+ L
2 ‖θk+1 − θk‖2 (22)
= f(θk) + ηk〈∇f(θk), θ̃k+1 − θk〉+ Lη2k
2 ‖θ̃k+1 − θk‖2
= f(θk) + ηk〈∇f(θk)− uk, θ̃k+1 − θk〉+ ηk〈uk, θ̃k+1 − θk〉+ Lη2k
2 ‖θ̃k+1 − θk‖2,
where the second equality is due to θk+1 = θk + ηk(θ̃k+1 − θk). By the step 4 of Algorithm 1 or 2, we have θ̃k+1 = arg minθ∈Θ { 〈uk, θ〉+ 1λDψk(θ, θk) } . By using Lemma 3 with φ(·) = 0, we have
〈uk, 1
λ (θk − θ̃k+1)〉 ≥ ν‖
1 λ (θk − θ̃k+1)‖2. (23)
Thus, we can obtain
〈uk, θ̃k+1 − θk〉 ≤ − ν
λ ‖θ̃k+1 − θk‖2. (24)
According to the Cauchy-Schwarz inequality and Young’s inequality, we have
〈∇f(θk)− uk, θ̃k+1 − θk〉 ≤ ‖∇f(θk)− uk‖‖θ̃k+1 − θk‖
≤ λ ν ‖∇f(θk)− uk‖2 + ν 4λ ‖θ̃k+1 − θk‖2. (25)
Combining the inequalities (22), (24) with (25), we obtain
f(θk+1) ≤ f(θk) + ηk〈∇f(θk)− uk, θ̃k+1 − θk〉+ ηk〈uk, θ̃k+1 − θk〉+ Lη2k
2 ‖θ̃k+1 − θk‖2
≤ f(θk) + ηkλ
ν ‖∇f(θk)− uk‖2 + νηk 4λ ‖θ̃k+1 − θk‖2 − νηk λ ‖θ̃k+1 − θk‖2 + Lη2k 2 ‖θ̃k+1 − θk‖2
= f(θk) + ηkλ
ν ‖∇f(θk)− uk‖2 − νηk 2λ ‖θ̃k+1 − θk‖2 − (νηk 4λ − Lη 2 k 2 ) ‖θ̃k+1 − θk‖2
≤ f(θk) + ηkλ
ν ‖∇f(θk)− uk‖2 − νηk 2λ ‖θ̃k+1 − θk‖2, (26)
where the last inequality is due to 0 < λ ≤ ν2Lηk .
A.1 CONVERGENCE ANALYSIS OF BGPO ALGORITHM
In this subsection, we analyze the convergence properties of BGPO algorithm. Lemma 7. Assume the stochastic policy gradient uk+1 be generated from Algorithm 1, given 0 < βk ≤ 1, we have
E‖∇f(θk+1)− uk+1‖2 ≤ (1− βk+1)E‖∇f(θk)− uk‖2 + 2
βk+1 L2η2kE‖θ̃k+1 − θk‖2 + β2k+1σ2.
Proof. By the definition of uk+1 in Algorithm 1, we have
uk+1 − uk = −βk+1uk − βk+1g(τk+1|θk+1). (27) Since∇f(θk) = −J(θk) for all k ≥ 1, we have
E‖∇f(θk+1)− uk+1‖2
= E‖ − ∇J(θk)− uk −∇J(θk+1) +∇J(θk)− (uk+1 − uk)‖2
= E‖ − ∇J(θk)− uk −∇J(θk+1) +∇J(θk) + βk+1uk + βk+1g(τk+1|θk+1)‖2 = E‖(1− βk+1)(−∇J(θk)− uk) + βk+1(−∇J(θk+1) + g(τk+1|θk+1)) + (1− βk+1) ( −∇J(θk+1) +∇J(θk) ) ‖2
= (1− βk+1)2E‖∇J(θk) + uk +∇J(θk+1)−∇J(θk)‖2 + β2k+1E‖∇J(θk+1)− g(τk+1|θk+1)‖2
≤ (1− βk+1)2(1 + βk+1)E‖∇J(θk) + uk‖2 + (1− βk+1)2(1 + 1
βk+1 )E‖∇J(θk+1)−∇J(θk)‖2
+ β2k+1E‖∇J(θk+1)− g(τk+1|θk+1)‖2
≤ (1− βk+1)E‖∇J(θk) + uk‖2 + 2
βk+1 E‖∇J(θk+1)−∇J(θk)‖2 + β2k+1E‖∇J(θk+1)− g(τk+1|θk+1)‖2
≤ (1− βk+1)E‖∇J(θk) + uk‖2 + 2
βk+1 L2E‖θk+1 − θk‖2 + β2k+1E‖∇J(θk+1)− g(τk+1|θk+1)‖2
≤ (1− βk+1)E‖∇f(θk)− uk‖2 + 2
βk+1 L2η2kE‖θ̃k+1 − θk‖2 + β2k+1σ2, (28)
where the fourth equality holds by Eτk+1∼p(τ |θk+1)[g(τk+1|θk+1)] = ∇J(θk+1); the first inequality holds by Young’s inequality; the second inequality is due to 0 < βk+1 ≤ 1 such that (1−βk+1)2(1+ βk+1) = 1− βk+1 − β2k+1 + β3k+1 ≤ 1− βk+1 and (1− βk+1)2(1 + 1βk+1 ) ≤ 1 + 1 βk+1
≤ 2βk+1 ; the last inequality holds by Assumption 2.
Theorem 3. Assume the sequence {θk}Kk=1 be generated from Algorithm 1. Let ηk = b(m+k)1/2 for all k ≥ 1, 0 < λ ≤ νm 1/2
9Lb , b > 0, 8Lλ ν ≤ c ≤
m1/2
b , and m ≥ max{b 2, (cb)2}, we have
1
K K∑ k=1 E‖Bψkλ,〈∇f(θk),θ〉(θk)‖ ≤ 2 √ 2Mm1/4 K1/2 + 2 √ 2M K1/4 ,
where M = J ∗−J(θ1) νλb + σ2 νλLb + mσ2 νλLb ln(m+K).
Proof. Since ηk = b(m+k)1/2 is decreasing on k, we have ηk ≤ η0 = b m1/2 ≤ 1 for all k ≥ 0. At the same time, let m ≥ (cb)2, we have βk+1 = cηk ≤ cη0 = cbm1/2 ≤ 1. Consider m ≥ (cb) 2, we have c ≤ m 1/2
b . Since 0 < λ ≤ νm1/2 9Lb , we have λ ≤ νm1/2 9Lb ≤ νm1/2 2Lb = ν 2Lη0 ≤ ν2Lηk for all k ≥ 0.
According to Lemma 7, we have
E‖∇f(θk+1)− uk+1‖2 − E‖∇f(θk)− uk‖2
≤ −βk+1E‖∇f(θk)− uk‖2 + 2
βk+1 L2η2kE‖θ̃k+1 − θk‖2 + β2k+1σ2
= −cηkE‖∇f(θk)− uk‖2 + 2L2
c ηkE‖θ̃k+1 − θk‖2 + c2η2kσ2
= −8Lλ ν ηkE‖∇f(θk)− uk‖2 + Lν 4λ ηkE‖θ̃k+1 − θk‖2 +
mη2kσ 2
b2 , (29)
where the first equality is due to βk+1 = cηk and the last equality holds by 8Lλν ≤ c ≤ m1/2 b . Next we define a Lyapunov function Φk = E [ f(θk) + 1 L‖∇f(θk)− uk‖ 2 ]
for any t ≥ 1. Then we have
Φk+1 − Φk = E [ f(θk+1)− f(θk) + 1
L
( ‖∇f(θk+1)− uk+1‖2 − ‖∇f(θk)− uk‖2 )] ≤ ληk
ν E‖∇f(θk)− uk‖2 − νηk 2λ E‖θ̃k+1 − θk‖2 − 8ληk ν E‖∇f(θk)− uk‖2
+ νηk 4λ E‖θ̃k+1 − θk‖2 + mη2kσ 2 Lb2
≤ − λ 4ν ηkE‖∇f(θk)− uk‖2 − ν 4λ ηkE‖θ̃k+1 − θk‖2 +
mη2kσ 2
Lb2 , (30)
where the first inequality follows by the Lemma 6 and the above inequality (29).
Summing the above inequality (30) over k from 1 to K, we can obtain
K∑ k=1 E[ λ 4ν ηkE‖∇f(θk)− uk‖2 + ν 4λ ηkE‖θ̃k+1 − θk‖2]
≤ Φ1 − ΦK+1 + mσ2
Lb2 K∑ k=1 η2k
= f(θ1)− f(θK+1) + 1
L ‖∇f(θ1)− u1‖2 −
1 L ‖∇f(θK+1)− uK+1‖2 +
mσ2
Lb2 K∑ k=1 η2k
≤ J(θK+1)− J(θ1) + 1
L ‖∇J(θ1)− g(τ1|θ1)‖2 +
mσ2
Lb2 K∑ k=1 η2k
≤ J∗ − J(θ1) + σ2 L + mσ2 L ∫ K 1 1 m+ k dk ≤ J∗ − J(θ1) + σ2
L + mσ2 L ln(m+K), (31)
where the last second inequality holds by Assumptions 2 and 4.
Since ηk is decreasing, we have
1
K K∑ k=1 E[ 1 4ν2 E‖∇f(θk)− uk‖2 + 1 4λ2 E‖θ̃k+1 − θk‖2] ≤ J ∗ − J(θ1) KνληK + σ2 KνλLηK + mσ2 νλLKηK ln(m+K)
≤ ( J∗ − J(θ1)
νλb +
σ2 νλLb + mσ2 νλLb ln(m+K)
) (m+K)1/2
K . (32)
Let M = J ∗−J(θ1) νλb + σ2 νλLb + mσ2 νλLb ln(m+K), the above inequality (32) reduces to
1
K K∑ k=1 E[ 1 4ν2 E‖∇f(θk)− uk‖2 + 1 4λ2 E‖θ̃k+1 − θk‖2] ≤ M K (m+K)1/2. (33)
According to Jensen’s inequality, we have
1
K K∑ k=1 E [ 1 2ν ‖∇f(θk)− uk‖+ 1 2λ ‖θ̃k+1 − θk‖ ] ≤ ( 2 K K∑ k=1 E [ 1 4ν2 ‖∇f(θk)− uk‖2 + 1 4λ2 ‖θ̃k+1 − θk‖2
])1/2 ≤ √ 2M
K1/2 (m+K)1/4 ≤
√ 2Mm1/4
K1/2 +
√ 2M K1/4 , (34)
where the last inequality is due to the inequality (a+ b)1/4 ≤ a1/4 + b1/4 for all a, b ≥ 0. Thus we have
1
K K∑ k=1 E [1 ν ‖∇f(θk)− uk‖+ 1 λ ‖θ̃k+1 − θk‖ ] ≤ 2 √ 2Mm1/4 K1/2 + 2 √ 2M K1/4 . (35)
By the step 4 of Algorithm 1, we have
Bψkλ,〈uk,θ〉(θk) = PΘ(θk, uk, λ) = 1
λ
( θk − θ̃k+1 ) . (36)
At the same time, as in Ghadimi et al. (2016), we define
Bψkλ,〈∇f(θk),θ〉(θk) = PΘ(θk,∇f(θk), λ) = 1
λ
( θk − θ+k+1 ) , (37)
where
θ+k+1 = arg min θ∈Θ
{ 〈∇f(θk), θ〉+ 1
λ Dψk(θ, θk)
} . (38)
According to the above Lemma 4, we have ‖Bψkλ,〈uk,θ〉(θk)−B ψk λ,〈∇f(θk),θ〉(θk)‖ ≤ 1 ν ‖uk−∇f(θk)‖. Then we have
‖Bψkλ,〈∇f(θk),θ〉(θk)‖ ≤ ‖B ψk λ,〈uk,θ〉(θk)‖+ ‖B ψk λ,〈uk,θ〉(θk)− B ψk λ,〈∇f(θk),θ〉(θk)‖
≤ ‖Bψkλ,〈uk,θ〉(θk)‖+ 1 ν ‖uk −∇f(θk)‖ = 1
λ ‖θ̃k+1 − θk‖+
1 ν ‖uk −∇f(θk)‖. (39)
By the above inequalities (35) and (39), we have
1
K K∑ k=1 E‖Bψkλ,〈∇f(θk),θ〉(θk)‖ ≤ 2 √ 2Mm1/4 K1/2 + 2 √ 2M K1/4 . (40)
A.2 CONVERGENCE ANALYSIS OF VR-BGPO ALGORITHM
In this subsection, we will analyze convergence properties of the VR-BGPO algorithm. Lemma 8. Assume that the stochastic policy gradient uk+1 be generated from Algorithm 2, given 0 < βk ≤ 1, we have
E‖∇f(θk+1)− uk+1‖2 ≤ (1− βk+1)E‖∇f(θk)− uk‖2 + 4L̂2η2k‖θ̃k+1 − θk‖2 + 2β2k+1σ2, where L̂2 = L2 + 2G2C2w and Cw = √ H(2HC2g + Ch)(W + 1).
Proof. By the definition of uk+1 in Algorithm 2, we have
uk+1 − uk = −βk+1uk − βk+1g(τk+1|θk+1) + (1− βk+1) ( − g(τk+1|θk+1) + w(τk+1|θk, θk+1)g(τk+1|θk) ) .
Since∇f(θk+1) = −∇J(θk+1), we have
E‖∇f(θk+1)− uk+1‖2
= E‖∇J(θk) + uk +∇J(θk+1)−∇J(θk) + (uk+1 − uk)‖2 (41) = E‖∇J(θk) + uk +∇J(θk+1)−∇J(θk)− βk+1uk − βk+1g(τk+1|θk+1)
+ (1− βk+1) ( − g(τk+1|θk+1) + w(τk+1|θk, θk+1)g(τk+1|θk) ) ‖2
= E‖(1− βk+1)(∇J(θk) + uk) + βk+1(∇J(θk+1)− g(τk+1|θk+1)) − (1− βk+1) ( g(τk+1|θk+1)− w(τk+1|θk, θk+1)g(τk+1|θk)− (∇J(θk+1)−∇J(θk)) ) ‖2
= (1− βk+1)2E‖∇J(θk) + uk‖2 + E‖βk+1(∇J(θk+1)− g(τk+1|θk+1)) − (1− βk+1) ( g(τk+1|θk+1)− w(τk+1|θk, θk+1)g(τk+1|θk)− (∇J(θk+1)−∇J(θk)) ) ‖2
≤ (1− βk+1)2E‖∇J(θk) + uk‖2 + 2β2k+1E‖∇J(θk+1)− g(τk+1|θk+1)‖2
+ 2(1− βk+1)2E‖g(τk+1|θk+1)− w(τk+1|θk, θk+1)g(τk+1|θk)− (∇J(θk+1)−∇J(θk))‖2
≤ (1− βk+1)E‖∇f(θk)− uk‖2 + 2β2k+1σ2 + 2E‖g(τk+1|θk+1)− w(τk+1|θk, θk+1)g(τk+1|θk)‖2︸ ︷︷ ︸ =T1 ,
where the forth equality holds by Eτk+1∼p(τ |θk+1)[g(τk+1|θk+1)] = ∇J(θk+1) and Eτk+1∼p(τ |θk+1)[g(τk+1|θk+1) − w(τk+1|θk, θk+1)g(τk+1|θk)] = ∇J(θk+1) − ∇J(θk); the second last inequality follows by Young’s inequality; and the last inequality holds by Assumption 2, and the inequality E‖ζ − E[ζ]‖2 = E‖ζ‖2 − (E[ζ])2 ≤ E‖ζ‖2, and 0 < βk+1 ≤ 1. Next, we give an upper bound of the term T1 as follows:
T1 = E‖g(τk+1|θk+1)− w(τk+1|θk, θk+1)g(τk+1|θk)‖2
= E‖g(τk+1|θk+1)− g(τk+1|θk) + g(τk+1|θk)− w(τk+1|θk, θk+1)g(τk+1|θk)‖2
≤ 2E‖g(τk+1|θk+1)− g(τk+1|θk)‖2 + 2E‖(1− w(τk+1|θk, θk+1))g(τk+1|θk)‖2
≤ 2L2‖θk+1 − θk‖2 + 2G2E‖1− w(τk+1|θk, θk+1)‖2 = 2L2‖θk+1 − θk‖2 + 2G2V ( w(τk+1|θk, θk+1) ) ≤ 2(L2 + 2G2C2w)‖θk+1 − θk‖2, (42)
where the second inequality holds by Lemma 1, and the third equality holds by Lemma 5, and the last inequality follows by Lemma 2.
Combining the inequalities (41) with (42), let L̂2 = L2 + 2G2C2w, we have
E‖∇f(θk+1)− uk+1‖2 ≤ (1− βk+1)E‖∇f(θk)− uk‖2 + 2β2k+1σ2 + 4L̂2‖θk+1 − θk‖2
= (1− βk+1)E‖∇f(θk)− uk‖2 + 2β2k+1σ2 + 4L̂2η2k‖θ̃k+1 − θk‖2.
Theorem 4. Suppose the sequence {θk}Kk=1 be generated from Algorithm 2. Let ηk = b(m+k)1/3 for all k ≥ 0, 0 < λ ≤ νm 1/3
5L̂b , b > 0, 23b3 +
20L̂2λ2 ν2 ≤ c ≤ m2/3 b2 and m ≥ max ( 2, b3, (cb)3, ( 56b ) 2/3 ) ,
we have
1
K K∑ k=1 E‖Bψkλ,〈∇f(θk),θ〉(θk)‖ ≤ 2 √ 2M ′m1/6 K1/2 + 2 √ 2M ′ K1/3 , (43)
where M ′ = J ∗−J(θ1) bνλ + m1/3σ2 16b2L̂2λ2 + c 2σ2b2 8L̂2λ2 and L̂2 = L2 + 2G2C2w.
Proof. Since ηk = b(m+k)1/3 on k is decreasing and m ≥ b 3, we have ηk ≤ η0 = bm1/3 ≤ 1. Due to L̂ = √ L2 + 2G2C2w ≥ L, we have 0 < λ ≤ νm 1/3 5L̂b ≤ νm 1/3 2Lb = ν 2Lη0 ≤ ν2Lηk for any k ≥ 0. Consider 0 < ηk ≤ 1 and m ≥ (cb)3, we have βk+1 = cη2k ≤ cb 2 m2/3 ≤ 1. At the same time, we have c ≤ m 2/3
b2 . According to Lemma 8, we have
1
ηk E‖∇f(θk+1)− uk+1‖2 −
1
ηk−1 E‖∇f(θk)− uk‖2
≤ (1− βk+1
ηk − 1 ηk−1
) E‖∇f(θk)− uk‖2 + 2β2k+1σ 2
ηk + 4L̂2ηk‖θ̃k+1 − θk‖2
= ( 1 ηk − 1 ηk−1 − cηk ) E‖∇f(θk)− uk‖2 + 2c2η3kσ2 + 4L̂2ηk‖θ̃k+1 − θk‖2
= (1 b ( (m+ k) 1 3 − (m+ k − 1) 13 ) − cηk ) E‖∇f(θk)− uk‖2 + 2c2η3kσ2 + 4L̂2ηk‖θ̃k+1 − θk‖2
≤ ( 2
3b3 ηk − cηk
) E‖∇f(θk)− uk‖2 + 2c2η3kσ2 + 4L̂2ηk‖θ̃k+1 − θk‖2, (44)
where the last inequality holds by the following inequality
(m+ k) 1 3 − (m+ k − 1) 13 ≤ 1 3(m+ k − 1)2/3 ≤ 1 3 ( m/2 + k )2/3 ≤ 2 2/3
3(m+ k)2/3 =
22/3 3b2 b2 (m+ k)2/3 = 22/3 3b2 η2k ≤ 2 3b2 ηk, (45)
where the first inequality holds by the concavity of function f(x) = x1/3, i.e., (x + y)1/3 ≤ x1/3 + y
3x2/3 ; the second inequality is due to m ≥ 2, and the last inequality is due to 0 < ηk ≤ 1.
Let c ≥ 23b3 + 20L̂2λ2 ν2 , we have
1
ηk E‖∇f(θk+1)− uk+1‖2 −
1
ηk−1 E‖∇f(θk)− uk‖2
≤ −20L̂ 2λ2
ν2 ηkE‖∇f(θk)− uk‖2 + 2c2η3kσ2 + 4L̂2ηk‖θ̃k+1 − θk‖2. (46)
Here we simultaneously consider c ≥ 23b3 + 20L̂2λ2 ν2 , c ≤ m2/3 b2 and 0 < λ ≤ νm1/3 5L̂b , we have
2
3b3 +
20L̂2λ2
ν2 ≤ 2 3b3 +
20L̂2 ν2 ν2m2/3 25L̂2b2 = 2 3b3 + 4m2/3 5b2 ≤ m 2/3 b2 . (47)
Then we have m ≥ ( 56b ) 2/3. Next we define a Lyapunov function Ωk = E [ f(θk) +
ν 16L̂2ληk−1
‖∇f(θk) − uk‖2 ]
for any k ≥ 1. According to Lemma 6, we have
Ωk+1 − Ωk = f(θk+1)− f(θk) + ν
16L̂2λ
( 1
ηk E‖∇f(θk+1)− uk+1‖2 −
1
ηk−1 E‖∇f(θk)− uk‖2 ) ≤ ηkλ
ν ‖∇f(θk)− uk‖2 − νηk 2λ ‖θ̃k+1 − θk‖2 − 5ληk 4ν E‖∇f(θk)− uk‖2
+ νηk 4λ E‖θ̃k+1 − θk‖2 + νc2η3kσ 2
8L̂2λ
≤ −ληk 4ν E‖∇f(θk)− uk‖2 − νηk 4λ E‖θ̃k+1 − θk‖2 + νc2η3kσ 2 8L̂2λ , (48)
where the first inequality is due to the above inequality (46). Thus, we can obtain
ληk 4ν E‖∇f(θk)− uk‖2 + νηk 4λ E‖θ̃k+1 − θk‖2 ≤ Ωk − Ωk+1 + νc2η3kσ 2 8L̂2λ . (49)
Taking average over k = 1, 2, · · · ,K on both sides of (49), we have
1
T K∑ k=1 E [ληk 4ν E‖∇f(θk)− uk‖2 + νηk 4λ E‖θ̃k+1 − θk‖2 ]
≤ f(θ1)− f(θK+1) K + ν‖∇f(θ1)− u1‖2 16L̂2η0λK − ν‖∇f(θK+1)− uK+1‖ 2 16L̂2ηKλK + 1 K K∑ k=1 νc2η3kσ 2 8L̂2λ
≤ J(θK+1)− J(θ1) K + νσ2
16L̂2η0λK +
1
K K∑ k=1 νc2η3kσ 2 8L̂2λ
≤ J ∗ − J(θ1) K + νσ2
16L̂2η0λK +
1
K K∑ k=1 νc2η3kσ 2 8L̂2λ , (50)
where the second inequality is due to u1 = −g(τ1|θ1), ∇f(θ1) = −∇J(θ1) and Assumption 1, and the last inequality holds by Assumption 2. Since ηk is decreasing, i.e., η−1K ≥ η −1 k for any
0 < k ≤ K, we have
1
K K∑ k=1 E [ 1 4ν2 E‖∇f(θk)− uk‖2 + 1 4λ2 E‖θ̃k+1 − θk‖2 ] ≤ J
∗ − J(θ1) KνληK + σ2 16L̂2ηKη0λ2K + 1 KληK K∑ k=1 c2η3kσ 2 8L̂2λ
≤ J ∗ − J(θ1) KνληK + m1/3σ2 16bL̂2λ2ηKK +
c2σ2
8L̂2λ2KηK ∫ K 1 b3 m+ k dk
≤ J ∗ − J(θ1) KληK + m1/3σ2 16bL̂2λ2ηKK + c2σ2b3 8L̂2λ2KηK ln(m+K)
=
( J∗ − J(θ1)
bνλ +
m1/3σ2 16b2L̂2λ2 + c2σ2b2 8L̂2λ2
) (m+K)1/3
K , (51)
where the second inequality holds by ∑K k=1 η 3 kdk ≤ ∫K 1 η3kdk = b 3 ∫K 1 (m+ k)−1dk.
Let M ′ = J ∗−J(θ1) bνλ + m1/3σ2 16b2L̂2λ2 + c 2σ2b2 8L̂2λ2 , the above inequality (51) reduces to
1
K K∑ k=1 E [ 1 4ν2 ‖∇f(θk)− uk‖2 + 1 4λ2 ‖θ̃k+1 − θk‖2 ] ≤ M ′ K (m+K)1/3. (52)
According to Jensen’s inequality, we have
1
K K∑ k=1 E [ 1 2ν ‖∇f(θk)− uk‖+ 1 2λ ‖θ̃k+1 − θk‖ ] ≤ ( 2 K K∑ k=1 E [ 1 4ν2 ‖∇f(θk)− uk‖2 + 1 4λ2 ‖θ̃k+1 − θk‖2
])1/2 ≤ √ 2M ′
K1/2 (m+K)1/6 ≤
√ 2M ′m1/6
K1/2 +
√ 2M ′
K1/3 , (53)
where the last inequality is due to the inequality (a+ b)1/6 ≤ a1/6 + b1/6 for all a, b ≥ 1. Thus we have
1
K K∑ k=1 E [1 ν ‖∇f(θk)− uk‖+ 1 λ ‖θ̃k+1 − θk‖ ] ≤ 2 √ 2M ′m1/6 K1/2 + 2 √ 2M ′ K1/3 . (54)
Then by using the above inequality (39), we can obtain
1
K K∑ k=1 E‖Bψkλ,〈∇f(θk),θ〉(θk)‖ ≤ 2 √ 2M ′m1/6 K1/2 + 2 √ 2M ′ K1/3 . (55)

heading: B DETAILED SETUP OF EXPERIMENTAL ENVIRONMENTS AND HYPER-PARAMETERS
text: In this section, we provide the detailed setup of experimental environments and hyper-parameters. We first provide the detailed setup of our experiments in Tab. 2 and Tab. 3. We use ADAM optimizer to optimize value functions for all methods and settings, which is a common practice. The importance sampling weight used for VR-BGPO algorithm is clipped within [0.5, 1.5]. The momentum term βk is set to be less or equal than one (βk = min(βk, 1.0) ) through the whole training process.
BGPO and VR-BGPO algorithms involve 4 hyper-parameters {λ, b,m, c}, which may bring additional efforts for hyper-parameter tuning. However, the actual hyper-parameter tuning is not so hard, and we only use one set of {b,m, c} for 9 environments. The strategy of hyper-parameter tuning is to separate the four hyper-parameters into two parts. The first part is {b,m, c}, which mainly decide when the momentum term βk actually affects (βk < 1.0) updates. The second part, λ, only affects how fast the policy is learning. To further reduce the complexity of hyper-parameter tuning, we always set m = 2.0. By grouping hyper-parameters, we only consider λ and how βk changes, which largely simplifies the process of hyper-parameter tuning.

Review summaries:
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.    

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.

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.