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 (UVFA) 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.
Introduction
In Reinforcement Learning (RL), agents typically learn through trial and error. While this works well in "dense reward" environments like Pong, it fails in "sparse reward" environments such as Montezuma’s Revenge or Pitfall!, where an agent might wander for thousands of steps without receiving any feedback. Standard exploration strategies, such as $\epsilon$-greedy, are often no better than a "drunkard’s walk," proving highly inefficient in large state spaces.
Existing "intrinsic motivation" methods reward agents for finding novel states, but they face two major hurdles:
- Vanishing Novelty: Once a state is visited, its novelty reward disappears. This can lead to "detachment," where an agent loses the incentive to return to a room it must pass through to reach deeper, undiscovered areas.
- The Noisy TV Problem: Agents can become obsessed with unpredictable environmental noise (like a TV showing static) because it always appears "novel," even if the agent cannot influence it.
The NGU Framework
The "Never Give Up" (NGU) agent addresses these issues by maintaining exploration throughout the entire training process using a sophisticated reward and architecture framework.
1. The Two-Part Intrinsic Reward
NGU calculates an intrinsic reward $r_t^i$ by multiplying two distinct signals:
- Episodic Novelty (Short-term): The agent maintains a memory of states visited within the current episode. Using a $k$-nearest neighbors (k-NN) lookup, it rewards the agent for visiting states that differ from its recent experience. To solve the "Noisy TV" problem, states are embedded into a lower-dimensional space using an inverse dynamics model, which only captures features the agent can actually influence.
- Life-long Novelty (Long-term): Utilizing Random Network Distillation (RND), NGU tracks how often a state has been seen across the entire training process. This signal scales down the episodic reward for states that have become globally "boring," forcing the agent to seek out entirely new regions.
2. Universal Value Function Approximators (UVFA)
Instead of a single policy, NGU learns a family of $N$ policies simultaneously using a single neural network. These range from "pure exploiters" (focusing only on game score) to "pure explorers" (focusing only on novelty). By sharing weights, exploratory policies act as scouts, and as they find extrinsic rewards, that value propagates to the exploitative policies via internal transfer.
Experimental Setup and Results
The primary benchmark for NGU is the Atari-57 suite, with a focus on the "Hard Exploration" subset (e.g., Montezuma’s Revenge, Pitfall!, Solaris). To specifically test the agent's resilience to noise, the authors used a Random Disco Maze—a gridworld with randomly changing wall colors.
Key Insights
- Controllability as a Filter: By training the state embedding to predict the action taken between two frames, the agent learns to ignore everything it cannot control. If the agent cannot change the "static" on a TV, that static is not represented in the embedding and does not trigger a reward.
- The Pitfall! Milestone: NGU is the first RL agent to achieve a non-zero score (mean of 8,400) on Pitfall! without human demonstrations or hand-crafted features.
- Broad Competence: Across all 57 Atari games, NGU achieved a median human-normalized score of 1344%, reaching superhuman performance on 51 of the 57 games.
Limitations and Future Work
Despite its success, NGU requires significant compute resources and billions of frames to reach peak performance. The inverse dynamics model currently only looks one step ahead; environments with very delayed consequences might require more sophisticated representations. Future work may explore dynamic adaptation of the exploration-exploitation balance (e.g., via Population Based Training) to improve efficiency.
Summary updated