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:
- 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.
- 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:
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.
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