Surrogate Models for Enhancing the Efficiency of Neuroevolution in Reinforcement Learning

Jörg Stork, Martin Zaefferer, Thomas Bartz-Beielstein, A. E. Eiben

Abstract

In the last years, reinforcement learning received a lot of attention. One method to solve reinforcement learning tasks is Neuroevolution, where neural networks are optimized by evolutionary algorithms. A disadvantage of Neuroevolution is that it can require numerous function evaluations, while not fully utilizing the available information from each fitness evaluation. This is especially problematic when fitness evaluations become expensive. To reduce the cost of fitness evaluations, surrogate models can be employed to partially replace the fitness function. The difficulty of surrogate modeling for Neuroevolution is the complex search space and how to compare different networks. To that end, recent studies showed that a kernel based approach, particular with phenotypic distance measures, works well. These kernels compare different networks via their behavior (phenotype) rather than their topology or encoding (genotype). In this work, we discuss the use of surrogate model-based Neuroevolution (SMB-NE) using a phenotypic distance for reinforcement learning. In detail, we investigate a) the potential of SMB-NE with respect to evaluation efficiency and b) how to select adequate input sets for the phenotypic distance measure in a reinforcement learning problem. The results indicate that we are able to considerably increase the evaluation efficiency using dynamic input sets.

Introduction

Neuroevolution (NE) is a powerful paradigm for training Artificial Neural Networks (ANNs) using evolutionary algorithms. It is particularly effective in Reinforcement Learning (RL) scenarios where gradient information is unavailable or difficult to compute. However, a significant drawback of NE is its high demand for data; it often requires thousands of full simulations (episodes) to evaluate the fitness of candidate networks. In real-world applications like robotics, these evaluations are computationally expensive and time-consuming.

To mitigate this, researchers have turned to Surrogate Models—mathematical approximations of the fitness function that can predict a network's performance without running a full simulation. The primary challenge in applying surrogates to NE is the "ruggedness" of the search space. Traditional genotypic distances (comparing network weights or connections) do not map smoothly to fitness. Two structurally different networks might behave identically, while a minor weight change can lead to catastrophic failure.

Methodology: Surrogate Model-Based Neuroevolution (SMB-NE)

The authors propose a framework called Surrogate Model-Based Neuroevolution (SMB-NE). The core innovation is the use of Phenotypic Distance (PhD) to build the surrogate model. Instead of comparing the "DNA" of networks, PhD compares their "behavior" by measuring the difference in their outputs when presented with the same set of input states.

The SMB-NE workflow: integrating reinforcement learning with surrogate modeling and phenotypic distance.

The process follows an iterative loop:

  1. Representation: Networks are evolved using Cartesian Genetic Programming (CGP-ANN), which supports flexible, non-layered topologies.
  2. Surrogate Modeling: A Kriging model (Gaussian Process Regression) is trained using phenotypic distance as the kernel.
  3. Input Selection: The choice of "test probes" for measuring behavior is critical. The authors explored several strategies, finding that Dynamic (Dyn) updates—refreshing test states whenever a new "best" network is found—ensured the surrogate remained accurate as the population evolved into new regions of the state space.
  4. Optimization: The surrogate model suggests new candidate networks, significantly reducing the need for expensive environment simulations.

Experimental Results

The SMB-NE approach was evaluated on two standard OpenAI Gym benchmarks: CartPole-v1 (a balancing task) and MountainCar-v0 (a momentum-based climbing task).

Performance comparison on CartPole-v1: SMB-NE variants (blue) significantly outperform standard CGP (red) and random search (green) in evaluation efficiency.

The results demonstrate substantial efficiency gains:

  • Efficiency Gains: In the CartPole-v1 task, SMB-NE achieved a median reduction in evaluations of approximately 70% compared to standard model-free CGP-ANN. The best-performing variant (DynSet 10) required only ~57 episodes on average, compared to 328 for the baseline.
  • Robustness in Hard Tasks: For MountainCar-v0, which is notoriously difficult for standard evolutionary methods, SMB-NE solved the task in an average of 179 episodes, while the model-free approach required over 900.
  • Search Stability: Beyond speed, the surrogate-based approach proved more robust, consistently finding solutions where standard NE occasionally failed within the allocated budget.

Discussion and Future Work

The success of SMB-NE hinges on the insight that behavior is a better metric than structure for surrogate modeling in neuroevolution. By focusing on phenotypes, the model bypasses the "competing conventions" problem inherent in neural network encodings.

However, challenges remain. Calculating Kriging models and phenotypic distances introduces its own computational overhead. This approach is most beneficial when the environment simulation itself is the primary bottleneck. Future research will focus on scaling these methods to high-dimensional state spaces and exploring dimensionality reduction techniques for behavioral vectors to maintain efficiency in more complex tasks.

Conclusion

This work demonstrates that surrogate models using phenotypic distance can dramatically enhance the efficiency of Neuroevolution in Reinforcement Learning. By dynamically adapting behavioral test cases, SMB-NE provides a path toward more data-efficient autonomous learning in complex environments.

Summary updated

Abstract

In the last years, reinforcement learning received a lot of attention. One method to solve reinforcement learning tasks is Neuroevolution, where neural networks are optimized by evolutionary algorithms. A disadvantage of Neuroevolution is that it can require numerous function evaluations, while not fully utilizing the available information from each fitness evaluation. This is especially problematic when fitness evaluations become expensive. To reduce the cost of fitness evaluations, surrogate models can be employed to partially replace the fitness function. The difficulty of surrogate modeling for Neuroevolution is the complex search space and how to compare different networks. To that end, recent studies showed that a kernel based approach, particular with phenotypic distance measures, works well. These kernels compare different networks via their behavior (phenotype) rather than their topology or encoding (genotype). In this work, we discuss the use of surrogate model-based Neuroevolution (SMB-NE) using a phenotypic distance for reinforcement learning. In detail, we investigate a) the potential of SMB-NE with respect to evaluation efficiency and b) how to select adequate input sets for the phenotypic distance measure in a reinforcement learning problem. The results indicate that we are able to considerably increase the evaluation efficiency using dynamic input sets.
BibTeX
@inproceedings{stork2019surrogate,
  author = {Jörg Stork and Martin Zaefferer and Thomas Bartz-Beielstein and A. E. Eiben},
  title = {{Surrogate Models for Enhancing the Efficiency of Neuroevolution in Reinforcement Learning}},
  booktitle = {GECCO},
  year = {2019},
  url = {https://openreview.net/forum?id=mYblaHXb09},
}
Figure