mlsanityData to 7 Oct 2026

The Importance of Non-Markovianity in Maximum State Entropy Exploration

arXiv 2202.03060 ↗First posted 7 Feb 2022cs.LGcited by 35

Not on the map. Why?

Abstract (arXiv)

In the maximum state entropy exploration framework, an agent interacts with a reward-free environment to learn a policy that maximizes the entropy of the expected state visitations it is inducing. Hazan et al. (2019) noted that the class of Markovian stochastic policies is sufficient for the maximum state entropy objective, and exploiting non-Markovianity is generally considered pointless in this setting. In this paper, we argue that non-Markovianity is instead paramount for maximum state entropy exploration in a finite-sample regime. Especially, we recast the objective to target the expected entropy of the induced state visitations in a single trial. Then, we show that the class of non-Markovian deterministic policies is sufficient for the introduced objective, while Markovian policies suffer non-zero regret in general. However, we prove that the problem of finding an optimal non-Markovian policy is NP-hard. Despite this negative result, we discuss avenues to address the problem in a tractable way and how non-Markovian exploration could benefit the sample efficiency of online reinforcement learning in future works.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). Builds on 19 of its 48 references that are in the map. First posted on arXiv 7 Feb 2022.

Builds on

19 of 48 references.

References · 19

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  3. 2015Contextual Markov Decision Processescited by 213
  4. 2019Efficient Exploration via State Marginal Matchingcited by 186
  5. 2021Reinforcement Learning with Prototypical Representationscited by 179
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2021Behavior From the Void: Unsupervised Active Pre-Trainingcited by 173
  8. 2021URLB: Unsupervised Reinforcement Learning Benchmarkcited by 138
  9. 2021APS: Active Pretraining with Successor Featurescited by 109
  10. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 108
  11. 2021State Entropy Maximization with Random Encoders for Efficient Explorationcited by 107
  12. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
7 more
  1. 2021Geometric Entropic Explorationcited by 32
  2. 2019Active Exploration in Markov Decision Processescited by 27
  3. 2019An Intrinsically-Motivated Approach for Learning Highly Exploring and Fast Mixing Policiescited by 20
  4. 2021Unsupervised Reinforcement Learning in Multiple Environmentscited by 17
  5. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 15
  6. 2019Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewardscited by 8
  7. 2020Exploration by Maximizing R'enyi Entropy for Reward-Free RL Frameworkcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 7; 2024: 10; 2025: 9; 2026: 8.

35 papers.

Sort:

By area:

  1. 2023DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimizationcited by 45
  2. 2023Maximum State Entropy Exploration using Predecessor and Successor Representationscited by 23
  3. 2023Accelerating Reinforcement Learning with Value-Conditional State Entropy Explorationcited by 22
  4. 2023Explore to Generalize in Zero-Shot RLcited by 20
  5. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  6. 2024ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularizationcited by 16
  7. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  8. 2025Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuningcited by 15
  9. 2025Provable Maximum Entropy Manifold Exploration via Diffusion Modelscited by 12
  10. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  11. 2024How to Explore with Belief: State Entropy Maximization in POMDPscited by 6
  12. 2024The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enoughcited by 6
23 more
  1. 2024Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstractioncited by 6
  2. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  3. 2025State Entropy Regularization for Robust Reinforcement Learningcited by 6
  4. 2026Verifier-Constrained Flow Expansion for Discovery Beyond the Datacited by 6
  5. 2026Efficient Tail-Aware Generative Optimization via Flow Model Fine-Tuningcited by 6
  6. 2022Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexitycited by 5
  7. 2023Policy Gradient Algorithms Implicitly Optimize by Continuationcited by 4
  8. 2024Effective Exploration Based on the Structural Information Principlescited by 4
  9. 2025Towards Principled Unsupervised Multi-Agent Reinforcement Learningcited by 4
  10. 2025Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Storycited by 4
  11. 2024Off-Policy Maximum Entropy RL with Future State and Action Visitation Measurescited by 3
  12. 2026A Unified Density Operator View of Flow Control and Mergingcited by 2
  13. 2024AIGB: Generative Auto-bidding via Conditional Diffusion Modelingcited by 1
  14. 2024Toward Debugging Deep Reinforcement Learning Programs with RLExplorercited by 1
  15. 2025Central Limit Theorems for Transition Probabilities of Controlled Markov Chainscited by 1
  16. 2025Blindfolded Experts Generalize Better: Insights from Robotic Manipulation and Videogamescited by 1
  17. 2025SEMDICE: Off-policy State Entropy Maximization via Stationary Distribution Correction Estimationcited by 1
  18. 2026Maximum Entropy Exploration Without the Rolloutscited by 1
  19. 2025Online Episodic Convex Reinforcement Learningcited by 0
  20. 2026K-Myriad: Jump-starting reinforcement learning with unsupervised parallel agentscited by 0
  21. 2026Maximum-Entropy Exploration with Future State-Action Visitation Measurescited by 0
  22. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  23. 2026The Dually Flat Geometry of Planning as Inferencecited by 0