Source-linked AI summary
Unifying Count-Based Exploration and Intrinsic Motivation
Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, Remi Munos
TL;DR
Non-tabular exploration needs uncertainty estimates that generalize beyond rarely revisited states. The paper derives pseudo-counts from density models, connects them to intrinsic motivation, and reports improved exploration on difficult Atari games, including Montezuma’s Revenge.
Problem
Visit counts are rarely useful in large domains because states are seldom revisited, motivating uncertainty measures that generalize across states.
Method
The paper derives pseudo-counts from arbitrary density models and uses them as intrinsic rewards within count-based exploration algorithms.
Results
The approach improves exploration in difficult Atari 2600 games, with an agent navigating 15 Montezuma’s Revenge rooms within 50 million frames.
Takeaways & Limitations
Pseudo-counts provide a way to generalize count-based exploration to non-tabular settings using density models over observations.
Takeaways & Limitations
The density model and value function may learn at mismatched rates, motivating compatible designs between them.
Abstract
from arXiv · showhide
We consider an agent's uncertainty about its environment and the problem of generalizing this uncertainty across observations. Specifically, we focus on the problem of exploration in non-tabular reinforcement learning. Drawing inspiration from the intrinsic motivation literature, we use density models to measure uncertainty, and propose a novel algorithm for deriving a pseudo-count from an arbitrary density model. This technique enables us to generalize count-based exploration algorithms to the non-tabular case. We apply our ideas to Atari 2600 games, providing sensible pseudo-counts from raw pixels. We transform these pseudo-counts into intrinsic rewards and obtain significantly improved exploration in a number of hard games, including the infamously difficult Montezuma's Revenge.
1 Introduction
The paper addresses the mismatch between theoretically grounded count-based exploration and practical non-tabular reinforcement learning. It connects count-based exploration with intrinsic motivation and introduces pseudo-counts that enable exploration from density models.
- Motivation: Visit counts are ineffective in large domains because states are rarely revisited, while intrinsic motivation remains applicable beyond tabular or Markov settings.Intrinsic motivation typically guides agents using prediction error or learning progress, but its theoretical foundations are limited.
- Contribution: The paper formally relates intrinsic motivation and count-based exploration through information gain and introduces pseudo-counts as the connecting quantity.The pseudo-count links information-gain-as-learning-progress with count-based exploration.
- Contribution: Pseudo-counts are derived from density models rather than transition models, extending count-based exploration to non-tabular observations.The approach is presented as function approximation for exploration and is applied to Atari using intrinsic rewards.
- Results: In Montezuma’s Revenge, the agent explores a significant portion of the first level and achieves substantially higher scores than previously published agents.The paper also reports improved performance in both experience-replay and actor-critic settings.
2 Notation
The notation formalizes sequences of states, density models, empirical distributions, and visit counts. It distinguishes density models that treat states independently from forward models that represent temporal state relationships.
- State-space notation: A sequence x1:n is a finite sequence of states from the countable state space X, with concatenation and the empty sequence denoted explicitly.The model maps finite state sequences to probability distributions over X.
- Empirical counts: The empirical count Nn(x) records how many times state x occurs in the sequence x1:n.The notation extends to state-action counts Nn(x, a).
- Empirical distributions: For an ergodic Markov chain, the empirical distribution’s limit point is the chain’s stationary distribution.A fixed policy in a finite-state MDP provides an example of this setting.
- Density models: A density model assumes states are independently, though not necessarily identically, distributed and therefore differs from a forward model.The empirical distribution µn is itself a density model.
3 From Densities to Counts
The paper derives pseudo-counts from density-model probabilities so uncertainty can generalize across states rather than relying on exact visit recurrences. A FREEWAY example shows that these pseudo-counts capture novelty, frequency structure, growth, and nonstationarity.
- Motivation: Exact visit counts are usually zero for novel states, so the paper derives a generalized count from a density model’s response to observing a state.The pseudo-count is designed to estimate uncertainty across states in practical non-tabular settings.
- Pseudo-count construction: The recoding probability is the density model’s probability for x after observing a new occurrence of x.Its interpretation is tied to statistical compression, where coding costs are inversely related to probabilities.
- Pseudo-count construction: The pseudo-count is obtained by imposing constraints that make the density model’s increased prediction after observing x correspond to a unit count increase.Solving the resulting linear system produces the pseudo-count function and pseudo-count total.
- Properties: When ρn = µn, pseudo-counts equal empirical counts, and when the density model generalizes across states, pseudo-counts generalize across states as well.The construction also recovers the usual pseudo-count for a Dirichlet estimator.
- FREEWAY example: FREEWAY pseudo-counts are roughly zero for novel events, respect state-frequency ordering, grow linearly on average, and remain robust under nonstationary data.The reported values are 10,000-frame averages from a CTS density model applied to pixel-level Atari frames.
- FREEWAY example: These properties support pseudo-counts as a generalized notion of visit counts in non-tabular settings.The CTS model ignores temporal dependencies and is selected partly for its fast learning.
4 The Connection to Intrinsic Motivation
The paper connects pseudo-counts to information gain and prediction gain, showing why pseudo-count bonuses can support more exploratory behavior while retaining count-based theoretical intuition.
- Information gain: Information gain measures novelty through the Kullback-Leibler divergence from a prior distribution to the posterior after observing x.It is commonly used to quantify curiosity and define intrinsic rewards.
- Prediction gain: Prediction gain approximates information gain using the difference between a density model’s recoding log-probability and log-probability of x.It is nonnegative exactly when the density model is learning-positive.
- Theoretical connection: Theorem 1 bounds information gain and prediction gain in terms of the pseudo-count, including IGn(x) ≤ PGn(x) ≤ N̂n(x)^−1.It also gives PGn(x) ≤ N̂n(x)^−1/2.
- Theoretical connection: A bonus proportional to N̂n(x)^−1/2 is at least as exploratory as an information-gain bonus and corresponds to the MBIE-EB form.Because pseudo-counts reduce to empirical counts tabularly, the approach preserves known theoretical guarantees in that setting.
- Implications: Pseudo-counts avoid reliance on a learned forward model, unlike many intrinsic-motivation algorithms.The paper notes that optimality guarantees cannot generally exist for intrinsic-motivation algorithms based on forward models.
5 Asymptotic Analysis
The asymptotic analysis establishes when pseudo-counts derived from density models track empirical visit counts, under assumptions on convergence and learning rates.
- The analysis bounds the approximation error of pseudo-counts from directed graphical models, including the CTS model as a special case.
- Under Assumption 1, the ratio of pseudo-counts to empirical counts has a limit for every state.
- The consistency result requires the density model's relative rate of change to converge, linking its learning dynamics to the pseudo-count ratio.
- For αn = n−1, the density model is the empirical distribution; αn = n−2/3 permits analysis through stochastic approximation.
- Density models that do not satisfy the learning-rate assumption may still yield useful pseudo-counts, but those counts are not comparable to empirical counts.
- If ˆNn is derived from ρn, then ˆNn(x)/Nn(x) →1 for all x with µ(x) > 0.
6 Empirical Evaluation
The empirical evaluation applies CTS-derived exploration bonuses to hard Atari games and to A3C, finding faster exploration and improved performance, especially in Montezuma’s Revenge.
- 6.1 Exploration in Hard Atari 2600 Games: The study uses CTS to generate exploration bonuses for five hard Atari 2600 games where ε-greedy exploration is inefficient.
- 6.1 Exploration in Hard Atari 2600 Games: Count-based bonuses enable quick progress in several games, with the strongest effects reported in MONTEZUMA’S REVENGE and VENTURE.
- 6.1 Exploration in Hard Atari 2600 Games: Within 50 million frames, the Montezuma’s Revenge agent consistently navigates 15 rooms and one run reaches 6600 points by 100 million frames.
- 6.2 Exploration for Actor-Critic Methods: In A3C experiments across 60 Atari games, A3C fails to learn in 15 games, whereas A3C+ fails to improve on random in only 10.
- 6.2 Exploration for Actor-Critic Methods: A3C+ achieves slightly higher median performance and significantly outperforms A3C on at least a quarter of the games.
7 Related Work
Related work connects intrinsic motivation, information-theoretic learning progress, and count-based exploration, while extending theoretical exploration guarantees beyond tabular settings remains recent.
- Compression progress equates novelty with improvement in an agent’s ability to compress its past.
- Information-theoretic analyses relate prediction gain, information gain, and visit counts across intrinsic-motivation and count-based exploration methods.
- Variational intrinsic motivation and squared prediction-error bonuses provide closely related approaches for exploration in Atari 2600 games.
- Theoretical guarantees for exploration in non-tabular, stateful settings have only recently emerged, including PAC-MDP and Thompson-sampling analyses.
8 Future Directions
The paper identifies open questions about how density models generalize across states, align with value functions, and define pseudo-counts in continuous spaces.
- Future Directions: The density model induces a state-space metric, but the paper does not explain where this generalization comes from.
- Future Directions: DQN learns much more slowly than the CTS density model, motivating value functions compatible with density-model learning rates.
- Future Directions: For continuous spaces, pseudo-counts can be defined using probability density functions, but their suitability as counts remains unclear.
- Theoretical Basis: Theoretical bounds relate information gain and prediction gain to pseudo-count bonuses under learning-positive density models.
B Asymptotic Analysis
The asymptotic analysis shows that pseudo-counts recover empirical visit counts under stated convergence and positivity conditions, including for graphical-model density estimators and the CTS model. The experiments use preprocessed Atari frames and evaluate exploration difficulty and progress in Montezuma’s Revenge.
- Directed Graphical Models: Directed graphical models satisfy the required regularity condition, linking their pseudo-counts asymptotically to empirical counts.
- Directed Graphical Models: The CTS density model is an induced graphical model, so the result characterizes how its computed pseudo-counts relate asymptotically to empirical counts.
- Under µ(x) > 0, the pseudo-count ratio ˆNn(x)/Nn(x) converges to 1.
- The convergence result applies when the density model’s auxiliary term grows monotonically but not too quickly and its normalized component converges.
- CTS Density Model: Atari frames are converted to grayscale and downsampled to 42×42, with each pixel modeled as a factor conditioned on selected neighboring pixels.
- Exploration in Montezuma’s Revenge: In Montezuma’s Revenge, the bonus agent had seen 15 rooms after 50 million frames versus two for the no-bonus agent, reaching average scores of 2461 and 3439 at 50 and 100 million frames.
C.4 Improving Exploration for Actor-Critic Methods
The actor-critic experiments add pseudo-count exploration bonuses to A3C and evaluate performance across Atari games under stochastic and deterministic settings. The bonus improves exploration in several difficult games, while outcomes depend strongly on the environment configuration and return-based training.
- DQN achieves 150% or less of random score on 10 games, including Montezuma’s Revenge, Pitfall!, Skiing, and Surround.
- A3C achieves 150% or less of random score on 14 games, including Gravitar, Pitfall!, Skiing, Surround, and Venture.
- A3C+ remains at or below 150% of random score on 10 Atari games, including Gravitar, Pitfall!, Skiing, and Venture.
- Under the stochastic ALE setting without life-loss termination, A3C+ achieves an average Montezuma’s Revenge score of 1127.05 after 200 million frames.
C.5 Comparing Exploration Bonuses
The paper compares prediction gain, count-based bonuses, and no bonus across Atari games using normalized inter-algorithm score distributions. Prediction gain is initially strong, while the pseudo-count bonus becomes superior later in training.
- The inter-algorithm score distribution normalizes each game from worst performance at 0 to best performance at 1, with higher curves indicating better scores.
- The scale parameter β is optimized separately for each exploration-bonus variant at β = 0.01.
- By 200 million frames, the ˆN^-1/2 exploration bonus outperforms both prediction gain and no bonus.
- By 50 million frames, prediction gain, the count-based variant, and no bonus perform equally well.
- Prediction gain initially achieves strong performance but yields a decent rather than top-performing score across all games.