Source-linked AI summary
Count-Based Exploration with the Successor Representation
Marlos C. Machado, Marc G. Bellemare, Michael Bowling
TL;DR
The paper tackles inefficient exploration in reinforcement learning, especially when rewards are sparse and random exploration is inadequate. It uses the successor representation and its norm as an exploration bonus, analyzes this behavior with a substochastic successor representation, and extends the approach to deep RL, where it achieves state-of-the-art Atari 2600 performance in a low-sample-complexity regime.
Problem
Reinforcement-learning algorithms often require many interactions, while commonly used uniform random exploration can fail in sparse-reward environments.
Method
The paper uses the successor representation norm as an exploration bonus, introduces the substochastic successor representation to analyze it, and extends the approach to function approximation.
Results
The approach performs as well as some theoretically sample-efficient tabular methods and achieves state-of-the-art performance in Atari 2600 games in a low-sample-complexity regime.
Takeaways & Limitations
The method implicitly counts state or feature visitation, is compatible with representation learning, and can be adapted to large domains.
Takeaways & Limitations
The paper identifies open questions about whether the substochastic successor representation can yield PAC-MDP bounds and how auxiliary tasks affect performance.
Abstract
from arXiv · showhide
In this paper we introduce a simple approach for exploration in reinforcement learning (RL) that allows us to develop theoretically justified algorithms in the tabular case but that is also extendable to settings where function approximation is required. Our approach is based on the successor representation (SR), which was originally introduced as a representation defining state generalization by the similarity of successor states. Here we show that the norm of the SR, while it is being learned, can be used as a reward bonus to incentivize exploration. In order to better understand this transient behavior of the norm of the SR we introduce the substochastic successor representation (SSR) and we show that it implicitly counts the number of times each state (or feature) has been observed. We use this result to introduce an algorithm that performs as well as some theoretically sample-efficient approaches. Finally, we extend these ideas to a deep RL algorithm and show that it achieves state-of-the-art performance in Atari 2600 games when in a low sample-complexity regime.
1 Introduction
The paper addresses exploration in reinforcement learning, where agents must learn effective behavior through trial-and-error interactions while balancing immediate and delayed rewards. It proposes using the successor representation to develop exploration methods for sparse-reward settings and extend them beyond tabular environments.
- Motivation: Exploration seeks to reduce the interactions needed for an initially uninformed agent to learn effective behavior in sequential decision-making tasks.RL agents maximize discounted rewards while actions affect future states and rewards.
- Motivation: Uniformly random exploratory actions remain common, but often fail when rewards are sparse.Sparse-reward environments provide zero reward for most states.
- Approach: The successor representation generalizes between states through similarity in their successor states and can be learned with temporal-difference learning.It can also be viewed as implicitly estimating environmental transition dynamics.
- Contributions: The paper uses the norm of the successor representation as an exploration bonus and introduces the substochastic successor representation to analyze its behavior.The SSR is more amenable to theoretical analysis and implicitly counts state visitation.
- Contributions: The resulting methods target theoretically justified tabular exploration while extending to function approximation and deep reinforcement learning.The paper reports performance comparable to some PAC-MDP approaches in tabular settings and state-of-the-art Atari 2600 performance in a low-sample-complexity regime.
2 Preliminaries
The paper develops reinforcement-learning foundations around value estimation, successor representations, and exploration bonuses. It argues that the learned SR norm can encourage exploration because the SSR implicitly tracks state visitation.
- Value estimation: Model-based RL estimates transition and reward models to compute values, whereas model-free RL estimates values directly from samples, often using TD learning.Large state spaces make accurate model learning difficult, motivating function approximation and neural-network-based model-free methods.
- Successor representation: The successor representation captures expected discounted future state occupancies under a policy and forms part of the value-function solution through vπ = Ψπr.Successor features extend this representation to feature vectors, reducing to the tabular SR when Φ=I.
- SR exploration bonus: The norm of the learned SR acts as an exploration bonus that rewards states visited less often during learning.The approach is evaluated empirically and extended conceptually to function-approximation settings.
- Empirical evaluation: Sarsa+SR obtains an approximate average return of 1.2 million versus approximately 25,000 for Sarsa in the tabular evaluation.The same performance trend is observed in both RIVERSWIM and SIXARMS, where easy-to-reach rewards can trap insufficiently exploratory agents.
- SSR analysis: The substochastic successor representation adds phantom transitions, underestimates the real SR, and permits an analysis showing that its norm implicitly estimates state-visitation counts.The SSR omits bootstrapping from the analysis while approaching the true SR in the limit.
- Empirical evaluation: ESSR performs as well as R-MAX and E3 on RIVERSWIM, outperforms them on SIXARMS, and is outperformed by MBIE in these domains.These comparisons are presented as evidence that the SSR norm is a promising exploration bonus.
4 Counting Feature Activations with the SR
The paper extends SR-based exploration to large, non-tabular environments by learning successor features alongside a deep value function and representation. Its intrinsic reward uses the inverse successor-feature norm, while auxiliary prediction helps avoid a zero-feature solution.
- Directly applying Sarsa+SR is infeasible when enumerating all states is impossible, motivating successor features for function approximation.
- The network combines a DQN-structured value-function component with learned features and successor features.The value-function layers match the architecture used by Oh et al. (2015).
- The feature representation is normalized to have ℓ1-norm 1, and ReLU gates keep its features non-negative.
- Because zero is an SR fixed point under sparse rewards, the method blocks SR-loss gradients into the features and adds next-observation prediction as an auxiliary task.The overall objective combines temporal-difference, SR, and reconstruction losses.
- The intrinsic reward is the inverse ℓ1-norm of the successor-feature vector for the current state.The successor features are parameterized by the target-network parameters θ−.
5 Evaluation of Exploration in Deep RL
The evaluation tests SR-derived exploration bonuses in tabular and deep RL, including Atari games with sparse rewards. The proposed method substantially improves exploration and performs competitively with established baselines, while auxiliary tasks and the exploration bonus both contribute to performance.
- Atari evaluation: The evaluation covers six sparse-reward Atari 2600 games using raw pixels and the reported protocol averages results over 10 seeds after 100 million frames.The games are FREEWAY, GRAVITAR, MONTEZUMA’S REVENGE, PRIVATE EYE, SOLARIS, and VENTURE.
- Overall performance: DQNMMC e +SR outperforms RND at 100 million frames, although RND is considered state of the art when trained for 2 billion frames.The paper also notes that performance at 100 million frames predicts performance at one billion frames for these games.
- Overall performance: DQNMMC e +SR outperforms DQNMMC CTS in five of six games and RND in four of five games, while remaining comparable to DQNMMC PIXELCNN.The comparisons target traditional, density-model, and recent exploration baselines.
- Ablations: The exploration bonus has a major effect in MONTEZUMA’S REVENGE, where architecture changes alone do not improve performance and the bonus appears essential for very sparse rewards.The authors caution that the architecture change and MMC contribution are not fully explainable in other games.
- Ablations: Without the reconstruction auxiliary task, performance in MONTEZUMA’S REVENGE falls to 100 points versus 1395.4 for the full algorithm after 100 million frames.These results suggest that auxiliary tasks are necessary for the method to perform well.
- Norm comparison: Using the ℓ2-norm instead of the ℓ1-norm produces comparable performance in both deep and tabular evaluations.The authors suggest this similarity may indicate that norm-based SR exploration is general across p-norm choices.
6 Related Work
The paper situates its approach between theoretically grounded tabular exploration methods and model-free methods that work in large domains. It emphasizes that SR-based exploration can retain counting-like behavior while remaining compatible with function approximation.
- Tabular and model-free exploration: Tabular model-based exploration algorithms provide regret or sample-complexity guarantees, whereas relatively few model-free approaches have proven sample-complexity bounds.RIVERSWIM and SIXARMS are standard evaluation domains for the tabular algorithms discussed.
- Tabular and model-free exploration: The paper introduces a model-free algorithm that performs well on RIVERSWIM and SIXARMS and a model-based algorithm that performs as well as some theoretically guaranteed methods.The paper identifies R-MAX as the closest comparison for its model-based approach.
- Comparison with R-MAX: Unlike R-MAX, which removes an imaginary-state transition after enough visits, the paper’s method lets that transition probability vanish with additional visitations.Both approaches augment the state space with an imaginary state to encourage visits and reduce uncertainty.
- Large-domain exploration: SR-based exploration at least matches density-model approaches while avoiding a density model and implicitly capturing induced transition dynamics through learned features.The method is presented as compatible with large domains and function approximation.
7 Conclusion
The paper frames poor exploration as a contributor to RL’s high sample complexity and presents its approach as compatible with representation learning and adaptable to large domains. It also identifies several directions requiring further study.
- Conclusion: Poor exploration contributes to RL’s high sample complexity, while uniform random exploration remains common partly because many alternatives rely on domain-specific knowledge.The paper motivates a more general exploration approach for real-world applicability.
- Conclusion: The proposed idea is compatible with representation learning and can be adapted to large domains.This conclusion connects the SR-based bonus to settings requiring function approximation.
- Future work: Future work includes testing whether the SSR can replace explicit visitation counts in algorithms with PAC-MDP bounds and studying how different auxiliary tasks affect performance.The authors also suggest evaluating simpler tasks such as predicting feature activations or input parts.