# Provably Efficient Maximum Entropy Exploration

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

## Key facts

- Cited by 242 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2018.

## Built on by (most cited first, 30 of 242)

- [PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training](https://mlsanity.com/paper/2106.05091/) (2021)
- [Reinforcement Learning with Prototypical Representations](https://mlsanity.com/paper/2102.11271/) (2021)
- [Behavior From the Void: Unsupervised Active Pre-Training](https://mlsanity.com/paper/2103.04551/) (2021)
- [Learning GFlowNets from partial episodes for improved convergence and stability](https://mlsanity.com/paper/2209.12782/) (2022)
- [Rapid Exploration for Open-World Navigation with Latent Goal Models](https://mlsanity.com/paper/2104.05859/) (2021)
- [APS: Active Pretraining with Successor Features](https://mlsanity.com/paper/2108.13956/) (2021)
- [State Entropy Maximization with Random Encoders for Efficient Exploration](https://mlsanity.com/paper/2102.09430/) (2021)
- [Reinforcement Learning with Action-Free Pre-Training from Videos](https://mlsanity.com/paper/2203.13880/) (2022)
- [B-Pref: Benchmarking Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2111.03026/) (2021)
- [Generalized Decision Transformer for Offline Hindsight Information Matching](https://mlsanity.com/paper/2111.10364/) (2021)
- [Curiosity-driven Red-teaming for Large Language Models](https://mlsanity.com/paper/2402.19464/) (2024)
- [METRA: Scalable Unsupervised RL with Metric-Aware Abstraction](https://mlsanity.com/paper/2310.08887/) (2023)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [On Reinforcement Learning and Distribution Matching for Fine-Tuning Language Models with no Catastrophic Forgetting](https://mlsanity.com/paper/2206.00761/) (2022)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [BYOL-Explore: Exploration by Bootstrapped Prediction](https://mlsanity.com/paper/2206.08332/) (2022)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Reward Uncertainty for Exploration in Preference-based Reinforcement Learning](https://mlsanity.com/paper/2205.12401/) (2022)
- [e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMs](https://mlsanity.com/paper/2506.09026/) (2025)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Correlated Proxies: A New Definition and Improved Mitigation for Reward Hacking](https://mlsanity.com/paper/2403.03185/) (2024)
- [Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2110.13625/) (2021)
- [DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimization](https://mlsanity.com/paper/2310.19668/) (2023)
- [Leveraging Non-uniformity in First-order Non-convex Optimization](https://mlsanity.com/paper/2105.06072/) (2021)
- [Adversarial Intrinsic Motivation for Reinforcement Learning](https://mlsanity.com/paper/2105.13345/) (2021)
- [MADE: Exploration via Maximizing Deviation from Explored Regions](https://mlsanity.com/paper/2106.10268/) (2021)
- [The Information Geometry of Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2110.02719/) (2021)
- [Discovering Policies with DOMiNO: Diversity Optimization Maintaining Near Optimality](https://mlsanity.com/paper/2205.13521/) (2022)
- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)

## Abstract (arXiv)

Suppose an agent is in a (possibly unknown) Markov Decision Process in the absence of a reward signal, what might we hope that an agent can efficiently learn to do? This work studies a broad class of objectives that are defined solely as functions of the state-visitation frequencies that are induced by how the agent behaves. For example, one natural, intrinsically defined, objective problem is for the agent to learn a policy which induces a distribution over state space that is as uniform as possible, which can be measured in an entropic sense. We provide an efficient algorithm to optimize such such intrinsically defined objectives, when given access to a black box planning oracle (which is robust to function approximation). Furthermore, when restricted to the tabular setting where we have sample based access to the MDP, our proposed algorithm is provably efficient, both in terms of its sample and computational complexities. Key to our algorithmic methodology is utilizing the conditional gradient method (a.k.a. the Frank-Wolfe algorithm) which utilizes an approximate MDP solver.