A Scalable Finite Difference Method for Deep Reinforcement Learning

Background

Distributed finite-difference optimizers — and their close cousins in the Evolution Strategies family — are appealing precisely because they are simple to parallelize. Each worker evaluates the return function at a perturbation of the current parameters, and the coordinator collects those evaluations into a gradient estimate. This structure has helped these methods become competitive with tailored reinforcement learning algorithms on a range of tasks.

They come with an awkward cost, however. Each update requires the return function to be sampled around the current parameters, so once the coordinator has issued a batch of perturbations, it must wait for every worker to finish before it can compute an update and begin the next round. When workers vary in speed — and in reinforcement learning environments they typically do — the slowest worker sets the pace, and the rest of the cluster sits idle.

Contributions

This paper introduces a scheme for reusing older evaluations within a finite-difference update, using the results of our earlier work on ES and FD to justify the substitution. The outcome is a distributed optimizer that avoids the waiting problem: workers can continue to run without waiting for a synchronization barrier, and no computation is discarded.

We pair this optimizer with a variant of Novelty Search built on the agent space topology, giving the method an explicit exploration mechanism that is well-defined in continuous parameter spaces. The combination is demonstrated end-to-end in a reinforcement learning setting, shown in the visualization below.

Abstract

Several low-bandwidth distributable black-box optimization algorithms in the family of finite differences such as Evolution Strategies have recently been shown to perform nearly as well as tailored Reinforcement Learning methods in some Reinforcement Learning domains. One shortcoming of these black-box methods is that they must collect information about the structure of the return function at every update, and can often employ only information drawn from a distribution centered around the current parameters. As a result, when these algorithms are distributed across many machines, a significant portion of total runtime may be spent with many machines idle, waiting for a final return and then for an update to be calculated. In this work we introduce a novel method to use older data in finite difference algorithms, which produces a scalable algorithm that avoids significant idle time or wasted computation.

Our method in action

In this environment, the reward of an episode is the x-coordinate of the player at the final frame. The black box is a border which the player cannot cross. Each path in this visualization is created using the parameters of the locus agent during an epoch of optimization.

• arXiv