Similarities and differences between policy gradient methods and evolution strategies

Verena Heidrich-Meisner, Christian Igel

Abstract

Direct policy search in reinforcement learning has traditionally been split between gradient-based optimization and evolutionary computation. This paper provides a head-to-head comparison between Natural Actor-Critic (NAC) and CMA-ES, revealing that both can be viewed as "variable metric" methods. Despite this conceptual overlap, empirical results on the Cart-Pole benchmark show that CMA-ES is significantly more robust to hyperparameter settings and difficult initial conditions compared to the highly sensitive NAC.

Introduction

In Reinforcement Learning (RL), direct policy search aims to find optimal parameters for a policy function to maximize cumulative rewards. Two dominant paradigms have emerged: Policy Gradient Methods (PGMs) and Evolution Strategies (ESs). Despite their widespread use, systematic comparisons using identical environments and policy architectures have been rare. This research bridges the gap by evaluating Natural Actor-Critic (NAC), a state-of-the-art PGM, against CMA-ES, a leading ES.

Methods: The Variable Metric Connection

The core contribution of this work is the identification of both NAC and CMA-ES as variable metric methods. While they originate from different optimization lineages, both algorithms adapt the "metric"—the way they measure distance and direction in the parameter search space—based on environmental feedback.

Conceptual framework of NAC and CMA-ES as variable metric methods.
  • Natural Actor-Critic (NAC): Uses the "natural gradient" to follow the steepest ascent in the space of probability distributions, typically utilizing the Fisher information matrix to adapt its metric.
  • CMA-ES: An evolutionary algorithm that maintains a population of policies and adapts a covariance matrix to shape its search distribution toward successful regions.

A key difference lies in the noise injection: NAC introduces stochasticity at every time step through its policy, whereas CMA-ES perturbs policy parameters only once per episode.

Experimental Setup

The algorithms were tested on the classic Cart-Pole benchmark under two conditions:

  1. Easy ($S_I$): The pole starts near vertical.
  2. Hard ($S_{II}$): The pole starts with aggressive tilts and off-center positions. Both methods utilized a simple linear policy: $\pi(s) = \theta^T s$.

Results and Discussion

The empirical evaluation revealed a stark contrast in robustness between the two methods.

Performance comparison and hyperparameter sensitivity of NAC vs. CMA-ES across various settings.

The Robustness Gap

CMA-ES proved to be remarkably "set and forget." Its performance remained largely consistent regardless of its primary hyperparameter, the step size $\sigma$. In contrast, NAC exhibited extreme sensitivity. Successful learning with NAC required precise tuning of the learning rate ($\alpha$) and initial variance ($\sigma_{NAC}$). As shown in Figure 2b, only a small fraction of hyperparameter combinations for NAC led to successful convergence, highlighting the fragility of the gradient-based approach in this setting.

Task Performance

On the easy task ($S_I$), both algorithms achieved near-optimal performance within 5,000 episodes, provided NAC was perfectly tuned. However, on the hard task ($S_{II}$), CMA-ES consistently dominated. NAC struggled to find stable solutions even with extensive hyperparameter optimization.

Conclusion

While NAC and CMA-ES share a conceptual foundation as variable metric methods, their practical application differs significantly. CMA-ES offers superior robustness and ease of use, making it a powerful tool for direct policy search. NAC, while potentially useful for fine-tuning policies in specific directions, requires meticulous tuning that may be prohibitive in complex or poorly understood environments. Future work will explore these comparisons in higher-dimensional tasks to further map the strengths of each approach.

Summary updated

BibTeX
@inproceedings{heidrichmeisner2008similarities,
  author = {Verena Heidrich-Meisner and Christian Igel},
  title = {{Similarities and differences between policy gradient methods and evolution strategies}},
  booktitle = {ESANN},
  year = {2008},
}
Figure