Year: 2019

Abstract:
Improving sample efficiency has been a longstanding goal in reinforcement learning. In this paper, we propose the VRMPO: a sample efficient policy gradient method with stochastic mirror descent. A novel variance reduced policy gradient estimator is the key of VRMPO to improve sample efficiency. Our VRMPO needs only O( −3) sample trajectories to achieve an -approximate first-order stationary point, which matches the best-known sample complexity. We conduct extensive experiments to show our algorithm outperforms state-of-the-art policy gradient methods in various settings.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) is one of the most wonderful fields of artificial intelligence, and it has achieved great progress recently (Mnih et al., 2015; Silver et al., 2017). To learn the optimal policy from the delayed reward decision system is the fundamental goal of RL. Policy gradient methods (Williams, 1992; Sutton et al., 2000) are powerful algorithms to learn the optimal policy.
Despite the successes of policy gradient method, suffering from high sample complexity is still a critical challenge for RL. Many existing popular methods require more samples to be collected for each step to update the parameters (Silver et al., 2014; Lillicrap et al., 2016; Schulman et al., 2015; Mnih et al., 2016; Haarnoja et al., 2018), which partially reduces the effectiveness of the sample. Although all the above existing methods claim it improves sample efficiency, they are all empirical results which lack a strong theory analysis of sample complexity.
To improve sample efficiency, in this paper, we explore how to design an efficient and stable algorithm with stochastic mirror descent (SMD). Due to its advantage of the simplicity of implementation, low memory requirement, and low computational complexity (Nemirovsky & Yudin, 1983; Beck & Teboulle, 2003; Lei & Tang, 2018), SMD is one of the most widely used methods in machine learning. However, it is not sound to apply SMD to policy optimization directly, and the challenges are two-fold: (I) The objective of policy-based RL is a typical non-convex function, but Ghadimi et al. (2016) show that it may cause instability and even divergence when updating the parameter of a non-convex objective function by SMD via a single batch sample. (II) Besides, the large variance of gradient estimator is the other bottleneck of applying SMD to policy optimization for improving sample efficiency. In fact, in reinforcement learning, the non-stationary sampling process with the environment leads to the large variance of existing methods on the estimate of policy gradient, which results in poor sample efficiency (Papini et al., 2018; Liu et al., 2018).
Contributions To address the above two problems correspondingly, in this paper (I) We analyze the theoretical dilemma of applying SMD to policy optimization. Our analysis shows that under the common Assumption 1, for policy-based RL, designing the algorithm via SMD directly can not guarantee the convergence. Hence, we propose the MPO algorithm with a provable convergence guarantee. Designing an efficiently computable, and unbiased gradient estimator by averaging its historical policy gradient is the key to MPO. (II) We propose the VRMPO: a sample efficient policy optimization algorithm via constructing a variance reduced policy gradient estimator. Specifically, we propose an efficiently computable policy gradient estimator, utilizing fresh information and yielding a more accurate estimation of the gradient w.r.t the objective, which is the key to improve sample efficiency. We prove VRMPO needs O( −3) sample trajectories to achieve an -approximate firstorder stationary point ( -FOSP) (Nesterov, 2004). To our best knowledge, our VRMPO matches the
best-known sample complexity among the existing literature. Besides, we conduct extensive experiments, which further show that our algorithm outperforms state-of-the-art bandit algorithms in various settings.

heading: 2 BACKGROUND AND NOTATIONS

heading: 2.1 POLICY-BASED REINFORCEMENT LEARNING
text: We consider the Markov decision processes M = (S,A,P,R, ρ0, γ), where S is state space, A is action space; At time t, the agent is in a state St ∈ S and takes an action At ∈ A, then it receives a feedback Rt+1; P ass′ = P (s
′ |s, a) ∈ P is the probability of the state transition from s to s′ under taking a ∈ A; The bounded reward function R : S × A → [−R,R], Ras 7→ E[Rt+1|St = s,At = a]; ρ0 : S → [0, 1] is the initial state distribution and γ ∈ (0, 1) is discounted factor. Policy πθ(a|s) is a probability distribution on S × A with the parameter θ ∈ Rp. Let τ = {st, at, rt+1}Hτt=0 be a trajectory, where s0 ∼ ρ0(s0), at ∼ πθ(·|st), rt+1 = R(st, at), st+1 ∼ P (·|st, at), and Hτ is the finite horizon of τ . The expected return J(πθ) is defined as:
J(θ) def = J(πθ) = ∫ τ P (τ |θ)R(τ)dτ = Eτ∼πθ [R(τ)], (1)
where P (τ |θ) = ρ0(s0) ∏Hτ t=0 P (st+1|st, at)πθ(at|st) is the probability of generating τ , R(τ) =∑Hτ
t=0 γ trt+1 is the accumulated discounted return.
Let J (θ) = −J(θ), the central problem of policy-based RL is to solve the problem: θ∗ = arg max
θ J(θ)⇐⇒ θ∗ = arg min θ J (θ). (2)
Computing the∇J(θ) analytically, we have
∇J(θ) = Eτ∼πθ [ Hτ∑ t=0 ∇θ log πθ(at|st)R(τ)]. (3)
For any trajectory τ , let g(τ |θ) = ∑Hτ t=0∇θ log πθ(at|st)R(τ), which is an unbiased estimator of ∇J(θ). Vanilla policy gradient (VPG) is a straightforward way to solve problem (2): θ ← θ + αg(τ |θ),
where α is step size. Assumption 1. (Sutton et al., 2000; Papini et al., 2018) For each pair (s, a), any θ ∈ Rp, and all components i, j, there exists positive constants G, F s.t.,
|∇θi log πθ(a|s)| ≤ G, | ∂2
∂θi∂θj log πθ(a|s)| ≤ F. (4)
According to the Lemma B.2 of (Papini et al., 2018), Assumption 1 implies ∇J(θ) is L-Lipschiz, i.e., ‖∇J(θ1)−∇J(θ2)‖ ≤ L‖θ1 − θ2‖, where
L = RH(HG2 + F )/(1− γ), (5) Besides, Assumption 1 implies the following property of the policy gradient estimator. Lemma 1 (Properties of stochastic differential estimators (Shen et al., 2019)). Under Assumption 1, for any policy πθ and τ ∼ πθ, we have
‖g(τ |θ)−∇J(θ)‖2 ≤ G 2R2
(1− γ)4 def = σ2. (6)

heading: 2.2 STOCHASTIC MIRROR DESCENT
text: Now, we review some basic concepts of SMD; in this section, the notation follows (Nemirovski et al., 2009). Let’s consider the stochastic optimization problem,
min θ∈Dθ
{f(θ) = E[F (θ; ξ)]}, (7)
where Dθ ∈ Rn is a nonempty convex compact set, ξ is a random vector whose probability distribution, µ is supported on Ξ ∈ Rd and F : Dθ × Ξ → R. We assume that the expectation E[F (θ; ξ)] = ∫ Ξ F (θ; ξ)dµ(ξ) is well defined and finite-valued for every θ ∈ Dθ. Definition 1 (Proximal Operator (Moreau, 1965)). T is a function defined on a closed convex X , and α > 0.Mψα,T (z) is the proximal operator of T , which is defined as:
Mψα,T (z) = arg min x∈X {T (x) + 1 α Dψ(x, z)}, (8)
where ψ(x) is a continuously-differentiable, ζ-strictly convex function: 〈x− y,∇ψ(x)−∇ψ(y)〉 ≥ ζ‖x−y‖2, ζ > 0,Dψ is Bregman distance:Dψ(x, y) = ψ(x)−ψ(y)−〈∇ψ(y), x−y〉, ∀ x, y ∈ X .
Stochastic Mirror Descent The SMD solves (7) by generating an iterative solution as follows,
θt+1 =Mψαt,`(θ)(θt) = arg minθ∈Dθ {〈gt, θ〉+
1
αt Dψ(θ, θt)}, (9)
where αt > 0 is step-size, `(θ) = 〈gt, θ〉 is the first-order approximation of f(θ) at θt, gt = g(θt, ξt) is stochastic subgradient such that g(θt) = E[g(θt, ξt)] ∈ ∂f(θ)|θ=θt , {ξt}t≥0 represents a draw form distribution µ, and ∂f(θ) = {g|f(θ)− f(ω) ≤ gT (θ − ω),∀ω ∈ dom(f)}.
If we choose ψ(x) = 1
2 ‖x‖22, which implies Dψ(x, y) =
1 2 ‖x − y‖22, since then iteration (9) is the
proximal gradient (Rockafellar, 1976) view of SGD. Thus, SMD is a generalization of SGD.
Convergence Criteria: Bregman Gradient Bregman gradient is a generation of projected gradient (Ghadimi et al., 2016). Recently, Zhang & He (2018); Davis & Grimmer (2019) develop it to measure the convergence of an algorithm for the non-convex optimization problem. Evaluating the difference between each candidate solution x and its proximity is the critical idea of Bregman gradient to measure the stationarity of x. Specifically, let X be a closed convex set on Rn, α > 0, T (x) is defined on X . The Bregman gradient of T at x ∈ X is:
Gψα,T (x) = α −1(x−Mψα,T (x)), (10)
whereMψα,T (·) is defined in Eq.(8). If ψ(x) = 1
2 ‖x‖22, then x∗ is a critical point of T if and only if
Gψα,T (x∗) = ∇T (x∗) = 0 (Bauschke et al. (2011);Theorem 27.1). Thus, Bregman gradient (10) is a generalization of gradient. The following Remark 1 is helpful for us to understand the significance of Bregman gradient, and it gives us some insights to understand this convergence criterion. Remark 1. Let T be a convex function, by the Proposition 5.4.7 of Bertsekas (2009): x∗ is a stationarity point of T if and only if
0 ∈ ∂(T + δX )(x∗), (11) where δX (·) is the indicator function on X . Furthermore, suppose ψ(x) is twice continuously differentiable, let x̃ =Mψα,T (x), by the definition of proximal operatorM ψ α,T (·), we have
0 ∈ ∂(T + δX )(x̃) + ( ∇ψ(x̃)−∇ψ(x) ) (?) ≈ ∂(T + δX )(x̃) + αGψα,T (x)∇ 2ψ(x), (12)
Eq.(?) holds due to the first-order Taylor expansion of∇ψ(x). By the criteria of (11), if Gψα,T (x) ≈ 0, Eq.(12) implies the origin point 0 is near the set ∂(T + δX )(x̃), i.e., x̃ is close to a stationary point.
In practice, we choose T (θ) = 〈−∇J(θt), θ〉, since then discriminant criterion (12) is suitable to RL problem (2). For the non-convex problem (2), we are satisfied with finding an -approximate First-Order Stationary Point ( -FOSP) (Nesterov, 2004), denoted by θ , such that
‖Gψα,T (θ )(θ )‖ ≤ . (13)

heading: 3 POLICY OPTIMIZATION WITH STOCHASTIC MIRROR DESCENT
text: In this section, we solve the problem (2) via SMD. Firstly, we analyze the theoretical dilemma of applying SMD directly to policy optimization. Then, we propose a convergent mirror policy optimization algorithm (MPO).

heading: 3.1 THEORETICAL DILEMMA
text: Let T = {τk}N−1k=0 be a collection of trajectories, τk ∼ πθk , we receive gradient information:
−g(τk|θk) = − Hτk∑ t=0 ∇θ log πθ(at|st)R(τk)|θ=θk , (14)
then by SMD (9), to solve (2), for each 0 ≤ k ≤ N − 1, we define the update rule as follows,
θk+1 =Mψαk,〈−g(τk|θk),θ〉(θk) = arg minθ {〈−g(τk|θk), θ〉+ 1 αk Dψ(θ, θk)}, (15)
where αk > 0 is step-size and other symbols are consistent to previous paragraphs. Due to −J(θ) is non-convex, according to (Ghadimi et al., 2016), a standard strategy for analyzing non-convex optimization methods is to pick up the output θ̃N randomly according to the following distribution over {1, 2, · · · , N}:
P (θ̃N = θn) = ζαn − Lα2n∑N
k=1(ζαk − Lα2k) . (16)
where ζ is defined in Definition 1, 0 < αn < ζL ,n = 1, 2, · · · , N . Theorem 1. (Ghadimi et al., 2016) Under Assumption 1, and the total trajectories are {τk}Nk=1. Consider the sequence {θk}Nk=1 generated by (15), the output θ̃N = θn follows the probability mass distribution of (16). Let 0 < αk < ζL , `(g, u) = 〈g, u〉, the term L and σ are defined in Eq.(5) and Eq.(6) correspondingly. Then, we have
E[‖Gψαn,`(−gn,θn)(θn)‖ 2] ≤
( J(θ∗)− J(θ1) ) +σ 2
ζ ∑N k=1 αk∑N
k=1(ζαk − Lα2k) , (17)
where gn is short for g(τn|θn).
Unfortunately, it is worth to notice that the lower bound of (17) reaches( J(θ∗)− J(θ1) ) +σ 2
ζ ∑N k=1 αk∑N
k=1(ζαk − Lα2k) ≥ σ
2
ζ2 , (18)
which can not guarantee the convergence of the iteration (15), no matter how the step-size αk is specified. Thus, under the Assumption 1, generating the solution {θk}Nk=1 according to (15) and the output following (16) lack a strong convergence guarantee.
An Open Problem The iteration (15) is a very important and general scheme that unifies many existing algorithms. For example, if the mirror map ψ(θ) = 1
2 ‖θ‖22, then the update (15) is reduced to
policy gradient algorithm (Sutton et al., 2000) which is widely used in modern RL. The update (15) is natural policy gradient (Kakade, 2002; Peters & Schaal, 2008; Thomas et al., 2013) if we choose mirror map ψ(θ) = 12θ
>F (θ)θ, where F = Eτ∼πθ [∇θ log πθ(s, a)∇θ log πθ(s, a)>] is Fisher information matrix. If ψ is Boltzmann-Shannon entropy function (Shannon, 1948), then Dψ is known as KL divergence and update (15) is reduced to relative entropy policy search (Peters et al., 2010; Fox et al., 2016; Chow et al., 2018). Despite the vast body of work around above specific methods, current works are scattered and fragmented in both theoretical and empirical aspects (Agarwal et al., 2019). Thus, it is of great significance to establish the fundamental theoretical convergence properties of iteration (15).
Please notice that for the non-convexity of problem (2), the lower bound of (18) holds under Assumption 1. It is natural to ask:
What conditions guarantee the convergence of scheme (15)?
This is an open problem. Although, the iteration (15) is intuitively a convergent scheme, as discussed above that particular mirror maps ψ can lead (15) to some popular empirically effective RL algorithms; there is still no generally complete theoretical convergence analysis of (15). Such convergence properties not only help us to understand better why those methods work but also inspire us to design novel algorithms with the principled approaches. We leave this open problem and the related questions, e.g., how fast the iteration (15) converges to global optimality or its finite sample analysis, as future works.
Algorithm 1 Mirror Policy Optimization Algorithm (MPO) 1: Initialize: parameter θ1, step-sizeαk > 0, g0 = 0, parametric policy πθ(a|s), and map ψ. 2: for k = 1 to N do 3: Generate a trajectory τk = {st, at, rt+1} Hτk t=0 ∼ πθk , temporary variable g0 = 0.
gk ← Hτk∑ t=0 ∇θ log πθ(at|st)R(τk)|θ=θk (21)
ĝk ← 1
k gk + (1−
1 k )gk−1 (22)
θk+1 ← arg min ω {〈−ĝk, ω〉+
1
αk Dψ(ω, θk)} (23)
4: end for 5: Output: θ̃N according to (16).

heading: 3.2 AN IMPLEMENTATION WITH CONVERGENT GUARANTEE
text: In this section, we propose a convergent implementation defined as follows, for each step k:
θk+1 =Mψαk,〈−ĝk,θ〉(θk) = arg minθ∈Θ{〈−ĝk, θ〉+ 1 αk Dψ(θ, θk)}, (19)
where ĝk is an arithmetic mean of previous episodes’ gradient estimate {g(τi|θi)}ki=1:
ĝk = 1
k k∑ i=1 g(τi|θi). (20)
We present the details of an implementation in Algorithm 1. Notice that Eq.(22) is an incremental implementation of the average (20), thus, (22) enjoys a lower storage cost than (20).
For a given episode, the gradient flow (20)/(22) of MPO is slightly different from the traditional VPG, REINFORCE (Williams, 1992), A2C (Mnih et al., 2016) or DPG (Silver et al., 2014) whose gradient estimator follows (14) that is according to the trajectory of current episode, while our MPO uses an arithmetic mean of previous episodes’ gradients. The estimator (14) is a natural way to estimate the term −∇J(θt) = −E[ ∑Hτt k=0∇θ log πθ(ak|sk)R(τt)], i.e. using a single current trajectory to estimate policy gradient. Unfortunately, under Assumption 1, the result of (18) shows using (14) with SMD lacks a guarantee of convergence. This is exactly the reason why we abandon the way (14) and turn to propose (20)/(22) to estimate policy gradient. We provide the convergence analysis of our scheme (20)/(22) in the next Theorem 2. Theorem 2 (Convergence Rate of Algorithm 1). Under Assumption 1, and the total trajectories are {τk}Nk=1. Consider the sequence {θk}Nk=1 generated by Algorithm 1, and the output θ̃N = θn follows the distribution of Eq.(16). Let 0 < αk < ζL , `(g, u) = 〈g, u〉, the term L and σ are defined in Eq.(5) and Eq.(6) correspondingly. Let ĝk = 1k ∑k i=1 gi, where gi = ∑Hτi t=0 ∇θ log πθ(at|st)R(τi)|θ=θi . Then we have
E[‖Gψαn,`(−gn,θn)(θn)‖ 2] ≤
( J(θ∗)− J(θ1) ) +σ 2
ζ ∑N k=1
αk k∑N
k=1(ζαk − Lα2k) . (24)
We prove the proof in Appendix A. Let αk = ζ/2L, then, Eq(24) is E[‖Gψαn,`(−ĝn,θn)(θn)‖ 2] ≤ 4L ( J(θ∗)−J(θ1) ) +2σ2 ∑N k=1 1 k Nζ2 = O(lnN/N). Our scheme of MPO partially answers the previous open problem through conducting a new policy gradient estimator.

heading: 4 VRMPO: A VARIANCE REDUCTION IMPLEMENTATION OF MPO
text: In this section, we propose a variance reduction version of MPO: VRMPO. In optimization community, variance reduction gradient estimator is a very popular method with provable convergence
Algorithm 2 Variance-Reduced Mirror Policy Optimization (VRMPO). 1: Initialize: Policy πθ(a|s) with parameter θ̃0, mirror map ψ,step-size αk > 0, epoch size K,m. 2: for k = 1 to K do 3: θk,0 = θ̃k−1, generate Tk = {τi}N1i=1 ∼ πθk,0 4: θk,1 = θk,0 − αkGk,0, where Gk,0 = −∇̂N1J(θk,0) = − 1N1 ∑N1 i=1 g(τi|θk,0).
5: for t = 1 to m− 1 do 6: Generate {τj}N2j=1 ∼ πθk,t
Gk,t = Gk,t−1 + 1
N2 N2∑ j=1 (−g(τj |θk,t) + g(τj |θk,t−1)), (25)
θk,t+1 = arg min ω {〈Gk,t, ω〉+
1
αk Dψ(ω, θk,t)} (26)
7: end for 8: θ̃k = θk,t with t chosen uniformly randomly from {0, 1, ...,m}. 9: end for
10: Output: θ̃K .
guarantee (Reddi et al., 2016; Fang et al., 2018; Horváth & Richtárik, 2019). Inspired by the above works, now, we present an efficiently computable policy gradient estimator. For any initial θ0, let {τ0j }Nj=1 ∼ πθ0 , we calculate the initial gradient estimate as follows,
G0 = −∇̂NJ(θ0) def = − 1
N N∑ j=1 g(τ0j |θ0). (27)
Let θ1 = θ0 − αG0, for each time t ∈ N+, let {τ tj}Nj=1 be the trajectories generated by πθt , we define the policy gradient estimate Gt and the update rule of parameter as follows,
Gt = Gt−1 + 1
N N∑ j=1 (−g(τ tj |θt) + g(τ tj |θt−1)), (28)
θt+1 = arg min θ {〈Gt, θ〉+
1 α Dψ(θ, θt)}, (29)
where α > 0 is step-size. We present more details in Algorithm 2.
In (28),−g(τ tj |θt) and g(τ tj |θt−1) share the same trajectory {τ tj}Nj=1, which plays a critical role in reducing the variance of gradient estimate (Shen et al., 2019). Besides, it is different from (20), we admit a simple recursive formulation to conduct the policy gradient estimator Gt (28), which captures some techniques from SARAH (Nguyen et al., 2017a;b). At each time t, the term 1 N ∑N j=1 ( − g(τ tj |θt) + g(τ tj |θt−1) ) can be seen as an additional “noise” for the policy gradient estimate. A lot of practices show that conducting a gradient estimator with the additional noise enjoys a lower variance and speeding up the convergence (Reddi et al., 2016; Schmidt et al., 2017; Nguyen et al., 2017a;b; Fang et al., 2018).
Theorem 3 (Convergence Analysis of Algorithm 2). The sequence {θ̃k}Kk=1 is generated according to Algorithm 2. Under Assumption 1, let ζ > 532 , for any positive scalar , the batch size of
the trajectories of outer loop N1 = ( 1
8Lζ2 + 1 2(ζ− 532 )
( 1 + 132ζ2 )) σ2 2 , the iteration times of in-
ner loop m − 1 = N2 = √( 1
8Lζ2 + 1 2(ζ− 532 )
( 1 + 132ζ2 ))σ , the iteration times of outer loop
K = 8L(E[J (θ̃0)]− J (θ∗)) (m− 1)(ζ − 532 ) ( 1 + 116ζ2 ) 1 2 , and step size αk = 14L . Then, Algorithm 2 outputs the point θ̃K achieves
E [ ‖Gψ α,〈−∇J(θ̃K),θ〉(θ̃K)‖ ] ≤ . (30)
By the result in Theorem 3, under Assumption 1, to achieve the -FOSP, Algorithm 2 (VRMPO) needs K(N1 +(m−1)N2) = 8L(E[J (θ̃0)]−J (θ ∗))
(ζ− 532 )
( 1+ 116ζ2 )( 1+ √( 1 8Lζ2 +
1 2(ζ− 532 )
( 1 + 132ζ2 )) σ ) 1 2 =
O( 1 3 ) random trajectories. As far as we know, our VRMPO matches the best-known sample complexity as the HAPG algorithm (Shen et al., 2019).
In fact, according to (Shen et al., 2019), REINFORCE needs O( −4) random trajectory trajectories to achieve the -FOSP, and no provable improvement on its complexity has been made so far. The same order of sample complexity of REINFORCE is shown by Xu et al. (2019). With the additional
assumptions Var [∏H
h=0 πθ0(ah|sh) πθt(ah|sh)
] ,Var[g(τ |θ)] < +∞, Papini et al. (2018) show that the SVRPG
achieves the sample complexity ofO( −4). Later, under the same assumption as (Papini et al., 2018), Xu et al. (2019) reduce the sample complexity of SVRPG toO( − 103 ). We provide more details of the comparison in Table 1, from which it is easy to see that our VRMPO matches the best-known sample complexity with least conditions.

heading: 5 RELATED WORKS
text: Stochastic Variance Reduced Gradient in RL Although it has achieved considerable successes in supervised learning, stochastic variance reduced gradient optimization is rarely a matter of choice in RL. To our best knowledge, Du et al. (2017) firstly introduce SVRG (Johnson & Zhang, 2013) to off-policy evaluation. Du et al. (2017) transform the empirical policy evaluation problem into a (quadratic) convex-concave saddle-point problem, then they solve the problem via SVRG straightforwardly. Later, to improve sample efficiency for complex RL, Xu et al. (2017) combine SVRG with TRPO (Schulman et al., 2015). Similarly, Yuan et al. (2019) introduce SARAH (Nguyen et al., 2017a) to TRPO to improve sample efficiency. However, the results presented by Xu et al. (2017) and Yuan et al. (2019) are empirical, which lacks a strong theory analysis. Metelli et al. (2018) present a surrogate objective function with a Rényi divergence (Rényi et al., 1961) to reduce the variance caused by importance sampling.
Recently, Papini et al. (2018) propose a stochastic variance reduced version of policy gradient (SVRPG), and they define the gradient estimator via important sampling,
Gt = G̃t−1 + 1
N N∑ j=1 ( − g(τ tj |θt) + H∏ h=0 πθ0(ah|sh) πθt(ah|sh) g(τ tj |θt−1) ) , (31)
where G̃t−1 is an unbiased estimator according to the trajectory generated by πθt−1 . Although the above algorithms are practical empirically, their gradient estimates are dependent heavily on important sampling. This fact partially reduces the effectiveness of variance reduction. Later, Shen et al. (2019) remove the important sampling term, and they construct the gradient estimator as follows,
Gt = G̃t−1 + 1
N N∑ j=1 ( − g(τ tj |θt) + g(τ tj |θt−1) ) . (32)
It is different from (Du et al., 2017; Xu et al., 2017; Papini et al., 2018; Shen et al., 2019), the proposed VRMPO admits a stochastic recursive iteration to estimate the policy gradient, see Eq.(28). Our VRMPO exploits the fresh information to improve convergence and reduce variance. Besides, VRMPO reduces the storage cost significantly due to it doesn’t require to store the complete historical information. We provide more details of the comparison in Table 1.
Baseline Methods for Variance Reduction of Policy Gradient Baseline (also also known as control variates (Cheng et al., 2019a) or reward reshaping (Ng et al., 1999; Jie & Abbeel, 2010)) is a widely used technique to reduce the variance (Weaver & Tao, 2001; Greensmith et al., 2004). For example, A2C (Sutton & Barto, 1998; Mnih et al., 2016) introduces the value function as baseline function, Wu et al. (2018) consider action-dependent baseline, and Liu et al. (2018) use the Stein’s identity (Stein, 1986) as baseline. Q-Prop (Gu et al., 2017) makes use of both the linear dependent baseline and GAE (Schulman et al., 2016) to reduce variance. Cheng et al. (2019b) present a predictorcorrector framework that can transform a first-order model-free algorithm into a new hybrid method that leverages predictive models to accelerate policy learning. Mao et al. (2019) derive a bias-free,
Algorithm Estimator Conditions Complexity
VPG/REINFORCE Eq.(14) Assumption 1;Var[g(τ |θ)] < +∞ O( −4) SVRPG (Papini et al., 2018) Eq.(31) Assumption 1;Var[ρt],Var[g(τ |θ)] < +∞ O( −4) SVRPG (Xu et al., 2019) Eq.(31) Assumption 1;Var[ρt],Var[g(τ |θ)] < +∞ O( −10/3) HAPG (Shen et al., 2019) Eq.(32) Assumption 1 O( −3) VRMPO (Our Works) Eq.(28) Assumption 1 O( −3)
Table 1: Comparison on complexity required to achieve ‖∇J(θ)‖ ≤ . Particularly, if ψ(θ) =
1 2‖θ‖ 2 2, then the result (30) of our VRMPO is measured by gradient. Beside, ρt def =
∏H
h=0 πθ0 (ah|sh) πθt (ah|sh) .
input-dependent baseline to reduce variance, and analytically show its benefits over state-dependent baselines. Recently, Grathwohl et al. (2018); Cheng et al. (2019a) provide a standard explanation for the benefits of such approaches with baseline function.
However, the capacity of all the above methods is limited by their choice of baseline function (Liu et al., 2018). In practice, it is troublesome to design a proper baseline function to reduce the variance of policy gradient estimate. Our VRMPO avoids the selection of baseline function, and it uses a current sample trajectory to construct a novel, efficiently computable gradient estimator to reduce variance and speed convergence.

heading: 6 EXPERIMENTS

heading: 6.1 NUMERICAL ANALYSIS OF MPO
text: In this section, we use an experiment to demonstrate MPO converges faster than VPG/REINFORCE. Then, we test how the mirror map ψ effects the performance of MPO.
Performance Comparison We compare the convergence rate of MPO with REINFORCE and VPG empirically on the Short Corridor with Switched Actions domain (Chapter 13, Sutton & Barto (2018); We provide some details in Appendix B). The task is to estimate the value function of state s1, V (s1) = G0 ≈ −11.6.
πθ(a|s) = exp{Lθ(s, a)}∑
a′∈A exp{Lθ(s, a ′)}
. The initial pa-
rameter θ0 = U [−0.5, 0.5], where U is uniform distribution.
Before we report the experimental results, it is necessary to explain why we only use VPG and REINFORCE as the baseline to compare with our MPO. VPG/REINFORCE is one of the most basic policy gradient methods in RL, and extensive modern policy-based algorithms are derived from VPG/REINFORCE. Our MPO is a novel framework via mirror map to learn the parameter, see (23). Thus, it is natural to compare with VPG and REINFORCE. The result in Figure 1 shows that MPO converges faster significantly and achieves a better performance than both REINFORCE and MPO.
Effect of Mirror Map ψ We use ψ = `p-norm to test how the mirror map affects the performance of MPO. Particularly, the iteration (23) reduces to gradient descent update if ψ = `2-norm. For ψ = `pnorm, Eq.(23) has a closed implementation. Let ψ∗(y) = ( ∑n i=1 |yi|q) 1 q be the conjugate map of ψ,
where p−1 + q−1 = 1, p, q > 1. According to (Beck & Teboulle, 2003), (23) is equivalent to
θk+1 = ∇ψ∗(∇ψ(θk) + αkĝk),
where ∇ψj(x) and ∇ψ∗j (y) are p-norm link functions (Gentile, 2003): ∇ψj(x) = sign(xj)|xj |p−1
‖x‖p−2p ,∇ψ∗j (y) =
sign(yj)|yj |q−1
‖y‖q−2q , and j is coordinate index of the vector∇ψ,∇ψ∗.
To compare fairly, we use the same random seed, and let p run in [P ] = {1.1, 1.2, · · · , 1.9, 2, 3, 4, 5}. For the non-Euclidean distance case, we only show p = 3, 4, 5, and “best”, where p = “best” value is that case it achieves the best performance among the set [P ]. For the limitation of space, we provide more details of experiments in Appendix D.1.
The result in Figure 2 shows that the best method is produced by non-Euclidean distance, not the Euclidean distance. The traditional policy gradient methods such as REINFORCE, VPG, and DPG are all the algorithms update parameters in Euclidean distance. This simple experiment gives us some lights that one can create better algorithms by combining the existing approaches with non-Euclidean distance, which is an interesting direction, and we left it as future work.

heading: 6.2 EVALUATE VRMPO ON CONTINUOUS CONTROL TASKS
text: In this section, we compare VRMPO on the MuJoCo continuous control tasks (Todorov et al., 2012) from OpenAI Gym (Brockman et al., 2016). We compare VRMPO with DDPG (Lillicrap et al., 2016), PPO (Schulman et al., 2017), TRPO (Schulman et al., 2015), and TD3 (Fujimoto et al., 2018). For fairness, all the setups mentioned above share the same network architecture that computes the policy and state value. We run all the algorithms with ten random seeds. The results of max-average epoch return are present in Table 2, and return curves are shown in Figure 3. For the limitation of space, we present all the details of experiments and some practical tricks for the implementation of VRMPO in Appendix D.2-D.5; in this section, we only offer our experimental results. We evaluate the performance of VRMPO by the following three aspects: score performance, the stability of training, and variance.
Score Performance Comparison From the results of Figure 3 and Table 2, overall, VRMPO outperforms the baseline algorithms in both final performance and learning process. Our VRMPO also learns considerably faster with better performance than the popular TD3 on Walker2d-v2, HalfCheetah-v2, Hopper-v2, InvDoublePendulum-v2, and Reacher-v2 domains. On the InvDoublePendulum-v2 task, our VRMPO has only a small advantage over other algorithms. This is because the InvPendulum-v2 task is relatively easy. The advantage of our VRMPO becomes more powerful when the task is more difficult. It is worth noticing that on the HalfCheetah-v2 domain, our VRMPO achieves a significant max-average score 16000+, which outperforms far more than the second-best score 11781.
Stability The stability of an algorithm is also an important topic in RL. Although DDPG exploits the off-policy sample, which promotes its efficiency in stable environments, DDPG is unstable on the Reacher-v2 task, while our VRMPO learning faster significantly with lower variance. DDPG fails to make any progress on InvDoublePendulum-v2 domain, and the result is corroborated by the work (Dai et al., 2018). Although TD3 takes the minimum value between a pair of critics to limit overes-
50 100 150 200 250 300 350 400 450 500 Epoch
0
1000
2000
3000 4000 A ve ra ge R et ur n
VRMPO DDPG PPO TD3 TRPO
(a) Walker2d-v2
200 400 600 800 1000 Epoch
0
2000
4000
6000
8000
10000
12000
14000
16000
A ve
ra ge
R et
ur n
VRMPO DDPG PPO TD3 TRPO
(b) HalfCheetah-v2
50 100 150 200 250 300 350 400 450 500 Epoch
10
9
8
7
6
5
4
Av er
ag e
R et
ur n
VRMPO PPO TD3 TRPO DDPG
(c) Reacher-v2
timation, it learns severely fluctuating in the InvertedDoublePendulum-v2 environment. In contrast, our VRMPO is consistently reliable and effective in different tasks.
Variance Comparison As we can see from the results in Figure 3, our VRMPO converges with a considerably low variance in the Hopper-v2, InvDoublePendulum-v2, and Reacher-v2. Although the asymptotic variance of VRMPO is slightly larger than other algorithms in HalfCheetah-v2, the final performance of VRMPO outperforms all the baselines significantly. The result in Figure 3 also implies conducting a proper gradient estimator not only reduce the variance of the score during the learning but speed the convergence of training.

heading: 7 CONCLUSION
text: In this paper, we propose the mirror policy optimization (MPO) by estimating the policy gradient via dynamic batch-size of historical gradient information. Results show that making use of historical gradients to estimate policy gradient is more effective to speed convergence. We also propose a variance reduction implementation for MPO: VRMPO, and prove the complexity of VRMPO achieves O( −3). To our best knowledge, VRMPO matches the best-known sample complexity so far. Finally, we evaluate the performance of VRMPO on the MuJoCo continuous control tasks, results show that VRMPO outperforms or matches several state-of-art algorithms DDPG, TRPO, PPO, and TD3.

heading: A PROOF OF THEOREM 2
text: Let f(x) be a L-smooth function defined on Rn, i.e ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖. Then, for ∀x, y ∈Rn, the following holds
‖f(x)− f(y)− 〈∇f(y), x− y〉‖ ≤ L 2 ‖x− y‖2. (33)
The following Lemma 2 is useful for our proof. Lemma 2 (Ghadimi et al. (2016), Lemma 1 and Proposition 1). Let X be a closed convex set in Rd, h : X → R be a convex function, but possibly nonsmooth, and Dψ : X × X → R is Bregman divergence. Moreover, define
x+ = arg min u∈X
{ 〈g, u〉+ 1
η Dψ(u, x) + h(u) } PX (x, g, η) = 1
η (x− x+), (34)
where g ∈ Rd, x ∈ X , and η > 0. Then, the following statement holds
〈g, PX (x, g, η)〉 ≥ ζ‖PX (x, g, η)‖2 + 1
η [h(x+)− h(x)], (35)
where ζ is a positive constant determined by ψ (i.e. ψ is a a continuously-differentiable and ζstrictly convex function) that satisfying 〈x − y,∇ψ(x) −∇ψ(y)〉 ≥ ζ‖x − y‖2. Moreover, for any g1, g2 ∈ Rd, the following statement holds
‖PX (x, g1, η)− PX (x, g2, η)‖ ≤ 1
ζ ‖g1 − g2‖. (36)
Theorem 2 (Convergence Rate of Algorithm 1) Under Assumption 1, and the total trajectories are {τk}Nk=1. Consider the sequence {θk}Nk=1 generated by Algorithm 1, and the output θ̃N = θn follows the distribution of Eq.(16). Let 0 < αk < ζL , `(g, u) = 〈g, u〉, the term L and σ are defined in Eq.(5) and Eq.(6) correspondingly. Let ĝk = 1k ∑k i=1 gi, where gi = ∑Hτi t=0 ∇θ log πθ(at|st)R(τi)|θ=θi . Then we have
E[‖Gψαn,`(−gn,θn)(θn)‖ 2] ≤
( J(θ∗)− J(θ1) ) +σ 2
ζ ∑N k=1
αk k∑N
k=1(ζαk − Lα2k) .
Proof. (Proof of Theorem 2)
Let T = {τk}Nk=1 be the trjecories generated by the differentiable parametric policy πθ. At each terminal end of a trajectory τk = {st, at, rt+1} Hτk t=0 ∈ T , let
gk = Hτk∑ t=0 ∇θ log πθ(at|st)R(τk)|θ=θk , ĝk = 1 k k∑ i=1 gi,
according to Algorithm 1, at the terminal end of k-th episode, k = 1, 2, · · · , N , the following holds,
θk+1 = arg min θ
{ 〈−ĝk, θ〉+ 1
αk Dψ(θ, θk)
} =Mψαk,`(−ĝk,θ)(θk).
To simplify expression, let J (θ) = −J(θ), then J (θ) is L-smooth, from Eq.(33), we have J (θk+1) ≤ J (θk) + 〈 ∇θJ (θ) ∣∣ θ=θk , θk+1 − θk 〉 + L
2 ∥∥∥θk+1 − θk∥∥∥2 = J (θk)− αk 〈 ∇J (θk),Gψαk,`(−ĝk,θk)(θk) 〉 + Lα2k
2 ∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 = J (θk)− αk 〈 ĝk,Gψαk,`(−ĝk,θk)(θk) 〉 + Lα2k
2 ∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 + αk 〈 k,Gψαk,`(−ĝk,θk)(θk) 〉 ,
where k = −ĝk − (−∇J(θk)) = −ĝk − ∇J (θk). By Eq.(34) and let h(x) ≡ 0 and η = α, then PX (θ, g, α) = Gψα,`(g,θ)(θ). Furthermore, by Eq.(35), let η = αk and g = −ĝk, then we have
J (θk+1) ≤ J (θk)− αkζ ∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 + Lα2k2 ∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2
+ αk 〈 k,Gψαk,`(−ĝk,θk)(θk) 〉 = J (θk)− αkζ
∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 + Lα2k2 ∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 + αk 〈 k,Gψαk,`(−∇J(θk),θk)(θk)
〉 + αk 〈 k,Gψαk,`(−ĝk,θk)(θk)− G ψ αk,`(−∇J(θk),θk)(θk) 〉 . (37)
Rearrange Eq.(37), we have
J (θk+1) ≤ J (θk)− ( ζαk −
Lα2k 2 )∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 + αk〈 k,Gψαk,`(−∇J(θk),θk)(θk)〉 + αk‖ k‖
∥∥∥Gψαk,`(−ĝk,θk)(θk)− Gψαk,`(−∇J(θk),θk)(θk)∥∥∥. By Eq.(36), let x = θk, g1 = −ĝk, g2 = −∇J(θk), h(x) ≡ 0, then the following statement holds
J (θk+1)
≤ J (θk)− ( ζαk −
Lα2k 2 )∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 + αk〈 k,Gψαk,`(−∇J(θk),θk)(θk)〉+ αkL ‖ k‖2. (38)
Summing the above Eq.(38) from k = 1 toN and with the condition αk ≤ ζ
L , we have the following
statement N∑ k=1 ( ζαk − Lα2k )∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 ≤
N∑ k=1 ( ζαk − Lα2k 2 )∥∥∥Gψαk,`(−ĝk,θk)(θk)∥∥∥2 ≤
N∑ k=1 [ αk 〈 k,Gψαk,`(−∇J(θk),θk)(θk) 〉 + αk ζ ‖ k‖2 ] + J (θ1)− J (θk+1)
≤ N∑ k=1 [ αk 〈 k,Gψαk,`(−∇J(θk),θk)(θk) 〉 + αk ζ ‖ k‖2 ] + J (θ1)− J ∗. (39)
Recall
gk = Hτk∑ t=0 ∇θ log πθ(at|st)R(τk), ĝk = 1 k k∑ i=1 gi,
by policy gradient theorem
E[−gk] = E[−ĝk] = −∇J(θk) = ∇J (θk). (40)
Let Fk be the σ-field generated by all random variables defined before round k, ̃k = gk −∇J (θk) then the Eq.(40) implies: for k = 1, · · · , N ,
E [〈 k,Gψαk,`(−∇J(θk),θk)(θk) 〉∣∣∣Fk−1] = E[〈̃k,Gψαk,`(−∇J(θk),θk)(θk)〉∣∣∣Fk−1] = 0. Let δs = ∑s t=1 ̃t, noticing that for s = 1, · · · , k,
E[〈δs, ̃s+1〉|δs] = 0. (41)
Furthermore, the following statement holds
E[‖δk‖2] = E [ ‖δk−1‖2 + 2 〈 δk−1, ̃k 〉 + ‖̃t‖2 ] (41) = E [ ‖δk−1‖2 + ‖̃t‖2 ] = · · · = k∑ t=1 E‖̃t‖2.
(42)
By Lemma 1 and Eq.(42), we have
E[‖ k‖2] = 1
k2 k∑ t=1 E‖̃t‖2 ≤ σ2 k . (43)
Taking Eq.(43) in to Eq.(39), and taking expections w.r.t FN , we have N∑ k=1 ( ζαk − Lα2k ) E [∥∥Gψαk,`(−ĝk,θk)(θk)∥∥2] ≤ J θ1)− J ∗ + σ2ζ N∑ k=1 αk k .
Now, consider the output θ̃N = θn follows the distribution of Eq.(16), we have
E[‖Gψαn,`(−gn,θn)(θn)‖ 2] ≤
( J(θ∗)− J(θ1) ) +σ 2
ζ ∑N k=1
αk k∑N
k=1(ζαk − Lα2k) .
Particularly, if the step-size αk is fixed to a constant:ζ/2L, then
E[‖Gψαn,`(−ĝn,θn)(θn)‖ 2] ≤
4L ( J(θ∗)− J(θ1) ) +2σ2 ∑N k=1 1 k
Nζ2 .
Recall the following estimation
N∑ k=1 1 k = lnN + C + o(1),
where C is the Euler constant—a positive real number and o(1) is infinitesimal. Thus the overall convergence rate reaches O( lnNN ) as
E[‖Gψαn,`(−ĝn,θn)(θn)‖ 2] ≤
4LD2J + 2σ ∑N k=1 1 k
Nζ = O( lnN N ).

heading: B SHORT CORRIDOR WITH SWITCHED ACTIONS
text: Consider the small corridor grid world which contains three sates S = {1, 2, 3}. The reward is −1 per step. In each of the three nonterminal states there are only two actions, right and left. These actions have their usual consequences in the state 1 and state 3 (left causes no movement in the first state), but in the state 2 they are reversed. so that right moves to the left and left moves to the right.
An action-value method with -greedy action selection is forced to choose between just two policies: choosing right with high probability 1 − 2 on all steps or choosing left with the same high probability on all time steps. If = 0.1, then these two policies achieve a value (at the start state) of less than −44 and −82, respectively, as shown in the following graph.
A method can do significantly better if it can learn a specific probability with which to select right. The best probability is about 0.58, which achieves a value of about −11.6.

heading: C PROOF OF THEOREM 3
text: We need the following lemmas to prove the convergence result.
Lemma 3 (Lemma1 (Fang et al., 2018)). Under Assumption 1, Gk,t is generated according to (25), θk,t is generated according to (26), then for any 0 ≤ t ≤ m, the following holds
E[‖Gk,t −∇J (θk,t)‖2] ≤ L2
N2 E[‖θk,t − θk,t−1‖2] + E[‖Gk,t−1 − J (θk,t−1)‖2]. (44)
Telescoping Eq.(3) over t from 1 to the time t, then the following holds
E[‖Gk,t −∇J (θk,t)‖2] ≤ t∑ i=1 L2 N2 E[‖θk,i+1 − θk,i‖2] + E[‖Gk−1,0 −∇J (θ̃k−1)‖2]. (45)
Lemma 4. Let ζ > 532 , the batch size of the trajectories of outer loop N1 =( 1 8Lζ2 + 1 2(ζ− 532 ) ( 1 + 132ζ2 )) σ2
2 , the iteration times of inner loop m − 1 = N2 =√( 1
8Lζ2 + 1 2(ζ− 532 )
( 1 + 132ζ2 )) σ
, and step size αk = 14L . For each k and t, Gk,0 and θk,0 are
generated by Algorithm 2, then the following holds, E‖∇J (θk,0)−Gk,0‖2 ≤ ( 1
8Lζ2 +
1 2(ζ − 532 ) ( 1 + 1 32ζ2 ))−1 2. (46)
Proof.
E‖∇J (θk,0)−Gk,0‖2 = E‖∇J(θk,0)− 1
N1 N1∑ i=1 g(τi|θk,0)‖2 (47)
= 1
N21 N1∑ i=1 E‖∇J(θk,0)− g(τi|θk,0)‖2 (48)
(6) ≤ σ 2
N1 (49) = ( 1
8Lζ2 +
1 2(ζ − 532 ) ( 1 + 1 32ζ2 ))−1
2︸ ︷︷ ︸ def = 21 . (50)
Theorem 3 (Convergence Rate of VRMPO) The sequence {θ̃k}Kk=1 is generated according to Algorithm 2. Under Assumption 1, let ζ > 532 , the batch size of the trajectories of outer loop
N1 = ( 1
8Lζ2 + 1 2(ζ− 532 )
( 1 + 132ζ2 )) σ2
2 , the iteration times of inner loop m − 1 = N2 =√( 1 8Lζ2 + 1 2(ζ− 532 ) ( 1 + 132ζ2 ))σ , the iteration times of outer loop K = 8L (m− 1)(ζ − 532 ) ( 1 +
1 16ζ2 ) 1 2 , and step size αk = 14L . Then, Algorithm 2 outputs the point θ̃K achieves
E[‖Gψ α,〈−∇J(θ̃K),θ〉(θ̃K)‖] ≤ . (51)
Proof. (Proof of Theorem 3)
By the definition of Bregman grdient mapping in Eq.(10) and iteration (26), let αk = α, we have
1 α (θk,t − θk,t+1) (26) = 1 α
( θk,t − arg min
u {〈Gk,t, u〉+
1
αk Dψ(u, θk,t)} ) ︸ ︷︷ ︸
gk,t
(10) = Gψα,〈Gk,t,u〉(θk,t),
(52)
where we introduce gk,t to simplify notations.
Step 1: Analyze the inner loop of Algorithm 2 Now, we analyze the inner loop of Algorithm 2. In this step, our goal is to prove
E[J (θ̃k)]− E[J (θ̃k−1)] ≤ − m−1∑ t=1 ( ηE[‖gk,t‖2]− α 2 2 ) .
In fact,
J (θk,t+1) (33) ≤ J (θk,t) + 〈∇J (θk,t), θk,t+1 − θk,t〉+ L
2 ‖θk,t+1 − θk,t‖2
(52) = J (θk,t)− α 〈∇J (θk,t), gk,t〉+
Lα2
2 ‖gk,t‖2
= J (θk,t)− α 〈∇J (θk,t)−Gk,t, gk,t〉 − α 〈Gk,t, gk,t〉+ Lα2
2 ‖gk,t‖2
≤ J (θk,t) + α
2 ‖∇J (θk,t)−Gk,t‖2 − α 〈Gk,t, gk,t〉+
( Lα2
2 + α 2
) ‖gk,t‖2 (53)
(35)
≤ J (θk,t) + α
2 ‖∇J (θk,t)−Gk,t‖2 − ζα‖gk,t‖2 +
( Lα2
2 + α 2
) ‖gk,t‖2, (54)
Eq.(53) holds due to the Cauchy-Schwarz inequality |〈u,v〉| ≤ ‖u‖‖v‖ ≤ 1 2
(‖u‖2 +‖v‖2) for any u,v ∈ Rn. Eq.(54) holds if h ≡ 0 by Eq.(35). Taking expectation on both sides of Eq(54), we have
E[J (θk,t+1)] ≤ E[J (θk,t)] + α 2 E [ ‖∇J (θk,t)−Gk,t‖2 ] − ( ζα− Lα 2 2 − α 2 ) E [ ‖gk,t‖2 ] ≤ E[J (θk,t)] + α
2 t∑ i=1 L2 N2 E‖θk,i+1 − θk,i‖2
+ α
2 E‖Gk−1,0 −∇J (θk−1,0)‖2 −
( ζα− Lα 2
2 − α 2
) E‖gk,t‖2 (55)
Eq.(55) holds due to Lemma 3.
By Lemma 4, Eq.(55) and Eq.(52), we have
E[J (θk,t+1)] ≤ E[J (θk,t)] + α3L2
2N2 t∑ i=1 E [ ‖gk,i‖2 ] + α 21 2 − ( ζα− Lα 2 2 − α 2 ) E‖gk,t‖2.
Recall the parameter θ̃k−1 = θk−1,m is generated by the last time of (k − 1)-th episode, we now consider the following equation
E[J (θk,t+1)]− E[J (θ̃k−1)]
≤α 3L2
2N2 t∑ j=1 j∑ i=1 E‖gk,i‖2 + α 2 t∑ j=1 21 − ( ζα− Lα 2 2 − α 2 ) t∑ j=1 E‖gk,j‖2
≤α 3L2
2N2 t∑ j=1 t∑ i=1 E‖gk,i‖2 + α 2 t∑ j=1 21 − ( ζα− Lα 2 2 − α 2 ) t∑ j=1 E‖gk,j‖2
= α3L2t
2N2 t∑ i=1 E‖gk,i‖2 + α 2 t∑ j=1 21 − ( ζα− Lα 2 2 − α 2 ) t∑ j=1 E‖gk,j‖2
≤α 3L2(m− 1)
2N2
t∑ i=1 E‖gk,i‖2 + α 2 t∑ j=1 21 − ( ζα− Lα 2 2 − α 2 ) t∑ j=1 E‖gk,j‖2 (56)
= α
2 t∑ j=1 21 − ( ζα− Lα 2 2 − α 2 − α 3L2(m− 1) 2N2 ) ︸ ︷︷ ︸
def =η= ζ − 532 4L
t∑ j=1 E‖gk,j‖2
=− t∑ i=1 ηE[‖gk,i‖2]− α 2 (( 1 8Lζ2 + 1 2(ζ − 532 ) ( 1 + 1 32ζ2 )))−1
2︸ ︷︷ ︸ = 21  , (57) Eq.(56) holds due to t ≤ m− 1. If t = m− 1, then by the last Eq.(57) implies
E[J (θ̃k)]− E[J (θ̃k−1)] ≤ − m−1∑ t=1 ( ηE[‖gk,t‖2]− α 2 21 ) . (58)
Step 2: Analyze the outer loop of Algorithm 2
We now consider the output of Algorithm 2, E[J (θ̃K)]− E[J (θ̃0)] = ( E[J (θ̃1)]− E[J (θ̃0)] ) + ( E[J (θ̃2)]− E[J (θ̃1)] ) + · · ·+ ( E[J (θ̃K)]− E[J (θ̃K−1)]
) (58)
≤ − m−1∑ t=0 ( ηE‖g1,t‖2 − α 2 21 ) − m−1∑ t=0 ( ηE‖g2,t‖2 − α 2 21 ) − · · · −
m−1∑ t=0 ( ηE‖gK,t‖2 − α 2 21 ) =−
K∑ k=1 m−1∑ t=0 ( ηE‖gk,t‖2 − α 2 21 ) =−
K∑ k=1 m−1∑ t=1 ( ηE‖gk,t‖2 ) + Kα 2 21,
then we have K∑ k=1 m−1∑ t=1 ( ηE‖gk,t‖2 ) ≤ E[J (θ̃0)]− J (θ∗) + K(m− 1)α 2 21. (59)
Recall the notation in Eq.(52)
gk,t = 1
α (θk,t − arg min u {〈Gk,t, u〉+
1 α Dψ(u, θk,t)}) = Gψα,〈Gk,t,u〉(θk,t),
and we introduce following g̃(θk,t) to simplify notations,
g̃(θk,t) = Gψα,〈−∇J(θk,t),u〉(θk,t) def = g̃k,t
= 1
α
( θk,t − arg min
u {〈−∇J(θk,t), u〉+
1 α Dψ(u, θk,t)}
) . (60)
Then, the following holds
E‖g̃k,t‖2 ≤E‖gk,t‖2 + E‖g̃k,t − gk,t‖2
(36)
≤ E‖gk,t‖2 + 1
ζ2 E‖∇J (θk,t)−Gk,t‖2, (61)
Eq.(61) holds due to the Eq.(36).
Let ν be the number that is selected randomly from {1, · · · , (m − 1)K} which is the output of Algorihtm 2,for the convenience of proof the there is no harm in hypothesis that ν = k · (m− 1) + t and we denote the output θν = θk,t.
Now, we analyze above Eq.(61) and show it is bounded as following two parts (63) and (66)
E‖g(θν)‖2 = 1
(m− 1)K K∑ k=1 m−1∑ t=1 E‖gk,t‖2 (59) ≤ E[J (θ̃0)]− J (θ ∗) (m− 1)Kη + α 2η 21, (62)
which implies the following holds
E‖gk,t‖2 ≤ E[J (θ̃0)]− J (θ∗)
(m− 1)Kη +
α 2η 21. (63)
For another part of Eq.(61), notice ν = k(m− 1) + t, then we have
E‖∇J (θk,t)−Gk,t‖2 =E‖∇J (θν)−Gν‖2 (64) (45)
≤ E
[ L2
N2 t∑ i=1 E‖θk,i+1 − θk,i‖2 + E[‖Gk−1,0 −∇J (θ̃k−1)‖2] ] (46)
≤ E
[ L2
N2 t∑ i=1 E‖θk,i+1 − θk,i‖2 + α 2 21 ] (52) = E [ L2α2
N2 t∑ i=1
E‖gk,i‖2 ] + α
2 21
t≤m ≤ E
[ L2α2
N2 m−1∑ i=1
E‖gk,i‖2 ] + α
2 21
≤L 2α2
KN2 K∑ k=1 m−1∑ t=1 E‖gk,t‖2 + α 2 21 (65)
(59) ≤ L 2α2
KN2η
( E[J (θ̃0)]− J (θ∗) ) + (L2α3(m− 1)
2N2η + α 2
) 21, (66)
Eq.(65) holds due to the fact that the probability of selecting ν = k · (m− 1) + t is less than 1K . Taking Eq(62) and Eq.(65) into Eq.(61), then we have the following inequity E‖g̃k,t‖2 ≤ ( 1
(m− 1)Kη +
L2α2
KN2ηζ2
)( E[J (θ̃0)]− J (θ∗) ) + (L2α3(m− 1)
2N2ηζ2 +
α
2ζ2 +
α
2η
) 21.
Recall α = 14L , N1 =
( 1 8Lζ2 + 1 2(ζ− 532 ) ( 1 + 132ζ2 )) σ2
2 , N2 = m − 1 =√( 1
8Lζ2 + 1 2(η− 532 )
( 1 + 132ζ2 )) σ
, then we have
E‖Gα,〈−∇J(θ̃K),θ〉‖ 2 = E‖g̃k,t‖2 ≤
4L K(m− 1)(ζ − 532 ) ( 1 + 1 16ζ2 ) (E[J (θ̃0)]− J (θ∗)) + 1 2 2.
(67)
Furthermore, K = 8L(1 + 116ζ2 ) (m− 1)(ζ − 532 ) · E[J (θ̃0)]− J (θ ∗) 2 , we have
E[‖Gψ α,〈−∇J(θ̃K),θ〉(θ̃K)‖] ≤ . (68)

heading: D EXPERIMENTS
text: D.1 EXPERIMENTS DETAILS OF FIGURE 2
For all `p, we set p ∈ [P ] = {1.1, 1.2, · · · , 1.9, 2, 3, 4, 5}, we set γ = 0.99. The learning rate is chosen by grid search from the set{0.01, 0.02, 0.04, 0.08, 0.1}. For our implementation of MPO, we use a two layer feedforward neural network of 200 and 100 hidden nodes respectively, with rectified linear units (ReLU) between each layer.
D.2 SOME PRACTICAL TRICKS FOR THE IMPLEMENTATION OF VRMPO
We present the details of the practical tricks we apply to VRMPO in the following Algorithm 3.
(I) For the complex real-world domains, we should tune necessitate meticulous hyper-parameter. In order to improve sample efficiency, we draw on the technique of Double Q-learning (Van Hasselt et al., 2016) to VRMPO.
(II) For Algorithm 2, the update rule of policy gradient (28)/(25) is a full-return update according to R(τ), which is the expensive Monte Carlo method and it tends to learn slowly. In practice, we use the one-step actor-critic structure. Let D be the replay memory, replacing the term 1 N2 ∑N2 j=1(−g(τj |θk,t) + g(τj |θk,t−1)) (in (25)) as the following δk,t
δk,t = 1
N2 N2∑ i=1 (∇θLθk,t(si, ai)−∇θLθk,t−1(si, ai)), (69)
where Lθ(s, a) = − log πθ(s, a)Qω(s, a) is the training loss of actor, {(si, ai)}Ni=1 ∼ D, Qω(s, a) is an estimate of action-value that can be trained to minimize the loss of critic
Lω = 1
N N∑ i=1 (Qωt−1(si, ai)−Qω(si, ai))2. (70)
More details of implementation are provided in the following Algorithm 3.
In this section, we use `p as the mirror map.
Algorithm 3 On-line VRMPO Initialize: Policy πθ(a|s) with parameter θ̃0, mirror map ψ,step-size α > 0, epoch size K,m. Initialize: Parameter ω̃j0, j = 1, 2 ,0 < κ < 1 . for k = 1 to K do
for each domain step do at ∼ πθ̃k−1(·|st) st+1 ∼ P (·|st, at) D = D ∪ {(st, at, rt, st+1)} end for sample mini-batch {(si, ai)}Ni=1 ∼ D θk,0 = θ̃k−1, ωk,0 = ω̃ j k−1, j = 1, 2 Lθ(s, a) = − log πθ(s, a) ( min j=1,2
Qωjk−1 (s, a))︸ ︷︷ ︸
Double Q-Learning (Van Hasselt et al., 2016) θk,1 = θk,0 − αkGk,0, where Gk,0 = 1N ∑N i=1∇θLθ(si, ai) ∣∣∣ θ=θk,0 for t = 1 to m− 1 do /* Update Actor (m− 1) Epochs */
sample mini-batch {(si, ai)}Ni=1 ∼ D
δk,t = 1
N N∑ i=1 ∇θLθ(si, ai) ∣∣∣ θ=θk,t − 1 N N∑ i=1 ∇θLθ(si, ai) ∣∣∣ θ=θk,t−1
(71)
Gk,t = δk,t +Gk,t−1 (72)
θk,t+1 = arg min u {〈Gk,t, u〉+
1
αk Dψ(u, θk,t)} (73)
end for for t = 1 to m− 1 do
/* Update Critic (m− 1) Epochs */ sample mini-batch {(si, ai)}Ni=1 ∼ D
Lωjk−1,t−1 (ω) =
1
N N∑ i=1 (Qωjk−1,t−1 (si, ai)−Qω(si, ai))2, j = 1, 2 (74)
ωjk,t = arg minω Lωjk−1,t−1 (ω), j = 1, 2 (75)
end for θ̃k def = θk,m−1, ω̃ j k def = ωjk,m−1, j = 1, 2 /* Soft Update */ θ̃k ← κθ̃k−1 + (1− κ)θ̃k ω̃jk ← κω̃ j k−1 + (1− κ)ω̃ j k, j = 1, 2
end for
D.3 TEST SCORE COMPARISON
We compare the VRMPO with baseline algorithm on test score. All the results are shown in the following Figure 6.
D.4 MAX-RETURN COMPARISON
We compare the VRMPO with baseline algorithm on max-return. All the results are shown in the following Figure 7.
50 100 150 200 250 300 350 400 450 500 Epoch
0
1000
2000
3000 4000 A ve ra ge T es t R et ur n
VRMPO DDPG PPO TD3 TRPO
(a) Walker2d-v2
50 100 150 200 250 300 350 400 450 500 Epoch
0
2000
4000
6000
8000
10000
12000
A ve
ra ge
T es
t R et
ur n
VRMPO DDPG PPO TD3 TRPO
(b) HalfCheetah-v2
50 100 150 200 250 300 350 400 450 500 Epoch
10
9
8
7
6
5
4
Av er
ag e
Te st
R et
ur n
DDPG VRMPO PPO TD3 TRPO
(c) Reacher-v2
D.5 DETAILS OF BASELINE IMPLEMENTATION
For all algorithms, we set γ = 0.99. For VRMPO, the learning rate is chosen by grid search from the set {0.1, 0.01, 0.004, 0.008}, batch-size N = 100. Memory size |D| = 106. We run 5000 iterations for each epoch.
DDPG For our implementation of DDPG, we use a two layer feedforward neural network of 400 and 300 hidden nodes respectively, with rectified linear units (ReLU) between each layer for both the actor and critic, and a final tanh unit following the output of the actor. This implementation is largely based on the recent work by (Fujimoto et al., 2018).
TD3 For our implementation of TD3, we refer to the work TD3 (Fujimoto et al., 2018) and https: //github.com/sfujim/TD3.
We excerpt some necessary details about the implementation of TD3 (Fujimoto et al., 2018). TD3 maintains a pair of critics along with a single actor. For each time step, we update the pair of critics towards the minimum target value of actions selected by the target policy:
y = r + γ min i=1,2 Qθ′i (s ′ , πφ′(s ′) + ),
∼ clip(N (0, σ),−c, c).
Every d iterations, the policy is updated with respect to Qθ1 following the deterministic policy gradient algorithm. The target policy smoothing is implemented by adding ∼ N (0, 0.2) to the actions chosen by the target actor network, clipped to (−0.5, 0.5), delayed policy updates consists of only updating the actor and target critic network every d iterations, with d = 2. While a larger d would result in a larger benefit with respect to accumulating errors, for fair comparison, the critics are only trained once per time step, and training the actor for too few iterations would cripple learning. Both target networks are updated with τ = 0.005.
TRPO and PPO For implementation of TRPO/PPO, we refer to https://github.com/openai/ baselines/tree/master/baselines and https://spinningup.openai.com/en/latest/algorithms/trpo.html.

Review summaries:
This paper proposed a variant of policy gradient algorithm with mirror descent update, which is a natural generalization of projected policy gradient descent. The authors also proposed a variance reduced policy gradient algorithm following the variance reduction techniques in optimization. The authors further proved the convergence of the proposed algorithms and some experiments are conducted to show the effectiveness of their algorithms. The paper is not written in a very good way due to many typos and misleading notations. Moreover, there seem to be some technical issues in the proofs of both main theorems.

This paper proposes MPO, a policy optimization method with convergence guarantees based on stochastic mirror descent that uses the average of previous gradients to update the policy parameters. A lower-variance method, VRMPO, is then proposed that matches the best known convergence rate in the in the literature. Experiments show that (1) MPO converges faster than basic policy optimization methods on a small task, and (2) VRMPO achieves a performance comparable to, and often better than, popular policy optimization methods (TD3, DDPG, PPO, and TRPO) on MuJoCo.