Discovered Policy Optimisation

Chris Lu, Jakub Grudzien Kuba, Alistair Letcher, Luke Metz, Christian Schröder de Witt, Jakob N. Foerster

TL;DR

This paper introduces a novel approach to discovering new Reinforcement Learning (RL) algorithms by meta-learning a "drift" function within the theoretically grounded Mirror Learning framework. The resulting algorithm, Discovered Policy Optimisation (DPO), achieves state-of-the-art performance and generalizes to unseen environments, offering a promising direction for automated RL algorithm design.

What Problem Does This Paper Address?

Designing effective Reinforcement Learning (RL) algorithms has historically relied heavily on human intuition, mathematical derivations, and extensive experimentation. While this has led to significant progress, it's a process limited by human creativity and understanding. Existing "algorithm discovery" methods often fall into two camps: black-box approaches that lack theoretical guarantees and fail to outperform hand-crafted algorithms, or meta-RL methods that only adapt to a narrow distribution of tasks. This paper aims to bridge this gap by discovering new RL algorithms that are both theoretically sound and empirically superior, leveraging the structured framework of Mirror Learning.

Methods

The core of this work lies in meta-learning a "drift function" within the Mirror Learning framework. Mirror Learning provides a theoretical guarantee of convergence to optimal policies, and its algorithms share a common template, with the drift function being a key component that can be designed.

  1. Learnt Policy Optimisation (LPO): The authors first meta-learn a neural network parameterizing the drift function. This is achieved by training the network using Evolution Strategies (ES) to maximize the final return of an RL agent over a fixed episode length. The input to the drift network includes the probability ratio between actions and the advantage function.
  2. Discovered Policy Optimisation (DPO): By analyzing the learned drift function of LPO, the authors identify key features, particularly an "update asymmetry" and "cautious optimism." These insights are then used to formulate a novel, closed-form drift function. DPO is a Mirror Learning algorithm that directly implements these discovered principles, making it a theoretically sound and efficient RL algorithm.

Datasets

The experiments are conducted using the Brax physics simulator environments. Brax is noted for its ability to leverage parallel computation for faster training. The paper also evaluates performance on Minatar environments to demonstrate generalization to out-of-distribution tasks.

Key Insights and Ideas

  • Mirror Learning as a fertile ground for discovery: The paper demonstrates that the structured Mirror Learning framework, with its theoretical guarantees, is an effective space for meta-learning new RL algorithms, avoiding the pitfalls of purely black-box approaches.
  • Learned drift functions reveal algorithmic principles: Analyzing the neural network drift function learned by LPO provided crucial insights into effective policy optimization strategies, such as "rollback" for negative advantages and "cautious optimism" for positive ones.
  • DPO: A theoretically sound, discovered algorithm: The derived DPO algorithm, based on LPO's insights, achieves state-of-the-art performance and is a novel, closed-form RL algorithm discovered through meta-learning, not manual design.
  • Implicit Entropy Maximization: LPO's learned drift function implicitly encourages entropy maximization, leading to richer exploration without explicitly adding an entropy bonus to the objective.
  • Update Asymmetry is Key: The discovered drift function exhibits a distinct asymmetry in how it handles positive versus negative advantages, a feature that significantly contributes to its performance and differentiates it from standard algorithms like PPO.

Key Results

  • State-of-the-art Performance: Both LPO and DPO achieve state-of-the-art performance in the Brax environments, outperforming PPO across most tested tasks.
  • Generalization: LPO, meta-trained on a single environment (Ant), demonstrates strong generalization to unseen environments within Brax. DPO also shows robust performance across various environments.
  • Robustness to Hyperparameters: LPO and DPO exhibit greater consistency across runs and are robust to hyperparameter changes, even outperforming PPO when PPO's hyperparameters are tuned for each specific task.
  • DPO's Efficiency: DPO, as a closed-form algorithm, is as easy to implement as PPO and achieves performance on par with LPO, the best learned drift function.
  • LPO-Zero Underperformance: An LPO variant trained from scratch (LPO-Zero) shows promise but generally underperforms compared to LPO and DPO, suggesting that initialization near PPO or longer training might be beneficial for scratch learning.

Limitations and Future Work

  • Overfitting to Implementation Details: The authors acknowledge that LPO's reliance on Brax's PPO implementation might lead to overfitting to specific code-level design choices that optimize for wall-clock time rather than sample efficiency.
  • Expanding Drift Function Inputs: Future work could involve expanding the set of inputs to the learned drift function beyond probability ratios and advantages, potentially including algorithm hyperparameters or task information.
  • Meta-learning Other Mirror Learning Components: The authors suggest meta-learning other components of the Mirror Learning framework, not just the drift function, to further advance policy optimization.
  • Broader Applicability: Investigating the transferability of these discovered principles to different RL algorithms and problem domains is a natural next step.

Summary updated

Abstract

Tremendous progress has been made in reinforcement learning (RL) over the past decade. Most of these advancements came through the continual development of new algorithms, which were designed using a combination of mathematical derivations, intuitions, and experimentation. Such an approach of creating algorithms manually is limited by human understanding and ingenuity. In contrast, meta-learning provides a toolkit for automatic machine learning method optimisation, potentially addressing this flaw. However, black-box approaches which attempt to discover RL algorithms with minimal prior structure have thus far not outperformed existing hand-crafted algorithms. Mirror Learning, which includes RL algorithms, such as PPO, offers a potential middle-ground starting point: while every method in this framework comes with theoretical guarantees, components that differentiate them are subject to design. In this paper we explore the Mirror Learning space by meta-learning a "drift" function. We refer to the immediate result as Learnt Policy Optimisation (LPO). By analysing LPO we gain original insights into policy optimisation which we use to formulate a novel, closed-form RL algorithm, Discovered Policy Optimisation (DPO). Our experiments in Brax environments confirm state-of-the-art performance of LPO and DPO, as well as their transfer to unseen settings.
BibTeX
@inproceedings{lu2022discovered,
  author = {Chris Lu and Jakub Grudzien Kuba and Alistair Letcher and Luke Metz and Christian Schröder de Witt and Jakob N. Foerster},
  title = {{Discovered Policy Optimisation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=bVVIZjQ2AA},
}
Figure