This paper, presented at GECCO '21, introduces BNET (Behavior-based Neuroevolutionary Training), a hybrid framework designed to bridge the gap between the structural flexibility of neuroevolution and the sample efficiency of modern reinforcement learning (RL).
TL;DR
BNET enhances neuroevolution by integrating behavior-based search and surrogate modeling, allowing it to exploit fine-grained state-action data typically ignored by evolutionary algorithms. By combining topology-changing networks with advantage-weighted behavior loss functions, the framework achieves high sample efficiency, outperforming standard RL baselines on sparse-reward tasks and real-world robotic benchmarks.
What Problem Does This Paper Address?
Neuroevolution (NE)—using evolutionary algorithms to train neural networks—is excellent at optimizing both network weights and topologies simultaneously. However, it is notoriously "sample hungry." Most NE methods treat an entire RL episode as a single data point (the final reward), ignoring the rich "experience" (the specific states and actions) gathered during the trial.
In real-world applications, like robotics, every second of operation is expensive. We cannot afford the millions of trials often required by standard NE. While value-based RL methods (like PPO or A2C) are more sample-efficient because they learn from every step, they struggle with optimizing non-fixed network topologies. BNET aims to get the best of both worlds: the structural search of NE and the data efficiency of value-based RL.
Methods
The core of BNET is a population-based approach using Cartesian Genetic Programming (CGP) to represent neural networks. Unlike standard layers, CGP allows for arbitrary, non-layered graphs. The framework generates new candidate policies through three parallel search "paths":
- Fitness-based Search: A standard evolutionary approach that selects a "champion" and creates direct mutations. It includes a Robust Selection mechanism that re-evaluates candidates to ensure they aren't just "lucky" in noisy environments.
- Behavior-based Search: This is the primary innovation. It uses an archive of "elite" experiences and a value-critic model to calculate advantage-weighted behavior distances. It essentially asks: "How can I change this network to mimic the successful actions of previous high-performing agents?" This allows for a directed search in behavior space without needing backpropagation through the network topology.
- Surrogate-based Search: The authors employ Surrogate Model-Based Optimization (SMBO). They fit a Kriging (Gaussian Process) model to the archive of evaluated candidates. Crucially, they use a behavioral distance kernel rather than a genotypic one, allowing the model to predict a new network's performance based on how it acts rather than how its code is structured.
Datasets
The authors evaluated BNET on three distinct environments:
- CartPole-v0: A classic control benchmark for balancing a pole.
- MountainCar-v0: A challenging "sparse reward" problem where an agent must build momentum to climb a hill. This is notoriously difficult for many gradient-based RL algorithms.
- Robot Maze (New): A custom-built real-world benchmark. It uses a Universal Robot UR10e robotic arm to tilt a physical Lego maze, moving a marble to a target. This environment introduces real-world noise, physical constraints, and high resource costs.
Key Insights and Ideas
- Behavior > Genotype: In topology-changing neuroevolution, two networks might look completely different "genetically" but behave identically. BNET focuses on Behavioral Embeddings, defining distance based on the actions taken in specific states. This makes surrogate modeling much more accurate.
- Advantage Weighting as a Bridge: By weighting behavioral loss by the "advantage" (how much better an action was than the average), the authors effectively perform a gradient-free version of policy improvement.
- Hybridization Prevents Stagnation: The results show that while the surrogate model sometimes struggles with high-dimensional spaces, the combination of mutation, imitation (behavior search), and prediction (surrogates) creates a diverse population that resists local optima.
Key Results
- Efficiency in CartPole: The "Base" BNET (using all modules) solved the task in a median of 3,576 steps, significantly faster than pure mutation-based neuroevolution (~17,000 steps).
- Dominance in MountainCar: BNET solved MountainCar consistently (median ~13.5k steps), whereas standard baselines like PPO and A2C failed to solve it within the same step budget in the authors' setup.
- Real-World Success: In the physical Robot Maze, BNET variants (specifically those combining behavior distance and cross-entropy) outperformed PPO, reaching the target in fewer timesteps (Mean: 1156 vs 1580).
Limitations and Future Work
- Computational Overhead: The current implementation is an R-based prototype and is relatively slow in terms of wall-clock time, even if it is efficient in terms of environment steps.
- Discrete Action Spaces: The current framework is tailored for discrete actions. Extending this to continuous control (e.g., joint torques in robotics) is a noted next step.
- Hyperparameter Sensitivity: The authors noted they did not perform extensive tuning. There is likely significant room for improvement by optimizing the mutation rates and surrogate kernel parameters.
- Offline Learning: The authors suggest that BNET could be "jumpstarted" using offline data from human demonstrations or other agents, further reducing the need for expensive real-world interactions.
Summary updated