Count-based exploration with the successor representation
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Machado et al. (2020) showed that the L1-norm of SFs is proportional to visitation count, and can therefore be used as an exploration bonus.
“Machado et al. (2020) showed that that the L1-norm of SFs is proportional to visitation count, and can therefore be used as an exploration bonus:”
From Predictive Representations: Building Blocks of Intelligence (2024) · cites this paper as Machado et al., 2020
Section 3 reports that the learned successor representation’s L1 norm increases with state visits and motivates using its inverse as an exploration bonus. Section 4 extends that bonus to successor features. The paper does not show that the L1 norm of successor features is proportional to visitation count; its count-related theorem concerns a modified successor representation, and the reported relationship for the ordinary representation is empirical rather than proportional. (LLM, conf=0.87)
Experimental — accuracy not yet measuredPOMDPs introduce challenges related to accurate estimation of the environment state, and higher-quality representations can lead to better exploration.
“POMDPs introduce another layer of challenges related to accurate estimation of the environment state—higher-quality representations can lead to better exploration [209,210].”
From Data-Driven Robotic Manipulation of Cloth-like Deformable Objects: The Present, Challenges and Future Prospects (2023) · cites this paper as [210]
The Conclusion states that better representations can lead to faster exploration. The paper’s Preliminaries discuss difficulty learning accurate models in large state spaces, but the passages do not address POMDPs or the challenge of accurately estimating an environment’s state under partial observability. (LLM, conf=0.88)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Human-level control through deep reinforcement learning
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015) · Nature · doi:10.1038/nature14236 · Cited by 30,357 · see citing works
Self-citationReinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225 · see citing works
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. (2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 25,263 · see citing works
Bellman, R. E. (2010) · doi:10.1515/9781400835386 · Cited by 14,588 · see citing works
(2010) · Cited by 14,134 · see citing works
Markov Chains and Stochastic Stability
Meyn, S., & Tweedie, R. L. (1993) · Springer eBooks · doi:10.1007/978-1-4471-3267-7 · Cited by 5,189 · see citing works
Learning to predict by the methods of temporal differences
Sutton, R. S. (1988) · Machine Learning · doi:10.1007/bf00115009 · Cited by 5,148 · see citing works
The Arcade Learning Environment: An Evaluation Platform for General Agents
Bellemare, M. G., Naddaf, Y., Veness, J., & Bowling, M. (2013) · Journal of Artificial Intelligence Research · doi:10.1613/jair.3912 · Cited by 2,161 · see citing works
Self-citationMarkov Chains and Stochastic Stability
Meyn, S., Tweedie, R. L., & Glynn, P. W. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511626630 · Cited by 1,688 · see citing works
Temporal difference learning and TD-Gammon
Tesauro, G. (1995) · Communications of the ACM · doi:10.1145/203330.203343 · Cited by 1,618 · see citing works
On-line Q-learning Using Connectionist Systems
Rummery, G. A. (1994) · Cited by 1,475 · see citing works
Reinforcement Learning with Unsupervised Auxiliary TasksPreprint
Jaderberg, M., Mnih, V., Czarnecki, W. M., Schaul, T., Leibo, J. Z., Silver, D., & Kavukcuoglu, K. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.05397 · Cited by 826 · see citing works
Near-Optimal Reinforcement Learning in Polynomial Time
Kearns, M. J., & Singh, S. P. (2002) · Machine Learning · doi:10.1023/a:1017984413808 · Cited by 795 · see citing works
(2016) · neural information processing systems · Cited by 735 · see citing works
Self-citationImproving generalization for temporal difference learning: The successor representation
Dayan, P. (1993) · Neural Computation · doi:10.1162/neco.1993.5.4.613 · Cited by 693 · see citing works
Exploration by Random Network Distillation
Burda, Y., Edwards, H., Storkey, A., & Klimov, O. (2018) · arXiv · doi:10.48550/arxiv.1810.12894 · Cited by 527 · see citing works
Seeger, M. (2000) · Applied Physics Letters · doi:10.1162/153244303765208377 · Cited by 492 · see citing works
Action-Conditional Video Prediction using Deep Networks in Atari GamesPreprint
Oh, J., Guo, X., Lee, H., Lewis, R. L., & Singh, S. P. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.08750 · Cited by 473 · see citing works
An analysis of model-based Interval Estimation for Markov Decision Processes
Strehl, A. L., & Littman, M. L. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.08.009 · Cited by 428 · see citing works
Parameter Space Noise for ExplorationPreprint
Plappert, M., Houthooft, R., Dhariwal, P., Sidor, S., Chen, R. Y., Chen, X., Asfour, T., Abbeel, P., & Andrychowicz, M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.01905 · Cited by 423 · see citing works
PAC model-free reinforcement learning
Strehl, A. L., Li, L. C., Wiewiora, E., Langford, J. C., & Littman, M. L. (2006) · International Conference on Machine Learning · doi:10.1145/1143844.1143955 · Cited by 391 · see citing works
Count-Based Exploration with Neural Density Models
Ostrovski, G., Bellemare, M. G., Oord, A. V. D., & Munos, R. (2017) · arXiv · doi:10.48550/arxiv.1703.01310 · Cited by 377 · see citing works
Self-citationR-MAX: a general polynomial time algorithm for near-optimal reinforcement learning
Brafman, R. I., & Tennenholtz, M. (2001) · Cited by 366 · see citing works
Machado, M. C., Bellemare, M. G., Talvitie, E., Veness, J., Hausknecht, M., & Bowling, M. (2018) · Journal of Artificial Intelligence Research · doi:10.1613/jair.5699 · Cited by 359 · see citing works
Self-citationSuccessor Features for Transfer in Reinforcement LearningPreprint
Barreto, A. D. M. S., Dabney, W., Munos, R., Hunt, J. J., Schaul, T., Silver, D., & van Hasselt, H. P. (2016) · arXiv (Cornell University) · doi:10.13140/rg.2.2.35439.18085 · Cited by 349 · see citing works
Unifying Count-Based Exploration and Intrinsic Motivation
Bellemare, M. G., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., & Munos, R. (2016) · arXiv · doi:10.48550/arxiv.1606.01868 · Cited by 264 · see citing works
Self-citationAction-conditional video prediction using deep networks in Atari games
Oh, J., Guo, X., Lee, H., Lewis, R. L., & Singh, S. P. (2015) · Cited by 196 · see citing works
The Arcade Learning Environment: An Evaluation Platform for General Agents
Bellemare, M. G., Naddaf, Y., Veness, J., & Bowling, M. (2012) · arXiv · doi:10.48550/arxiv.1207.4708 · Cited by 187 · see citing works
Self-citationSuccessor Features for Transfer in Reinforcement LearningPreprint
Barreto, A., Dabney, W., Munos, R., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.05312 · Cited by 175 · see citing works
Generalization and Exploration via Randomized Value FunctionsPreprint
Osband, I., Roy, B. V., & Wen, Z. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.0635 · Cited by 169 · see citing works
Contextual Decision Processes with low Bellman rank are PAC-Learnable
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., & Schapire, R. E. (2016) · arXiv · doi:10.48550/arxiv.1610.09512 · Cited by 144 · see citing works
Deep Successor Reinforcement LearningPreprint
Kulkarni, T. D., Saeedi, A., Gautam, S., & Gershman, S. J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.02396 · Cited by 120 · see citing works
Finite Sample Analyses for TD(0) With Function Approximation
Dalal, G., Szörényi, B., Thoppe, G., & Mannor, S. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.12079 · Cited by 101 · see citing works
Count-Based Exploration in Feature Space for Reinforcement Learning
Martin, J., Sasikumar, S. N., Everitt, T., & Hütter, M. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/344 · Cited by 87 · see citing works
Parameter Space Noise for Exploration
Plappert, M., Houthooft, R., Dhariwal, P., Sidor, S., Chen, R. Y., Chen, X., Asfour, T., Abbeel, P., & Andrychowicz, M. (2018) · International Conference on Learning Representations · Cited by 78 · see citing works
Eigenoption Discovery through the Deep Successor RepresentationPreprint
Machado, M. C., Rosenbaum, C., Guo, X., Liu, M., Tesauro, G. J., & Campbell, M. S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.11089 · Cited by 71 · see citing works
Self-citationThe Laplacian in RL: Learning Representations with Efficient ApproximationsPreprint
Wu, Y., Tucker, G., & Nachum, O. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.04586 · Cited by 29 · see citing works
Benchmarking Bonus-Based Exploration Methods on the Arcade Learning EnvironmentPreprint
Taïga, A. A., Fedus, W., Machado, M. C., Courville, A. C., & Bellemare, M. G. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.02388 · Cited by 20 · see citing works
Self-citation
Flagged first, then by citations
1 of the 39 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Exploration in deep reinforcement learning: A survey
Ladosz, P., Weng, L., Kim, M., & Oh, H. (2022) · Information Fusion · doi:10.1016/j.inffus.2022.03.003 · Cited by 525 · see citing works
Exploration by Random Network Distillation
Burda, Y., Edwards, H., Storkey, A., & Klimov, O. (2018) · arXiv · doi:10.48550/arxiv.1810.12894 · Cited by 527 · see citing works
Wu, J., Huang, Z., Hu, Z., & Lv, C. (2023) · Engineering · doi:10.1016/j.eng.2022.05.017 · Cited by 205 · see citing works
Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain
Hao, J., Yang, T., Tang, H., Bai, C., Liu, J., Meng, Z., Liu, P., & Wang, Z. (2021) · arXiv · doi:10.48550/arxiv.2109.06668 · Cited by 192
Learning structures: Predictive representations, replay, and generalization
Momennejad, I. (2020) · Current Opinion in Behavioral Sciences · doi:10.1016/j.cobeha.2020.02.017 · Cited by 159 · see citing works
An Information-Theoretic Perspective on Intrinsic Motivation in Reinforcement Learning: A Survey
Aubret, A., Matignon, L., & Hassas, S. (2023) · Entropy · doi:10.3390/e25020327 · Cited by 52 · see citing works
Lee, G. T., & Kim, C. O. (2020) · IEEE Access · doi:10.1109/access.2020.3046284 · Cited by 34 · see citing works
Fast and slow curiosity for high-level exploration in reinforcement learning
Bougie, N., & Ichise, R. (2020) · Applied Intelligence · doi:10.1007/s10489-020-01849-3 · Cited by 33 · see citing works
Human-in-the-Loop Deep Reinforcement Learning with Application to Autonomous DrivingPreprint
Wu, J., Huang, Z., Huang, C., Hu, Z., Hang, P., Xing, Y., & Lv, C. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.07246 · Cited by 29 · see citing works
Model primitives for hierarchical lifelong reinforcement learning
Wu, B., Gupta, J. K., & Kochenderfer, M. J. (2020) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-020-09451-0 · Cited by 24 · see citing works
Self-Attention-Based Temporary Curiosity in Reinforcement Learning Exploration
Hu, H., Song, S., & Huang, G. M. (2019) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2019.2957051 · Cited by 21 · see citing works
Kadi, H. A., & Terzić, K. (2023) · Sensors · doi:10.3390/s23052389 · Cited by 19 · see citing works
“POMDPs introduce another layer of challenges related to accurate estimation of the environment state—higher-quality representations can lead to better exploration [209,210].”
BackgroundPredictive Representations: Building Blocks of Intelligence
Carvalho, W., Tomov, M. S., de Cothi, W., Barry, C., & Gershman, S. J. (2024) · Neural Computation · doi:10.1162/neco_a_01705 · Cited by 15 · see citing works
FoX: Formation-Aware Exploration in Multi-Agent Reinforcement Learning
Jo, Y., Lee, S., Yeom, J., & Han, S. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i12.29196 · Cited by 12 · see citing works
Hierarchical learning from human preferences and curiosity
Bougie, N., & Ichise, R. (2021) · Applied Intelligence · doi:10.1007/s10489-021-02726-3 · Cited by 10 · see citing works
Zhou, F., Zhu, Z., Kuang, Q., & Zhang, L. (2021) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2021/476 · Cited by 9 · see citing works
Pecháč, M., Chovanec, M., & Farkaš, I. (2024) · Neurocomputing · doi:10.1016/j.neucom.2024.128033 · Cited by 8 · see citing works
Towered Actor Critic For Handling Multiple Action Types In Reinforcement Learning For Drug Discovery
Gottipati, S. K., Pathak, Y., Sattarov, B., Sahir, Nuttall, R., Amini, M., Taylor, M. E., & Chandar, S. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i1.16087 · Cited by 6 · see citing works
A Hybrid and Hierarchical Approach for Spatial Exploration in Dynamic Environments
Zhang, Q., Song, Y., Jiao, P., & Hu, Y. (2022) · Electronics · doi:10.3390/electronics11040574 · Cited by 4 · see citing works
Exploration-Driven Generative Interactive Environments
Savov, N., Kazemi, N., Mahdi, M., Paudel, D. P., Wang, X., & Van Gool, L. (2025) · 2025 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr52734.2025.02570 · Cited by 2 · see citing works
“Recent exploration methods emphasize state novelty [3, 7, 11, 35, 36, 45, 55, 67], focusing on encouraging agents to assess novelty only after visiting states.”
State-novelty guided action persistence in deep reinforcement learning
Hu, J., Weng, P., & Ban, Y. (2025) · Machine Learning · doi:10.1007/s10994-024-06675-z · Cited by 2 · see citing works
Bougie, N., & Ichise, R. (2021) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-021-09527-5 · Cited by 2 · see citing works
A Study of Global and Episodic Bonuses for Exploration in Contextual MDPs
Henaff, M., Jiang, M., & Raileanu, R. (2023) · arXiv · doi:10.48550/arxiv.2306.03236 · Cited by 1 · see citing works
“…(Bellemare et al., 2016b; Strehl & Littman, 2008; Bellemare et al., 2016a; Ostrovski et al., 2017; Martin et al., 2017; Tang et al., 2017; Machado et al., 2020), as well as model-based approaches (Shyam et al., 2019; Henaff, 2019; Sekar et al., 2020; Zhang et al., 2021a; Manek & Kolter,…”
BackgroundSheng, L., Chen, H., & Chen, X. (2024) · Algorithms · doi:10.3390/a17120579 · Cited by 1 · see citing works
GX-Chen, A., Chelu, V., Richards, B. A., & Pineau, J. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20639 · Cited by 1 · see citing works
Don't Do What Doesn't Matter: Intrinsic Motivation with Action UsefulnessPreprint
Seurin, M., Strub, F., Preux, P., & Pietquin, O. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2105.09992 · Cited by 1 · see citing works
Kadi, H. A., & Terzić, K. (2022) · Preprints.org · doi:10.20944/preprints202212.0305.v1 · Cited by 1 · see citing works
Intrinsic Motivation Model Based on Reward Gating
Pecháč, M., & Farkaš, I. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-86380-7_56
- Authors
- Machado, M. C., Bellemare, M. G., & Bowling, M.
- Affiliations
- Google (United States) (US)
- Venue
- Proceedings of the AAAI Conference on Artificial Intelligence
- Published
- 2020-04-03
- Volume
- 34
- Issue
- 04
- Pages
- 5125-5133
- ISSN
- 2159-5399 (ISSN-L)
- 2374-3468
- OpenAlex
- W2886012730
- Cited by
- 19
- References
- 39
- Citations by year
- 2025: 1 · 2024: 3 · 2023: 1 · 2022: 3 · 2021: 7 · 2020: 3 · 2019: 1
- FWCI
- 1.34
- Type
- conference paper
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- www.aaai.org/ (unspecified)
- Locations
- Proceedings of the AAAI Conference on Artificial Intelligence (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Compute Canada
- Alberta Machine Intelligence Institute
- University of Alberta
- Alberta Innovates
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Keywords
- exploration in reinforcement learning, successor representation, sample efficiency, function approximation, deep reinforcement learning, Atari 2600
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
