Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning — part 3/4
Cleaned-text code points [31297, 46638). Bibliography omitted here; source.md includes it.
As expected, ES also fails to solve the task because it focuses solely on maximizing reward (Fig. 1 & SI Fig. 5 ). We also test Q-learning (DQN) and policy gradients on this problem. We did not have source code for A3C, but were able to obtain source code for A2C, which has similar performance ( Wu et al., 2017 ) : the only difference is that it is synchronous instead of asynchronous. For these experiments we modified the rewards of the domain to step-by-step rewards (the negative change in distance to goal since the last time-step), but for plotting purposes, we record the final distance to the goal. Having per-step rewards is standard for these algorithms and provides more information, but does not remove the deception. Because DQN requires discrete outputs, for it we discretize each of the two continuous outputs into to five equally sized bins. To enable all possible output combinations, it learns 5 2 = 25 5^{2}=25 Q-values.
Also as expected, DQN and A2C fail to solve this problem (Fig. 1 , SI Fig. 5 ). Their default exploration mechanisms are not enough to find the global optimum given the deceptive reward function in this domain. DQN is drawn into the expected Trap 2. For unclear reasons, even though A2C visits Trap 2 often early in training, it converges on getting stuck in a different part of the maze. Of course, exploration techniques could be added to these controls to potentially make them perform as well as GA-NS. Here we only sought to show that the Deep GA allows algorithms developed for small-scale neural networks can be harnessed on hard, high-dimensional problems that require DNNs.
In future work, it will be interesting to combine NS with a Deep GA on more domains, including Atari and robotics domains. More importantly, our demonstration suggests that other algorithms that enhance GAs can now be combined with DNNs. Perhaps most promising are those that combine a notion of diversity (e.g. novelty) and quality (i.e. being high performing), seeking to collect a set of high-performing, yet interestingly different policies ( Mouret & Clune, 2015 ; Lehman & Stanley, 2011b ; Cully et al., 2015 ; Pugh et al., 2016 ) . The results also motivate future research into combining deep RL algorithms (e.g. DQN, A3C) with novelty search and quality diversity algorithms.
### 4.3 Humanoid Locomotion
The GA was also able to solve the challenging continuous control benchmark of Humanoid Locomotion ( Brockman et al., 2016 ) , which has validated modern, powerful algorithms such as A3C, TRPO, and ES. While the GA did produce robots that could walk well, it took ∼ \scriptstyle\sim 15 times longer to perform slightly worse than ES (SI Sec. 7.5 ), which is surprising because GAs have previously performed well on robot locomotion tasks ( Clune et al., 2011 ; Huizinga et al., 2016 ) . Future research is required to understand why.
## 5 Discussion
The surprising success of the GA and RS in domains thought to require at least some degree of gradient estimation suggests some heretofore under-appreciated aspects of high-dimensional search spaces. They imply that densely sampling in a region around the origin is sufficient in some cases to find far better solutions than those found by state-of-the-art, gradient-based methods even with far more computation or wall-clock time, suggesting that gradients do not point to these solutions, or that other optimization issues interfere with finding them, such as saddle points or noisy gradient estimates. The GA results further suggest that sampling in the region around good solutions is often sufficient to find even better solutions, and that a sequence of such discoveries is possible in many challenging domains. That result in turn implies that the distribution of solutions of increasing quality is unexpectedly dense, and that you do not need to follow a gradient to find them.
Another, non-mutually exclusive hypothesis, is that GAs (and ES) have improved performance due to temporally extended exploration ( Osband et al., 2016 ) , meaning they explore consistently since all actions in an episode are a function of the same set of mutated parameters, which improves exploration ( Plappert et al., 2017 ) . This helps exploration for two reasons, (1) an agent takes the same action (or has the same distribution over actions) each time it visits the same state, which makes it easier to learn whether the policy in that state is advantageous, and (2) the agent is also more likely to have correlated actions across states (e.g. always go up) because mutations to its internal representations can affect the actions taken in many states similarly.
Perhaps more interesting is the result that sometimes it is actually worse to follow the gradient than sample locally in the parameter space for better solutions. This scenario probably does not hold in all domains, or even in all the regions of a domain where it sometimes holds, but that it holds at all expands our conceptual understanding of the viability of different kinds of search operators. A reason GA might outperform gradient-based methods is if local optima are present, as it can jump over them in the parameter space, whereas a gradient method cannot (without additional optimization tricks such as momentum, although we note that ES utilized the modern ADAM optimizer in these experiments ( Kingma & Ba, 2014 ) , which includes momentum). One unknown question is whether GA-style local, gradient-free search is better early on in the search process, but switching to a gradient-based search later allows further progress that would be impossible, or prohibitively computationally expensive, for a GA to make. Another unknown question is the promise of simultaneously hybridizing GA methods with modern algorithms for deep RL, such as Q-learning, policy gradients, or evolution strategies.
We still know very little about the ultimate promise of GAs versus competing algorithms for training deep neural networks on reinforcement learning problems. Additionally, here we used an extremely simple GA, but many techniques have been invented to improve GA performance ( Eiben et al., 2003 ; Haupt & Haupt, 2004 ) , including crossover ( Holland, 1992 ; Deb & Myburgh, 2016 ) , indirect encoding ( Stanley, 2007 ; Stanley et al., 2009 ; Clune et al., 2011 ) , and encouraging quality diversity ( Mouret & Clune, 2015 ; Pugh et al., 2016 ) , just to name a few. Moreover, many techniques have been invented that dramatically improve the training of DNNs with backpropagation, such as residual networks ( He et al., 2015 ) , SELU or RELU activation functions ( Krizhevsky et al., 2012 ; Klambauer et al., 2017 ) , LSTMs or GRUs ( Hochreiter & Schmidhuber, 1997 ; Cho et al., 2014 ) , regularization ( Hoerl & Kennard, 1970 ) , dropout ( Srivastava et al., 2014 ) , and annealing learning rate schedules ( Robbins & Monro, 1951 ) . We hypothesize that many of these techniques will also improve neuroevolution for large DNNs.
Some of these enhancements may improve the GA performance on Humanoid Locomotion. For example, indirect encoding, which allows genomic parameters to affect multiple weights in the final neural network (in a way similar to convolution’s tied weights, but with far more flexibility), has been shown to dramatically improve performance and data efficiency when evolving robot gaits ( Clune et al., 2011 ) . Those results were found with the HyperNEAT algorithm ( Stanley et al., 2009 ) , which has an indirect encoding that abstracts the power of developmental biology ( Stanley, 2007 ) , and is a particularly promising direction for Humanoid Locomotion and Atari we are investigating. It will further be interesting to learn on which domains Deep GA tends to perform well or poorly and understand why. Also, GAs could help in other non-differentiable domains, such as architecture search ( Liu et al., 2017 ; Miikkulainen et al., 2017 ) and for training limited precision (e.g. binary) neural networks.
## 6 Conclusion
Our work introduces a Deep GA that competitively trains deep neural networks for challenging RL tasks, and an encoding technique that enables efficient distributed training and a state-of-the-art compact network encoding. We found that the GA is fast, enabling training Atari in ∼ \scriptstyle\sim 4h on a single desktop or ∼ \scriptstyle\sim 1h distributed on 720 CPUs. We documented that GAs are surprisingly competitive with popular algorithms for deep reinforcement learning problems, such as DQN, A3C, and ES, especially in the challenging Atari domain. We also showed that interesting algorithms developed in the neuroevolution community can now immediately be tested with deep neural networks, by showing that a Deep GA-powered novelty search can solve a deceptive Atari-scale game. It will be interesting to see future research investigate the potential and limits of GAs, especially when combined with other techniques known to improve GA performance. More generally, our results continue the story – started by backprop and extended with ES – that old, simple algorithms plus modern amounts of computation can perform amazingly well. That raises the question of what other old algorithms should be revisited.
## Acknowledgements
We thank all of the members of Uber AI Labs for helpful suggestions throughout the course of this work, in particular Zoubin Ghahramani, Peter Dayan, Noah Goodman, Thomas Miconi, and Theofanis Karaletsos. We also thank Justin Pinkul, Mike Deats, Cody Yancey, and the entire OpusStack Team at Uber for providing resources and technical support. Thanks also to David Ha for many helpful suggestions that improved the paper.
## 7 Supplementary Information
### 7.1 Why the GA is faster than ES
The GA is faster than ES for two main reasons: (1) for every generation, ES must calculate how to update its neural network parameter vector θ \theta . It does so via a weighted average across many (10,000 in Salimans et al. 2017 ) pseudo-offspring (random θ \theta perturbations) weighted by their fitness. This averaging operation is slow for large neural networks and large numbers of pseudo-offspring (the latter is required for healthy optimization), and is not required for the Deep GA. (2) The ES requires require virtual batch normalization to generate diverse policies amongst the pseudo-offspring, which is necessary for accurate finite difference approximation ( Salimans et al., 2016 ) . Virtual batch normalization requires additional forward passes for a reference batch–a random set of observations chosen at the start of training–to compute layer normalization statistics that are then used in the same manner as batch normalization ( Ioffe & Szegedy, 2015 ) . We found that the random GA parameter perturbations generate sufficiently diverse policies without virtual batch normalization and thus avoid these additional forward passes through the network.
### 7.2 Hyperparameters
We use Xavier initialization ( Glorot & Bengio, 2010 ) as our policy initialization function ϕ \phi where all bias weights are set to zero, and connection weights are drawn from a standard normal distribution with variance 1 / N i n 1/N_{in} , where N i n N_{in} is the number of incoming connections to a neuron.
### 7.3 Additional information about the Deep GA compact encoding method
The compact encoding technique is based on the principle that the seeds need only be long enough to generate a unique mutation vector per offspring per parent. If any given parent θ n − 1 \theta^{n-1} produces at most x x offspring, then τ n \tau_{n} in Eq. 1 can be as small as a l o g 2 ( x ) log_{2}(x) -bit number. τ 0 \tau_{0} is a special case that needs one unique seed for each of N N per θ \theta vectors in generation 0, and can thus be encoded with l o g 2 ( N ) log_{2}(N) bits. The reason the seed bit-length can be vastly smaller than the search space size is because not every point in the search space is a possible offspring of θ n \theta^{n} , and we only need to be able generate offspring randomly (we do not need to be able to reach any point in the search space in one random step). However, because we perform n n random mutations to produce θ n \theta^{n} , the process can reach many points in the search space.
However, to truly be able to reach every point in the search space we need our set of mutation vectors to span the search space, meaning we need the seed to be at least l o g 2 ( | θ | ) log_{2}(|\theta|) bits. To do so we can use a function ℋ ( θ , τ ) \mathcal{H}(\theta,\tau) that maps a given ( θ , τ n ) (\theta,\tau_{n}) -pair to a new seed and applies it as such:
ψ ( θ n − 1 , τ n ) = θ n − 1 + ε ( ℋ ( θ n − 1 , τ n ) ) \psi(\theta^{n-1},\tau_{n})=\theta^{n-1}+\varepsilon(\mathcal{H}(\theta^{n-1},\tau_{n})) (2)
Note that in this case there are two notions of seeds. The encoding is a series of small τ \tau seeds, but each new seed τ \tau is generated from the parent θ \theta and the previous seed.
### 7.4 Additional experimental details for the Image Hard Maze
For temporal context, the current frame and previous three frames are all input at each timestep, following Mnih et al. (2015) . The outputs remain the same as in the original Hard Maze problem formulation in Lehman & Stanley (2011a) . Unlike the Atari domain, the Image Hard Maze environment is deterministic and does not need multiple evaluations of the same policy.
Following Lehman & Stanley (2011a) , the BC is the ( x , y ) (x,y) position of the robot at the end of the episode (400 timesteps), and the behavioral distance function is the squared Euclidean distance between these final ( x , y ) (x,y) positions. The simulator ignores forward or backward motion that would result in the robot penetrating walls, preventing a robot from sliding along a wall, although rotational motor commands still have their usual effect in such situations.
### 7.5 Humanoid Locomotion
We tested the GA on a challenging continuous control problem, specifically humanoid locomotion. We test with the MuJoCo Humanoid-v1 environment in OpenAI Gym ( Todorov et al., 2012 ; Brockman et al., 2016 ) , which involves a simulated humanoid robot learning to walk. Solving this problem has validated modern, powerful algorithms such as A3C ( Mnih et al., 2016 ) , TRPO ( Schulman et al., 2015 ) , and ES ( Salimans et al., 2017 ) .
This problem involves mapping a vector of 376 scalars that describe the state of the humanoid (e.g. its position, velocity, angle) to 17 joint torques. The robot receives a scalar reward that is a combination of four components each timestep. It gets positive reward for standing and its velocity in the positive x x direction, and negative reward the more energy it expends and for how hard it impacts the ground. These four terms are summed over every timestep in an episode to calculate the total reward.
To stabilize training, we normalize each dimension of the input by subtracting its mean and dividing by its standard deviation, which are computed from executing 10,000 random policies in the environment. We also applied annealing to the mutation power σ \sigma , decreasing it to 0.001 after 1,000 generations, which resulted in a small performance boost at the end of training. The full set of hyperparameters are listed in SI Table 2 .