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.
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.
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