Count-Based Exploration with the Successor Representation

By Marlos C. Machado, Marc G. Bellemare, Michael H. Bowling. 2018

210 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Exploration by Random Network Distillation (2018, background): “Since then a number of other works have achieved similar performance (O’Donoghue et al., 2017; Ostrovski et al., 2018; Machado et al., 2018; Osband et al., 2018), without exceeding it.”
Exploration in Deep Reinforcement Learning: A Survey (2022, methodology): “Successor state representation (SSR) [65] is a method which combines count and representation.”
Semantic Exploration from Language Abstractions and Pretrained Representations (2022, background): “Exploration in RL Classical exploration strategies include ✏-greedy action selection [51], statecounting [49, 4, 32, 30, 3], curiosity driven exploration [44], and intrinsic motivation methods [36].”
Improving Intrinsic Exploration with Language Abstractions (2022, background): “Exploration in RL. Exploration has a long history in RL, from " -greedy [48] or count-based exploration [4, 29, 30, 32, 47, 50] to intrinsic motivation [33–35] and curiosity-based learning [42].”
Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning (2022, unknown): “…(Burda et al., 2019), count-based, (Strehl & Littman, 2008; Bellemare et al., 2016; Ostrovski et al., 2017; Martin et al., 2017; Tang et al., 2017; Machado et al., 2020), curiosity-based (Schmidhuber, 1991; 1990), and model-based (Stadie et al., 2015; Pathak et al., 2017; Achiam & Sastry, 2017)…”
Multi-Stage Episodic Control for Strategic Exploration in Text Games (2022, unknown): “Prior work has also explored the addition of curiosity bonuses to encourage exploration (Pathak et al., 2017; Tang et al., 2017; Li et al., 2020; Bellemare et al., 2016; Machado et al., 2020; Taiga et al., 2021).”
On Bonus Based Exploration Methods In The Arcade Learning Environment (2020, methodology): “This bonus may be computed, for example, from approximate counts (Bellemare et al., 2016; Ostrovski et al., 2017; Tang et al., 2017; Machado et al., 2018a), from the prediction error of a dynamics model (ICM, Pathak et al., 2017) or by measuring the discrepancy to a random network (RND, Burda et…”