# The Importance of Non-Markovianity in Maximum State Entropy Exploration

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

## Key facts

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

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [Efficient Exploration via State Marginal Matching](https://mlsanity.com/paper/1906.05274/) (2019)
- [Reinforcement Learning with Prototypical Representations](https://mlsanity.com/paper/2102.11271/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Behavior From the Void: Unsupervised Active Pre-Training](https://mlsanity.com/paper/2103.04551/) (2021)
- [URLB: Unsupervised Reinforcement Learning Benchmark](https://mlsanity.com/paper/2110.15191/) (2021)
- [APS: Active Pretraining with Successor Features](https://mlsanity.com/paper/2108.13956/) (2021)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [State Entropy Maximization with Random Encoders for Efficient Exploration](https://mlsanity.com/paper/2102.09430/) (2021)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Geometric Entropic Exploration](https://mlsanity.com/paper/2101.02055/) (2021)
- [Active Exploration in Markov Decision Processes](https://mlsanity.com/paper/1902.11199/) (2019)
- [An Intrinsically-Motivated Approach for Learning Highly Exploring and Fast Mixing Policies](https://mlsanity.com/paper/1907.04662/) (2019)
- [Unsupervised Reinforcement Learning in Multiple Environments](https://mlsanity.com/paper/2112.08746/) (2021)
- [A Provably Efficient Sample Collection Strategy for Reinforcement Learning](https://mlsanity.com/paper/2007.06437/) (2020)
- [Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards](https://mlsanity.com/paper/1905.06466/) (2019)
- [Exploration by Maximizing R'enyi Entropy for Reward-Free RL Framework](https://mlsanity.com/paper/2006.06193/) (2020)

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

- [DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimization](https://mlsanity.com/paper/2310.19668/) (2023)
- [Maximum State Entropy Exploration using Predecessor and Successor Representations](https://mlsanity.com/paper/2306.14808/) (2023)
- [Accelerating Reinforcement Learning with Value-Conditional State Entropy Exploration](https://mlsanity.com/paper/2305.19476/) (2023)
- [Explore to Generalize in Zero-Shot RL](https://mlsanity.com/paper/2306.03072/) (2023)
- [Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space](https://mlsanity.com/paper/2306.01854/) (2023)
- [Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning](https://mlsanity.com/paper/2511.22640/) (2025)
- [ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularization](https://mlsanity.com/paper/2402.14528/) (2024)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Provable Maximum Entropy Manifold Exploration via Diffusion Models](https://mlsanity.com/paper/2506.15385/) (2025)
- [Active Coverage for PAC Reinforcement Learning](https://mlsanity.com/paper/2306.13601/) (2023)
- [Efficient Tail-Aware Generative Optimization via Flow Model Fine-Tuning](https://mlsanity.com/paper/2602.16796/) (2026)
- [Verifier-Constrained Flow Expansion for Discovery Beyond the Data](https://mlsanity.com/paper/2602.15984/) (2026)
- [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)
- [Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction](https://mlsanity.com/paper/2407.13364/) (2024)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [State Entropy Regularization for Robust Reinforcement Learning](https://mlsanity.com/paper/2506.07085/) (2025)
- [Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity](https://mlsanity.com/paper/2211.07092/) (2022)
- [Policy Gradient Algorithms Implicitly Optimize by Continuation](https://mlsanity.com/paper/2305.06851/) (2023)
- [Effective Exploration Based on the Structural Information Principles](https://mlsanity.com/paper/2410.06621/) (2024)
- [Towards Principled Unsupervised Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2502.08365/) (2025)
- [Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Story](https://mlsanity.com/paper/2505.01336/) (2025)
- [Off-Policy Maximum Entropy RL with Future State and Action Visitation Measures](https://mlsanity.com/paper/2412.06655/) (2024)
- [AIGB: Generative Auto-bidding via Conditional Diffusion Modeling](https://mlsanity.com/paper/2405.16141/) (2024)
- [A Unified Density Operator View of Flow Control and Merging](https://mlsanity.com/paper/2602.08012/) (2026)
- [Toward Debugging Deep Reinforcement Learning Programs with RLExplorer](https://mlsanity.com/paper/2410.04322/) (2024)
- [Central Limit Theorems for Transition Probabilities of Controlled Markov Chains](https://mlsanity.com/paper/2508.01517/) (2025)
- [Blindfolded Experts Generalize Better: Insights from Robotic Manipulation and Videogames](https://mlsanity.com/paper/2510.24194/) (2025)
- [SEMDICE: Off-policy State Entropy Maximization via Stationary Distribution Correction Estimation](https://mlsanity.com/paper/2512.10042/) (2025)
- [Maximum Entropy Exploration Without the Rollouts](https://mlsanity.com/paper/2603.12325/) (2026)

## 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.