mlsanityData to 7 Oct 2026

Fast Rates for Maximum Entropy Exploration

arXiv 2303.08059 ↗First posted 14 Mar 2023stat.ML cs.LGcited by 32

Not on the map. Why?

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.

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

Builds on

26 of 57 references.

References · 26

  1. 2021Convex optimizationcited by 2,479
  2. 2018Exploration by Random Network Distillationcited by 966
  3. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 659
  4. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 632
  5. 2014Convex Optimization: Algorithms and Complexitycited by 569
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  9. 2019Go-Explore: a New Approach for Hard-Exploration Problemscited by 207
  10. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  11. 2019Efficient Exploration via State Marginal Matchingcited by 186
  12. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
14 more
  1. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  2. 2017A unified view of entropy-regularized Markov decision processescited by 174
  3. 2017Equivalence Between Policy Gradients and Soft Q-Learningcited by 172
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2015Taming the Noise in Reinforcement Learning via Soft Updatescited by 125
  6. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  7. 2021Reward is enough for convex MDPscited by 82
  8. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  9. 2017Boltzmann Exploration Done Rightcited by 69
  10. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  11. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  12. 2019If MaxEnt RL is the Answer, What is the Question?cited by 27
  13. 2018Entropy Maximization for Markov Decision Processes Under Temporal Logic Constraintscited by 11
  14. 2019Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewardscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 11; 2025: 7; 2026: 11.

32 papers.

Sort:

By area:

  1. 2025The Unreasonable Effectiveness of Entropy Minimization in LLM Reasoningcited by 160
  2. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  3. 2023Generative Flow Networks as Entropy-Regularized RLcited by 60
  4. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
  5. 2024Optimizing Backward Policies in GFlowNets via Trajectory Likelihood Maximizationcited by 12
  6. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  7. 2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
  8. 2024Robot Policy Learning with Temporal Optimal Transport Rewardcited by 8
  9. 2024How to Explore with Belief: State Entropy Maximization in POMDPscited by 6
  10. 2024The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enoughcited by 6
  11. 2025State Entropy Regularization for Robust Reinforcement Learningcited by 6
  12. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
20 more
  1. 2024Surprise-Adaptive Intrinsic Motivation for Unsupervised Reinforcement Learningcited by 4
  2. 2025Towards Principled Unsupervised Multi-Agent Reinforcement Learningcited by 4
  3. 2025Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspectivecited by 4
  4. 2025Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Storycited by 4
  5. 2024Off-Policy Maximum Entropy RL with Future State and Action Visitation Measurescited by 3
  6. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  7. 2024Maximum Entropy On-Policy Actor-Critic via Entropy Advantage Estimationcited by 2
  8. 2024ELEMENT: Episodic and Lifelong Exploration via Maximum Entropycited by 2
  9. 2026E2HiL: Entropy-Guided Sample Selection for Efficient Real-World Human-in-the-Loop Reinforcement Learningcited by 2
  10. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  11. 2024Generalizing Machine Learning Evaluation through the Integration of Shannon Entropy and Rough Set Theorycited by 1
  12. 2025SEMDICE: Off-policy State Entropy Maximization via Stationary Distribution Correction Estimationcited by 1
  13. 2026From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPscited by 1
  14. 2026Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrabilitycited by 1
  15. 2026K-Myriad: Jump-starting reinforcement learning with unsupervised parallel agentscited by 0
  16. 2026kappa-Explorer: A Unified Framework for Active Model Estimation in MDPscited by 0
  17. 2026Maximum-Entropy Exploration with Future State-Action Visitation Measurescited by 0
  18. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  19. 2026Efficient Exploration for Iterative Nash Preference Optimizationcited by 0
  20. 2026Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learningcited by 0