Back to Basics: Benchmarking Canonical Evolution Strategies for Playing Atari

1 Introduction

In machine learning, Evolution Strategies (ES) are mainly used for direct policy search in reinforcement learning [Gomez et al., 2008; Heidrich-Meisner and Igel, 2009; Stulp and Sigaud, 2013; Salimans et al., 2017] and hyperparameter tuning in supervised learning, e.g., for Support Vector Machines [Glasmachers and Igel, 2008; Igel, 2011] and Deep Neural Networks [Loshchilov and Hutter, 2016].

Recently it has been shown [Salimans et al., 2017] that ES algorithms can be used for tasks which are dominated by deep reinforcement learning (RL) algorithms. Those tasks include learning a policy with discrete action set to control an agent's behavior in a wide variety of Atari environments, as well as learning a policy with continuous action space for agents operating in MuJoCo [Todorov et al., 2012] environments. ES algorithms offer a set of attractive advantages when compared to deep RL algorithms:

• They are highly parallelizable, since the amount of information that has to be exchanged between workers does not depend on the network size.
• Depending on the problem, they can offer better exploration, and as a result different training runs can converge to qualitatively different solutions.
• They are not sensitive to the distribution of rewards and do not require careful tuning of discount factors while still facilitating long-term foresight more than traditional discount-based RL algorithms.
• They can be used for the optimization of nondifferentiable policy functions.

In this work, we go one step further than Salimans et al. [2017] and study the applicability of even simpler ES algorithm to the task of learning a policy network for playing Atari games. Salimans et al. [2017] used a specialized ES algorithm that belongs to the class of Natural Evolution Strategies (NES) [Wierstra et al., 2014], which computes approximate gradients similar to the REINFORCE algorithm [Williams, 1992]. Here, we demonstrate that comparable results can already be achieved with a simpler very basic Canonical ES algorithm from the 1970s [Rechenberg, 1973; Rudolph, 1997].

Our contributions in this work are as follows:

• We demonstrate that even a very basic Canonical ES algorithm is able to match (and sometimes supersede) the performance of the Natural Evolution Strategy used by Salimans et al. [2017] for playing Atari games.
• We demonstrate that after 5 hours of training, Canonical ES is able to find novel solutions that exploit the game design and even find bugs in one game that allow them to achieve unprecedented high scores.
• We experimentally study the performance characteristics of both ES algorithms, demonstrating that (1) individual runs have high variance in performance and that (2) longer runs (5h instead of 1h) lead to significant further performance improvements.
• By demonstrating that Canonical ES is a competitive alternative to traditional RL algorithms and the specialized ES algorithms tested so far on the Atari domain we set a benchmark for future work on modern ES variants that are directly based on the canonical version.

2 Background

In this section, we discuss background on RL for playing Atari and on the previously-introduced NES method.

2.1 Reinforcement Learning for Playing Atari

In the Atari task of the OpenAI gym environment [Brockman et al., 2016], the agent needs to learn to maximize its cumulative reward solely by interacting with the environment (i.e., playing the game). Inputs to the agent include the raw pixels displayed on the Atari console as well as the reward signal; its actions correspond to joystick movements to execute.

Recent developments in the field of deep RL have made it possible to address challenging problems that require processing of high dimensional inputs, such as the raw images in this Atari domain, which can be addressed by deep convolutional neural networks. This approach was popularized by Google DeepMind's Nature paper on the deep Q network (DQN) [Mnih and others, 2015], a Q-learning method that estimates the utility of an action given a current state by means of a deep neural network. Given this network for approximating the Q function, in any state s, DQN's policy then simply selects the action a with the largest predicted Q value Q(s, a).

While DQN requires this maximization over the action space, policy gradient algorithms directly parameterize a policy networks that maps a state to a probability distribution over actions. Policy gradient algorithms, such as the Asynchronous Advantage Actor Critic (A3C) [Mnih et al., 2016], directly optimize this policy network.

State Representation. In Atari games it is important to model the state to include information from previous frames that will influence an agent's performance. In this work we use the following standard preprocessing pipeline [Mnih and others, 2015] with an implementation provided by OpenAI [Dhariwal et al., 2017]. First, we apply preprocessing to the screen frames to reduce the dimensionality and remove artifacts related to the technical limitations of the Atari game console (flickering). Specifically, we apply a pixel-wise max operation on the current frame and the one preceeding it. Next, we convert the output from this operation into a grayscale image, resize it and crop it to 84x84 pixels. At the end of this pipeline, we stack together the result of the 4 last frames produced this way to construct a 84x84x4 state tensor. Also following common practice, to speed up policy evaluation (and thus reduce training time), instead of collecting every frame and making a decision at every step, we collect every 4th frame (3rd frame for SpaceInvaders to make the laser visible [Mnih et al., 2013]) and apply the same action for all frames in between. Figure 1 visualizes the full preprocessing pipeline. Figure 2 shows an example of the state representation for 2 different games.

2.2 Natural Evolution for Playing Atari

Salimans et al. [2017] recently demonstrated that an ES algorithm from the specialized class of Natural Evolution Strategies (NES; [Wierstra et al., 2014]) can be used to successfully train policy networks in a set of RL benchmark environments (Atari, MuJoCo) and compete with state-of-the-art RL algorithms. Algorithm 1 describes their approach on a high level. In a nutshell, it evolves a distribution over policy networks over time by evaluating a population of λ different networks in each iteration, starting from initial policy parameter vector θ0. At each iteration t, the algorithm evaluates the game scores F(·) of λ different policy parameter vectors centered around θt (lines 3-5) to estimate a gradient signal, using mirrored sampling [Brockhoff et al., 2010] to reduce the variance of this estimate. Since the λ game evaluations are independent of each other, ES can make very efficient use of parallel compute resources. The resulting λ game scores are then ranked (line 6), making the algorithm invariant to their scale; as noted by the authors, this approach (called fitness shaping [Wierstra et al., 2014] but used in all ESs since the 1970s) decreases the probability of falling into local optima early and lowers the influence of outliers. Based on these λ ranks of local steps around θt, the algorithm approximates a gradient g (line 7) and uses this with a modern version of gradient descent (Adam [Kingma and Ba, 2014] or SGD with momentum) with weight decay to compute a robust parameter update step (line 8) in order to move θt towards the parameter vectors that achieved higher scores.

We note that the computation of the approximate gradient g in line 7 follows the same approach as the well-known policy gradient algorithm REINFORCE. This can be shown as follows. Denoting the distribution from which we draw policy network parameters θ as pψ, the gradient of the expected reward F(θ) with respect to ψ is:

Because pψ is chosen as an isotropic Gaussian distribution with mean θt and fixed standard deviation (mutation step-size)

Algorithm 1: OpenAI ES

Input: optimizer - Optimizer function σ - Mutation step-size λ - Population size θ0 - Initial policy parameters F - Policy evaluation function 1 for t = 0, 1, ... do 2 for i = 1, 2, ... λ2 do 3 Sample noise vector: ϵi ∼ N(0, I) 4 Evaluate score in the game: s+i ←F(θt +σ ∗ ϵi) 5 Evaluate score in the game: s-i ←F(θt -σ ∗ ϵi) 6 Compute normalized ranks: r = ranks(s), ri ∈ [0, 1) 7 Estimate gradient: g ← 1 σ∗λ ∑λi=1 (ri ∗ ϵi) 8 Update policy network: θt+1 ← θt + optimizer(g)

σ, the only parameter of pψ is θt and we have:

and therefore the following identity holds:

where the last step is simply an approximation by λ samples θ(i) ∼ pψ. Equation 4 is exactly as in line 7 of the algorithm except that the raw game scores F(θ(i) ) are replaced with their ranks ri due to fitness shaping.

Salimans et al. [2017] also made two further contributions to stabilize the training and improve performance. Firstly, they introduced a novel parallelization technique (which uses a noise table to reduce communication cost in order to scale to a large number of λ parallel workers) and used virtual batch normalization [Salimans et al., 2016] to make the network output more sensitive to the noise in the parameter space.

3 Canonical ES

While the specialized ES algorithm proposed by OpenAI is equivalent to a policy gradient algorithm, in this work we consider a very basic canonical ES algorithm that belongs to the prominent family of (µ, λ) - ES optimization algorithms. Algorithm 2 illustrates this simple approach. Starting from a random parameter vector θ0, in each iteration t we generate an offspring population of size λ. For each element of the population, we add sampled mutation noise ϵi ∼ N(0, σ2 ) to the current parameter vector θt (line 3) and evaluate the game score of the resulting vector by one episode rollout (line 4). We then pick the top µ parameter vectors according to the collected score and form a new parameter vector θt+1 as their weighted mean (lines 5-6).

This algorithm is very basic in its setting and conceptually simpler than the NES-inspired algorithm by Salimans et al. [2017]. While our presentation of the latter (see Algorithm

1) hides complexity in the final call to an advanced gradientbased optimizer (Salimans et al. [2017] used Adam [Kingma and Ba, 2014] for MujoCo in their publicly available implementation), in canonical ES we do not use any advanced optimizer. We also do not decay the parameters. We use standard weights to compute the weighted mean of the top µ solutions instead of uniform weights used in OpenAI ES. The new elements introduced by Salimans et al. [2017] that we do use are virtual batch normalization (which is a component of the game evaluations F and not really of the ES algorithm itself) and the efficient parallelization of ES using a random noise table.

We initially implemented the Cumulative Step-size σ Adaptation (CSA) procedure [Hansen and Ostermeier, 1996], which is standard in canonical ES algorithms. However, due to the high time cost of game evaluations, during our time-limited training, we are only able to perform up to thousands update iterations. Since the dimensionality of the parameter vector is relatively large (1.7M), this results in only a negligible change of σ during the training. Therefore, effectively, our algorithm used a fixed step-size and thus we removed step-size adaptation from the description from Algorithm 2 making it even somewhat simpler than typical ES. We employed weighted recombination [Rudolph, 1997] and weights w as in CSA-ES.

Algorithm 2: Canonical ES Algorithm

Input:

• σ - Mutation step-size
• θ0 - Initial policy parameters
• F - Policy evaluation function
• λ - Offspring population size
• µ - Parent population size

Initialize :

4 Experiments

In our experiments, we evaluate the performance of the Canonical ES on a subset of 8 Atari games available in OpenAI Gym [Brockman et al., 2016]. We selected these games to represent different levels of difficulty, ranging from simple ones like Pong and Breakout to complex games like Qbert and Alien. We make our implementation of the Canonical ES algorithm available online at https://github.com/PatrykChrabaszcz/ Canonical ES Atari.

We compare our results against those obtained with the ES algorithm proposed by OpenAI [Salimans et al., 2017]. Since no implementation of that algorithm is publicly available for Atari games, we re-implemented it with help from OpenAI 1 , and the results of our implementation, which we refer to as "OpenAI ES (our)", roughly match those reported by Salimans et al. [2017], which we refer to as "OpenAI ES" (see Table 1). We believe that differences between the original OpenAI results and the results from our reimplementation are mainly due to the fact that our approach does not adjust the max episode length during training. Thus, from the beginning, we shift the search direction towards solutions that performwell in long runs. This seems to have varying effects that strongly depends on the game.

1 We thank Tim Salimans for his helpful email support.

Network Architecture. We use the same network structure as the original DQN work [Mnih and others, 2015], only changing the activation function from ReLU to ELU [Clevert et al., 2015] and adding batch normalization layers [Ioffe and Szegedy, 2015]. The network as presented in Figure 3 has approximately 1.7M parameters. We initialize network weights using samples from a normal distribution N(µ = 0, σ = 0.05).

Virtual Batch Normalization. Following Salimans et al. [2017], we use virtual batch normalization [Salimans et al., 2016]. In order to collect the reference batch, at the beginning of the training we play the game using random actions. In each step, we save the corresponding state with the probability p(save) = 1% and stop when 128 samples have been collected.

Training. For each game and each ES variant we tested, we performed 3 training runs, each on 400 CPUs with a time budget of 10 hours. Every worker (CPU) evaluates 2 offspring solutions, meaning that our setting is roughly the same as training for 5 hours with full parallelization (800 CPUs); therefore, we label this setting as "5 hours". In addition, we save the solution proposed after 2 hours of training (equivalent to 1 hour with full parallelization) or after 1 billion training frames (whatever comes first) to allow for a fair comparison with results reported by Salimans et al. [2017]; we label this setting as "1 hour". During training, one CPU is reserved to evaluate the performance of the solution proposed in the current iteration; hence, the offspring population size in our experiments is λ = 798. In each decision step, the agent passes its current environment state through the network and performs an action that corresponds to the output with the highest value. We limit episodes to have a maximum length of 25k steps; we do not adjust this value during training.

An episode includes multiple lives, and we do not terminate an episode after the agent dies the first time in order to allow the learning of strategies that span across multiple lives. We start each episode with up to 30 initial random no-op actions.

Results. First, we studied the importance of the parent population size µ. This hyperparameter is known to often be important for ES algorithms and we found this to also hold here. We measured performance for µ ∈ {10, 20, 50, 100, 200, 400} and observed different optimal values of µ for different games (Figure 4). For the subsequent analyses we fixed µ = 50 for all games.

In Table 1, for each game and for both Canonical ES and OpenAI ES, we report the results of our 3 training runs; for each of these runs, we evaluated the final policy found using 30 rollouts. We ordered the 3 runs according to their mean score and compared the results row-wise. We ran a Mann-Whitney U test to check if the distributions of the 30 rewards significantly differed between the two ES variants. After 5 hours of training, Canonical ES performed significantly better than OpenAI ES in 9 out of 24 different runs (p < 0.05) and worse in 7 (with 8 ties); this shows that our simple Canonical ES is competitive with the specialized OpenAI ES algorithm on complex benchmark problems from the Atari domain. Additionally, we tested whether the algorithms still made significant progress between 1 and 5 hours of training; indeed, the performance of our Canonical ES algorithm improved significantly in 16 of 24 cases, demonstrating that it often could make effective use of additional training time. However, qualitatively, we observed that the performance of both algorithms tends to plateau in locally optimal solutions for extended periods of time (see Figure 5) and that they often find solutions that are not robust to the noise in the domain; i.e., there is a high variance in the points scored with the same trained policy network across initial environment conditions.

5 Qualitative Analysis

Visual inspection and comparison between solutions found by reinforcement learning algorithms and solutions found by ES algorithms shows some significant differences. In this section we describe interesting agent behaviors on different games; a video with evaluation runs on all games is available on-line at goo.gl/Mz2ZUs.

First, we study two games in which most of the ES runs converged to similar sub-optimal solutions: Seaquest and Enduro. In Seaquest, the agent dives to the bottom of the sea and starts to shoot left and right, occasionally hitting an enemy and scoring points (Figure 6). However, it is not able to detect the lack of oxygen and quickly dies. In Enduro, the agent steers the car to keep it in the middle of the road and accelerate, but from time to time it bounces back after hitting a rival car in front of it. Both solutions are easy-to-reach local optima and do not require developing any complex behavior; since the corresponding scores achieved with these policies are much higher than those of random policies we believe that it is hard for ES to escape from these local attractor states in policy space.

We next study the game Qbert, in which Canonical ES found two particularly interesting solutions that exploit bugs in the game. In the first case, which turned out to be a known bug, instead of completing the first level, the agent loops a sequence of actions, in which it baits an enemy to jump off the game platform together and scores the points for killing the enemy; for some unknown reason, the game engine does not count this suicide as a loss of life, and the agent is able to repeat this process indefinitely. This pattern is shown in Figure 7 (top) and in a video at goo.gl/ig8E3t. In the second, more interesting, and previously unknown bug, the agent finds a sequence of actions that completes the first level, but, for an unknown reason, does not lead to the game advancing to the next level; instead, all platforms start to blink and the agent quickly gains a huge amount of points. This pattern is shown in Figure 7 (bottom) and in a video at goo.gl/1K9A17; it has since been reproduced on the original Atari console (goo.gl/jkt6jS).

Breakout seems to be a challenging environment for ES algorithms. Canonical ES only found reasonable solutions for a few settings. The best solution shows a strategy that looks similar to the best strategies obtained by using reinforcement learning algorithms, in which the agent creates a hole on one side of the board and shoots the ball through it to gain many points in a short amount of time (Figure 8). However, even this best solution found by ES is not stable: for different initial environment conditions the agent with the same policy network quickly loses the game with only few points.

In the games SpaceInvaders and Alien we also observed interesting strategies. We do not clip rewards during the training as is sometimes done for reinforcement learning algorithms. Because of that the agent puts more attention to behaviors that result in a higher reward, sometimes even at the cost of the main game objective. In SpaceInvaders, we observe that in the best solution the agent hits the mother-ship that appears periodically on the top of the screen with 100% accuracy. In Alien, the agent focuses on capturing an item that makes it invincible and then goes to the enemy spawn point to collect rewards for eliminating newly appearing enemies. However, the agent is not able to detect when the invincibility period ends.

6 Recent RelatedWork

Evolution strategies, such as the Covariance Matrix Adaptation Evolution Strategy (CMA-ES [Hansen et al., 2003]), are commonly used as a baseline approach in reinforcement learning tasks [Heidrich-Meisner and Igel, 2009; Stulp and Sigaud, 2013; Duan et al., 2016; Li, 2017]. Here, we only discuss the most recent related works, which also followed up on the work by Salimans et al. [2017]; in particular, we discuss three related arXiv preprints that scientists at Uber released in the last two months about work concurrent to ours.

Similarly to our work, Such et al. [2017] studied the performance of simpler algorithms than OpenAI's specialized ES variant. They show that genetic algorithms (another broad class of black-box optimization algorithms) can also reach results competitive to OpenAI's ES variant and other RL algorithms. Additionally, interestingly, the authors show that for some of the games even simple random search can outperform carefully designed RL and ES algorithms.

Lehman et al. [2017] argue that comparing ES to finitedifference-based approximation is too simplistic. The main difference comes from the fact that ES tries to optimize the performance of the distribution of solutions rather than a single solution, thus finding solutions that are more robust to the noise in the parameter space. The authors leave open the question whether this robustness in the parameter space also affects the robustness to the noise in the domain. In our experiments we observe that even for the best solutions on some of the games, the learned policy network is not robust against environment noise.

Conti et al. [2017] try to address the problems of local minima (which we also observed in games like Seaquest and Enduro) by augmenting ES algorithms with a novelty search and quality diversity. Their proposed algorithms add an additional criterion to the optimization procedure that encourages exploring qualitatively different solutions during training, thus reducing the risk of getting stuck in a local optimum. The authors also propose to manage a meta-population of diverse solutions allocating resources to train more promising ones. In our experiments we observe that training runs with the same hyperparameters and different initializations often converge to achieve very different scores; managing a meta-population could therefore be an easy way to improve the results and reduce the variance between the runs. Overall, the success of Conti et al. [2017] in improving performance with some of these newer ES methods strengthens our expectation that a wide range of improvements to the state of the art are possible by integrating the multitude of techniques developed in ES research over the last decades into our canonical ES.

7 Conclusion and FutureWork

The recent results provided by Open AI [Salimans et al., 2017] suggest that natural evolution strategies represent a viable alternative to more common approaches used for deep reinforcement learning. In this work, we analyzed whether the results demonstrated in that work are due to the special type of ES used there. Our results suggest that even a very basic decadesold ES provides comparable results; thus, more modern ES methods should be considered as a potentially competitive approach to modern deep reinforcement learning algorithms.

In future work, we plan on improving upon the current canonical ES algorithm in several ways. We plan to study CMA-ES for problems where small networks can be applied. Both ES algorithm variants studied in this paper are characterized by a high variance, both between runs with the same hyperparameters and between evaluation runs of the same already trained policy. We believe that the high variance between the runs could be addressed by managing a meta population of solutions and allocating resources to the more promising ones. We also plan to explore possible ways to reduce currently high computational requirements of our approach; preliminary experiments suggest that lower population sizes still obtain good results. One of the drawbacks of ES algorithms we discussed is that they tend to get stuck in locally optimal solutions. We believe that this can be addressed using quality diversity and novelty search algorithms, thus making ES more robust and potentially improving the score in longer training runs. It would be promising to study lower-memory ES methods for larger networks, such as LM-MA-ES [Loshchilov et al., 2017], which we expect to yield further improvements over canonical ES.

We also believe that it is promising to combine ES and RL algorithms. For example, Plappert et al. [2017] propose to augment RL with noise injection in the parameter space (as in an ES algorithm) to improve the exploration, and demonstrates the benefits of this approach. We expect that there are further opportunities along these lines to gain improvements by more explicitly combining RL and ES.

Acknowledgments

This work has partly been supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant no. 716721. The authors acknowledge support by the state of Baden-W¨urttemberg through bwHPC and the German Research Foundation (DFG) through grant no. INST 39/963-1 FUGG.