TL;DR
This paper introduces two novel methods for training deep reinforcement learning agents using evolutionary algorithms, specifically addressing the challenge of deceptive local optima. By leveraging novelty search based on action sequence edit distance and a population resampling strategy, the authors demonstrate a competitive alternative to traditional reward-driven learning, leading to more diverse and potentially more robust policies.
What Problem Does This Paper Address?
Reinforcement learning (RL) agents often struggle with "deceptive local optima," situations where a policy that seems good locally leads to suboptimal overall performance. Traditional reward-maximizing algorithms can get stuck in these traps, failing to explore alternative strategies. While novelty search has been proposed as a solution by rewarding exploration, existing methods often require domain-specific knowledge for defining "novelty." This paper aims to address this by proposing a more general approach to novelty search for deep RL policies, focusing on the sequence of actions an agent takes as a measure of its behavior.
Methods
The authors build upon a "seed-based genetic algorithm" (GA) for training deep RL policy network weights, which is known for its scalability. They introduce two main methods:
- Method I: Novelty Search with Action Sequence Edit Distance: This method replaces the reward signal entirely with a novelty score. The "behavior characteristic" of an agent is defined as the sequence of actions it performs during an episode. The novelty is measured using a modified Levenshtein distance (an edit distance metric for strings) between these action sequences. This allows for a more general and less domain-specific way to quantify behavioral differences.
- Method II: Novelty-Based Population Resampling: This method combines reward-based learning with novelty. It incorporates a "stagnation detection" mechanism that monitors validation scores. If progress stalls, the algorithm resamples individuals from an archive of past behaviors, prioritizing those that are most novel compared to the current population. This aims to break out of local optima without completely abandoning reward optimization.
Datasets
The experiments were conducted using four games from the Atari 2600 benchmark: ASSAULT, ASTEROIDS, MSPACMAN, and SPACE INVADERS. These games were chosen for their variety in gameplay, including one-dimensional and multi-dimensional navigation. The authors used the OpenAI Gym platform for these environments.
Key Insights and Ideas
- Action Sequences as General Behavior Descriptors: Defining an agent's behavior by its action sequence, and measuring novelty with Levenshtein distance, provides a domain-agnostic way to encourage exploration in deep RL.
- Levenshtein Distance vs. Lifespan: The paper demonstrates that using Levenshtein distance as a novelty metric is not equivalent to simply rewarding longer lifespans, suggesting it captures more nuanced behavioral differences.
- Hybrid Approach for Stagnation: Method II shows that combining reward-based selection with novelty-driven population resampling can effectively overcome stagnation and improve performance, especially in challenging games.
- GA Competitiveness: The results further support the idea that genetic algorithms can be competitive with gradient-based methods like DQN for training deep RL policies, particularly when novel exploration strategies are employed.
Key Results
- Method I: While not outperforming the base GA in terms of raw game scores, Method I produced policies with potentially more diverse and "defensive" behaviors, such as increased use of obstacles or longer lifespans in certain games.
- Method II: This method showed improvements over the Base GA in two out of the four tested games, and in some cases, outperformed the original DQN method. It was particularly effective in SPACE INVADERS, where it helped the agent escape local optima that the Base GA seemed to get stuck in.
- Comparison to DQN: Method II performed comparably to or better than DQN in one game, similarly in another, and was outperformed in two games, aligning with previous findings that compare gradient-based and gradient-free methods.
Limitations and Future Work
- Computational Cost: The authors note that computing Levenshtein distance can be computationally expensive, leading them to use a segmented approach to make it practical.
- Method I Performance: Method I, while promoting novelty, did not consistently achieve higher game scores than the base GA.
- DQN Limitations: The authors suggest that the DQN architecture itself, combined with pure reward optimization, might be insufficient for tasks requiring complex strategy shifts (like MSPACMAN's pill-eating mechanic).
- Future Work: The authors plan to extend their methods to include automated network architecture search, combining the open-endedness of evolutionary algorithms with the reliability of functional modules. They also envision applications in areas like autonomous transport where evaluating policies with diverse behaviors is crucial for safety.
Summary updated