#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning

By Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, Pieter Abbeel. 2016

866 citations recorded by the source corpus.

Count-based exploration algorithms are known to perform near-optimally when used in conjunction with tabular reinforcement learning (RL) methods for solving small discrete Markov decision processes (MDPs). It is generally thought that count-based methods cannot be applied in high-dimensional state spaces, since most states will only occur once. Recent deep RL exploration strategies are able to deal with high-dimensional continuous state spaces through complex heuristics, often relying on optimism in the face of uncertainty or intrinsic motivation. In this work, we describe a surprising finding: a simple generalization of the classic count-based approach can reach near state-of-the-art performance on various high-dimensional and/or continuous deep RL benchmarks. States are mapped to hash codes, which allows to count their occurrences with a hash table. These counts are then used to compute a reward bonus according to the classic count-based exploration theory. We find that simple hash functions can achieve surprisingly good results on many challenging tasks. Furthermore, we show that a domain-dependent learned hash code may further improve these results. Detailed analysis reveals important aspects of a good hash function: 1) having appropriate granularity and 2) encoding information relevant to solving the MDP. This exploration strategy achieves near state-of-the-art performance on both continuous control tasks and Atari 2600 games, hence providing a simple yet powerful baseline for solving MDPs that require considerable exploration.

Subfields: Reinforcement Learning

How researchers see this paper

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

In Reinforcement Learning

Citations in the corpus

Reinforcement Learning in Healthcare: A Survey (2019, background): “proposed, such as PAC guaranteed exploration methods targeting at continuous spaces [150], [151], concurrent exploration mechanisms [318], [319], [320] and exploration in deep RL [321], [322], [323].”
Curiosity-Driven Exploration by Self-Supervised Prediction (2017, background): “State visitation counts have also been investigated for exploration (Bellemare et al., 2016; Oh et al., 2015; Tang et al., 2016).”
Self-Imitation Learning (2018, methodology): “We further compared our method against the state-of-the-art count-based exploration actor-critic agents (A3C-CTS (Bellemare et al., 2016), Reactor-PixelCNN (Ostrovski et al., 2017), and SimHash (Tang et al., 2017)).”
Continual Learning of Control Primitives: Skill Discovery via Reset-Games (2020, positive): “In the direction of curiosity-driven exploration, recent work has used state novelty to reward an agent [5, 44, 33].”
Exploration by Random Network Distillation (2018, methodology): “Special access to the underlying RAM state can also be used to improve exploration by using it to hand-craft exploration bonuses (Kulkarni et al., 2016; Tang et al., 2017; Stanton & Clune, 2018).”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, methodology): “More details can be found in appendix. well as popular exploration methods, i.e., count-based exploration (PG+CNT) (Tang et al., 2017) and MAVEN (Mahajan et al., 2019).”
Emergent Tool Use From Multi-Agent Autocurricula (2019, background): “One example is count-based exploration, where agents are incentivized to reach infrequently visited states by maintaining state visitation counts [37, 38, 39] or density estimators [40, 41].”
Hindsight Experience Replay (2017, methodology): “Moreover, we compare against DDPG with count-based exploration5 (Strehl and Littman, 2005; Kolter and Ng, 2009; Tang et al., 2016; Bellemare et al., 2016; Ostrovski et al., 2017).”
Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Play (2017, methodology): “On the other hand, if the light is usually off at the start 4Experiments in VIME and SimHash papers skip 50 frames, but we matched the total number of frames in an episode by reducing the number of steps.”
Parameter Space Noise for Exploration (2017, background): “…plethora of methods have been proposed to tackle this challenge in high-dimensional and/or continuous-action MDPs, they often rely on complex additional structures such as counting tables [1], density modeling of the state space [2], learned dynamics models [3–5], or self-supervised curiosity [6].”
Benchmarking Batch Deep Reinforcement Learning Algorithms (2019, methodology): “However, in principle D ( s, a ) can be computed with a number of pseudo-count methods [Bellemare et al., 2016, Tang et al., 2017, Burda et al., 2018].”
Reinforced Cross-Modal Matching and Self-Supervised Imitation Learning for Vision-Language Navigation (2018, background): “Exploration Much work has been done on improving exploration [4, 12, 16, 28, 36] because the trade-off between exploration and exploitation is one of the fundamental challenges in RL.”
Dynamics-Aware Unsupervised Discovery of Skills (2019, background): “Examples of such works include empowerment [37, 47], count-based exploration [8, 50, 67, 21], information gain about agent’s dynamics [64] and forward-inverse dynamics models [53].”
A Brief Survey of Deep Reinforcement Learning (2017, neutral): “Whilst easily achievable in small tabular cases, the use of powerful density models [11], or conversely, hashing [139], has allowed this algorithm to scale to high-dimensional visual domains with DRL.”
Curiosity Driven Exploration of Learned Disentangled Goal Spaces (2018, background): “However, many of these approaches are not directly applicable to high-dimensional redundant continuous action spaces [12, 15], or face complexity challenges to be applicable to real world robots [16, 17].”
Large-Scale Study of Curiosity-Driven Learning (2018, background): “Smoothed versions of state visitation counts can be used for intrinsic rewards [3, 9, 24, 47].”
Go-Explore: a New Approach for Hard-Exploration Problems (2019, background): “Montezuma’s Revenge has become an important benchmark for exploration algorithms (including intrinsic motivation algorithms) [4, 16, 32–39] because precise sequences of hundreds of actions must be taken in between receiving rewards.”
EX2: Exploration with Exemplar Models for Deep Reinforcement Learning (2017, methodology): “Several reasonable choices for the function f include log D s ( s ) or a count-based 1 / N ( s ) (as done by Tang et al. (2016)), where N ( s ) = n ˆ P ( s ) , with ˆ P ( s ) estimated via Equation (3), and n being the size of the replay buffer R .”