Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning — part 2/4

Cleaned-text code points [15921, 31297). Bibliography omitted here; source.md includes it.

NS requires a behavior characteristic (BC) that describes the behavior of a policy B ​ C ​ ( π ) BC(\pi) and a behavioral distance function between the BCs of any two policies: dist ​ ( B ​ C ​ ( π i ) , B ​ C ​ ( π j ) ) \text{dist}(BC(\pi_{i}),BC(\pi_{j})) , both of which are domain-specific. After each generation, members of the population have a probability p p (here, 0.01) of having their BC stored in an archive . The novelty of a policy is defined as the average distance to the k k (here, 25) nearest neighbors (sorted by behavioral distance) in the population or archive. Novel individuals are thus determined based on their behavioral distance to current or previously seen individuals. The GA otherwise proceeds as normal, substituting novelty for fitness (reward). For reporting and plotting purposes only, we identify the individual with the highest reward per generation. The algorithm is presented in SI Algorithm 2 .

## 4 Experiments

Our experiments focus on the performance of the GA on the same challenging problems that have validated the effectiveness of state-of-the-art deep RL algorithms and ES ( Salimans et al., 2017 ) . They include learning to play Atari directly from pixels ( Mnih et al., 2015 ; Schulman et al., 2017 ; Mnih et al., 2016 ; Bellemare et al., 2013 ) and a continuous control problem involving a simulated humanoid robot learning to walk ( Brockman et al., 2016 ; Schulman et al., 2017 ; Salimans et al., 2017 ; Todorov et al., 2012 ) . We also tested on an Atari-scale maze domain that has a clear local optimum (Image Hard Maze) to study how well these algorithms avoid deception ( Lehman & Stanley, 2011a ) .

For Atari and Image Hard Maze experiments, we record the best agent found in each of multiple, independent, randomly initialized GA runs: 5 for Atari, 10 for the Image Hard Maze. Because Atari is stochastic, the final score for each run is calculated by taking the highest-scoring elite across generations, and averaging the score it achieves on 200 independent evaluations. The final score for the domain is then the median of final run scores. Humanoid Locomotion details are in SI. Sec 7.5 .

### 4.1 Atari

Training deep neural networks to play Atari – mapping directly from pixels to actions – was a celebrated feat that arguably launched the deep RL era and expanded our understanding of the difficulty of RL domains that machine learning could tackle ( Mnih et al., 2015 ) . Here we test how the performance of DNNs evolved by a simple GA compare to DNNs trained by the major families of deep RL algorithms and ES. We model our experiments on those from the ES paper by Salimans et al. (2017) since it inspired our study. Due to limited computational resources, we compare results on 13 Atari games. Some were chosen because they are games on which ES performs well (Frostbite, Gravitar, Kangaroo, Venture, Zaxxon) or poorly (Amidar, Enduro, Skiing, Seaquest) and the remaining games were chosen from the ALE ( Bellemare et al., 2013 ) set in alphabetical order (Assault, Asterix, Asteroids, Atlantis). To facilitate comparisons with results reported in Salimans et al. (2017) , we keep the number of game frames agents experience over the course of a GA run constant (at one billion frames). The frame limit results in a differing number of generations per independent GA run (SI Sec. Table 3 ), as policies of different quality in different runs may see more frames in some games (e.g. if the agent lives longer).

During training, each agent is evaluated on a full episode (capped at 20k frames), which can include multiple lives, and fitness is the sum of episode rewards, i.e. the final Atari game score. The following are identical to DQN ( Mnih et al., 2015 ) : (1) data preprocessing, (2) network architecture, and (3) the stochastic environment that starts each episode with up to 30 random, initial no-op operations. We use the larger DQN architecture from Mnih et al. (2015) consisting of 3 convolutional layers with 32, 64, and 64 channels followed by a hidden layer with 512 units. The convolutional layers use 8 × 8 8\times 8 , 4 × 4 4\times 4 , and 3 × 3 3\times 3 filters with strides of 4, 2, and 1, respectively. All hidden layers were followed by a rectifier nonlinearity (ReLU). The network contains over 4M parameters; interestingly, many in the past assumed that a simple GA would fail at such scales. All results are from our single-machine CPU+GPU GA implementation.

Fair comparisons between algorithms is difficult, as evaluation procedures are non-uniform and algorithms realize different trade-offs between computation, wall-clock speed, and sample efficiency. Another consideration is whether agents are evaluated on random starts (a random number of no-op actions), which is the regime they are trained on, or on starts randomly sampled from human play, which tests for generalization ( Nair et al., 2015 ) . Because we do not have a database of human starts to sample from, our agents are evaluated with random starts. Where possible, we compare our results to those for other algorithms on random starts. That is true for DQN and ES, but not for A3C, where we had to include results on human starts.

We also attempt to control for the number of frames seen during training, but because DQN is far slower to run, we present results from the literature that train on fewer frames (200M, which requires 7-10 days of computation vs. hours of computation needed for ES and the GA to train on 1B frames). There are many variants of DQN that we could compare to, including the Rainbow ( Hessel et al., 2017 ) algorithm that combines many different recent improvements to DQN ( Van Hasselt et al., 2016 ; Wang et al., 2015 ; Schaul et al., 2015 ; Sutton & Barto, 1998 ; Bellemare et al., 2017 ; Fortunato et al., 2017 ) . However, we choose to compare the GA to the original, vanilla DQN algorithm, partly because we also introduce a vanilla GA, without the many modifications and improvements that have been previously developed ( Haupt & Haupt, 2004 ) .

In what will likely be a surprise to many, the simple GA is able to train deep neural networks to play many Atari games roughly as well as DQN, A3C, and ES (Table 1 ). Among the 13 games we tried, DQN, ES and the GA produced the best score on 3 games, while A3C produced the best score on 4. On Skiing, the GA produced a score higher than any other algorithm to date that we are aware of, including all the DQN variants in the Rainbow DQN paper ( Hessel et al., 2017 ) . On some games, the GA performance advantage over DQN, A3C, and ES is considerable (e.g. Frostbite, Venture, Skiing). Videos of policies evolved by the GA can be viewed here: https://goo.gl/QBHDJ9 . In a head-to-head comparisons, the GA performs better than ES, A3C, and DQN on 6 games each out of 13 (Tables 1 & 4 ).

The GA also performs worse on many games, continuing a theme in deep RL where different families of algorithms perform differently across different domains ( Salimans et al., 2017 ) . However, all such comparisons are preliminary because more computational resources are needed to gather sufficient sample sizes to see if the algorithms are significantly different per game; instead the key takeaway is that they all tend to perform roughly similarly in that each does well on different games.

Because performance did not plateau in the GA runs, we test whether the GA improves further given additional computation. We thus run the GA six times longer (6B frames) and in all games, its score improves (Table 1 ). With these post-6B-frame scores, the GA outperforms A3C, ES, and DQN on 7, 8, 7 of the 13 games in head-to-head comparisons, respectively (SI Table 4 ). In most games, the GA’s performance still has not converged at 6B frames (SI Fig. 3 ), leaving open the question of to how well the GA will ultimately perform when run even longer. To our knowledge, this 4M+ parameter neural network is the largest neural network ever evolved with a simple GA.

One remarkable fact is how quickly the GA finds high-performing individuals. Because we employ a large population size (1k), each run lasts relatively few generations (min 348, max 1,834, SI Table 3 ). In many games, the GA finds a solution better than DQN in only one or tens of generations! Specifically, the median GA performance is higher than the final DQN performance in 1, 1, 3, 5, 11, and 29 generations for Skiing, Venture, Frostbite, Asteroids, Gravitar, and Zaxxon, respectively. Similar results hold for ES, where 1, 2, 3, 7, 12, and 25 GA generations were needed to outperform ES on Skiing, Frostbite, Amidar, Asterix, Asteroids, and Venture, respectively. The number of generations required to beat A3C were 1, 1, 1, 1, 1, 2, and 52 for Enduro, Frostbite, Kangaroo, Skiing, Venture, Gravitar, and Amidar, respectively.

Each generation, the GA tends to make small-magnitude changes (controlled by σ \sigma ) to the parameter vector (see Methods). That the GA outperforms DQN, A3C, and ES in so few generations – especially when it does so in the first generation (which is before a round of selection) – suggests that many high-quality policies exist near the origin (to be precise, in or near the region in which the random initialization function generates policies). That raises the question: is the GA doing anything more than random search?

To answer this question, we evaluate many policies randomly generated by the GA’s initialization function ϕ \phi and report the best score. We gave random search approximately the same amount of frames and computation as the GA and compared their performance (Table 1 ). In every game, the GA outperformed random search, and did so significantly on 9/13 games (Fig. 3 , p < 0.05 p<0.05 , this and all future p p values are via a Wilcoxon rank-sum test). The improved performance suggests the GA is performing healthy optimization over generations.

Surprisingly, given how celebrated and impressive DQN, ES and A3C are, out of 13 games random search actually outperforms DQN on 3 (Frostbite, Skiing, & Venture), ES on 3 (Amidar, Frostbite, & Skiing), and A3C on 6 (Enduro, Frostbite, Gravitar, Kangaroo, Skiing, & Venture). Interestingly, some of these policies produced by random search are not trivial, degenerate policies. Instead, they appear quite sophisticated. Consider the following example from the game Frostbite, which requires an agent to perform a long sequence of jumps up and down rows of icebergs moving in different directions (while avoiding enemies and optionally collecting food) to build an igloo brick by brick (SI Fig. 4 ). Only after the igloo is built can the agent enter the igloo to receive a large payoff. Over its first two lives, a policy found by random search completes a series of 17 actions, jumping down 4 rows of icebergs moving in different directions (while avoiding enemies) and back up again three times to construct an igloo. Then, only once the igloo is built, the agent immediately moves towards it and enters it, at which point it gets a large reward. It then repeats the entire process on a harder level, this time also gathering food and thus earning bonus points (video: https://youtu.be/CGHgENV1hII ). That policy resulted in a very high score of 3,620 in less than 1 hour of random search, vs. an average score of 797 produced by DQN after 7-10 days of optimization. One may think that random search found a lucky open loop sequence of actions overfit to that particular stochastic environment. Remarkably, we found that this policy actually generalizes to other initial conditions too, achieving a median score of 3,170 (with 95% bootstrapped median confidence intervals of 2,580 - 3,170) on 200 different test environments (each with up to 30 random initial no-ops, a standard testing procedure ( Hessel et al., 2017 ; Mnih et al., 2015 ) ).

These examples and the success of RS versus DQN, A3C, and ES suggest that many Atari games that seem hard based on the low performance of leading deep RL algorithms may not be as hard as we think, and instead that these algorithms for some reason are performing poorly on tasks that are actually quite easy. These results further suggest that sometimes the best search strategy is not to follow the gradient, but instead to conduct a dense search in a local neighborhood and select the best point found, a subject we return to in the discussion (Sec. 5 ).

### 4.2 Image Hard Maze

This experiment seeks to demonstrate a benefit of GAs working at DNN scales, which is that algorithms that were developed to improve GAs can be immediately taken off the shelf to improve DNN training. The example algorithm is Novelty search (NS), which is a popular evolutionary method for exploration in RL ( Lehman & Stanley, 2011a ) .

NS was originally motivated by the Hard Maze domain ( Lehman & Stanley, 2011a ) , which is a staple in the neuroevolution community. It demonstrates the problem of local optima (aka deception) in reinforcement learning. In it, a robot receives more reward the closer it gets to the goal as the crow flies. The problem is deceptive because greedily getting closer to the goal leads an agent to permanently get stuck in one of the map’s deceptive traps (Fig. 1 , Left). Optimization algorithms that do not conduct sufficient exploration suffer this fate. NS solves this problem because it ignores the reward and encourages agents to visit new places ( Lehman & Stanley, 2011a ) .

The original version of this problem involves only a few inputs (radar sensors to sense walls) and two continuous outputs for speed (forward or backward) and rotation, making it solvable by small neural networks (tens of connections). Because here we want to demonstrate the benefits of NS at the scale of deep neural networks, we introduce a new version of the domain called Image Hard Maze. Like many Atari games, it shows a bird’s-eye view of the world to the agent in the form of an 84 × 84 84\times 84 pixel image (Fig. 1 , Left). This change makes the problem easier in some ways (e.g. now it is fully observable), but harder in others because it is much higher-dimensional: the neural network must learn to process this pixel input and take actions. SI Sec. 7.4 has additional experimental details.

We confirm that the results that held for small neural networks on the original, radar-based version of this task also hold for the high-dimensional, visual version of this task with deep neural networks. With a 4M+ parameter network processing pixels, the GA-based novelty search (GA-NS) is able to solve the task by finding the goal (Fig. 1 ). The GA optimizes for reward only and, as expected, gets stuck in the local optima of Trap 2 (SI Fig. 5 ) and thus fails to solve the problem (Fig. 1 ), significantly underperforming GA-NS ( p < 0.001 p<0.001 ). Our results confirm that we are able to use exploration methods such as novelty search to solve this sort of deception, even in high-dimensional problems such as those involving learning directly from pixels. This is the largest neural network optimized by novelty search to date by three orders of magnitude. In an companion paper ( Conti et al., 2017 ) , we also demonstrate a similar finding, by hybridizing novelty search with ES to create NS-ES, and show that it too can help deep neural networks avoid deception in challenging RL benchmark domains.