This paper, presented at GECCO '19, explores how to make Neuroevolution (NE) more efficient for Reinforcement Learning (RL) tasks by using surrogate models to predict the performance of neural networks without running full, expensive simulations.
TL;DR
The authors introduce a surrogate model-based approach to Neuroevolution that uses "phenotypic distance"—comparing how neural networks behave rather than how they are structured—to significantly reduce the number of fitness evaluations required. By dynamically updating the behavioral test cases during evolution, they achieved up to an 80% reduction in required evaluations on standard reinforcement learning benchmarks.
What Problem Does This Paper Address?
Neuroevolution is a powerful tool for training Artificial Neural Networks (ANNs) using evolutionary algorithms, particularly in Reinforcement Learning where gradients aren't always available. However, it is notoriously "data-hungry," requiring thousands of fitness evaluations. In RL, each evaluation involves running a full simulation (an "episode"), which can be computationally expensive or even physically impossible in real-world robotics.
Standard optimization uses Surrogate Models (like Gaussian Processes) to approximate the fitness function and skip expensive evaluations. The challenge with ANNs is that their "genotype" (weights and topology) doesn't map smoothly to their "fitness." Two networks with very different structures might behave identically, while a tiny change in one weight might cause a network to fail completely. This lack of "smoothness" makes traditional surrogate modeling based on network structure very difficult.
Methods
The authors propose Surrogate Model-Based Neuroevolution (SMB-NE). The core innovation lies in how they measure the distance between two networks to build their model:
- Cartesian Genetic Programming (CGP-ANN): They use CGP to evolve the networks, which allows for flexible topologies where nodes can be active or inactive.
- Phenotypic Distance (PhD): Instead of comparing the "DNA" (weights/connections) of two networks, they compare their "behavior." They feed a set of input states into both networks and measure the Manhattan distance between their resulting outputs.
- Kriging (Gaussian Process Regression): They use this phenotypic distance as the kernel for a Kriging model, which predicts the fitness of new candidate networks.
- Input Selection Strategies: Since phenotypic distance depends on which inputs you test, the authors investigated four ways to select these "test probes":
- Precomputed (Pre): States from a known optimal run (a "best-case" baseline).
- Static Initial (Init): States observed during the very first random generation.
- Sampling (LHS): Artificial states generated via Latin Hypercube Sampling to cover the whole state space.
- Dynamic (Dyn): Updating the test states whenever a new "best" network is found, ensuring the surrogate model stays relevant as the networks evolve.
Datasets
The researchers evaluated their approach using two classic benchmarks from the OpenAI Gym toolkit:
- CartPole-v1: A balancing task where a pole is attached to a cart moving on a track.
- MountainCar-v0: A classic "under-powered" car problem where the agent must build momentum to drive up a steep hill.
Key Insights and Ideas
- Behavior > Structure: The "competing conventions" problem (where different genotypes represent the same phenotype) makes genotypic distance a poor metric for surrogates. Phenotypic distance bypasses this by focusing entirely on what the network does.
- The Importance of "Relevant" States: A network's behavior only matters in the states it actually visits. The Dynamic (Dyn) strategy is crucial because as networks get better at the task, they encounter entirely different parts of the state space. A surrogate model trained only on the "failure states" of early random networks won't be able to distinguish between mediocre and elite networks later in the run.
- Efficiency Gains: The surrogate model doesn't just save time; it makes the search more "stable." SMB-NE variants were consistently able to solve the environments within the budget, whereas standard Neuroevolution occasionally failed to find a solution at all.
Key Results
- CartPole-v1: SMB-NE required roughly 70% (median) to 80% (mean) fewer evaluations than the standard model-free CGP-ANN. While the baseline averaged 328 episodes to solve the task, the best SMB-NE variant (DynSet 10) averaged only ~57 episodes.
- MountainCar-v0: This task proved much harder for the model-free approach. The best SMB-NE variant (DynSet 5) solved the task in an average of 179 episodes, while the standard evolutionary approach required over 900 episodes on average.
- Robustness: The authors found that SMB-NE is fairly robust to the choice of input vectors, though the dynamic update strategy provided the most consistent performance across different tasks.
Limitations and Future Work
- Computational Overhead: While SMB-NE reduces the number of simulations, calculating the Kriging model and phenotypic distances adds its own computational cost. This trade-off is only beneficial when the simulation itself is "expensive."
- Dimensionality: The length of the phenotypic output vector can become very large, which can slow down the Kriging model. The authors suggest further research into dimension reduction for these behavioral vectors.
- Scalability: The benchmarks used (CartPole and MountainCar) have small state spaces. It remains to be seen how well this phenotypic approach scales to high-dimensional inputs like raw pixels (Atari games) or complex humanoid robotics.
Summary updated