# Fast Rates for Maximum Entropy Exploration

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 57 references that are in the map.
- First posted on arXiv 14 Mar 2023.

## Builds on (most cited first, 26 of 26)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Go-Explore: a New Approach for Hard-Exploration Problems](https://mlsanity.com/paper/1901.10995/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Efficient Exploration via State Marginal Matching](https://mlsanity.com/paper/1906.05274/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [Taming the Noise in Reinforcement Learning via Soft Updates](https://mlsanity.com/paper/1512.08562/) (2015)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Boltzmann Exploration Done Right](https://mlsanity.com/paper/1705.10257/) (2017)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [If MaxEnt RL is the Answer, What is the Question?](https://mlsanity.com/paper/1910.01913/) (2019)
- [Entropy Maximization for Markov Decision Processes Under Temporal Logic Constraints](https://mlsanity.com/paper/1807.03223/) (2018)
- [Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards](https://mlsanity.com/paper/1905.06466/) (2019)

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

- [The Unreasonable Effectiveness of Entropy Minimization in LLM Reasoning](https://mlsanity.com/paper/2505.15134/) (2025)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Generative Flow Networks as Entropy-Regularized RL](https://mlsanity.com/paper/2310.12934/) (2023)
- [Logarithmic Regret for Online KL-Regularized Reinforcement Learning](https://mlsanity.com/paper/2502.07460/) (2025)
- [Optimizing Backward Policies in GFlowNets via Trajectory Likelihood Maximization](https://mlsanity.com/paper/2410.15474/) (2024)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Minimax Optimal Q Learning with Nearest Neighbors](https://mlsanity.com/paper/2308.01490/) (2023)
- [Robot Policy Learning with Temporal Optimal Transport Reward](https://mlsanity.com/paper/2410.21795/) (2024)
- [How to Explore with Belief: State Entropy Maximization in POMDPs](https://mlsanity.com/paper/2406.02295/) (2024)
- [The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enough](https://mlsanity.com/paper/2406.12795/) (2024)
- [Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents](https://mlsanity.com/paper/2410.22908/) (2024)
- [State Entropy Regularization for Robust Reinforcement Learning](https://mlsanity.com/paper/2506.07085/) (2025)
- [E2HiL: Entropy-Guided Sample Selection for Efficient Real-World Human-in-the-Loop Reinforcement Learning](https://mlsanity.com/paper/2601.19969/) (2026)
- [Near-Optimal Regret for KL-Regularized Multi-Armed Bandits](https://mlsanity.com/paper/2603.02155/) (2026)
- [Surprise-Adaptive Intrinsic Motivation for Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2405.17243/) (2024)
- [Maximum Entropy On-Policy Actor-Critic via Entropy Advantage Estimation](https://mlsanity.com/paper/2407.18143/) (2024)
- [Towards Principled Unsupervised Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2502.08365/) (2025)
- [Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective](https://mlsanity.com/paper/2502.19255/) (2025)
- [Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Story](https://mlsanity.com/paper/2505.01336/) (2025)
- [On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization](https://mlsanity.com/paper/2605.02141/) (2026)
- [Off-Policy Maximum Entropy RL with Future State and Action Visitation Measures](https://mlsanity.com/paper/2412.06655/) (2024)
- [Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability](https://mlsanity.com/paper/2605.09214/) (2026)
- [ELEMENT: Episodic and Lifelong Exploration via Maximum Entropy](https://mlsanity.com/paper/2412.03800/) (2024)
- [Generalizing Machine Learning Evaluation through the Integration of Shannon Entropy and Rough Set Theory](https://mlsanity.com/paper/2404.12511/) (2024)
- [SEMDICE: Off-policy State Entropy Maximization via Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2512.10042/) (2025)
- [From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPs](https://mlsanity.com/paper/2601.11890/) (2026)
- [K-Myriad: Jump-starting reinforcement learning with unsupervised parallel agents](https://mlsanity.com/paper/2601.18580/) (2026)
- [kappa-Explorer: A Unified Framework for Active Model Estimation in MDPs](https://mlsanity.com/paper/2602.20404/) (2026)
- [Maximum-Entropy Exploration with Future State-Action Visitation Measures](https://mlsanity.com/paper/2603.18965/) (2026)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)

## Abstract (arXiv)

We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. In this work, we study the maximum entropy exploration problem of two different types. The first type is visitation entropy maximization previously considered by Hazan et al.(2019) in the discounted setting. For this type of exploration, we propose a game-theoretic algorithm that has widetildeO(H3S2A/varepsilon2) sample complexity thus improving the varepsilon-dependence upon existing results, where S is a number of states, A is a number of actions, H is an episode length, and varepsilon is a desired accuracy. The second type of entropy we study is the trajectory entropy. This objective function is closely related to the entropy-regularized MDPs, and we propose a simple algorithm that has a sample complexity of order widetildeO(poly(S,A,H)/varepsilon). Interestingly, it is the first theoretical result in RL literature that establishes the potential statistical advantage of regularized MDPs for exploration. Finally, we apply developed regularization techniques to reduce sample complexity of visitation entropy maximization to widetildeO(H2SA/varepsilon2), yielding a statistical separation between maximum entropy exploration and reward-free exploration.