# Flipping Coins to Estimate Pseudocounts for Exploration in Reinforcement Learning

arXiv: https://arxiv.org/abs/2306.03186 · HTML: https://mlsanity.com/paper/2306.03186/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 56 references that are in the map.
- First posted on arXiv 5 Jun 2023.

## Builds on (most cited first, 30 of 36)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Learning Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrations](https://mlsanity.com/paper/1709.10087/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents](https://mlsanity.com/paper/1709.06009/) (2017)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research](https://mlsanity.com/paper/1802.09464/) (2018)
- [Count-Based Exploration with Neural Density Models](https://mlsanity.com/paper/1703.01310/) (2017)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [Never Give Up: Learning Directed Exploration Strategies](https://mlsanity.com/paper/2002.06038/) (2020)
- [Skew-Fit: State-Covering Self-Supervised Reinforcement Learning](https://mlsanity.com/paper/1903.03698/) (2019)
- [Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models](https://mlsanity.com/paper/1507.00814/) (2015)
- [RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments](https://mlsanity.com/paper/2002.12292/) (2020)
- [Dopamine: A Research Framework for Deep Reinforcement Learning](https://mlsanity.com/paper/1812.06110/) (2018)
- [Count-Based Exploration with the Successor Representation](https://mlsanity.com/paper/1807.11622/) (2018)
- [A Deeper Look at Experience Replay](https://mlsanity.com/paper/1712.01275/) (2017)
- [Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning](https://mlsanity.com/paper/2007.02832/) (2020)
- [The Uncertainty Bellman Equation and Exploration](https://mlsanity.com/paper/1709.05380/) (2017)
- [BYOL-Explore: Exploration by Bootstrapped Prediction](https://mlsanity.com/paper/2206.08332/) (2022)
- [Learning Markov State Abstractions for Deep Reinforcement Learning](https://mlsanity.com/paper/2106.04379/) (2021)

## Built on by (most cited first, 28 of 28)

- [Exploration and Anti-Exploration with Distributional Random Network Distillation](https://mlsanity.com/paper/2401.09750/) (2024)
- [Highly Efficient Self-Adaptive Reward Shaping for Reinforcement Learning](https://mlsanity.com/paper/2408.03029/) (2024)
- [Episodic Novelty Through Temporal Distance](https://mlsanity.com/paper/2501.15418/) (2025)
- [Leveraging Skills from Unlabeled Prior Data for Efficient Online Exploration](https://mlsanity.com/paper/2410.18076/) (2024)
- [EntroPIC: Towards Stable Long-Term Training of LLMs via Entropy Stabilization with Proportional-Integral Control](https://mlsanity.com/paper/2511.15248/) (2025)
- [RLeXplore: Accelerating Research in Intrinsically-Motivated Reinforcement Learning](https://mlsanity.com/paper/2405.19548/) (2024)
- [An Optimal Tightness Bound for the Simulation Lemma](https://mlsanity.com/paper/2406.16249/) (2024)
- [Hierarchical Empowerment: Towards Tractable Empowerment-Based Skill Learning](https://mlsanity.com/paper/2307.02728/) (2023)
- [Improving Intrinsic Exploration by Creating Stationary Objectives](https://mlsanity.com/paper/2310.18144/) (2023)
- [Beyond Optimism: Exploration With Partially Observable Rewards](https://mlsanity.com/paper/2406.13909/) (2024)
- [Uncertainty Prioritized Experience Replay](https://mlsanity.com/paper/2506.09270/) (2025)
- [Analytical Survey of Learning with Low-Resource Data: From Analysis to Investigation](https://mlsanity.com/paper/2510.08962/) (2025)
- [Emergence of Exploration in Policy Gradient Reinforcement Learning via Retrying](https://mlsanity.com/paper/2606.00151/) (2026)
- [Surprise-Adaptive Intrinsic Motivation for Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2405.17243/) (2024)
- [BAMDP Shaping: a Unified Framework for Intrinsic Motivation and Reward Shaping](https://mlsanity.com/paper/2409.05358/) (2024)
- [Novelty-Guided Data Reuse for Efficient and Diversified Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2412.15517/) (2024)
- [β-DQN: Improving Deep Q-Learning By Evolving the Behavior](https://mlsanity.com/paper/2501.00913/) (2025)
- [ETGL-DDPG: A Deep Deterministic Policy Gradient Algorithm for Sparse Reward Continuous Control](https://mlsanity.com/paper/2410.05225/) (2024)
- [Finite-time Convergence Analysis of Actor-Critic with Evolving Reward](https://mlsanity.com/paper/2510.12334/) (2025)
- [Exploration by Random Distribution Distillation](https://mlsanity.com/paper/2505.11044/) (2025)
- [Exploration by Random Reward Perturbation](https://mlsanity.com/paper/2506.08737/) (2025)
- [Maximum Entropy Exploration Without the Rollouts](https://mlsanity.com/paper/2603.12325/) (2026)
- [VLAConf: Calibrated Task-Success Confidence for Vision-Language-Action Models](https://mlsanity.com/paper/2605.29605/) (2026)
- [Retry Policy Gradients in Continuous Action Spaces](https://mlsanity.com/paper/2606.05888/) (2026)
- [Going Beyond State-Reaching: Learning Abstractions for Intrinsically Motivated Option Discovery](https://mlsanity.com/paper/2609.36473/) (2026)
- [Exploration Behavior of Untrained Policies](https://mlsanity.com/paper/2506.22566/) (2025)
- [Fill in the Blanks: Accelerating Q-Learning with a Handful of Demonstrations in Sparse Reward Settings](https://mlsanity.com/paper/2510.24432/) (2025)
- [CIG: Exploration via Conditional Information Gain](https://mlsanity.com/paper/2605.20878/) (2026)

## Abstract (arXiv)

We propose a new method for count-based exploration in high-dimensional state spaces. Unlike previous work which relies on density models, we show that counts can be derived by averaging samples from the Rademacher distribution (or coin flips). This insight is used to set up a simple supervised learning objective which, when optimized, yields a state's visitation count. We show that our method is significantly more effective at deducing ground-truth visitation counts than previous work; when used as an exploration bonus for a model-free reinforcement learning algorithm, it outperforms existing approaches on most of 9 challenging exploration tasks, including the Atari game Montezuma's Revenge.