Sample-Efficient Evolutionary Function Approximation for Reinforcement Learning

Shimon Whiteson, Peter Stone

Introduction

A fundamental bottleneck in reinforcement learning (RL) is the manual design of function approximators. While neuroevolution offers a way to automate representation discovery, it typically incurs a heavy "sample tax"—requiring a vast number of environment interactions to evaluate candidate structures. This paper, originally presented at AAAI 2006, introduces Sample-Efficient NEAT+Q, an algorithm that combines neuroevolution with off-policy learning to achieve superior performance with orders of magnitude fewer interactions.

The Challenge of Representation Discovery

RL agents often use neural networks to estimate action values in large state spaces. However, performance is highly sensitive to network architecture (layers, neurons, connectivity), which is traditionally designed through human trial and error. Evolutionary Function Approximation, such as the NEAT+Q algorithm, automates this by evolving network topology.

NEAT mutations: Add Node and Add Link allow for the evolution of complex network topologies from simple beginnings.

In standard NEAT+Q, every candidate network must be evaluated over many episodes to allow its internal Q-learning mechanism to converge. In domains where episodes are expensive (e.g., robotics or server management), this high sample complexity is a major barrier.

Methods: Sample-Efficient NEAT+Q

The authors build upon NEAT (NeuroEvolution of Augmenting Topologies) and Q-learning. NEAT evolves the structure and initial weights, while Q-learning updates weights during an agent's "lifetime." This leverages the Baldwin Effect, where the ability to learn a behavior becomes an evolutionary advantage.

The key innovation is exploiting the off-policy nature of Q-learning. Since Q-learning can learn from transitions $(s, a, r, s')$ generated by any policy, the algorithm saves transition data from the previous generation's evaluations. Before a new generation is tested in the environment, each individual is "pre-trained" offline using this recycled experience. This "jumpstarts" the networks, allowing them to begin live evaluation with an informed value function.

Experimental Domain: Server Job Scheduling

The method was evaluated in a Server Job Scheduling task within the field of autonomic computing. A server must order jobs of four types to maximize aggregate utility, where each type has a distinct, non-linear utility function. The state space involves 16 features, and the agent must choose from 16 possible actions.

Key Results and Insights

The authors demonstrated that Sample-Efficient NEAT+Q significantly outperforms standard NEAT, standalone Q-learning, and the original NEAT+Q. Statistical analysis using Student’s t-tests confirmed these gains are significant at a 95% confidence level.

Performance comparison: (a) shows results with 5,000 episodes per generation, while (b) shows the dramatic advantage of Sample-Efficient NEAT+Q when limited to only 50 episodes per generation.

A critical finding was the method's robustness to low sample counts. In the deterministic scheduling task, original NEAT+Q failed to improve when limited to 50 episodes per generation because networks lacked sufficient training time. In contrast, the sample-efficient version achieved high performance rapidly by leveraging offline pre-training.

Furthermore, the authors observed diminishing returns with data: pre-training on just 5 saved episodes provided a massive boost, with 100 episodes offering little additional benefit. This suggests that even minimal recycled experience can effectively "prime" a new generation.

Conclusion

By shifting the burden of learning from live environment interactions to offline computation, Sample-Efficient NEAT+Q makes evolutionary RL viable for resource-constrained tasks. While it introduces computational overhead per generation due to backpropagation, the reduction in required "real-world" samples is a decisive advantage. Future work may explore the impact of stochasticity and the potential for long-term experience buffers.

Summary updated

Abstract

Reinforcement learning problems are commonly tackled with temporal difference methods, which attempt to estimate the agent's optimal value function. In most real-world problems, learning this value function requires a function approximator, which maps state-action pairs to values via a concise, parameterized function. In practice, the success of function approximators depends on the ability of the human designer to select an appropriate representation for the value function. A recently developed approach called evolutionary function approximation uses evolutionary computation to automate the search for effective representations. While this approach can substantially improve the performance of TD methods, it requires many sample episodes to do so. We present an enhancement to evolutionary function approximation that makes it much more sample-efficient by exploiting the off-policy nature of certain TD methods. Empirical results in a server job scheduling domain demonstrate that the enhanced method can learn better policies than evolution or TD methods alone and can do so in many fewer episodes than standard evolutionary function approximation.
BibTeX
@inproceedings{whiteson2006sample,
  author = {Shimon Whiteson and Peter Stone},
  title = {{Sample-Efficient Evolutionary Function Approximation for Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure