PaperlayerView exact revision on arXiv

Source-linked AI summary

Never Give Up: Learning Directed Exploration Strategies

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

arXiv:2002.06038v1cs.LGstat.ML

TL;DR

Hard exploration in sparse-reward reinforcement learning remains difficult because novelty bonuses can vanish after states become familiar, limiting useful revisitation. The paper combines controllable-state novelty with UVFA-conditioned exploratory and exploitative policies sharing one network. It reports strong performance across Atari hard-exploration games, including non-zero Pitfall! rewards without demonstrations or hand-crafted features.

  • Problem

    Sparse-reward exploration can fail when agents stop gathering the experience needed to learn, while conventional novelty rewards do not encourage revisiting familiar states.

  • Method

    The method combines episodic k-nearest-neighbor novelty over inverse-dynamics embeddings with life-long modulation and UVFA-conditioned policies sharing network weights.

  • Results

    The method achieves high scores across Atari hard-exploration games and non-zero rewards on Pitfall! without human demonstrations or hand-crafted features.

  • Takeaways & Limitations

    Shared exploratory and exploitative policies maintain exploration throughout training while allowing the exploitative policy to focus on extrinsic reward.

  • Takeaways & Limitations

    The method has high sample complexity, consuming large amounts of simulated experience over several days of wall-clock time, and controllable-state novelty may not suit every environment.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper addresses exploration failure in sparse-reward deep reinforcement learning by combining persistent novelty with jointly learned exploratory and exploitative policies. Its approach uses shared weights and UVFA conditioning to maintain exploration while supporting task-focused behavior.

  • Motivation: Sparse-reward exploration can fail when agents become greedy before collecting the data needed to learn optimal behavior.Simple stochastic strategies are inefficient in large state spaces and may require exponentially many steps.
  • Motivation: Intrinsic rewards encourage exploration through state novelty, but standard bonuses disappear after states become familiar and do not encourage revisitation.This limits exploration of familiar states that may provide downstream learning opportunities.
  • Approach: NGU jointly learns exploration and exploitation policies from the same network, varying their trade-off through UVFA conditioning.Exploratory policies maintain directed exploration while the exploitative policy focuses on extrinsic reward.
  • Approach: The intrinsic reward combines episodic and life-long novelty to encourage repeated visits to controllable states throughout training.Episodic novelty supports revisitation across episodes, while life-long novelty down-modulates increasingly familiar states.
  • Contributions: The paper reports scalability and performance on par with or better than state-of-the-art methods on hard exploration tasks.The contributions include a shared conditional architecture that separates exploration and exploitation.

2 THE NEVER-GIVE-UP INTRINSIC REWARD

The never-give-up intrinsic reward combines episodic and life-long novelty while representing observations through controllable-state embeddings. Episodic memory and similarity-based pseudo-counts promote broad within-episode exploration, while long-term modulation preserves exploration across episodes.

  • Reward construction: The augmented reward combines extrinsic reward with an intrinsic reward weighted by β.Agents train on the augmented reward while performance is measured using extrinsic reward.
  • Reward properties: The intrinsic reward is designed to rapidly discourage within-episode revisits, slowly discourage cross-episode familiarity, and ignore uncontrollable variation.These properties combine episodic and life-long novelty around controllable states.
  • Episodic novelty: Episodic novelty stores controllable-state embeddings from the current episode and assigns larger bonuses to observations more different from memory contents.It promotes visiting many different states within one episode without using inter-episode history for that module.
  • Life-long novelty: Life-long novelty modulates episodic novelty across episodes, using RND as a long-term novelty estimator and gradually reducing the modulation over time.The combined design retains episodic exploration while incorporating longer-term familiarity.
  • Controllable-state embedding: A self-supervised inverse dynamics model trains embeddings to emphasize environmental variation influenced by the agent’s actions.This reduces intrinsic rewards for changes that are unrelated to meaningful agent-controlled exploration.
  • Episodic novelty: Pseudo-counts estimate visits to an embedded state by summing kernel similarities over its k-nearest neighbors in episodic memory.The additive constant c ensures a minimum pseudo-count, while the inverse kernel provides generalization in large state spaces.
  • Implementation: The kernel’s running distance normalization improves robustness across tasks with different typical distances between learned embeddings.The experiments fix ϵ to 10^-3 and the maximum reward scaling L to 5.

3 THE NEVER-GIVE-UP AGENT

The never-give-up agent integrates intrinsic rewards into a recurrent, distributed value-learning system that represents multiple exploration–exploitation trade-offs. UVFA conditioning enables an explicitly exploitative policy alongside exploratory policies sharing network parameters.

  • Agent design: The agent maintains multiple value functions with different exploration–exploitation trade-offs and incorporates the intrinsic reward into each policy.This extends the episodic reward mechanism into a full agent with a collection of conditioned value functions.
  • Agent design: Intrinsic rewards can make the process partially observed when they vary unpredictably, so the agent receives them as inputs and maintains recurrent history state.The implementation uses R2D2, combining recurrence, replay, off-policy value learning, and distributed training.
  • Conditional policies: Exploratory and exploitative policies are learned jointly because the never-give-up intrinsic reward does not vanish and cannot be easily turned off in a single policy.The explicit exploitative policy is driven only by the task’s extrinsic reward.
  • Conditional policies: The UVFA Q(x, a, β_i) approximates value functions for augmented rewards with different intrinsic-reward weights, including β_0 = 0.Greedy action selection with β_0 = 0 turns off exploratory behavior.
  • Conditional policies: Shared weights allow exploratory policies to build representations and skills that can transfer to the exploitative policy before extrinsic rewards are observed.The architecture encodes the selected intrinsic-reward weighting as a policy condition.
  • Training: Distributed training collects experience from many actors running in parallel, matching the agent’s use of recurrent replay and off-policy learning.Different discount factors are associated with different exploration weights, with the exploitative policy using the highest discount factor.

4 EXPERIMENTS

Experiments evaluate NGU in a controllable-state maze and Atari, examining exploration representations, mixture settings, and performance on hard-exploration and dense-reward games. The results show strong hard-exploration performance, broad Atari performance, and remaining interference from shared representations on some dense-reward games.

  • Experimental setup: NGU is evaluated first in Random Disco Maze, then against baselines on Atari’s hard-exploration and dense-reward games.The experiments also analyze architecture choices, hyperparameters, and multiple policy mixtures.
  • Random Disco Maze: The Random Disco Maze study compares random projections, learned controllable states, and a baseline RND implementation.The maze uses randomly generated 21x21 layouts, with changing wall colors at every time step.
  • Hard exploration games: NGU achieves similar or higher average return than state-of-the-art baselines on all six hard-exploration games.NGU(N = 1)-RND obtains a best Pitfall! score of 15,200, described as the first positive score without privileged information.
  • Hard exploration games: NGU(N = 32) improves over NGU(N = 1) in 4 of 6 hard-exploration games while using shared weights across intrinsically conditioned mixtures.The exploitative policy leverages these shared weights while optimizing final episode score.
  • Dense reward games: On dense-reward games, NGU(N = 1) underperforms R2D2 on most games, whereas NGU(N = 32) reliably learns to play Pong.NGU(N = 32) nevertheless does not match R2D2 on Breakout and Beam Rider, suggesting interference from shared intrinsic-signal representations.
  • Atari-57 results: NGU achieves a 1354.4% overall median score on Atari-57, above human level on 51 of 57 games but below R2D2’s 1920.6%.The reported comparison also includes 95% for Nature DQN, 191.8% for IMPALA, and 1451.8% for R2D2 using retrace loss.

5 CONCLUSIONS

The agent maintains exploration throughout training by combining exploratory and exploitative policies, achieving strong Atari hard-exploration performance while using distributed experience collection. The approach remains bounded by high sample complexity, controllable-state assumptions, shared-policy compatibility, and reward-scale dependence.

  • The agent achieves high scores across Atari hard-exploration games while maintaining a very high average score across Atari-57.
  • A shared-parameter policy family separates exploration from exploitation, allowing exploratory behavior to persist throughout training.
  • In the absence of extrinsic rewards, the method traverses controllable states in a depth-first manner.
  • Distributed actors provide strong performance but incur high sample complexity and several days of wall-clock training.
  • The controllable-state signal may fail when action consequences require more than two consecutive steps to appear.
  • Shared parameterization can be limiting when exploratory and exploitative policies are nearly adversarial, as in Surround and Ice hockey.
  • The exploration weight β depends on extrinsic-reward scale, so environments with substantially different scales may require different β values.

A EVALUATION SETUP

The evaluation setup uses distributed actors, replayed fixed-length sequences, recurrent Q-learning, and auxiliary intrinsic-reward models. Actors receive different exploration conditions, while training computes reinforcement-learning and auxiliary losses from sampled sequences.

  • Distributed evaluation: Actors, evaluators, and a learner interact with separate environment instances, with the evaluator sharing weights with actors and learners.
  • Replay and learning: Training samples augmented rewards, intrinsic rewards, observations, actions, and discounts from replayed sequences.
  • Replay and learning: The Q-network learns from replayed observations and actions using the R2D2 retrace procedure.
  • Auxiliary objectives: The action-prediction and optional RND losses use only the final 5 frames of each sampled sequence.
  • Policy mixtures: Each actor is assigned a fixed β_i and acts with an ε-greedy version of its corresponding policy.
  • Policy mixtures: The β_i schedule emphasizes the fully exploitative and very exploratory policies among the mixture.
  • Replay and learning: Sequences contain 80 timesteps, overlap adjacent samples by 40 timesteps, and never cross episode boundaries.
  • Discounting: Discount factors are spaced in log-space, with the exploitative policy receiving the highest discount and the most exploratory policy the smallest.

B ABLATIONS FOR NGU(N=1)

The NGU(N=1) ablations examine controllable-state size, nearest-neighbor count, and clipping-factor choices on Pitfall! and Montezuma’s Revenge. Results show substantial game-dependent sensitivity, especially on Montezuma’s Revenge, while Pitfall! is generally more robust.

  • Scope: NGU(N=1) lacks a pure exploitative mode and therefore performs poorly in dense-reward games.The ablation analysis consequently focuses on the sparse-reward games Montezuma’s Revenge and Pitfall!.
  • B.1 SIZE OF CONTROLLABLE STATES: Controllable-state size has little effect on Pitfall!, where scores sometimes exceed 25,000 points.On Montezuma’s Revenge, size 32 is consistently better than 64, while size 16 is less stable despite sometimes solving the level.
  • B.2 NEAREST NEIGHBORS USED: Using more nearest neighbors produces slight gains on Pitfall!, whereas 10 neighbors clearly outperform 5 or 30 on Montezuma’s Revenge.
  • B.3 CLIPPING FACTOR: Pitfall! is robust to the clipping factor, with marginally worse performance at L = 10.The passage attributes this to RND generally harming NGU performance on Pitfall!.
  • B.3 CLIPPING FACTOR: The highest clipping-factor value performs best on Montezuma’s Revenge.

C.1 GENERAL ABLATIONS

General ablations evaluate mixture count, cross-mixture experience sharing, and exploration weighting across dense- and hard-exploration Atari games. Increasing mixture count generally helps hard exploration, while performance effects vary by game and mixture.

  • Exploration weighting: β = 0.2 and β = 0.5 outperform RND, R2D2, R2D2(Retrace), and R2D2+RND on Pitfall! and Private Eye individually.Despite lower averages on the three hard-exploration games, these mixtures perform strongly on those individual games.
  • Game-specific behavior: On Breakout, a high score is achieved without extrinsic reward because the exploratory policy learns to survive.

C.2 FURTHER ABLATIONS ON HARD EXPLORATION

Further ablations compare exploration-mixture weights and computational considerations, while documenting evaluation and implementation details. Results vary across games, and distributed computation is difficult to compare directly because actor count affects data volume and off-policy character.

  • Further mixture ablations: β = 0.2 and β = 0.5 perform slightly better than β = 0.3 on all three evaluated games.The maximum difference between β = 0.3 and β = 0.2 is 1.5k points on Solaris.
  • Further mixture ablations: The evaluated policies on these three games appear to focus more on exploitation than extended environmental exploration.The passage presents this as a hypothesis based on the games’ relative performance patterns.
  • Computational comparison: Computation remains difficult to compare across algorithms because distributed actor counts affect both learner data volume and the data’s off-policy character.In R2D2, more actors can make replayed learner data more recent.
  • Hyperparameter selection: Hyperparameters for NGU(N = 32) were selected through a grid search using three seeds on eight Atari games.Kernel epsilon and nearest-neighbor ranges were fixed after initial Atari experiments.
  • Baseline selection: The R2D2+RND baseline used a sweep over β values 0.1, 0.3, and 0.5, with β = 0.3 selected as best.

G DETAILED ATARI RESULTS

Figure 14 compares R2D2(Retrace) with NGU(N=32) under two evaluation exploration weights. The comparison focuses on how evaluation conditioning changes the resulting policy behavior.

  • Figure 14: Figure 14 compares R2D2(Retrace) with NGU(N=32) evaluated at β = 0.0 and β = 0.3.

H.1 ARCHITECTURE OF THE EMBEDDING NETWORK WITH INVERSE DYNAMICS PREDICTION

This section presents the embedding, RND, and R2D2 architectures, and evaluates learned controllable states using Montezuma’s Revenge as a case study.

  • The embedding network architecture is documented in Figure 15.
  • The RND network architecture is documented in Figure 16.
  • The R2D2 agent architecture is documented in Figure 17.
  • Montezuma’s Revenge is used to evaluate learned controllable states and oracle controllable states containing only necessary information.

I.1 INSPECTING THE PROPERTIES OF LEARNED CONTROLLABLE STATES

The learned controllable state is trained through inverse dynamics and retains information useful for predicting player position and room identity, while better representations remain a future-work direction.

  • The embedding network is trained with an inverse dynamics model so controllable states retain information relevant to the agent’s action.Other information may remain if a simple classifier can ignore it.
  • Position-prediction error stabilises near 12 units, below 10% of the observed coordinate range, without increasing when new rooms are discovered.
  • Room prediction error stabilises slightly above 20%, compared with 96% random chance.
  • The results motivate future work on alternative controllable-state learning methods that retain more relevant information.

I.2 MONTEZUMA’S REVENGE WITH HAND-CRAFTED CONTROLLABLE STATES

Hand-crafted controllable states and meta-episodes help the agent explore Montezuma’s Revenge, including environments with irreversible choices and delayed key–door consequences.

  • Meta-episodes let episodic exploration handle irreversible choices by trying alternatives across multiple episodes before wiping memory.The comparison concerns detachment and the limitations of resetting episodic memory after every episode.
  • Long-term novelty produces close to 15,000 average return while visiting an average of 25 rooms per episode.Three of five seeds reach the second level, and one reaches the third level.
  • Without extrinsic guidance, the agent consistently reaches a large number of rooms and explores more than 20 rooms.
  • When keys are represented in the controllable state, the agent selects different key–door combinations across three episodes without wiping episodic memory.
  • At training’s end, the first post-reset episode scores 14,660 ± 196, while the third scores 34,040 ± 9,835 and averages over 30 rooms.
  • The reported gains support improving controllable-state representations as a direction for future work.
Loading 2002.06038v1…