Title: POLICY OPTIMIZATION WITH STOCHASTIC MIRROR DESCENT

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.

1. INTRODUCTION:

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.

2. BACKGROUND AND NOTATIONS:

2.1 POLICY-BASED REINFORCEMENT LEARNING 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 S t ∈ S and takes an action A t ∈ A, then it receives a feedback R t+1 ; P a ss = 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 :

EQUATION

]; ρ 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 θ ∈ R p . Let τ = {s t , a t , r t+1 } Hτ t=0 be a trajectory, where s 0 ∼ ρ 0 (s 0 ), a t ∼ π θ (•|s t ), r t+1 = R(s t , a t ), s t+1 ∼ P (•|s t , a t ), and H τ is the finite horizon of τ . The expected return J(π θ ) is defined as:

EQUATION

where P (τ |θ) = ρ 0 (s 0 ) Hτ t=0 P (s t+1 |s t , a t )π θ (a t |s t ) is the probability of generating τ , R(τ ) = Hτ t=0 γ t r t+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

EQUATION

For any trajectory τ , let g(τ |θ) = Hτ t=0 ∇ θ log π θ (a t |s t )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 θ ∈ R p , and all components i, j, there exists positive constants G, F s.t.,

EQUATION

According to the Lemma B.2 of (Papini et al., 2018) , Assumption 1 implies

EQUATION

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 2 R 2 (1 -γ) 4 def = σ 2 .

(6)

2.2. STOCHASTIC MIRROR DESCENT:

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,

EQUATION

where D θ ∈ R n is a nonempty convex compact set, ξ is a random vector whose probability distribution, µ is supported on Ξ ∈ R d 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:

EQUATION

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,

EQUATION

where

α t > 0 is step-size, (θ) = g t , θ is the first-order approximation of f (θ) at θ t , g t = 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 (ω) ≤ g T (θ -ω), ∀ω ∈ dom(f )}. If we choose ψ(x) = 1 2 x 2 2 , which implies D ψ (x, y) = 1 2

x -y 2 2 , 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 R n , α > 0, T (x) is defined on X . The Bregman gradient of T at x ∈ X is:

EQUATION

where 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

M ψ α,T (•) is defined in Eq.(8). If ψ(x) = 1 2 x 2 2 , then x * is a critical point of T if and only if G ψ α,T (x * ) = ∇T (x * ) = 0 (Bauschke

EQUATION

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 operator M ψ α,T (•), we have

EQUATION

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

EQUATION

)

3. POLICY OPTIMIZATION WITH STOCHASTIC MIRROR DESCENT:

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).

3.1. THEORETICAL DILEMMA:

Let T = {τ k } N -1 k=0 be a collection of trajectories, τ k ∼ π θ k , we receive gradient information:

EQUATION

then by SMD (9), to solve (2), for each 0 ≤ k ≤ N -1, we define the update rule as follows,

EQUATION

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 }:

EQUATION

)

where (Ghadimi et al., 2016) Under Assumption 1, and the total trajectories are {τ k } N k=1 . Consider the sequence {θ k } N k=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

ζ is defined in Definition 1, 0 < α n < ζ L ,n = 1, 2, • • • , N . Theorem 1.

EQUATION

)

where g n is short for g(τ n |θ n ).

Unfortunately, it is worth to notice that the lower bound of (17) reaches

EQUATION

)

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 } N k=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 θ 2 2 , 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 ψ(θ) = 1 2 θ 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, g 0 = 0, parametric policy π θ (a|s), and map ψ.

EQUATION

) 4: end for 5: Output: θN according to (16).

3.2. AN IMPLEMENTATION WITH CONVERGENT GUARANTEE:

In this section, we propose a convergent implementation defined as follows, for each step k:

EQUATION

)

where ĝk is an arithmetic mean of previous episodes' gradient estimate {g(τ

EQUATION

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 π θ (a k |s k )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 } N k=1 . Consider the sequence {θ k } N k=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

EQUATION

)

We prove the proof in Appendix A. Let

α k = ζ/2L, then, Eq(24) is E[ G ψ αn, (-ĝn,θn) (θ n ) 2 ] ≤ 4L J(θ * )-J(θ1) +2σ 2 N k=1 1 k N ζ 2

= O(ln N /N ). Our scheme of MPO partially answers the previous open problem through conducting a new policy gradient estimator.

4. VRMPO: A VARIANCE REDUCTION IMPLEMENTATION OF MPO:

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.

EQUATION

EQUATION

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; Horváth & Richtárik, 2019) . Inspired by the above works, now, we present an efficiently computable policy gradient estimator. For any initial θ 0 , let {τ 0 j } N j=1 ∼ π θ0 , we calculate the initial gradient estimate as follows,

EQUATION

Let θ 1 = θ 0 -αG 0 , for each time t ∈ N + , let {τ t j } N j=1 be the trajectories generated by π θt , we define the policy gradient estimate G t and the update rule of parameter as follows,

EQUATION

EQUATION

where α > 0 is step-size. We present more details in Algorithm 2.

In (28), -g(τ t j |θ t ) and g(τ t j |θ t-1 ) share the same trajectory {τ t j } N j=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 G t (28), which captures some techniques from SARAH (Nguyen et al., 2017a; b) . At each time t, the term

1 N N j=1 -g(τ t j |θ t ) + g(τ t j |θ 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 } K k=1 is generated according to Algorithm 2. Under Assumption 1, let ζ > 5 32 , for any positive scalar , the batch size of the trajectories of outer loop

N 1 = 1 8Lζ 2 + 1 2(ζ-5 32 ) 1 + 1 32ζ 2 σ 2 2 , the iteration times of in- ner loop m -1 = N 2 = 1 8Lζ 2 + 1 2(ζ-5 32 ) 1 + 1 32ζ 2 σ

, the iteration times of outer loop

K = 8L(E[J ( θ0 )] -J (θ * )) (m -1)(ζ -5 32 ) 1 + 1 16ζ 2

1 2 , and step size α k = 1 4L . Then, Algorithm 2 outputs the point θK achieves

EQUATION

)

By the result in Theorem 3, under Assumption 1, to achieve the -FOSP, Algorithm 2 (VRMPO) needs 13 ) random trajectories. As far as we know, our VRMPO matches the best-known sample complexity as the HAPG algorithm (Shen et al., 2019) .

K(N 1 + (m -1)N 2 ) = 8L(E[J ( θ0)]-J (θ * )) (ζ-5 32 ) 1 + 1 16ζ 2 1 + 1 8Lζ 2 + 1 2(ζ-5 32 ) 1 + 1 32ζ 2 σ 1 2 = O(

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 Papini et al. (2018) show that the SVRPG achieves the sample complexity of O( -4 ). Later, under the same assumption as (Papini et al., 2018) , Xu et al. (2019) reduce the sample complexity of SVRPG to O( -10 3 ). 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.

H h=0 π θ0 (a h |s h ) π θt (a h |s h ) ,Var[g(τ |θ)] < +∞,

5. RELATED WORKS:

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 Rényi divergence (Ré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,

EQUATION

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,

EQUATION

)

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) -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 ) 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.

6. EXPERIMENTS:



6.1. NUMERICAL ANALYSIS OF MPO:

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. 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. where p -1 + q -1 = 1, p, q > 1. According to (Beck & Teboulle, 2003) , ( 23) is equivalent to

Performance Comparison:



Effect of Mirror:

θ k+1 = ∇ψ * (∇ψ(θ k ) + α k ĝk ),

where ∇ψ j (x) and ∇ψ * j (y) are p-norm link functions (Gentile, 2003) :

∇ψ j (x) = sign(xj )|xj | p-1 x p-2 p , ∇ψ * j (y) = sign(yj )|yj | q-1 y q-2 q

, 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.

6.2. EVALUATE VRMPO ON CONTINUOUS CONTROL TASKS:

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- 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.

7. CONCLUSION:

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.

A PROOF OF THEOREM 2:

Let f (x) be a L-smooth function defined on R n , i.e ∇f (x) -∇f (y) ≤ L x -y . Then, for ∀x, y ∈R n , the following holds

EQUATION

)

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 R d , h : X → R be a convex function, but possibly nonsmooth, and D ψ : X × X → R is Bregman divergence. Moreover, define

EQUATION

)

where g ∈ R d , x ∈ X , and η > 0. Then, the following statement holds

EQUATION

)

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 g 1 , g 2 ∈ R d , the following statement holds

EQUATION

)

Theorem 2 (Convergence Rate of Algorithm 1) Under Assumption 1, and the total trajectories are {τ k } N k=1 . Consider the sequence {θ k } N k=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 ĝk = 1 k k i=1 g i , where

g i = Hτ i t=0 ∇ θ log π θ (a t |s t )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α 2 k )

.

Proof. (Proof of Theorem 2):

Let T = {τ k } N k=1 be the trjecories generated by the differentiable parametric policy π θ . At each terminal end of a trajectory τ k = {s t , a t , r t+1 }

Hτ k t=0 ∈ T , let g k = Hτ k t=0 ∇ θ log π θ (a t |s t )R(τ k )| θ=θ k , ĝk = 1 k k i=1 g i ,

according to Algorithm 1, at the terminal end of k-th episode, k = 1, 2, • • • , N , the following holds,

θ k+1 = arg min θ -ĝ k , θ + 1 α k D ψ (θ, θ k ) = M ψ α k , (-ĝ 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 , (-ĝ k ,θ k ) (θ k ) + Lα 2 k 2 G ψ α k , (-ĝ k ,θ k ) (θ k ) 2 = J (θ k ) -α k ĝk , G ψ α k , (-ĝ k ,θ k ) (θ k ) + Lα 2 k 2 G ψ α k , (-ĝ k ,θ k ) (θ k ) 2 + α k k , G ψ α k , (-ĝ k ,θ k ) (θ k ) , where k = -ĝ k -(-∇J(θ k )) = -ĝ k -∇J (θ k )

. By Eq.( 34) and let h(x) ≡ 0 and η = α, then P X (θ, g, α) = G ψ α, (g,θ) (θ). Furthermore, by Eq.( 35), let η = α k and g = -ĝ k , then we have

EQUATION

Rearrange Eq.( 37), we have

J (θ k+1 ) ≤ J (θ k ) -ζα k - Lα 2 k 2 G ψ α k , (-ĝ k ,θ k ) (θ k ) 2 + α k k , G ψ α k , (-∇J(θ k ),θ k ) (θ k ) + α k k G ψ α k , (-ĝ k ,θ k ) (θ k ) -G ψ α k , (-∇J(θ k ),θ k ) (θ k ) .

By Eq.( 36), let x = θ k , g 1 = -ĝ k , g 2 = -∇J(θ k ), h(x) ≡ 0, then the following statement holds

EQUATION

Summing the above Eq.( 38) from k = 1 to N and with the condition α k ≤ ζ L , we have the following statement

EQUATION

Recall

EQUATION

Let F k be the σ-field generated by all random variables defined before round k, ˜ k = g k -∇J (θ k ) then the Eq.( 40) implies:

EQUATION

Furthermore, the following statement holds

EQUATION

)

By Lemma 1 and Eq.( 42), we have

EQUATION

Taking Eq.( 43) in to Eq.( 39), and taking expections w.r.t F N , we have

N k=1 ζα k -Lα 2 k E G ψ α k , (-ĝ 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α 2 k )

.

Particularly, if the step-size α k is fixed to a constant:ζ/2L, then

E[ G ψ αn, (-ĝ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 = ln N + 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( ln N N ) as

E[ G ψ αn, (-ĝn,θn) (θ n ) 2 ] ≤ 4LD 2 J + 2σ N k=1 1 k N ζ = O( ln N N ).

B SHORT CORRIDOR WITH SWITCHED ACTIONS:

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.

S G:

1 2 3

(a)

Figure 4 : Short corridor with switched actions (Chapter 13, (Sutton & Barto, 2018) ).

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.

C PROOF OF THEOREM 3:

We need the following lemmas to prove the convergence result. Lemma 3 (Lemma1 (Fang et al., 2018) ). Under Assumption 1, G k,t is generated according to (25), θ k,t is generated according to (26), then for any 0 ≤ t ≤ m, the following holds

EQUATION

Telescoping Eq.(3) over t from 1 to the time t, then the following holds

EQUATION

) Lemma 4. Let ζ > 5 32

, the batch size of the trajectories of outer loop

N 1 = 1 8Lζ 2 + 1 2(ζ-5 32 ) 1 + 1 32ζ 2 σ 2 2 , the iteration times of inner loop m -1 = N 2 = 1 8Lζ 2 + 1 2(ζ-5 32 ) 1 + 1 32ζ 2 σ

, and step size α k = 1 4L . For each k and t, G k,0 and θ k,0 are generated by Algorithm 2, then the following holds,

EQUATION

)

Proof.

EQUATION

)

Theorem 3 (Convergence Rate of VRMPO) The sequence { θk } K k=1 is generated according to Algorithm 2. Under Assumption 1, let ζ > 5 32 , the batch size of the trajectories of outer loop

N 1 = 1 8Lζ 2 + 1 2(ζ-5 32 ) 1 + 1 32ζ 2 σ 2 2 , the iteration times of inner loop m -1 = N 2 = 1 8Lζ 2 + 1 2(ζ-5 32 ) 1 + 1 32ζ 2 σ

, the iteration times of outer loop K = 8L (m -1)(ζ -5 32 )

1 + By the definition of Bregman grdient mapping in Eq.( 10) and iteration (26), let α k = α, we have

EQUATION

EQUATION

where we introduce g k,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[ g k,t 2 ] - α 2 2 .

In fact,

EQUATION

Eq.( 53) holds due to the Cauchy-Schwarz inequality | u, v | ≤ u v ≤ 1 2 ( u 2 + v 2 ) for any u, v ∈ R n . Eq.( 54) holds if h ≡ 0 by Eq.( 35).

Taking expectation on both sides of Eq(54), we have

EQUATION

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 )] + α 3 L 2 2N 2 t i=1 E g k,i 2 + α 2 1 2 -ζα - Lα 2 2 - α 2 E g k,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

EQUATION

Eq.( 56) holds due to t ≤ m -1.

If t = m -1, then by the last Eq.( 57) implies

EQUATION

Step 2: Analyze the outer loop of Algorithm 2

We now consider the output of Algorithm 2,

EQUATION

Recall the notation in Eq.( 52)

g k,t = 1 α (θ k,t -arg min u { G k,t , u + 1 α D ψ (u, θ k,t )}) = G ψ α, G k,t ,u (θ k,t ),

and we introduce following g(θ k,t ) to simplify notations,

EQUATION

Then, the following holds

EQUATION

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)

EQUATION

which implies the following holds

EQUATION

For another part of Eq.( 61), notice ν = k(m -1) + t, then we have

EQUATION

Eq.( 65) holds due to the fact that the probability of selecting ν = k • (m -1) + t is less than 1 K . Taking Eq(62) and Eq.( 65) into Eq.( 61), then we have the following inequity

EQUATION

EQUATION

D EXPERIMENTS 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

EQUATION

where L θ (s, a) = -log π θ (s, a)Q ω (s, a) is the training loss of actor, {(s i , a i )} N i=1 ∼ D, Q ω (s, a) is an estimate of action-value that can be trained to minimize the loss of critic

EQUATION

)

More details of implementation are provided in the following Algorithm 3.

In this section, we use p as the mirror map. 

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| = 10 6 . 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.

:



Figures and Tables:

Figure 1: Comparison the performance of MPO with REINFORCE and VPG on the short-corridor grid world domain. In this experiment, we use features φ(s, right) = [1, 0] and φ(s, left) = [0, 1] , s ∈ S. Let L θ (s, a) = φ (s, a)θ, (s, a) ∈ S × A, where A = {right, left}. π θ (a|s) is a exponential soft-max distribution defined as π θ (a|s) = exp{L θ (s, a)} a ∈A exp{L θ (s, a )} . The initial parameter θ 0 = U[-0.5, 0.5], where U is uniform distribution.

Figure 2: Comparison of the empirical performance of MPO between non-Euclidean distance (p = 2) and Euclidean distance (p = 2) on standard domains: MountainCar, Acrobot and CartPole.

Figure 3: Learning curves for continuous control tasks. The shaded region represents the standard deviation of the score over the best three trials. Curves are smoothed uniformly for visual clarity.

Figure 5: Short corridor with switched actions (Chapter 13, (Sutton & Barto, 2018)).

step size α k = 1 4L . Then, Algorithm 2 outputs the point θK achievesE[ G ψ α, -∇J( θK ),θ ( θK ) ] ≤ .(51)Proof. (Proof of Theorem 3)

Figure 6: Learning curves of test score over epoch, where we run 5000 iterations for each epoch. The shaded region represents the standard deviation of the test score over the best 3 trials. Curves are smoothed uniformly for visual clarity.

Figure 7: Learning curves of max-return over epoch, where we run 5000 iterations for each epoch. The shaded region represents the standard deviation of test score over the best 3 trials. Curves are smoothed uniformly for visual clarity.

Comparison on complexity required to achieve ∇J(θ) ≤ . Particularly, if ψ(θ) = (a h |s h )π θ t (a h |s h ) .input-dependent baseline to reduce variance, and analytically show its benefits over state-dependent baselines. Recently,Grathwohl et al. (2018);Cheng et al. (

Table content: <table><tr><td>1 2 θ 2 2 , then the result (30) of our VRMPO is measured by gradient. Beside, ρ t</td><td>def =</td><td>h=0 H</td><td>π θ 0</td></tr></table>

Max-average return over 500 epochs, where we run 5000 iterations for each epoch. Maximum value for each task is bolded.

Table content: <table><tr><td>Environment</td><td>Our VRMPO</td><td>TD3</td><td>DDPG</td><td>PPO</td><td>TRPO</td></tr><tr><td>Walker2d-v2</td><td>5251.83</td><td colspan="4">4887.85 5795.13 3905.99 3636.59</td></tr><tr><td>HalfCheetah-v2</td><td>16095.51</td><td colspan="4">11781.07 8616.29 3542.60 3325.23</td></tr><tr><td>Reacher-v2</td><td>-0.49</td><td>-1.47</td><td>-1.55</td><td>-0.44</td><td>-0.66</td></tr><tr><td>Hopper-v2</td><td>3751.43</td><td colspan="4">3482.06 3558.69 3609.65 3578.06</td></tr><tr><td>InvDoublePendulum-v2</td><td>9359.82</td><td colspan="4">9248.27 6958.42 9045.86 9151.56</td></tr><tr><td>InvPendulum-v2</td><td>1000.00</td><td>1000.00</td><td colspan="3">907.81 1000.00 1000.00</td></tr></table>

Peer review (iclr2020):
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. The notations are inconsistent. In eq (14) the trajectory index is k, while in eq (16) the index changed to n. In eq (28), the trajectory is denoted by , while in the algorithm, there is no index in . Definition of P in eq (36) seems to overlap with that of in eq (10), which means the same quantity was defined twice using two different notations. Section 3.1 is almost the same as in Ghadimi et al., (2016), both the theorem and remarks. Since this is not a new finding, I suggest the authors to simplify the current statement in this subsection. In Theorem 1 & 2, the authors used the criteria to establish the convergence result. However, they used to establish the convergence result in Theorem 3. This is kind of confusing because in different criteria, the complexity result will be different. It seems that eq (32) is the same as eq (28). Can the authors elaborate the differences discussed in the paragraph after eq (32) in more detail? In eq (40), is defined as the average gradient over all the iterates up to , which means is a function of . But , according to eq (21) in Algorithm 1, is just defined based on the current policy parameter . I am skeptical why these two terms will be equal. This seems to be a technical issue of the whole proof of Theorem 2. The derivation in (55) seems incorrect. In particular, the authors called Lemma 3, which is the result in Fang et al. (2018). However, the recursive gradient is defined differently in the current paper and in Fang’s paper. In Fang’s paper, at different iterations, the data are sampled from an unknown but fixed data distribution. But in this paper, since the data are sampled from the current policy which varies at each iteration, the data distribution is changing all the time. Therefore, Lemma 3 does not hold in the setting of this paper. In all the experiments, it is strange that the proposed VRMPO was not compared with any of the other variance reduced algorithms listed in Table 1. I think it would be more convincing to demonstrate the improvement in Table 1 by comparing the proposed VRMPO with at least one other variance reduced algorithm. Other comments: 1. On page 15, the first sentence of the proof: “trjecories” -> “trajectories” 2. What is in eq (39)? It was not defined in the paper. 3. In the statement of Lemma 3, the authors said “telescoping Eq. (3) ...” However, Eq (3) in this paper is the definition of policy gradient. I assume this is a typo? 4. What is in eq (50)? It seems that this term does not appear in Lemma 4. ====after rebuttal==== Thanks for the authors* response. I am not satisfied with their response since they did not directly answer many of my questions about the technical flaws in this paper. The response of the authors on the difference between estimator in Shen et al (2019) and the estimator in this paper is incorrect. The estimator in Shen et al. (2019) can also be constructed recursively based on G_0. The authors also claimed that equation (40) is correct. However, this is not true. Although the authors removed from equation (40), they still used the property that is an unbiased estimator in the equation after (40). Note that is defined based on . Therefore, the proof is still problematic. The authors did not show how to fix it. A more important issue of the direct use of Lemmas from Fang et al. (2018) is not fixed either. In their response, the authors simply changed the data generation in the inner loop of their algorithm such that all the iterates generate data from the initial policy . However, this will cause the expectation of all the stochastic gradients used in their proof to be equal to the true policy gradient at the initial point, i.e., . In other words, they can never obtain the full gradient even though their goal is to bound which definitely requires an approximation of . Therefore, the issue cannot be fixed by simply using the same distribution in all the inner loop iterates. I suggest the authors to read more carefully the paper by Fang et al. (2018) and Papini et al. (2018) to understand the difference in the two settings.