PaperlayerView exact revision on arXiv

Source-linked AI summary

Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents

Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth O. Stanley, Jeff Clune

arXiv:1712.06560v3cs.AI

TL;DR

Sparse or deceptive rewards make directed exploration important, but how to obtain it with scalable evolution strategies remains unclear. The paper hybridizes ES with novelty search and quality diversity, finding that NS-ES, NSR-ES, and NSRA-ES can avoid local optima and improve performance on challenging RL tasks. The authors also identify behavior characterization and exploration-cost trade-offs as important boundaries for these methods.

  • Problem

    Sparse or deceptive reward functions can trap RL agents in local optima, creating a need for directed exploration that ES does not yet address.

  • Method

    The paper hybridizes ES with novelty search and quality diversity, using populations of agents to scale directed exploration to deep RL.

  • Results

    NS-ES, NSR-ES, and NSRA-ES avoid local optima encountered by ES and achieve higher performance across Atari and deceptive simulated-robot tasks.

  • Takeaways & Limitations

    The methods add holistic, population-based exploration options to the RL toolbox and motivate combinations with other deep-RL algorithms.

  • Takeaways & Limitations

    Novelty-search efficacy depends on the behavior characterization, which can be difficult to specify for complex environments.

Abstract

from arXiv · show

Evolution strategies (ES) are a family of black-box optimization algorithms able to train deep neural networks roughly as well as Q-learning and policy gradient methods on challenging deep reinforcement learning (RL) problems, but are much faster (e.g. hours vs. days) because they parallelize better. However, many RL problems require directed exploration because they have reward functions that are sparse or deceptive (i.e. contain local optima), and it is unknown how to encourage such exploration with ES. Here we show that algorithms that have been invented to promote directed exploration in small-scale evolved neural networks via populations of exploring agents, specifically novelty search (NS) and quality diversity (QD) algorithms, can be hybridized with ES to improve its performance on sparse or deceptive deep RL tasks, while retaining scalability. Our experiments confirm that the resultant new algorithms, NS-ES and two QD algorithms, NSR-ES and NSRA-ES, avoid local optima encountered by ES to achieve higher performance on Atari and simulated robots learning to walk around a deceptive trap. This paper thus introduces a family of fast, scalable algorithms for reinforcement learning that are capable of directed exploration. It also adds this new family of exploration algorithms to the RL toolbox and raises the interesting possibility that analogous algorithms with multiple simultaneous paths of exploration might also combine well with existing RL algorithms outside ES.

1 Introduction

Deep RL can require directed exploration because sparse or deceptive rewards may trap reward-seeking agents in local optima. This paper studies combining novelty search and quality diversity with scalable evolution strategies to address that problem.

  • Motivation: Deceptive or sparse rewards can limit an RL agent’s training data and prevent discovery of higher-payoff strategies.Greedy reward optimization may repeatedly select actions that produce locally rewarding but inferior behavior.
  • Related approaches: Exploration methods for high-dimensional RL commonly encourage visits to rarely observed states or state-action pairs.Approaches include approximate visitation counts, learned dynamics models, and compression-based signals.
  • Novelty and quality diversity: Novelty search and quality diversity instead promote behavioral differences using holistic descriptions of an agent’s lifetime behavior and populations of agents.These methods had previously shown promise mainly with smaller neural networks and low-dimensional inputs and outputs.
  • Evolution strategies: Evolution strategies offer scalable optimization for deep RL because they parallelize effectively across many computers.The paper contrasts this scalability with the need for directed exploration on sparse or deceptive tasks.
  • Contribution: NS-ES, NSR-ES, and NSRA-ES combine novelty-oriented exploration with ES and achieve higher performance while avoiding local optima across simulated robots and Atari games.The study positions these algorithms as scalable additions to the RL exploration toolbox.

2 Background

The paper describes ES as parameter-space black-box optimization using noisy policy evaluations, then motivates novelty search as a complementary way to explore deceptive RL tasks.

  • Evolution strategies: ES evolves neural-network parameter vectors through mutation, optional crossover, fitness evaluation, and selection.Individuals with higher reward tend to produce offspring in subsequent generations.
  • Evolution strategies: The ES variant used here estimates an approximate gradient of expected episode reward from sampled parameter perturbations.It uses static covariance distributions for comparison with prior work.
  • Evolution strategies: Large sample populations reduce the high variance of the gradient estimate, while Gaussian parameter noise samples policies near the current parameters.The perturbation scale σ remains fixed in the evaluated ES variant.
  • Prior performance: Reward-weighted parameter search gives this ES variant performance comparable to contemporary gradient-based methods on simulated locomotion and Atari environments.The comparison is reported for difficult reinforcement-learning domains.
  • Novelty search: Novelty search evaluates behavioral difference from previously generated policies and moves the population toward regions of parameter space with high novelty.It was previously effective on deceptive maze and biped-walking tasks with smaller neural networks.

3 Methods

The proposed methods use ES to optimize novelty, or combinations of novelty and reward, across a population of agents. NSRA-ES further adapts the balance between exploration and performance during training.

  • NS-ES: NS-ES computes an ES gradient of expected novelty conditioned on a shared archive of prior behavior characterizations.The archive is fixed during each iteration and updated afterward, changing the novelty landscape over time.
  • NS-ES: NS-ES maintains a meta-population of M agents, each rewarded for differing from prior agents and their ancestors.This population-based design encourages multiple simultaneous behavioral explorations.
  • NS-ES: At each iteration, NS-ES probabilistically selects an agent for updating according to its novelty relative to the meta-population.The selection probability is novelty normalized by the total novelty across policies.
  • Design boundary: The meta-population is represented as independent Gaussians, while more expressive multimodal sampling distributions remain a future direction.The authors identify the current distributional choice as a simple design for representing multiple agents.
  • NSR-ES: NSR-ES averages rank-normalized reward and novelty signals so agents pursue behaviors that are both high-performing and different from one another.The combined signals are evaluated over complete episodes using the same sampled parameter vectors.
  • NSRA-ES: NSRA-ES dynamically adjusts the performance weight, decreasing it when reward stagnates and increasing it after performance resumes.This design shifts toward novelty when stuck and back toward reward after escaping a local optimum.

4 Experiments

Experiments evaluate NS-ES, NSR-ES, and NSRA-ES on simulated humanoid locomotion and Atari, testing whether novelty-based exploration helps ES avoid deceptive local optima. Across these tasks, combining reward and novelty generally provides the strongest exploration-performance trade-off, while behavior-characterization design remains consequential.

  • Simulated Humanoid Locomotion problem: The experiments test novelty-only, reward-plus-novelty, and adaptive reward-plus-novelty ES variants on humanoid locomotion and Atari control tasks.The humanoid study includes ordinary locomotion and a variant containing a deceptive trap; Atari provides high-dimensional pixel-input benchmarks.
  • Simulated Humanoid Locomotion problem: The humanoid behavior characterization uses the policy’s final {x, y} location, with squared Euclidean distance defining behavioral differences.The modified locomotion reward is isotropic, measuring distance traveled from the origin rather than progress in a fixed direction.
  • Simulated Humanoid Locomotion problem: On ordinary humanoid locomotion, ES achieves higher final reward than NS-ES and NSR-ES, while NSRA-ES performs similarly to ES.NSR-ES learns faster than NS-ES but has similar final performance after 600 generations; the reported ES comparisons with NS-ES and NSR-ES are significant at p < 0.05.
  • Simulated Humanoid Locomotion problem: In the deceptive humanoid task, ES gets stuck in the trap, whereas NSR-ES and NSRA-ES escape it and achieve higher performance than the alternatives.NS-ES avoids the trap but progresses slowly on reward; NSR-ES outperforms NS-ES and ES, while NSRA-ES ultimately exceeds NS-ES and NSR-ES at p < 0.01.
  • Simulated Humanoid Locomotion problem: The meta-population uses M = 5 agents, allowing lineages trapped in the deceptive region to incentivize other policies to explore around it.The algorithms then allocate more computational resources to the newly discovered, more promising strategy through probabilistic selection.
  • Atari: On Atari, NSRA-ES outperforms the other algorithms on 5/12 games, while Noisy DQN and A3C+ do so on 3/12 and 2/12 games, respectively.NSR-ES achieves higher median reward than ES in each of the five games where ES was observed converging to premature local optima; extra exploration can hurt when reward optimization already suffices.
  • Atari: Atari results indicate that novelty search can support directed exploration when behavior characterization is appropriate, while combining novelty with reward performs better on tasks where ES gets stuck.The Atari behavior characterization concatenates RAM states across episode timesteps, and unnormalized behavioral distance biases novelty toward longer trajectories.

5 Discussion and Conclusion

Hybridizing novelty search and quality diversity with ES preserves its scalability while helping avoid local optima in deceptive reinforcement-learning tasks. The paper also identifies adaptive exploration and population-based exploration as directions for broader RL research.

  • Hybridized NS and QD algorithms preserve ES’s scalability while enabling directed exploration in high-dimensional reinforcement-learning environments.The paper presents this as the first attempt to augment ES with directed exploration in high-dimensional environments.
  • The proposed algorithms avoid local optima encountered by ES and achieve higher performance on simulated walking and Atari tasks.
  • NSRA-ES overcomes the Seaquest local optimum by switching the novelty–reward weighting every 10 generations instead of every 50.
  • Holistic behavior descriptions and populations of simultaneously exploring agents provide alternative exploration strategies to per-state bonuses and single-agent exploration.
  • Exploration can reduce performance when unnecessary, motivating adaptive exploration and leaving dynamic exploitation–exploration balancing as an open challenge.NS-ES and NSR-ES perform worse than ES in some non-deceptive domains, while NSRA-ES invests more in exploration only after a performance plateau.

6 Supplementary Information

Population-based exploration can preserve complementary skills and pursue multiple promising behaviors, while novelty methods retain ES scalability. The approach is constrained by the need to choose an informative behavior characterization.

  • 6.2 Population-based exploration vs. single-agent exploration: NS and QD explore through populations that seek different holistic lifetime behaviors rather than counting each state separately.This distinguishes them from state-visitation methods and motivates their use with reinforcement learning.
  • 6.2 Population-based exploration vs. single-agent exploration: The hypothetical maze requires traversing four terrains, each demanding a distinct skill to reach associated rewards.The example illustrates why exploration may require learning multiple skills rather than optimizing one local behavior.
  • 6.2 Population-based exploration vs. single-agent exploration: Single-agent exploration risks catastrophic forgetting, leaving the final agent specialized in one skill while previously learned skills are lost.Learning new skills can rapidly reduce the ability to perform earlier ones.
  • 6.2 Population-based exploration vs. single-agent exploration: A population can learn separate corridor-specific skills in parallel, retaining specialists for distinct tasks and potentially combining them through policy distillation.Population-based exploration also allows different agents to pursue different directions simultaneously.
  • 6.3 Choosing an appropriate behavior characterization: Novelty effectiveness depends on the behavior characterization, whose design can inject domain knowledge but may be difficult in complex environments.The Atari results suggest novelty can still help with reward even when the RAM state is not carefully designed as a behavior characterization.
  • Scalability: NS-ES, NSR-ES, and NSRA-ES retain ES scalability because their optimization process is nearly identical and archive communication adds effectively zero network overhead.Archive novelty computation adds O(Mn) coordinator work, which is reported as insignificant when M is small and fixed.

6.5 NS-ES, NSR-ES, and NSRA-ES Algorithms

NSRA-ES initially follows reward and reduces its reward weighting after stagnation, shifting toward a weighted combination of novelty and reward.

  • 6.5 NS-ES, NSR-ES, and NSRA-ES Algorithms: NSRA-ES starts with w = 1.0, so it initially follows the reward gradient alone.The weighting is adjusted only after performance fails to improve for the specified stagnation interval.
  • 6.5 NS-ES, NSR-ES, and NSRA-ES Algorithms: After 50 generations without increased best episodic reward, NSRA-ES decreases w by 0.05 and follows gradients of a weighted novelty-reward average.The process continues until performance increases, after which w is increased.

6.6 Atari training details

The Atari experiments use fixed ES-style training settings and a compact meta-population, with standard convolutional processing of stacked grayscale frames and randomized no-op starts.

  • 6.6 Atari training details: The Atari policy uses two convolutional layers, a 256-unit fully connected layer, and a linear action-output layer.The convolutional layers use 16 8x8 filters with stride 4 and 32 4x4 filters with stride 2.
  • 6.6 Atari training details: Atari observations are 84x84 grayscale images formed by concatenating four subsequent frames, with actions executed using frameskip 4.Training and evaluation include randomized no-op starts, with up to 30 during training and 1–30 during evaluation.
  • 6.6 Atari training details: All Atari methods use Adam with η = 10^-2 and σ = 0.02, while ES, NS-ES, NSR-ES, and NSRA-ES are trained for the same number of generations per game.The fixed settings are intended to support fair comparison.
  • 6.6 Atari training details: The experiments draw n = 5000 samples per generation and use M = 3 meta-population agents with k = 10 nearest neighbors for novelty computation.The smaller meta-population enables more generations because Atari networks make each generation computationally expensive.

6.7 Humanoid Locomotion problem training details

The humanoid experiments use MuJoCo Humanoid-v1, where reward combines locomotion benefits with standing and energy-related costs, under matched training schedules.

  • 6.7 Humanoid Locomotion problem training details: Humanoid-v1 rewards standing and positive x-direction velocity while penalizing ground-impact energy and energy expenditure.The four components are summed across timesteps to produce total episode reward.
  • 6.7 Humanoid Locomotion problem training details: The humanoid experiments use n = 10000 samples per generation, M = 5 meta-population agents, and k = 10 nearest neighbors.The training hyperparameters were fixed for fair comparison across ES and its exploration variants.
  • 6.7 Humanoid Locomotion problem training details: Training runs last 600 generations for Humanoid Locomotion and 800 generations for Humanoid Locomotion with Deceptive Trap.Both tasks use the same number of generations across the compared algorithms.

6.8 Humanoid Locomotion problem tabular results

Table 2 reports final Humanoid Locomotion results using a robust summary across independent runs and policy evaluations.

  • Final Humanoid Locomotion scores are reported for the compared algorithms.The passage identifies these as final results but does not provide the individual score values.
  • Each algorithm’s score is the median over 10 independent runs.
  • Each run contributes the reward of its highest-scoring policy, averaged over ∼30 evaluations.

6.9 Plots of Atari learning across training (generations)

Figure 5 compares ES, NS-ES, NSR-ES, and NSRA-ES learning across 12 Atari games.

  • The figure compares four algorithms: ES, NS-ES, NSR-ES, and NSRA-ES.
  • The comparison covers learning across 12 Atari games.
  • The plots show how these algorithms learn across the Atari-game benchmark.

6.10 Overhead plots of agent behavior on the Humanoid Locomotion with Deceptive Trap Problem.

Figures 6 and 7 show overhead plots of algorithm behavior across 10 independent runs on Humanoid Locomotion with a deceptive trap.

  • Figure 6 places ES on the left and NS-ES on the right across 10 independent runs.
  • Figure 7 places NSR-ES on the left and NSRA-ES on the right across 10 independent runs.
Loading 1712.06560v3…