Never Give Up: Learning Directed Exploration Strategies

Adrià Puigdomènech Badia, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, Bilal Piot, Steven Kapturowski, Olivier Tieleman, Martín Arjovsky, Alexander Pritzel, Andrew Bolt, Charles Blundell

In the world of Reinforcement Learning (RL), "exploration" is often the difference between an agent that solves a game and one that wanders aimlessly in a corner. While standard agents thrive on "dense" rewards (getting points for every small action), they often fail miserably in "sparse" reward environments like the infamous Atari game Pitfall!, where an agent can travel for minutes without seeing a single point.

The paper "Never Give Up: Learning Directed Exploration Strategies" (NGU), published at ICLR 2020 by researchers at DeepMind, introduces a sophisticated architecture designed to ensure agents never stop searching for the next breakthrough.

TL;DR

NGU is an RL agent that solves hard-exploration problems by decoupling short-term "episodic" curiosity from long-term "life-long" familiarity. By learning a spectrum of policies—from purely exploratory to purely exploitative—within a single neural network, it became the first algorithm to achieve a non-zero score on Pitfall! without using human demonstrations.

The Exploration Problem

Most RL agents use simple exploration strategies like $\epsilon$-greedy (occasionally taking a random action). In games with sparse rewards, this is like trying to find a needle in a haystack by walking in random directions.

More advanced "curiosity-driven" methods provide an intrinsic reward for visiting novel states. However, these suffer from two main issues:

  1. Vanishing Curiosity: Once an agent visits a state, the novelty "wears off." If the agent needs to pass through that state to reach a new area, it might lose the motivation to go back.
  2. The Noisy TV Problem: Agents can get "distracted" by unpredictable parts of the environment they can't control (like a TV showing static), perceiving them as infinitely novel.

Methods

The NGU agent tackles these challenges through three core innovations:

NGU Architecture combining inverse dynamics, episodic novelty, and life-long novelty

1. The Hybrid Intrinsic Reward

The agent's total reward is a combination of the environment's score and an intrinsic bonus. This bonus is the product of two modules:

  • Episodic Novelty Module: Uses an episodic memory (a buffer of states visited in the current episode) and a $k$-nearest neighbors ($k$-NN) lookup. It rewards the agent for visiting states that look different from what it has seen recently. This resets every episode, encouraging the agent to re-explore the map every time.
  • Life-long Novelty Module: Uses Random Network Distillation (RND) to track familiarity across the entire training process. It gradually "down-modulates" the episodic reward for states that have been visited thousands of times across many episodes.

2. Learning Controllable States

To avoid the "Noisy TV" problem, NGU learns a specialized embedding network using an inverse dynamics objective. It trains the network to predict the action taken between two consecutive frames. Because random noise (like the "static" on a TV) cannot be predicted by the agent's actions, the network learns to ignore it, focusing only on "controllable" aspects of the world.

Random Disco Maze and exploration performance showing the agent overcoming visual noise

To test this, the authors used a custom environment called Random Disco Maze, which is filled with irrelevant visual noise. As shown above, the action prediction embedding allows the agent to successfully explore the maze, whereas baseline RND completely fails, getting distracted by the noise.

3. Universal Value Function Approximators (UVFA)

Instead of learning one policy, NGU learns a family of policies simultaneously. The network is conditioned on a parameter $\beta$, which determines the trade-off between exploration and exploitation. This allows the "exploratory" versions of the agent to find new areas, while the "exploitative" versions learn to maximize the actual game score using the data gathered by the explorers.

Key Insights and Results

  • "Never Give Up" is literal: By resetting episodic curiosity every round but keeping a long-term "boredom" filter, the agent is forced to repeatedly traverse known areas to find the "frontier" of its knowledge.
  • The Pitfall! Breakthrough: NGU was the first RL algorithm to achieve a non-zero reward (averaging 8,400) on Pitfall! without using human play data or hand-crafted features.
  • State-of-the-Art on Hard Games: It doubled the performance of previous base agents on the hardest exploration games in the Atari-57 suite.
  • Consistent Performance: Unlike some exploration-heavy agents that struggle on "easy" games, NGU maintained a very high median human-normalized score of 1344.0% across all 57 games.

Limitations and Future Work

The primary drawback of NGU is its sample complexity. Achieving these results required 35 billion frames of experience—equivalent to years of real-time play. The authors also note that the hyperparameter $\beta$ (the exploration weight) is sensitive to the scale of the environment's rewards, suggesting that dynamic adaptation of this parameter is a promising area for future research. Additionally, while the inverse dynamics model handles simple noise, learning "controllable states" in more complex, multi-step environments remains an ongoing challenge.

Summary updated

Abstract

We propose a reinforcement learning agent to solve hard exploration games by learning a range of directed exploratory policies. We construct an episodic memory-based intrinsic reward using k-nearest neighbors over the agent's recent experience to train the directed exploratory policies, thereby encouraging the agent to repeatedly revisit all states in its environment. A self-supervised inverse dynamics model is used to train the embeddings of the nearest neighbour lookup, biasing the novelty signal towards what the agent can control. We employ the framework of Universal Value Function Approximators to simultaneously learn many directed exploration policies with the same neural network, with different trade-offs between exploration and exploitation. By using the same neural network for different degrees of exploration/exploitation, transfer is demonstrated from predominantly exploratory policies yielding effective exploitative policies. The proposed method can be incorporated to run with modern distributed RL agents that collect large amounts of experience from many actors running in parallel on separate environment instances. Our method doubles the performance of the base agent in all hard exploration in the Atari-57 suite while maintaining a very high score across the remaining games, obtaining a median human normalised score of 1344.0%. Notably, the proposed method is the first algorithm to achieve non-zero rewards (with a mean score of 8,400) in the game of Pitfall! without using demonstrations or hand-crafted features.
BibTeX
@inproceedings{badia2020never,
  author = {Adrià Puigdomènech Badia and Pablo Sprechmann and Alex Vitvitskyi and Zhaohan Daniel Guo and Bilal Piot and Steven Kapturowski and Olivier Tieleman and Martín Arjovsky and Alexander Pritzel and Andrew Bolt and Charles Blundell},
  title = {{Never Give Up: Learning Directed Exploration Strategies}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=rlAqTTTJkw0},
}
Figure