A Restart-based Rank-1 Evolution Strategy for Reinforcement Learning

Zefeng Chen, Yuren Zhou, Xiaoyu He, Siyu JiangIJCAI 2019 · DOI

TL;DR

This paper introduces R-R1-ES, a novel evolution strategy for reinforcement learning that efficiently trains deep neural networks by adapting its search direction and incorporating mechanisms to escape local optima. It achieves competitive or superior performance to state-of-the-art methods on classic control and Atari game benchmarks, offering a more scalable and efficient alternative to existing approaches.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents learn by trial and error to maximize cumulative rewards. While deep neural networks have significantly advanced RL capabilities, training them effectively, especially in complex environments, remains a challenge. Evolution Strategies (ESs) are a class of black-box optimization algorithms that have shown promise in training deep neural networks for RL. However, existing ES variants for deep RL often use simplified versions and lack advanced techniques like adaptive mutation strength or sophisticated search direction adaptation. Specifically, the powerful Covariance Matrix Adaptation Evolution Strategy (CMA-ES), while effective in lower dimensions, is computationally too expensive for large-scale problems like training deep neural networks. This creates a gap in efficient, advanced ES methods for deep RL.

Methods

The paper proposes Restart-based Rank-1 Evolution Strategy (R-R1-ES), which builds upon the principles of CMA-ES but is optimized for efficiency in large-scale RL. Key innovations include:

  • Rank-1 Covariance Matrix Adaptation: Instead of adapting the full covariance matrix (which is computationally expensive), R-R1-ES uses a rank-1 approximation. This means it focuses on adapting the principal search direction and mutation strength, making it computationally tractable for deep RL. The covariance matrix is represented as $C_t = (1 - c_{cov})I + c_{cov}p_t p_t^T$, where $p_t$ is the principal search direction.
  • Adaptive Mutation Strength: The mutation strength ($\sigma_t$) is dynamically adjusted based on the rank difference of solutions between consecutive generations. This allows the strategy to fine-tune its exploration based on performance feedback.
  • Adaptive Principal Search Direction: The principal search direction ($p_t$) is updated using a mechanism similar to momentum in gradient descent. This allows the strategy to accumulate information about promising search directions over time, improving its ability to handle dependencies between variables.
  • Mechanisms for Escaping Local Optima:
    • Adaptive Number of Elitists ($\mu$): The number of best-performing individuals selected to guide the next generation is linearly increased over time. This balances exploration and exploitation, preventing premature convergence.
  • Restart Procedure: The algorithm can "restart" if the mutation strength becomes too small or if performance plateaus. During a restart, population size and a decay parameter are doubled, allowing for renewed exploration.

Datasets

The paper evaluates R-R1-ES on:

  • Classic Control Problems: CartPole-v1, MountainCar-v0, and Pendulum-v0 from OpenAI Gym.
  • Atari Games: Breakout-v0, Pong-v0, Qbert-v0, and Seaquest-v0.

These are standard benchmarks for evaluating RL algorithms. No new datasets were introduced.

Key Insights and Ideas

  • Rank-1 Approximation is Sufficient for RL: The core idea that a rank-1 adaptation of the covariance matrix is efficient and effective for deep RL is a significant insight. It suggests that the full complexity of CMA-ES might be overkill for these tasks.
  • Momentum-like Search Direction Adaptation: Borrowing the concept of momentum from gradient-based methods and applying it to the principal search direction in ES is a clever way to improve exploration and exploit past search information.
  • Integrated Local Optima Escape: The combination of adaptive elitism and a restart mechanism provides a robust way to prevent the algorithm from getting stuck in suboptimal solutions, a common problem in RL.
  • Efficiency Gains: The linear time and low space complexity of R-R1-ES make it a practical choice for large-scale deep RL problems where traditional CMA-ES would be infeasible.

Key Results

  • Classic Control Problems: R-R1-ES performed competitively with or better than OpenAI-ES on CartPole-v1 and Pendulum-v0. On MountainCar-v0, its performance was slightly lower than OpenAI-ES but still competitive.
  • Atari Games:
    • On Pong-v0, OpenAI-ES achieved the highest scores, with R-R1-ES performing competitively with other advanced ES variants.
  • On Seaquest-v0, R-R1-ES achieved the highest score among the tested algorithms, demonstrating its effectiveness in environments with local optima.
  • On Breakout-v0, R-R1-ES performed best, outperforming other ES variants, suggesting its robustness in challenging environments.
  • On Qbert-v0, R-R1-ES and Canonical ES (both (μ, λ)-ES variants) achieved higher scores than other methods, indicating the benefit of this framework.

Overall, R-R1-ES demonstrated superior or competitive performance across a range of RL tasks.

Limitations and Future Work

  • Parameter Tuning: The paper notes that the threshold values for the restart procedure were set based on empirical study and could potentially be problem-specific for optimal performance.
  • Future Research: The authors suggest investigating the performance of R-R1-ES on more challenging RL tasks and exploring other state-of-the-art CMA-ES variants for large-scale black-box optimization. They also propose combining R-R1-ES with advanced techniques to further enhance its effectiveness and efficiency.

Summary updated

BibTeX
@inproceedings{chen2019restart,
  author = {Zefeng Chen and Yuren Zhou and Xiaoyu He and Siyu Jiang},
  title = {{A Restart-based Rank-1 Evolution Strategy for Reinforcement Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/295},
}
Figure