Source-linked AI summary
Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning
Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O. Stanley, Jeff Clune
TL;DR
The paper asks whether non-gradient-based evolution can train deep neural networks at scales where gradient-based methods dominate. It evolves DNN weights with a simple genetic algorithm, combines the approach with novelty search, and finds competitive deep-RL performance alongside faster training and compact encodings.
Problem
The paper addresses whether a truly gradient-free evolutionary algorithm can train deep neural networks effectively on challenging reinforcement-learning problems.
Method
The paper evolves DNN parameter vectors with a simple population-based GA and applies novelty search to encourage behavioral exploration on deceptive tasks.
Results
The GA is roughly as competitive overall as A3C, DQN, and ES, trains Atari in ∼4h on one desktop or ∼1h on 720 CPUs, and supports compact evolved-network encodings.
Takeaways & Limitations
The results support using gradient-free genetic algorithms and established neuroevolution techniques as additional tools for deep reinforcement learning.
Takeaways & Limitations
Atari comparisons are preliminary because more computation is needed for sufficient per-game sample sizes, and evaluation regimes are not uniform across algorithms.
Abstract
from arXiv · showhide
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 ${\raise.17ex\hbox{$\scriptstyle\sim$}}$4 hours on one desktop or ${\raise.17ex\hbox{$\scriptstyle\sim$}}$1 hour distributed on 720 cores), and enables a state-of-the-art, up to 10,000-fold compact encoding technique.
1. Introduction
The paper asks whether a simple, genuinely gradient-free genetic algorithm can train deep networks effectively on difficult reinforcement-learning problems. Across Atari and locomotion, the GA is competitive overall, faster in wall-clock time, and motivates gradient-free and hybrid search.
- The paper tests a simple genetic algorithm on challenging Atari 2600 and Humanoid Locomotion deep-RL benchmarks.
- The GA performs better on some domains and worse on others, but roughly as well overall as A3C, DQN, and ES.
- Random search outperforms DQN on 3/13 Atari games, A3C on 6/13, and ES on 3/13, while the GA always beats random search.
- ∼4 hours trains Atari on one desktop, versus ∼7-10 days for DQN and ∼4 days for A3C.
- The results suggest that some search spaces favor gradient-free local sampling and motivate research into hybrid algorithms.
2. Background
Deep reinforcement learning uses DNNs to address high-dimensional control, while dominant Q-learning, policy-gradient, and ES approaches optimize parameters through calculated or approximate gradients. The paper tests whether a truly gradient-free GA can serve as another effective deep-RL algorithm.
- Deep reinforcement learning combines traditional RL with DNNs to handle high-dimensional problems such as acting directly from pixels.
- Deep RL includes Q-learning methods such as DQN, policy-gradient methods such as A3C, and evolution strategies.
- DQN backpropagates through a Q-value loss, policy gradients reinforce successful sampled behaviors, and ES approximates gradients.
- The paper tests whether a truly gradient-free GA performs well on challenging deep-RL tasks and finds it surprisingly competitive.
3. Methods
The methods use a deliberately simple population-based GA with truncation selection, Gaussian mutation, elitism, and compact seed-based encoding. The paper also combines GA training with novelty search to explore deceptive, image-based RL tasks.
- Genetic Algorithm: The baseline GA is intentionally simple so future enhancements can be measured against its performance.
- Genetic Algorithm: Each generation evaluates N neural-network parameter vectors, retains the top T as parents, mutates offspring with Gaussian noise, and preserves the best individual through elitism.
- Experimental setup: Hyperparameters are fixed across Atari games after testing 36 configurations on six games.
- Compact encoding: Seed-based representations reconstruct parameter vectors from an initialization seed and mutation seeds, reducing distributed memory and transmission costs.
- Compact encoding: 4M+ parameter Atari networks compress to thousands of bytes, achieving 8,000-50,000-fold compression, but only for networks evolved with a GA.
- Implementation: The distributed GA preserves and slightly improves ES's wall-clock advantage, while GPUs can accelerate DNN forward passes.
- Novelty Search: Novelty search replaces reward fitness with behavioral novelty based on distances to nearest neighbors in the population or an archive.
4. Experiments
The experiments show that a simple genetic algorithm can train 4M+ parameter networks competitively across Atari, solve visual maze navigation with novelty search, and learn humanoid locomotion, though performance varies by domain and comparison conditions.
- 4.1. Atari: The GA used a DQN-matched Atari architecture containing over 4M parameters, demonstrating that a simple GA can evolve networks at deep-learning scale.Agents were evaluated on full episodes, with fitness equal to the sum of episode rewards.
- 4.1. Atari: The GA performed roughly as well as DQN, A3C, and ES across 13 Atari games, with each algorithm achieving the best score on different games.The GA produced the best score on 3 games, while DQN and ES also led on 3 each and A3C on 4.
- 4.1. Atari: After 6B frames, the GA outperformed A3C, ES, and DQN on 7, 8, and 7 of 13 games, respectively, while performance had not converged in most games.The authors identify this as the largest neural network evolved with a simple GA.
- 4.1. Atari: The GA found performance exceeding final DQN scores within 1 to 29 generations on six Atari games, including Skiing in one generation.The reported generation counts were 1, 1, 3, 5, 11, and 29 for Skiing, Venture, Frostbite, Asteroids, Gravitar, and Zaxxon.
- 4.1. Atari: Random search beat DQN on 3/13 games, ES on 3/13, and A3C on 6/13, indicating that some difficult-looking Atari tasks reward dense local search over gradient following.The authors suggest these algorithms may perform poorly on tasks that are actually relatively easy.
- 4.2. Image Hard Maze: The experiments also demonstrate that novelty search can be applied directly to deep GA training, motivating combinations of deep networks with other evolutionary diversity and quality-diversity methods.The authors propose testing such combinations across additional Atari and robotics domains.
- 4.3. Humanoid Locomotion: The GA solved Humanoid Locomotion but took approximately 15 times longer than ES and performed slightly worse.The result motivates further research into why GA performance differed from prior locomotion studies.
5. Discussion
The discussion suggests that gradient-free search can succeed at deep-RL scales, while the ultimate promise and best operating domains of GAs remain uncertain. It also identifies enhancements and hybrid methods as important directions for improving or extending Deep GA.
- Search-space interpretation: Gradient-free search can find increasingly better solutions in some high-dimensional domains without following a gradient.The authors suggest that good solutions may be unexpectedly dense around the origin and around already good solutions.
- Search-space interpretation: Temporally extended exploration may improve GA and ES performance because one parameterized policy governs actions throughout an episode.Consistent behavior on repeated state visits can make exploration easier.
- Search-space interpretation: GA-style local search may outperform gradient following in some regions, but the authors do not expect this pattern to hold across all domains.The discussion proposes local-optimum escape as one possible reason and raises hybrid GA–gradient methods as an open question.
- Open questions: The ultimate promise of GAs versus competing deep-RL training algorithms remains poorly understood.The paper explicitly frames this as an unresolved limitation.
- Open questions: Existing neuroevolution enhancements, including crossover, indirect encoding, and quality diversity, could improve the simple GA.Indirect encoding is highlighted as promising for Humanoid Locomotion and Atari, based on prior results in evolving robot gaits.
6. Conclusion
The paper concludes that a simple Deep GA can competitively train deep networks for challenging RL tasks while supporting fast distributed training and compact encodings. Its results also motivate testing broader neuroevolution techniques and revisiting simple algorithms with modern computation.
- Conclusion: The Deep GA competitively trains deep neural networks on challenging reinforcement-learning tasks and supports efficient distributed training plus compact network encoding.The paper presents both the training method and an encoding technique as core contributions.
- Conclusion: ∼4h on a single desktop or ∼1h distributed on 720 CPUs are reported for Atari training with the Deep GA.These are the paper’s reported training times for its single-machine and distributed implementations.
- Conclusion: The results show that GAs are surprisingly competitive with DQN, A3C, and ES, especially on challenging Atari problems.The conclusion positions this as a central empirical finding.
- Conclusion: Deep GA-powered novelty search demonstrates that neuroevolution methods can be tested with deep neural networks on deceptive Atari-scale tasks.The paper states that novelty search solved a deceptive game where reward-maximizing algorithms failed in the abstract.
- Conclusion: The broader conclusion is that simple algorithms combined with modern amounts of computation can perform remarkably well, motivating renewed attention to other older algorithms.The authors connect this observation to the history of backpropagation and evolution strategies.
7. Supplementary Information
The supplementary information details the GA and novelty-search procedures, compact encoding, experimental settings, and results across Atari and humanoid locomotion. It also documents frame accounting and the domain dependence of GA performance.
- Genetic algorithm: The simple GA selects the top T individuals, then repeatedly mutates randomly selected parents with additive Gaussian noise to form the next generation.The algorithm evaluates each individual for fitness, retains truncation-selected parents, and returns the elite after sorting offspring by fitness.
- Novelty search: Novelty search replaces reward fitness with behavioral novelty computed from distances to k nearest neighbors in the population or archive.Individuals’ behavioral characteristics may enter an archive with probability p, while reward is used only to identify the best individual for reporting.
- Compact encoding: The compact encoding stores an initialization seed and mutation seeds instead of full parameter vectors, enabling deterministic reconstruction while representation size grows with generations rather than network size.Seed lengths can be as small as log2(x) bits for at most x offspring per parent, although spanning the full search space requires at least log2(|θ|) bits.
- Humanoid locomotion: The humanoid experiment uses a 376-scalar state input, 17 joint-torque outputs, and a two-hidden-layer tanh network containing approximately 167k parameters.Inputs are normalized using statistics from 10,000 random policies, and mutation power is annealed to 0.001 after 1,000 generations.
- Humanoid locomotion: The GA exceeds the Humanoid-v1 solved threshold of ∼6,000 after ∼1,500 generations, whereas ES exceeds it after ∼100 generations.The result shows that the GA eventually solves the task but requires substantially more computation, and its advantage depends on the domain.
- Frame accounting: Atari training is reported in both game frames and training frames, distinguishing emulator-emitted frames from the subsampled frames used for learning.The terminology is intended to clarify comparisons and improve reproducibility.