Evolution Strategies Converges to Finite Differences

Background

In 2017, a team at OpenAI led by Tim Salimans reported that a method they called Evolution Strategies (ES) could compete with tailored reinforcement learning algorithms on Atari and MuJoCo benchmarks. Because ES draws on ideas from evolutionary computation and does not require backpropagation, this result was widely read as evidence that evolutionary methods can be competitive with gradient-based RL at scale.

At almost the same time, Zhang et al. (2017) and Lehman et al. (2018) observed that ES looked suspiciously like an old and well-understood class of algorithms known as finite differences. Finite differences approximate the gradient of a function at a point by evaluating the function at small perturbations around that point and combining the resulting values. Prior work had noted the similarity but stopped short of establishing an exact relationship.

The result

In this paper we prove that ES and a finite differences gradient estimator, though not identical, converge as the dimension of the vector under optimization grows. Establishing this required some adjustments to the standard formulation of finite differences, which the paper carries out explicitly.

The consequence is a re-reading of the OpenAI ES result: Salimans' success should be understood as a success of finite differences at large scale, not as a demonstration that evolutionary or genetic methods are competitive with gradient-based RL. The distinction matters both for how we describe the method and for what improvements we should expect to transfer between the two families.

Abstract

Since the debut of Evolution Strategies (ES) as a tool for Reinforcement Learning by Salimans et al. 2017, there has been interest in determining the exact relationship between the Evolution Strategies gradient and the gradient of a similar class of algorithms, Finite Differences (FD) (Zhang et al. 2017, Lehman et al. 2018). Several investigations into the subject have been performed, investigating the formal motivational differences (Lehman et al. 2018) between ES and FD, as well as the differences in a standard benchmark problem in Machine Learning, the MNIST classification problem (Zhang et al. 2017). This paper proves that while the gradients are different, they converge as the dimension of the vector under optimization increases.

• arXiv