A Restart-based Rank-1 Evolution Strategy for Reinforcement Learning

1 Introduction

In reinforcement learning (RL), faced with a specific environment, an agent attempts to learn to conduct a sequence of actions with the aim of maximizing a kind of cumulative reward [Sutton and Barto, 1998]. The popular RL algorithms (such as Q-learning and policy gradient method) and the neuroevolution approach (that is, applying black-box optimization methods to train neural networks) have been demonstrated to perform well on challenging deep RL problems. It is worth noting that among these algorithms for RL, evolution strategies (ESs) have been demonstrated to have the ability to roughly train deep neural networks and can well accomplish the deep RL tasks [Salimans et al., 2017].

Existing ES variants for deep RL only involve the plain variants (such as Natural Evolution Strategies (NES) [Wierstra et al., 2008] and (µ, λ)-ES [Schwefel, 1981]), but do not adopt one of the most efficient ESs, that is, the covariance matrix adaptation evolution strategy (CMA-ES) [Hansen and Ostermeier, 2014]. CMA-ES adapts the complete covariance matrix (representing the population) of the normal search distribution. It maintains and updates a Gaussian distribution during the search process. and attempts to use the contours of the Gaussian distribution to approximate that of the objective function. CMA-ES owns several important invariances, including the invariance against angle preserving transformations of the search space, the invariance against order preserving transformations of the objective function, and the scale invariance [Hansen and Kern, 2004]. Owing to its nice properties, CMA-ES has been successful in solving optimization problems in low to medium dimension. However, due to its high space and time complexity, it is unsuitable for large scale optimization [Varelas et al., 2018], and also unsuited to the training of deep neural networks and the solving of deep RL problems. Particularly, when training the neural network, standard CMAES needs to consume much time on maintaining and updating its full covariance matrix, due to its quadratic time complexity. As a result, the research of applying CMA-ES to RL is still a gap. In reality, the issue of how to apply CMA-ES or other advanced ES variants [Li and Zhang, 2017; Varelas et al., 2018] to deep RL in an efficient way is a rich research area, and has a great practical research value for deep RL problems.

To this end, this paper proposes a restart-based rank-1 evolution strategy (called R-R1-ES for short) for RL. This algorithm can be regarded as a simplified CMA-ES and can retain the excellent performance of CMA-ES. Notably, it is of linear time complexity and low space complexity, thus making it suitable for dealing with large scale black-box optimization and deep RL problems. Furthermore, compared to the original CMA-ES which searches along the coordinate axes and is more suitable for separable problem, the proposed ES variant can well deal with the dependency problem of different variables by virtue of adapting the principal search direction.

2 Preliminaries

As a class of black-box optimization algorithms, ESs belong to heuristic search algorithms inspired by natural evolution. At every generation, a population of parameter vectors are perturbed through sampling from a Gaussian distribution, and their objective function values are evaluated. The parameter vectors with better quality are then recombined to construct new distribution for the next generation, and this procedure is iterated until the termination criterion is fulfilled. Algorithms in this class differ in how they represent the population and how they perform mutation and recombination.

Substantially, NES can be viewed as an (1, λ)-ES algorithm [Beyer, 1993]. Suppose the parameter vector and the fitness function for a specific optimization problem are θ and F(θ), respectively. And let pφ(θ) denote a distribution of parameter vectors θ characterized by parameters φ. NES represents the population as pφ(θ), and strives to maximize the average fitness of the population Eθ∼pφ [F (θ)] by means of optimizing φ with stochastic gradient ascent method [Ruder, 2016].

Recently, scientists from OpenAI designed a version of NES applied to RL problems [Salimans et al., 2017]. This variant will be referred to as OpenAI-ES hereinafter. For an RL problem, θ is the parameters of a policy πθ, and the fitness function F(θ) denotes the stochastic reward over a full episode of agent interaction. At the t-th iteration, the population distribution pφt is an isotropic multivariate Gaussian with mean θt and covariance σ2 I (i.e., N (θt, σ2 I)). Different from NES which updates the mean and the covariance of the population distribution during the evolutionary process, OpenAI-ES does not attempt to evolve the covariance (reflected by σ). Thus, the mutation strength σ is fixed during the evolutionary process of OpenAI-ES.

At each iteration, λ parameter vectors θi t ∼ N (θt, σ2 I) (i = 1, . . . , λ) are sampled from the Gaussian distribution N (θt, σ2 I), and their corresponding policies πθi t are evaluated to obtain a reward F (θi t ). Similar to the classical REINFORCE method [Williams, 1992] in RL, OpenAI-ES computes the approximate gradient of expected reward with respect to θt in the following manner:

In fact, the sampling of θi t in OpenAI-ES is reformulated as adding additive Gaussian noise to θt: θi t = θt +σεi (εi ∼ N (0, I)). Then, Eq. (1) can be simplified according to the property of Gaussian distribution. Concretely, Eq. (1) can be converted to the following formula:

Furthermore, they also made several contributions to improve the performance of ES. The technique of virtual batch normalization [Salimans et al., 2016] and other reparameterizations of the neural network policy are adopted to enhance the reliability of ES. Moreover, by virtue of the high parallelization property of ES, a novel communication strategy based on common random numbers is introduced to reduce communication cost, and it can make the algorithm well scaled to a large number of parallel workers.

3 ProposedMethod: R-R1-ES

This section detailedly introduces the proposed R-R1-ES.

3.1 DistributionModel

Unlike all these existing ES variants for RL, the proposed R-R1-ES utilizes the Gaussian distribution model N (θt, σ2 t Ct ), where θt ∈ Rn (n is the dimension of the parameter vector θ) is the distribution mean, σt > 0 is the mutation strength, and Ct is the n × n covariance matrix at the t-th iteration. The covariance matrix Ct is set as follows [Li and Zhang, 2017]:

where ccov ∈ (0, 1) is called the changing rate of covariance matrix, and pt ∈ Rn is called principal search direction.

In reality, the aforementioned model is designed for capturing the most important search direction (reflected by pt) and parameter dependencies, so as to endow the proposed algorithm with the ability of handling the dependency problem of different variables. In addition, the term ptpTt in Eq. (3) produces an n × n matrix whose rank is 1. This is also why we call our proposed algorithm a rank-1 ES.

To realize the aforementioned model, the proposed R-R1ES needs to maintain the following critical variables at each generation of the evolutionary process:

• distribution mean θt ∈ Rn ;
• mutation strength σt > 0;
• principal search direction pt ∈ Rn .

Thus, the new model enables the R-R1-ES to achieve the adaptation of mean and mutation strength as well as the search direction.

3.2 Framework Of R-R1-ES

Algorithm 1 sketches the framework of our proposed R-R1ES algorithm. The important procedures will be introduced in details hereinafter.

At the beginning of Algorithm 1, the initialization procedure initializes a random parameter vector θ0 and several distribution parameters, including mutation strength σ0 = 0.05, principal search direction p0 = 0 and cumulative rank rate s0 = 0. For convenience, we set F0 = [F (θ0) , . . . , F (θ0)], which indicates that F0 contains µ function values of the initialized parameter vector θ0.

At the t-th generation, R-R1-ES samples λ random vectors zi ∼ N (0, I) and λ random variables ri ∼ N (0, 1) (i = 1, ..., λ), and constructs λ new solutions in the following manner:

Since R-R1-ES adopts the Gaussian distribution model N (θt, σ2 t Ct ) where Ct is determined by Eq. (3), new solutions can be sampled by using Eq. (4). Then, these λ new solutions are sorted in descending order according to their reward function values, and the best µ ones are selected to form Ft+1 = [F (x1:λ) , . . . , F (xµ:λ)], , where xi:λ (i = 1, . . . , λ) means that it is the i-th best solution among all the λ solutions. The best µ solutions will be utilized to update the distribution mean and principal search direction. The updating of the

Algorithm 1 R-R1-ES

• 1: Parameters setting: wi = ln(µ+1)-ln i µ ln(µ+1)-∑µj=1 ln j (i = 1, . . . , µ), µeff = 1 ∑µi=1 w2 i , ccov = 1 3√n+5 , c = 2 n+7 , q∗ = 0.3, cs = 0.3, dσ = 1;
• 2: Initialization: θ0, σ0 = 0.05, p0 = 0, s0 = 0;
• 3: Set F0 = [F (θ0) , . . . , F (θ0)];
• 4: for t ← 0 to T do
• 5: for i ← 1 to λ do
• 6: Sample zi ∼ N (0, I), ri ∼ N (0, 1);
• 7:
• xi ← θt + σt (√1 - ccovzi + √ccovript );
• 8: end for
• 9: Sort xi as F (x1:λ) ≥ F (x2:λ) ≥ . . . ≥ F (xλ:λ);
• 10: Increase µ linearly from µ0 to λ;
• 11: Set Ft+1 = [F (x1:λ) , . . . , F (xµ:λ)];
• 12: Update distribution mean: θt+1 ← ∑µi=1 wixi:λ;
• 13: Update principal search direction: pt+1 ← (1 - c) pt + √c (2 - c) µef f θt+1-θt σt ;
• 14: Rt,Rt+1 ← ranks of Ft, Ft+1 in Ft ∪Ft+1;
• 15: Compute rank difference: q ← 1µ ∑µi=1 wi (Rt (i) - Rt+1 (i));
• 16: Compute cumulative rank rate: st+1 ← (1- cs) st + cs (q - q∗);
• 17: Adapt mutation strength: σt+1 ← σt exp ( st+1 dσ );
• 18: if restart criterion is fulfilled then
• 19: Conduct restart procedure;
• 20: end if
• 21: t ← t + 1;
• 22: end for

distribution mean and principal search direction can be formulated as follows:

where c ∈ (0, 1) denotes the changing rate of principal search direction, µeff = 1 ∑µi=1 w2 i , and wi > 0 (i = 1, . . . , µ) are weighting parameters satisfying ∑µi=1 wi = 1. Additionally, these weighting parameters are required to satisfy w1 ≥ w2 ≥ · · · ≥ wµ for the reason that setting larger weighting parameter value for better solution can put more emphasize on better solutions. The concrete settings for these parameters can be seen in Line 1 of Algorithm 1.

As for the adaptation of the mutation strength, R-R1-ES adopts a slightly modified version of the rank-based success rule proposed in [Li and Zhang, 2017] (Lines 14-17 of Algorithm 1). The adaptation of mutation strength is based on fitness ranking, and is irrelevant to the concrete objective function value. Firstly, the elements in Ft ∪ Ft+1 are sorted in descending order, and the ranks of the i-th best solutions of Ft and Ft+1 in Ft ∪Ft+1 are expressed as Rt(i) and Rt+1(i) (i = 1, ..., µ), respectively. Then, the cumulative rank rate st ∈ R is computed as follow:

Based on the computed cumulative rank rate, the mutation strength is adapted in the following manner:

3.3 Mechanisms For Escaping Local Optima

In RL, optimizing the stochastic reward experienced over a full episode of agent interaction can often make an agent trapped in local optima. Thus, it is necessary to design mechanisms for escaping local optima. To this aim, our proposed R-R1-ES algorithm integrates two mechanisms: one is the adaptation of the number of elitists µ, and the other is the restart procedure.

As for the adaptation of µ, we make the value of µ linearly increase from an initial value µ0 to λ. This adaptation can add more diversity to the updating of distribution mean at the later stage of algorithm, and can promote the balance between exploration and exploitation to a certain extent. Thus, it can make R-R1-ES less prone to getting stuck in local optima. It is noticeable that the settings of wi (i = 1, . . . , µ) and µeff rely on the value of µ (see Line 1 of Algorithm 1). Thus, when the value of µ is changed during the evolutionary process, the values of wi and µeff are also adjusted.

As for the restart procedure, it is invoked when the mutation strength σt < 10-10 1 or the difference between the latest reward function value and the mean of the reward function values during the latest n generations is less than 10% 2 of the latest reward function value. When the restart procedure is invoked, both the values of population size λ and damping parameter dσ are doubled. This is because that increasing the population size and slowing down the decaying speed of the mutation strength are conducive to the further evolution process. The novel restart procedure fully considers the stochastic characteristics of reward function in RL problems, and thus can make R-R1-ES more suitable for RL problems.

3.4 Analyses Of R-R1-ES Complexity Of R-R1-ES

The proposed R-R1-ES is of low space and time complexity. On the one hand, R-R1-ES has a space complexity of O (λn) at each generation. On the other hand, since R-R1-ES utilizes a novel distribution model and the sampling procedure only involves the multiplications of scalar and vector (see Eq. (4)), the time complexity of R-R1-ES in terms of the time consumed on one evaluation of objective function is O(n).

1 The threshold value for mutation strength is set according to the suggestion in [Li and Zhang, 2017].

2 The threshold value for the difference in reward function in the restart condition is set based on our study of parameter tuning. In fact, this value should change per problem so as to make the performance of our proposed R-R1-ES become better on different problems. However, in our experiments, for the sake of convenience and uniformity, we simply use a fixed value for different problems. To a certain extent, this setting also makes the numerical comparison fairer.

This means that R-R1-ES greatly reduces the time complexity of the original CMA-ES, and can become more efficient when dealing with the issue of training deep neural networks and solving deep RL problems.

Analysis On Updating Of Distribution Mean

Focusing on the updating rule of the distribution mean (see Eq. (5)) in our proposed R-R1-ES, since ∑µi=1 wi = 1, Eq. (5) is equivalent to the following formula:

Recall from previous section that OpenAI-ES is based on NES, and estimates the natural gradient with respect to the distribution mean in a manner shown in Eq. (2). In fact, Eq. (2) can be rewritten as follow:

As can be seen from Eq. (9) and Eq. (10), if we regard the term F(θi t) σ2 λ as a weighting parameter (in fact, this term plays a role of weighting parameter), then the updating formula of the distribution mean (i.e., Eq. (5)) adopted in our proposed R-R1-ES can serve as an estimator to the natural gradient ∇θt E [F (θ)].

Analysis On Updating Of Principal Search Direction

As noted above, Eq. (5) can approximate the natural gradient ∇θt E [F (θ)]. Thus, if we replace the term θt+1 - θt in Eq. (6) with ∇θt E [F (θ)], then the updating of principal search direction can be rewritten as follow:

For comparison, we pay attention to the momentum method [Qian, 1999]. It is an ameliorated version of stochastic gradient descent, and is commonly used for training neural networks. When handling a maximization problem with objective function f, this method can be formulated as follow:

where α, β > 0 are two parameters.

As can be seen from Eq. (11) and Eq. (12), the principal search direction in our proposed R-R1-ES acts as a momentum term. Moreover, the principal search direction can accumulate the natural gradients with respect to the distribution mean over all the generations during the evolutionary process of R-R1-ES. In this way, solutions with good quality can be more likely to be generated.

4 Experiments

The experiments are conducted on classic control theory problems and Atari games.

4.1 Classic Control Theory Problems

In the empirical experiments, to investigate the performance of the proposed R-R1-ES algorithm, we firstly adopt three classic control theory problems from the OpenAI Gym [Brockman et al., 2016], including CartPole-v1, MountainCar-v0 and Pendulum-v0. As shown in Figure 1, these three problems attempt to achieve some kind of goal through controlling an object. The goal of CartPole-v1 is to prevent the pole on a cart from falling over, while that of MountainCar-v0 is to drive up the mountain on the right. The Pendulum-v0 aims to swing the pendulum up so it stays upright. These problems stem from the classical RL literature, and can serve as the benchmark problems for verifying the performance of RL algorithm. Thus, we adopt these problems to compare the performance of the proposed R-R1-ES algorithm and the OpenAI-ES [Salimans et al., 2017].

Since these classic control theory problems are relatively simple, we directly use a simple neural network with two hidden layers (one with 30 units and one with 20 units) to act as the network to be trained by ES. Virtual batch normalization is utilized as suggested in [Salimans et al., 2017].

The population size λ is set as λ = 20. Besides, the initial value µ0 for the proposed R-R1-ES is set as µ0 = 10. The maximum number of generations T is set as follows: T = 100 for CartPole-v1 and Pendulum-v0, T = 10000 for MountainCar-v0. Further, the mechanisms for escaping local optima in the proposed R-R1-ES are temporarily removed in this part of experiments.

For each algorithm on each problem, 21 independent training runs (each run with a final reward value) are performed, and the median reward values are recorded. As shown in Figure 2, the median values obtained by R-R1-ES on CartPole-v1 and Pendulum-v0 are higher than those obtained by OpenAI- ES. As for the MountainCar-v0 problem, the median reward value of R-R1-ES is a bit lower than that of OpenAI-ES. In short, R-R1-ES is on par with OpenAI-ES when solving classic control theory problems.

4.2 Atari Games

In the second part, the performance of the R-R1-ES is further evaluated on four Atari games (i.e., Breakout-v0, Pongv0, Qbert-v0 and Seaquest-v0), which are shown in Figure 3. And we compare R-R1-ES with four ES variants, including OpenAI-ES [Salimans et al., 2017], NS-ES [Conti et al., 2017], NSR-ES [Conti et al., 2017] and Canonical ES [Chrabaszcz et al., 2018].

As for the neural network architecture, we adopt the suggestion in [Chrabaszcz et al., 2018], which is a bit different from the DQN [Mnih et al., 2015]. And the virtual batch normalization is also utilized as suggested in [Salimans et al., 2017].

As for the training of each ES variant on each game, 20 CPUs are used with a time budget of 20 hours. The population size λ and the initial value µ0 are set to λ = 798 and µ0 = 50, respectively. As for the other parameters used in each ES variant, we follow the suggestions given by their developers, and keep their settings the same as in their original literature.

For each algorithm on each game, 21 independent training runs are performed. After each training, 30 independent evaluation runs (each evaluation run with a score evaluated from the final policy) are conducted for each algorithm, and the mean values of 30 evaluation scores are recorded. In this way, each training run is corresponding to a mean evaluation score, and the median value of all the mean evaluation scores among 21 training runs serves as the final evaluation score obtained by each algorithm on each game. The experimental results are displayed in Figures 4-7.

For the simple Pong-v0 game, as shown in Figure 4, OpenAI-ES obtain the highest scores, and the other four ES variants obtain lower scores.

Seaquest-v0 game has an easy-to-reach local optima, which does not require performing complex behavior. As can be known from [Conti et al., 2017], NS-ES and NSR-ES avoid local optima by means of novelty search (NS) [Lehman and Stanley, 2011] and quality diversity (QD) [Pugh et al., 2016], respectively. Our proposed R-R1-ES integrates two mechanisms (i.e., the adaptation of the number of elitists and the restart procedure) to deal with the issue of local optima. The effects of these mechanisms for escaping local optima are experimentally validated and underpinned by Figure 5 which shows that the aforementioned three ES variants (i.e., NS-ES, NSR-ES and R-R1-ES) have nice performance on Seaquestv0 game. Among them, R-R1-ES obtains the highest score and NSR-ES obtains the second highest score.

As can be seen from Figure 6, all the five algorithms obtain low scores on Breakout-v0 game. This can also provide evidence that Breakout-v0 is challenging to ES algorithms. The proposed R-R1-ES performs best, while two ES variants (NS-ES and NSR-ES) involving NS and QD also have a good performance. Compared to the aforementioned three ES variants which unite mechanism for escaping local optima, the other two ES variants (that is, OpenAI-ES and Canonical ES) perform even worse on Breakout-v0 game. This phenomenon indicates that Breakout-v0 game may also encounter the issue of local optima.

For Qbert-v0 game, both Canonical ES and R-R1-ES obtain higher scores than the other three ES variants which do not adopt the framework of (µ, λ)-ES algorithms. Since both Canonical ES and R-R1-ES belong to the family of (µ, λ)-ES algorithms and they can obtain nice performance on Qbert-v0 game, it is natural to think that their nice performance may be attributed to the superiority of the framework of (µ, λ)-ES algorithms.

To sum up, the whole performance of the proposed R-R1ES on Atari games is superior to or competitive with existing ES variants for reinforcement learning.

5 RelatedWork

In the literature of neuroevolution, there exist a lot of researches which employ ES-related methods to train neural networks for RL tasks [Risi and Togelius, 2017]. In 2010, Sehnke et al. proposed a novel algorithm called policy gradients with parameter-based exploration (PGPE for short) based on a gradient-based search through model parameter space [Sehnke et al., 2010]. Koutn´ık et al. [Koutnik et al., 2010; Koutn´ık et al., 2013] and Srivastava et al. [Srivastava et al., 2012] adopted different ways to compress the policy, but they both attempted to apply an ES method to RL tasks with visual inputs in a similar manner. In 2014, Hausknecht et al. applied four neuroevolution algorithms with three different state representations to Atari games, and demonstrated that neuroevolution is a promising approach to general video game playing [Hausknecht et al., 2014].

Recently, researchers fromOpenAI [Salimans et al., 2017] studied a version of ES algorithm from the class of NES [Wierstra et al., 2008], and demonstrated that it can reliably train neural network policies in a set of RL benchmark environments. This version of ES can obtain competitive performance with state-of-the-art RL algorithms. Notably, it has motivated several nice works by scientists from tech companies and researchers from universities.

Following OpenAI's work, Conti et al. attempted to improve the performance of ES on sparse and/or deceptive control tasks by introducing novelty search (NS) [Lehman and Stanley, 2011] and quality diversity (QD) [Pugh et al., 2016], and form two algorithms (called NS-ES and NSR-ES, respectively) [Conti et al., 2017]. The resultant algorithms can effectively avoid local optima encountered by ES.

Zhang et al. investigated the relationship between the OpenAI-ES and the stochastic gradient descent method by conducting several MNIST-based experiments [Zhang et al., 2017]. This work gives a nuanced insight into the behaviors of ES, and can promote more informed decisions on the application of ES within RL and other paradigms.

Lehman et al. demonstrated that although ES is not just a traditional finite-difference approximator [Lehman et al., 2017]. Most importantly, ES is aimed to optimize the performance of the distribution of solutions rather than a single solution, and thus it can seek out solutions that are more robust to the noise in the parameter space.

Chrabaszcz et al. demonstrated that even a very basic canonical ES algorithm, which belongs to the family of (µ, λ)-ES algorithms [Schwefel, 1981], can obtain comparable performance with the OpenAI-ES [Chrabaszcz et al., 2018]. This indicates that with the integration of the state-ofthe-art advances made in ES field, we can further promote the performance of ES when solving deep RL problems.

6 Conclusion

In this paper, we have proposed an ES variant called R-R1-ES for training neural networks on RL problems. As the first attempt of applying CMA-ES to RL, our proposed R-R1-ES is based on a simplified CMA-ES for large scale black-box optimization, and involves the procedures of adapting the mutation strength, updating the distribution and the principal search direction, and escaping local optima. Strikingly, the R-R1-ES proposed for RL is of linear time complexity and low space complexity. Moreover, the updating formula of the distribution mean in our proposed R-R1-ES can serve as an estimator to the natural gradient, and the updating of the principal search direction adopted in R-R1-ES acts like the momentum method. Through the empirical experiments on some RL tasks including classic control problems and Atari games, we have demonstrated that the proposed R-R1-ES is superior to or competitive with existing ES variants for RL.

In the future research, the effect of the proposed algorithm on more tough RL tasks can be investigated with the support of more advanced hardware devices. In addition, other stateof-the-art CMA-ES variants for large scale black-box optimization and advanced techniques can be studied in depth and combined to further promote the effectiveness and efficiency of RL algorithm.

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grants 61773410 and 61673403.