Source-linked AI summary
#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, Pieter Abbeel
TL;DR
High-dimensional and continuous state spaces make direct count-based exploration difficult, despite its theoretical success in small finite MDPs. The paper hashes states into discrete codes, counts those codes, and uses the counts for classic exploration bonuses. This simple generalization achieves near state-of-the-art performance across continuous-control and Atari benchmarks.
Problem
Count-based exploration is theoretically effective in small finite MDPs, but direct state counting is difficult in high-dimensional spaces and existing deep-RL exploration methods are often complex.
Method
The method hashes states into discrete codes, counts state visits, and adds a count-based bonus while supporting static or learned hash representations.
Results
The approach achieves near state-of-the-art performance across continuous-control and Atari benchmarks, with learned hashing improving results on selected Atari games.
Takeaways & Limitations
Hashing provides a simple, powerful baseline for exploration in continuous or high-dimensional MDPs requiring informed exploration.
Takeaways & Limitations
The method relies on visiting unseen states before assigning their bonus, so uninformed exploration remains necessary at the beginning.
Abstract
from arXiv · showhide
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.
1 Introduction
Count-based exploration has strong theoretical foundations in small finite MDPs but is difficult to apply directly in high-dimensional spaces. This paper extends counting through hashing and reports near state-of-the-art performance across challenging continuous-control and Atari benchmarks.
- Sparse-reward tasks can make heuristic exploration sample complexity grow exponentially with state-space size.
- Classic methods count state-action visitations and convert those counts into bonus rewards, but MBIE-style methods are practical only for small finite state spaces.
- The proposed approach discretizes high-dimensional or continuous states with a hash function and applies a visitation-count bonus.
- Hash granularity can balance generalization across similar states with separation of distant states, while the method remains fast, flexible, and complementary to existing RL algorithms.
- The paper evaluates sparse-reward problems from rllab and Atari 2600, including games that defeat naïve exploration strategies.
2 Methodology
The method turns high-dimensional states into discrete hash codes, counts code occurrences, and adds count-based exploration bonuses. It uses fixed SimHash or learned autoencoder codes, whose granularity, stability, and semantic relevance determine exploration quality.
- Count-based exploration: The approach discretizes states with a hash function, increments the corresponding code count, and adds a count-based bonus during training.Performance is evaluated using environmental rewards without exploration bonuses.
- Count-based exploration: The method uses state counts rather than state-action counts because supplementary experiments found no significant gains from counting actions separately.The authors suggest policy randomness may already encourage trying most actions at novel states.
- Hash-function design: A useful hash function must separate distant states while merging similar ones and may incorporate salient state features known to matter for the MDP.The learned code also faces a trade-off between temporal consistency and uniqueness for distinct nearby states.
- Static hashing: SimHash converts continuous, high-dimensional states into binary codes, with the projection dimension controlling granularity and collision frequency.Higher k values produce fewer collisions and are more likely to distinguish states.
- Learned hashing: An autoencoder can learn binary hash codes from states, optionally followed by SimHash projection, to provide more meaningful representations for complex observations.For image inputs, the autoencoder uses a dense sigmoid code layer whose activations are rounded to binary values.
- Learned hashing: Autoencoder codes are stabilized through binary-value regularization, sigmoid saturation, and implementation choices such as downsampling or slower training.These mechanisms reduce code changes while preserving distinctions needed for reconstruction and hashing.
3 Related Work
The paper places hashing-based count exploration alongside classical optimism, Bayesian, curiosity, model-based, bootstrapped, and pseudo-count strategies for deep RL. Its approach differs by approximating counts through hashing rather than learned density models or state-action tables.
- Classical exploration: Classical optimism-based methods such as MBIE-EB provide theoretical guarantees in tabular settings by propagating exploration bonuses through an inner-loop Bellman solution.These methods include MBIE, MBIE-EB, R-Max, UCRL, and E3.
- Position of this work: Unlike classical methods, the proposed approach assigns bonuses after unseen states are visited and therefore still relies initially on uninformed exploration.Its rollout-based deep-RL updates also propagate bonus signals more slowly than classical inner-loop Bellman methods.
- Deep RL alternatives: Bayesian, curiosity-based, information-gain, prediction-error, and bootstrapped methods address exploration using uncertainty, surprise, learned dynamics, or ensembles.The cited approaches include Bayesian RL, VIME, learned-dynamics prediction error, and bootstrapped Q-functions.
- Approximate counting: Pseudo-count methods estimate visitation through density-model probability improvements, whereas hashing performs approximate counting with a different generalization mechanism.Both approaches seek generalization over unseen states, but pseudo-counts require a density model over visited states.
4 Experiments
Experiments test hashing-based count exploration on sparse-reward continuous-control and Atari benchmarks, varying preprocessing and comparing against established deep-RL methods. Hashing reaches goals across the control tasks, while preprocessing can substantially improve Atari performance.
- Experimental design: The experiments address cross-domain performance, comparisons with deep-RL exploration, and the effects of static or learned image preprocessing.TRPO is used throughout because it supports discrete and continuous actions and offers stable policy improvement.
- Continuous control: The selected rllab tasks use sparse rewards and are difficult for naïve Gaussian-noise exploration, spanning classic control, locomotion, and hierarchical tasks.The experiments include MountainCar, CartPoleSwingup, HalfCheetah, and SwimmerGather.
- Continuous-control results: Hashing reaches the goal in all tested continuous-control environments, while baseline TRPO with Gaussian control noise fails completely.SimHash is comparable to VIME on MountainCar, outperforms VIME on SwimmerGather, and underperforms VIME on HalfCheetah.
- Atari evaluation: The Atari evaluation uses six long-horizon games requiring substantial exploration and reports average total reward after 50 M time steps.Training curves report undiscounted return per iteration, with seed counts varying by method.
- Atari results: TRPO-pixel-SimHash beats the previous best result on Frostbite, BASS-SimHash improves Montezuma’s Revenge and Venture, and AE-SimHash is near state-of-the-art on three games.The reported near-state-of-the-art games for AE-SimHash are Freeway, Frostbite, and Solaris.
- Preprocessing analysis: BASS and learned autoencoder preprocessing produce much better performance on Gravitar, Montezuma’s Revenge, and Venture, showing that preprocessing can matter for hash quality.BASS encodes object locations while remaining invariant to negligible object motions, but may miss game-specific structure.
- Limitations: The method does not achieve state-of-the-art performance on every game, partly because TRPO does not reuse off-policy experience as DQN-based methods do.This limits the efficiency with which extremely sparse rewards can be exploited.
5 Conclusions
Hashing generalizes classical counting to continuous and high-dimensional MDPs with function approximators. Across benchmarks, it provides near state-of-the-art performance and a simple baseline for tasks requiring informed exploration.
- Conclusion: Hashing-based classical counting provides an appropriate exploration signal in continuous and/or high-dimensional MDPs using function approximators.The paper reports near state-of-the-art performance across benchmarks.
1 Hyperparameter Settings
The experiments use TRPO with task-specific policy and autoencoder configurations, alongside convolutional architectures for Atari image inputs and counting Bloom filters for compact state counting.
- The rllab policy maps each state to a Gaussian action distribution whose mean comes from a tanh MLP and whose standard deviation is state-independent.
- Atari image inputs use convolutional layers with ReLU nonlinearities and pixel-wise softmax outputs with shared weights across pixels.
- The Atari autoencoder uses a binary code layer between convolutional encoding and transposed-convolutional reconstruction layers.
- Counting Bloom filters maintain a compact hash table for state counts during the experiments.
2 Description of the Adapted rllab Tasks
The adapted rllab tasks use continuous state and action spaces with sparse rewards, requiring agents to discover task-specific target behaviors rather than relying on dense initial feedback.
- The benchmark includes CartPoleSwingup, MountainCar, HalfCheetah, and SwimmerGather with state dimensions ranging from 3 to 33 and continuous actions.
- MountainCar rewards the agent with +1 only after reaching the goal by escaping the valley from the right side.
- The sparse CartPoleSwingup task requires discovering how to swing up the pole without initial external rewards.
- HalfCheetah rewards +1 when xbody > 5.
- The tasks use a time horizon of T = 500 and sparse-reward adaptations.
3 Analysis of Learned Binary Representation
The learned binary codes vary across Atari frames in ways that appear related to persistent state, objects, and events, suggesting they provide a useful abstraction of game state.
- Figure 1 presents downsampled autoencoder codes for Frostbite, Freeway, and Montezuma’s Revenge across consecutive Atari frames.
- The corresponding binary codes are shown one per frame, alongside reconstructions of subsequent images.
- Some binary components remain consistent across frames, while others appear responsive to specific objects or events.
- Although the precise meaning of each binary number is unclear, the learned hash code appears to be a reasonable abstraction of game state.
4 Counting Bloom Filter/Count-Min Sketch
The paper compares dictionary counting, counting Bloom filters, and Count-Min Sketches for compact state counting, finding similar exploration behavior with computational advantages for fixed-array methods.
- A direct dictionary stores state hashes as keys, whereas Count-Min Sketch uses multiple modular hash functions and a fixed integer array.
- Count-Min Sketch increments all per-hash counters and reports a count agreed upon by the weaker hash functions, reducing over-counting probability.
- Dictionary counting and Bloom filters produce similar performance, while Bloom filters require less computation time.
- Direct counting and a much larger Bloom-filter table yield nearly identical average bonus rewards, indicating similar exploration–exploitation trade-offs.
- Bloom filters require a fixed table size that may be unknown beforehand.
- Counting Bloom filters support insertion and deletion by maintaining counters for each hash location, unlike standard Bloom filters.
- The probability of over-counting decays exponentially in the number of hash functions.
5 Robustness Analysis
The analysis shows that hash-based count exploration is sensitive to hash granularity, bonus scaling, and information encoded in the hash. Across experiments, appropriate settings and task-relevant representations improve exploration performance, while overly fine or semantically misaligned hashing can degrade it.
- 5.1 Granularity: Hash granularity must avoid both under-generalizing and over-generalizing states, and the best setting depends on the hash function and MDP.The authors also report that increasing granularity requires lowering the bonus coefficient.
- 5.1 Granularity: k = 16 cannot distinguish semantically distinct states, whereas k = 512 captures trivial Frostbite image details and makes every state appear new.The first failure reduces useful discrimination; the second encourages indiscriminate exploration.
- 5.2 Hyperparameter sensitivity: With fixed k, performance is roughly concave in β and peaks around 0.2; small β-values underexplore, while large β-values overwhelm true rewards.The analysis concludes that the method is robust to hyperparameter changes and can be tuned with a relatively coarse grid search.
- 5.3 A Case Study of Montezuma’s Revenge: SmartHash improves Montezuma’s Revenge over TRPO-BASS-SimHash, reaching 3500 compared with 2500 when using RAM states with TRPO-BASS-SimHash.SmartHash incorporates the agent’s location, room number, and other useful RAM information.
- 5.3 A Case Study of Montezuma’s Revenge: Hash codes should encode information relevant to solving the MDP rather than merely visual similarity: ignoring enemy locations reaches 5661, versus 1672 when enemy locations are included directly.Including enemy locations caused the agent to focus on enemy motion and forget its objective of entering other rooms.
- 5.4 State and state-action counting: State counting achieves the best Frostbite performance with k = 256 and β = 0.2, while relative state-versus-state-action performance depends strongly on hyperparameter settings.The comparison uses TRPO-RAM-SimHash under the same experimental setup.