Title: POLICY OPTIMIZATION VIA STOCHASTIC RECURSIVE GRADIENT ALGORITHM

Abstract: In this paper, we propose the StochAstic Recursive grAdient Policy Optimization (SARAPO) algorithm which is a novel variance reduction method on Trust Region Policy Optimization (TRPO). The algorithm incorporates the StochAstic Recursive grAdient algoritHm(SARAH) into the TRPO framework. Compared with the existing Stochastic Variance Reduced Policy Optimization (SVRPO), our algorithm is more stable in the variance. Furthermore, by theoretical analysis the ordinary differential equation and the stochastic differential equation (ODE/SDE) of SARAH, we analyze its convergence property and stability. Our experiments demonstrate its performance on a variety of benchmark tasks. We show that our algorithm gets better improvement in each iteration and matches or even outperforms SVRPO and TRPO.

1. INTRODUCTION:

Reinforcement Learning (RL) (Sutton et al., 1998) is a dynamic learning approach to interact with the environment and make actions so certain measure of cumulative rewards is maximized. It achieves remarkable performance in several tasks including continuous control, video games, etc. Among all existing RL algorithms, policy gradient (Sutton et al., 1999) is the most fundamental method for RL. However, policy gradient suffers from sample inefficiency and high variance during the training phase. We could use reward shaping techniques such as, REINFORCE (Williams, 1992) , GAE (Schulman et al., 2015b) , etc., as an variance reduction. Besides, trust region policy optimization (TRPO) was proposed by (Schulman et al., 2015a) to remedy this problem. It merges the trust region method (Nocedal & Wright, 2006) and the natural gradient theory (Amari, 1998) into the policy gradient framework. The basic idea is to make the policy move toward the direction that improves mean episode rewards under the constraint of the Kullback-Leibler (KL) divergence with the old policy distribution.

Compared to traditional gradient descent which corresponds to the L 2 constraint, constraints that uses KL distance has been widely adopted as an alternative choice. The KL constraint results a natural gradient update firstly proposed by Amari (1998) . Later Kakade (2001) merges the natural gradient into the policy gradient (See Martens (2014) for further extensions). Natural gradient attempts to solve the problem of vanishing gradients in the so-called plateau areas. TRPO which strictly constrain the KL distance achieves a more robust performance on continuous control tasks.

Policy gradient optimization method shares similar structure with traditional optimization thus can be powerfully augmented by variance reduced gradient methods. For example, SVRG (Johnson & Zhang, 2013 ) is a kind of stochastic variance reduced method that overcomes the fallback of SGD of large variance and potentially accelerates the RL training. Previous works use SVRG to accelerate policy gradient (SVRPG) and its TRPO variants (SVRPO) (Xu et al., 2017; Papini et al., 2018) . The variance reduced version of policy gradient allows a multi-step optimization for each batch of data, while the vanilla policy gradient optimizes the policy once each iteration. In theory, SVRG accommodates with larger stepsize for each iteration and observably outperforms traditional PG and TRPO, respectively. Furthermore, the introduction of stochastic variance reduction not only improves sample efficiency but also stabilizes the training process by reducing the variance and accommodate larger stepsize.

In this paper, we focus on studying variance reduction method on TRPO. We discussed an alternative variance reduction method called SARAH, recently proposed by (Nguyen et al., 2017) whose convergence rate matches that of SVRG in the convex case and has the inner-loop convergence property that SVRG does not possess. We propose a new algorithm named SARAPO which hybrids the SARAH method with TRPO and analyze the dynamics of SVRG/SARAH on natural gradient updates via its approximating ordinary and stochastic differential equation (ODE/SDE).

In experiments, we test the performance and sample efficiency of SARAPO, SVRPO, and TRPO. To allow larger steps in SVRPO/SARAPO, we remove the KL constraint in the line search of TRPO. We verify that variance reduction enables a larger leap towards the optima and find that SARAPO outperforms TRPO and matches the performance of SVRPO in most of the tasks.

The rest of this paper is organized as the following: we introduce some background, propose and analyze our algorithm in Section 2. In Section 3, we theoretically analyze our proposed SARAPO algorithm from a dynamical system viewpoint. We present the numerical results of experiments in Section 4 and conclude our paper in Section 5.

2. PRELIMINARIES AND METHODOLOGY:

The reinforcement learning task can be considered as solving a discrete time Markov Decision Process (MDP) M = {S, A, P, R, γ, ρ}, where S is the set of states, A is the set of actions, R : S × A → R is the reward function, γ is the discount factor and ρ the initial state distribution. The policy gradient method take steps by directly maximizing the expected sum of discounted rewards:

L(π w ) = E πw ∞ t=0 γ t r t (s t , a t )

with respect to the parameters w of the stochastic policy π w (a|s). The gradient of the objective function ∇ w L is given by:

EQUATION

where Q π is the state-action function (i.e., the Q function) defined as the expected return when taking action a t from state s t . The expectatioin is calculated by Monte-Carlo simulation by sampling n timesteps {s t , a t , r t } n t=1 of policy π w .

2.1. TRUST REGION POLICY GRADIENT:

As the policy gradient is highly unstable and sample inefficient, TRPO introduces the trust region method to policy gradient to limit how far the new policy is deviated from the old policy. Instead of the L 2 norm in trust region method, TRPO takes KL as the measure of distance. Furthermore, to make computation easy, the algorithm turns the KL constraint problem into a penalized problem. TRPO optimizes the surrogate loss at every iteration:

EQUATION

At every iteration, TRPO takes an update of:

EQUATION

where v t = ∇ w L and F is the Fisher Information Matrix (FIM)

F = E a,s∼piw [∇ log π w (a|s) • ∇ log π w (a|s) T ].

The initial step size η is calculated by limiting the KL distance within the range δ:

EQUATION

Algorithm 1 SARAPO Initialization:

Initialize w 0 = w 1 to be a randomized parameter. for t = 1 to T do if t%m == 0 then Set w = w t Run policy π wt for N timesteps. Store a batch of trajectories D. Calculate the baseline gradients:

ṽ0 = 1 |D| x∈D ∇L x (w t )

else Draw a mini-batch D t of size M from D Calculate the estimated gradient w t :

ṽt = ṽt-1 + 1 |D t | x∈Dt (∇L x (w t ) -∇L x (w t-1 ))

end if Update policy parameter with Algorithm 2 end for Ensure: w ← wT 2.2 SARAH AND SVRG FOR NATURAL GRADIENT SARAH (Nguyen et al., 2017) and SVRG (Johnson & Zhang, 2013) are among the recently popularized variance reduced gradient algorithms in optimization. They reduce the variance during the optimization process and achieve a faster convergence rate. Instead of calculating the full gradient ∇L.

Recall that SVRG calculate a mini batch of size m in each inner loop, and it updates the weights as follows:

v t+1 = ṽ + ∇ w L m (w t ) -∇ w L m ( w) w t+1 = w t -ηF -1 v t+1

where ṽ and w stores the full gradient and weight parameters as the output of the previous loop, and L m is the objective function estimated using m samples. Here the update rule of w t involves the inverse of the Fisher information matrix as in TRPO, which is computed via CG method. Also, v t provides an unbiased estimation of the true gradient while the variance is much reduced when w t is close to w SARAH, on the other hand, estimates each gradients using a recursive gradient update rule. It adds the gradient estimated one step before v t by the difference of gradients between the current parameter and the previous parameter

∇ w L m (w t ) -∇ w L m (w t-1 ) estimated over a mini batch.

The core update rule is as follows:

v t+1 = v t + ∇ w L m (w t ) -∇ w L m (w t-1 ) w t+1 = w t -ηF -1 v t+1

In SARAH, the algorithm exchanges unbiasedness of the gradient with a much reduced variance of such. We will analyze the iteration in Section 3.

2.3. STOCHASTIC GRADIENT RECURSIVE POLICY OPTIMIZATION:

Our goal in this section is to combine the SARAH with TRPO for natural gradient and formally propose the SARAPO algorithm. The details of calculating the estimated gradients are listed in Algorithm 1. There, we use w to denote the old policy parameters saved at the beginning of each outer loop. After calculating the estimate of the gradient, we conduct a TRPO step. We note that as the Fisher Information Matrix can be approximated by Hessian matrix of the KL divergence when Algorithm 2 Inner loop details Estimate the Fisher Information Matrix F =

∂ 2 ∂wn∂wm KL(π wt (• s n ), π w (• s n ))

| wt Update policy parameter with mini-batch I j :

w t+1 ← w t + η t F -1 (w t ) • vt .

where the F -1 (w t ) • vt is computed using the conjugate gradient method Initialize η t according to equation 4 Line-search η j , η j /2, η j /4, • • • for improving L π w (πw)

the current distribution exactly matches that of the base distribution. As a consequence, we should use the second derivative of the KL distance between the current parameters and the parameters one step before to estimate F , which is to penalize the KL between each inner loop updates, instead of the outer loop updates in TRPO. The Fisher information matrix is only estimated using a mini batch of the data. And the inverse Fisher vector product is calculated by the conjugate gradients algorithm.

Different from the line-search process in TRPO, we do line-search only to find the stepsize η that can improve the policy loss. Due to the fact that the variance is reduced, we can take a larger step away. So we remove the KL condition in the line-search and let the algorithm to find the KL distance of the outer loop updates itself. Detailed description is in Sec 4.

3. THEORY OF DYNAMICAL SYSTEMS:

Recall that the core inner-loop update rule of Stochastic Recursive Gradient Method (SARAH) (Nguyen et al., 2017) is, assuming the minibatch size is 1,

v t+1 =v t + ∇L it+1 (w t ) -∇L it+1 (w t-1 ), w t+1 =w t -ηv t+1 .

Here we provide a simple alternative viewpoint of (random) dynamical systems. The method of using dynamical systems and continuous-time framework have been adopted to characterize variants of gradient descent algorithms (Su et al., 2016; Li et al., 2017) , but to our best knowledge, it has never been used to analyze variance reduced gradient methods before this work.

As we could see from Algorithm 1, we applied a scaled-form of SARAH in combination with Trust Region Policy Optimization by the inverse Fisher Information matrix F -1 . Seeing this, the inner loop update has the essential form of

EQUATION

For simplicity of analysis, we consider the quadratic approximation approach. Let the quadratic objective function L(w

) := 1 n n i=1 L i (w), with L i (w) = 1 2 w H i w + g i w.

We sketch the analysis using ODE and SDE, in order to better understand the dynamics.

3.1. ODE ANALYSIS:

By rescaling the time t = η -1 s according to the stepsize η, we define a new process

V (s) = v η -1 s and X(s) = w η -1 s .

Then the newly defined process is converted from equation 5 and has the form

V (s + η) =V (s) + ∇L is+η (X(s)) -∇L is+η (X(s -η)) =V (s) + HX(s) -HX(s -η) + ηe s+η ,

where e s+η is a martingale difference noise term of O(1), and

X(s + η) =X(s) -ηF -1 V (s + η).

Substituting X(s) -X(s -η) with -ηF -1 V (s), we derive the update rule for V (s)

η -1 (V (s + η) -V (s)) = -HF -1 V (s) + e s+η .

From the standard weak convergence theory, one easily conclude the following:

Theorem 1 When η → 0 + , the scaled SARAH update rule (5) can be approximated by the following ODE system

EQUATION

Note in ( 6), the dynamics of V (s) forms an autonomous ODE, which is independent of the dynamics of X(s).

Left multiplying both sides of the first line of equation 6 by F -1 , one obtains

d ds (F -1 V (s)) = -F -1 H(F -1 V (s)).

Noticing V (0) = HX 0 , we can easily verify that the V (s) can be solved as

EQUATION

By combining V (s)'s solution with the update rule for X(s), we have

d ds X(s) = -exp(-s • F -1 H)F -1 HX 0 ,

and has the expressed solution

X(s) = X 0 -(I -exp(-s • F -1 H))X 0 .

As a result, we reach the following solution to (6):

EQUATION

From ( 7) and ( 8), both the vectors X(s) and V (s) exponentially decays with rate matrix F -1 H which is consistent with the theory of natural gradient ascent (Kakade, 2001) .

3.2. SDE ANALYSIS:

The ODE analysis simply neglects the effect of noise. Here we turns to develop a stochastic differential equation approximation tool to exploit the effect of noise. Denote H i = H + E i , H being the Hessian for L(w). Further assume that the noise term E i is σdiag(χ 1 , . . . , χ d ) where χ i are i.i.d. standard normal, for simplicity.

Define the coordinate-wise product of two vectors (x 1 , . . . , x d ) • (y 1 , . . . , y d ) = (x 1 y 1 , . . . , x d y d ) . Let W (s) = (W 1 (s), . . . , W d (s)) be a d-dimensional standard Wiener processes. Then under standard assumptions, the inner loop has an update rule for V (s) which can be written as

V (s + η) -V (s) = -ηHF -1 V (s) -ησ χ • (F -1 V (s)) = -ηHF -1 V (s) -η 1/2 σ (W (s + η) -W (s)) • (F -1 V (s)).

As η → 0 + , it becomes a SDE system

d ds V (s) = -HF -1 V (s) -η 1/2 σ d ds W (s) • (F -1 V (s)),

which can be simplified as

EQUATION

From the above analysis, one can verify that the approximating SDE in (9) introduces a small (size of O(η 1/2 )) noise deviation from its ODE curve, and hence enjoys similar property as the natural gradient descent update. In the case where H is convex, the dynamics validates the property of innerloop convergence in (Nguyen et al., 2017) [Theorem 1a & 1b] , and hence the multi-loop geometric convergence [Theorem 2]. The per-step cost, however, turns to be evaluations of two individual gradients instead of the whole-batched gradients.

Remark 1 One may also conduct a similar analysis for SVRG and conclude the same approximating ODE for scaled SVRG. The approximating SDE, nevertheless, shall differ by an extra noise term that is proportional to the distance between the current iterate and the control point. This well-explains the inner-loop convergence and stability properties that SARAH enjoy upon SVRG.

4. EXPERIMENTS:

In this section, we design a set of experiments to investigate the following questions:

• Does the performance of SARAPO matches the performance of SVRPO or even better? Which algorithm trains faster and achieves better mean episode reward? • What happens in the inner loop? Does the variance reduction methods reaches a better optimum than gradient descent? • What is the actual KL divergence between the updated policy and the old policy?

Our implementation is based on the modular rl. We choose the commonly used MuJoCo (Todorov et al., 2012) environment on several tasks: Swimmer, Half-Cheetah, Walker, and Hopper, and we also test the algorithms on two classic continuous control tasks: Pendulum and CartPole. We compare our implementation of SARAPO with SVRPO and the original TRPO. The result is shown in Figure 1 .

4.1. EXPERIMENTAL SETTINGS:

We follow the settings of Xu et al. (2017) and Schulman et al. (2015a) to fix part of our parameters. We set the number of steps per iteration to be 50000 and the discount factor to be 0.995. We use a gaussian policy with a diagonal covariance matrix, whose mean is parameterized by a multi-layer perceptron (MLP). For all tasks, we use two hidden layers of size (64, 64) with tanh activation function. We fine-tuned other parameters as follows: minibatch size chosen in {1000, 5000}, the number of inner loop iteration in {20, 50}, inner loop max Kullback-Leibler divergence being in [0.005, 0.01], and the Conjugate Gradient damping factor is 0.1. We list the detailed parameters of each experiment in the Appendix.

For comparing fairly, we chose five different random seeds and plotted our result as the average of the five runs. As the number of the outer loop iteration is fixed, the x-axis is proportional to the number of samples we have drawn and the curve corresponds to the sample efficiency.

4.2. COMPARISON BETWEEN SARAPO, SVRPO AND TRPO:

In Figure 1 , we compared the learning curve of three algorithms which are SARAPO, SVRPO and TRPO. On the classic continuous control tasks such as Pendunlum and CartPole which are 2D balancing tasks, SARAPO outperforms other two algorithms. Specifically, SARAPO converges faster than SVRPO and TRPO and gets high mean episode reward at the end stage of the training process. We see that in Half-Cheetah environment which is a 3D continuous-control locomotion task, SARAPO observably performs better than other two algorithms and achieves a high score in 500 epochs. In Walker and Hopper (3D continuous-control locomotion task), the three algorithms exhibits comparable performance. SARAPO converges faster in Swimmer but SVRPO reaches a better score.

We make two more tables to get a clearer view of our result. Table 1 presents the number of iterations needed to cross the threshold of 90 percent of the best score. In four of the tasks, SARAPO reaches Table 2 shows the final performance of policy which is the average of best reward over five different seeds.

4.3. DETAILS:

We perform further experiments to investigate the phenomenon during the training process. By analyzing on statistics of the small step updates and the outer loop updates respectively, we summarize three meaningful statistics: The norm of estimated gradients in each small step gives us a glimpse on how the gradient value is changing. The policy loss improvement is the absolute difference between the objective function value before and after an outer loop update, which intuitively visualize the expected increase in the mean episode reward. And the KL divergence between outer loop updates illustrates the difference between the old policy and the updated policy. Larger KL divergence and loss improvement are indicators of a good policy update. We zoom in the plot and choose the range of our x-axis to be in an interval that the mean episode reward is increasing. Note that this is a result of one single random run. The training curve of this run is shown in the Appendix.

In the first column, we plot the L 2 norm of the estimated gradient of SVRG and SARAH. Then the second column is the loss function both before and after an outer loop update. For SARAPO and SVRPO, this statistics is the sum of the increase in each small step update. We compare the result with the policy loss improvement in TRPO. From this, we verify our conjecture that both SARAH and SVRG reach a better optimum than SGD. Generally, a more significant increase in loss corresponds to a higher mean episode rewards.

The third column shows the KL divergence between the old policy and the updated policy. We observe that although we do not constrain the KL strictly in the line search, the KL of TRPO stays under the given threshold. In the interval to plot the result, KL constraint is set to be 0.01, TRPO stays under 0.01, SARAPO stays under 0.02, and SVRPO stays under 0.03. This is a good illustration that KL divergence won't step two far away after several inner loop updates. The variance reduced gradient finds a better solution slightly outside the KL range.

5. CONCLUSION:

In this work, we propose a sample-efficient and variance reduction method for reinforcement learning called Stochastic Recursive Gradient Policy Optimization (SARAPO) algorithm. We hybrid the recently proposed SARAH algorithm which is a kind of variance reduction method with TRPO, which is the state-of-the-art model-free policy gradient methods in continuous control tasks together. We also provide theory which presents our algorithm enjoys the better properties by using ordinary and stochastic differential equations. Our experiments show its advantage over existing policy optimization methods such as TRPO and SVRPO. We hope this work can inspire future works and ultimately achieve higher performance in the reinforcement learning tasks. 

:



Figures and Tables:

Figure 1: A comparison of variance reduced policy optimization and traditional TRPO. The result is the mean of five runs on different random seeds.

Figure 4.3 incorporates the result of all three statistics of three different tasks. The first row shows the training process of Swimmer, the second row is the Hopper task and the third row is Half-Cheetah.

Figure 2: An illustration of the policy loss improvement, the estimated gradients norm and the KL divergence during training. The first row is the results on the Swimmer task. The second row is the results on the Hopper task. The third row is the results on the HalfCheetah. The pictures are zoomed in to show more details and the x-axis is normalized to be the number of outer loop iterations.

Figure 3: The Mean Episode Reward of the experiments in Figure 4.3

Number of Iteration Below the Threshold

Table content: <table><tr><td>Tasks</td><td colspan="5">Threshold SARAPO SVRPO TRPO</td></tr><tr><td>Pendulum</td><td colspan="2">-250</td><td>23</td><td>27</td><td>34</td></tr><tr><td>CartPole</td><td>450</td><td/><td>5</td><td>10</td><td>18</td></tr><tr><td>Swimmer</td><td>302</td><td/><td>52</td><td>72</td><td>71</td></tr><tr><td>Half-Cheetch</td><td colspan="2">4561</td><td>216</td><td>251</td><td>402</td></tr><tr><td>Walker</td><td colspan="2">4669</td><td>343</td><td>274</td><td>330</td></tr><tr><td>Hopper</td><td colspan="2">3198</td><td>74</td><td>65</td><td>78</td></tr><tr><td>Tasks</td><td colspan="4">SARAPO SVRPO TRPO</td></tr><tr><td colspan="2">Pendulum</td><td>-149.4</td><td colspan="2">-167.9 -147.1</td></tr><tr><td colspan="2">CartPole</td><td>500</td><td>500</td><td>500</td></tr><tr><td colspan="2">Swimmer</td><td>343.0</td><td>355.7</td><td>336.5</td></tr><tr><td colspan="2">Half-Cheetch</td><td>6845.1</td><td>5291.4</td><td>5080.9</td></tr><tr><td>Walker</td><td/><td>5232.9</td><td>5529.2</td><td>5265.2</td></tr><tr><td>Hopper</td><td/><td>3578.1</td><td>3625.8</td><td>3692.8</td></tr></table>

Performance of Policythe threshold the fastest and in the other two tasks, SVRPO outperforms the other two algorithms. In Table2, on HalfCheetah task, SARAPO outperforms other two algorithms.

Table content: <table/>

Peer review (iclr2019):
 The paper extends Sarah to policy optimization with theoretical analysis and experimental study. 1) The theoretical analysis under certain assumption seems novel. But the significance is unknown compared to similar analysis. 2) The analysis demonstrates the advantage of Sarah over SVRG, as noted in Remark 1. It would be better to give explicit equations for SVRG in order for comparison. 3) Experimental results seem to show empirically that the SARAH is only comparable to SVRG. 4) Presentation needs to be improved.