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

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

# Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning

###### Abstract

Deep artificial neural networks (DNNs) are typically trained via gradient-based learning algorithms, namely backpropagation. Evolution strategies (ES) can rival backprop-based algorithms such as Q-learning and policy gradients on challenging deep reinforcement learning (RL) problems. However, ES can be considered a gradient-based algorithm because it performs stochastic gradient descent via an operation similar to a finite-difference approximation of the gradient. That raises the question of whether non-gradient-based evolutionary algorithms can work at DNN scales. Here we demonstrate they can: we evolve the weights of a DNN with a simple, gradient-free, population-based genetic algorithm (GA) and it performs well on hard deep RL problems, including Atari and humanoid locomotion. The Deep GA successfully evolves networks with over four million free parameters, the largest neural networks ever evolved with a traditional evolutionary algorithm. These results (1) expand our sense of the scale at which GAs can operate, (2) suggest intriguingly that in some cases following the gradient is not the best choice for optimizing performance, and (3) make immediately available the multitude of neuroevolution techniques that improve performance. We demonstrate the latter by showing that combining DNNs with novelty search, which encourages exploration on tasks with deceptive or sparse reward functions, can solve a high-dimensional problem on which reward-maximizing algorithms (e.g. DQN, A3C, ES, and the GA) fail. Additionally, the Deep GA is faster than ES, A3C, and DQN (it can train Atari in ∼ \scriptstyle\sim 4 hours on one desktop or ∼ \scriptstyle\sim 1 hour distributed on 720 cores), and enables a state-of-the-art, up to 10,000-fold compact encoding technique.

Uber AI Labs {felipe.such, jeffclune}@uber.com

## 1 Introduction

A recent trend in machine learning and AI research is that old algorithms work remarkably well when combined with sufficient computing resources and data. That has been the story for (1) backpropagation applied to deep neural networks in supervised learning tasks such as computer vision ( Krizhevsky et al., 2012 ) and voice recognition ( Seide et al., 2011 ) , (2) backpropagation for deep neural networks combined with traditional reinforcement learning algorithms, such as Q-learning ( Watkins & Dayan, 1992 ; Mnih et al., 2015 ) or policy gradient (PG) methods ( Sehnke et al., 2010 ; Mnih et al., 2016 ) , and (3) evolution strategies (ES) applied to reinforcement learning benchmarks ( Salimans et al., 2017 ) . One common theme is that all of these methods are gradient-based, including ES, which involves a gradient approximation similar to finite differences ( Williams, 1992 ; Wierstra et al., 2008 ; Salimans et al., 2017 ) . This historical trend raises the question of whether a similar story will play out for gradient-free methods, such as population-based GAs.

This paper investigates that question by testing the performance of a simple GA on hard deep reinforcement learning (RL) benchmarks, including Atari 2600 ( Bellemare et al., 2013 ; Brockman et al., 2016 ; Mnih et al., 2015 ) and Humanoid Locomotion in the MuJoCo simulator ( Todorov et al., 2012 ; Schulman et al., 2015 ; Schulman et al., 2017 ; Brockman et al., 2016 ) . We compare the performance of the GA with that of contemporary algorithms applied to deep RL (i.e. DQN ( Mnih et al., 2015 ) , a Q-learning method, A3C ( Mnih et al., 2016 ) , a policy gradient method, and ES). One might expect GAs to perform far worse than other methods because they are so simple and do not follow gradients. Surprisingly, we found that GAs turn out to be a competitive algorithm for RL – performing better on some domains and worse on others, and roughly as well overall as A3C, DQN, and ES – adding a new family of algorithms to the toolbox for deep RL problems. We also validate the effectiveness of learning with GAs by comparing their performance to that of random search (RS). While the GA always outperforms random search, interestingly we discovered that in some Atari games random search outperforms powerful deep RL algorithms (DQN on 3/13 games, A3C on 6/13, and ES on 3/13), suggesting that local optima, saddle points, noisy gradient estimates, or some other force is impeding progress on these problems for gradient-based methods. Note that although deep neural networks often do not struggle with local optima in supervised learning ( Pascanu et al., 2014 ) , local optima remain an issue in RL because the reward signal may deceptively encourage the agent to perform actions that prevent it from discovering the globally optimal behavior.

Like ES and the deep RL algorithms, the GA has unique benefits. GAs prove slightly faster than ES (discussed below). The GA and ES are thus both substantially faster in wall-clock speed than Q-learning and policy gradient methods. We explore two distinct GA implementations: (1) a single-machine version with GPUs and CPUs, and (2) a distributed version on many CPUs across many machines. On a single modern desktop with 4 GPUs and 48 CPU cores, the GA can train Atari in ∼ \scriptstyle\sim 4 hours. Training to comparable performance takes ∼ \scriptstyle\sim 7-10 days for DQN and ∼ \scriptstyle\sim 4 days for A3C. This speedup enables individual researchers with single (albeit expensive) desktops to start using domains formerly reserved for well-funded labs only and iterate perhaps more quickly than with any other RL algorithm. Given substantial distributed computation (here, 720 CPU cores across dozens of machines), the GA and ES can train Atari in ∼ \scriptstyle\sim 1 hour. Also beneficial, via a new technique we introduce, even multi-million-parameter networks trained by GAs can be encoded with very few (thousands of) bytes, yielding the state-of-the-art compact encoding method.

Overall, the unexpectedly competitive performance of the GA (and random search) suggests that the structure of the search space in some of these domains is not amenable to gradient-based search. That realization opens up new research directions on when and how to exploit the regions where a gradient-free search might be more appropriate and motivates research into new kinds of hybrid algorithms.

## 2 Background

At a high level, an RL problem challenges an agent to maximize some notion of cumulative reward (e.g. total, or discounted) without supervision as to how to accomplish that goal ( Sutton & Barto, 1998 ) . A host of traditional RL algorithms perform well on small, tabular state spaces ( Sutton & Barto, 1998 ) . However, scaling to high-dimensional problems (e.g. learning to act directly from pixels) was challenging until RL algorithms harnessed the representational power of deep neural networks (DNNs), thus catalyzing the field of deep reinforcement learning (deep RL) ( Mnih et al., 2015 ) . Three broad families of deep learning algorithms have shown promise on RL problems so far: Q-learning methods such as DQN ( Mnih et al., 2015 ) , policy gradient methods ( Sehnke et al., 2010 ) (e.g. A3C ( Mnih et al., 2016 ) , TRPO ( Schulman et al., 2015 ) , PPO ( Schulman et al., 2017 ) ), and more recently evolution strategies (ES) ( Salimans et al., 2017 ) .

Deep Q-learning algorithms approximate the optimal Q function with DNNs, yielding policies that, for a given state, choose the action that maximizes the Q-value ( Watkins & Dayan, 1992 ; Mnih et al., 2015 ; Hessel et al., 2017 ) . Policy gradient methods directly learn the parameters of a DNN policy that outputs the probability of taking each action in each state. A team from OpenAI recently experimented with a simplified version of Natural Evolution Strategies ( Wierstra et al., 2008 ) , specifically one that learns the mean of a distribution of parameters, but not its variance. They found that this algorithm, which we will refer to simply as evolution strategies (ES), is competitive with DQN and A3C on difficult RL benchmark problems, with much faster training times (i.e. faster wall-clock time when many CPUs are available) due to better parallelization ( Salimans et al., 2017 ) .

All of these methods can be considered gradient-based methods, as they all calculate or approximate gradients in a DNN and optimize those parameters via stochastic gradient descent/ascent (though they do not require differentiating through the reward function, e.g. a simulator). DQN calculates the gradient of the loss of the DNN Q-value function approximator via backpropagation. Policy gradients sample behaviors stochastically from the current policy and then reinforce those that perform well via stochastic gradient ascent. ES does not calculate gradients analytically, but approximates the gradient of the reward function in the parameter space ( Salimans et al., 2017 ; Wierstra et al., 2008 ) .

Here we test whether a truly gradient-free method, a GA, can perform well on challenging deep RL tasks. We find GAs perform surprisingly well and thus can be considered a new addition to the set of algorithms for deep RL problems.

## 3 Methods

### 3.1 Genetic Algorithm

We purposefully test with an extremely simple GA to set a baseline for how well gradient-free evolutionary algorithms work for RL problems. We expect future work to reveal that adding the legion of enhancements that exist for GAs ( Fogel & Stayton, 1994 ; Haupt & Haupt, 2004 ; Clune et al., 2011 ; Mouret & Doncieux, 2009 ; Lehman & Stanley, 2011b ; Stanley et al., 2009 ; Mouret & Clune, 2015 ) will improve their performance on deep RL tasks.

A genetic algorithm ( Holland, 1992 ; Eiben et al., 2003 ) evolves a population 𝒫 \mathcal{P} of N N individuals (here, neural network parameter vectors θ \theta , often called genotypes ). At every generation , each θ i \theta_{i} is evaluated, producing a fitness score (aka reward) F ⁡ ( θ i ) F(\theta_{i}) . Our GA variant performs truncation selection , wherein the top T T individuals become the parents of the next generation. To produce the next generation, the following process is repeated N − 1 N-1 times: A parent is selected uniformly at random with replacement and is mutated by applying additive Gaussian noise to the parameter vector: θ ′ = θ + σ ​ ϵ \theta^{\prime}=\theta+\sigma\epsilon where ϵ ∼ 𝒩 ⁡ ( 0 , I ) \epsilon\sim\mathcal{N}(0,I) . The appropriate value of σ \sigma was determined empirically for each experiment, as described in Supplementary Information (SI) Table 2 . The N N th individual is an unmodified copy of the best individual from the previous generation, a technique called elitism . To more reliably try to select the true elite in the presence of noisy evaluation, we evaluate each of the top 10 individuals per generation on 30 additional episodes (counting these frames as ones consumed during training); the one with the highest mean score is the designated elite. Historically, GAs often involve crossover (i.e. combining parameters from multiple parents to produce an offspring), but for simplicity we did not include it. The new population is then evaluated and the process repeats for G G generations or until some other stopping criterion is met. SI Algorithm 1 provides pseudocode for our version.

Open source code and hyperparameter configurations for all of our experiments are available: http://bit.ly/2K17KxX . Hyperparameters are also listed in SI Table 2 . Hyperparameters were fixed for all Atari games, chosen from a set of 36 hyperparameters tested on six games (Asterix, Enduro, Gravitar, Kangaroo, Seaquest, Venture).

GA implementations traditionally store each individual as a parameter vector θ \theta , but this approach scales poorly in memory and network transmission costs with large populations and large (deeper and wider) neural networks. We propose a novel method to store large parameter vectors compactly by representing each parameter vector as an initialization seed plus the list of random seeds that produce the series of mutations that produced each θ \theta , from which each θ \theta can be reconstructed. This innovation was critical for an efficient implementation of a distributed deep GA.

SI Fig. 2 shows, and Eq. 1 describes, the method. θ n = ψ ⁡ ( θ n − 1 , τ n ) = θ n − 1 + σ ​ ε ​ ( τ n ) \theta^{n}=\psi(\theta^{n-1},\tau_{n})=\theta^{n-1}+\sigma\varepsilon(\tau_{n}) (1) where θ n \theta^{n} is an offspring of θ n − 1 \theta^{n-1} , ψ ⁡ ( θ n − 1 , τ n ) \psi(\theta^{n-1},\tau_{n}) is a deterministic mutation function, τ \tau is the encoding of θ n \theta^{n} consisting of a list of mutation seeds, θ 0 = ϕ ⁡ ( τ 0 ) \theta^{0}=\phi(\tau_{0}) , where ϕ \phi is a deterministic initialization function, and ε ⁡ ( τ n ) ∼ 𝒩 ⁡ ( 0 , I ) \varepsilon(\tau_{n})\sim\mathcal{N}(0,I) is a deterministic Gaussian pseudo-random number generator with an input seed τ n \tau_{n} that produces a vector of length | θ | |\theta| . In our case, ε ⁡ ( τ n ) \varepsilon(\tau_{n}) is a large precomputed table that can be indexed using 28-bit seeds. SI Sec. 7.3 provides more encoding details, including how the seeds could be smaller.

This technique is advantageous because the size of the compressed representation increases linearly with the number of generations (often order thousands), and is independent of the size of the network (often order millions or more). It does, of course, require computation to reconstruct the DNN weight vector. Competitive Atari-playing agents evolve in as little as tens of generations, enabling a compressed representation of a 4M+ parameter neural network in just thousands of bytes (a 10,000-fold compression). The compression rate depends on the number of generations, but in practice is always substantial: all Atari final networks were compressible 8,000-50,000-fold. This represents the state of the art in encoding large networks compactly. However, it is not a general network compression technique because it cannot compress arbitrary networks, and instead only works for networks evolved with a GA.

One motivation for choosing ES versus Q-learning and policy gradient methods is its faster wall-clock time with distributed computation, owing to better parallelization ( Salimans et al., 2017 ) . We found that the distributed CPU-only Deep GA not only preserves this benefit, but slightly improves upon it (SI Sec. 7.1 describes why GAs–distributed or local–are faster than ES). Importantly, GAs can also use GPUs to speed up the forward pass of DNNs (especially large ones), making it possible to train on a single desktop. With our GPU-enabled implementation, on one modern desktop we can train Atari in ∼ \scriptstyle\sim 4 hours what takes ∼ \scriptstyle\sim 1 hour with 720 distributed cores. Distributed GPU training would further speed up training for large population sizes.

### 3.2 Novelty Search

One benefit of training deep neural networks with GAs is it enables us to immediately take advantage of algorithms previously developed in the neuroevolution community. As a demonstration, we experiment with novelty search (NS) ( Lehman & Stanley, 2011a ) , which was designed for deceptive domains in which reward-based optimization mechanisms converge to local optima. NS avoids these local optima by ignoring the reward function during evolution and instead rewarding agents for performing behaviors that have never been performed before (i.e. that are novel). Surprisingly, it can often outperform algorithms that utilize the reward signal, a result demonstrated on maze navigation and simulated biped locomotion tasks ( Lehman & Stanley, 2011a ) . Here we apply NS to see how it performs when combined with DNNs on a deceptive image-based RL problem (that we call the Image Hard Maze ). We refer to the GA that optimizes for novelty as GA-NS.