# Active Exploration in Markov Decision Processes

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2019.

## Built on by (most cited first, 27 of 27)

- [BYOL-Explore: Exploration by Bootstrapped Prediction](https://mlsanity.com/paper/2206.08332/) (2022)
- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Maximum State Entropy Exploration using Predecessor and Successor Representations](https://mlsanity.com/paper/2306.14808/) (2023)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Active Exploration via Experiment Design in Markov Chains](https://mlsanity.com/paper/2206.14332/) (2022)
- [Pretraining in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2211.03959/) (2022)
- [Unsupervised Reinforcement Learning in Multiple Environments](https://mlsanity.com/paper/2112.08746/) (2021)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Learning Altruistic Behaviours in Reinforcement Learning without External Rewards](https://mlsanity.com/paper/2107.09598/) (2021)
- [Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processes](https://mlsanity.com/paper/2306.07001/) (2023)
- [How to Explore with Belief: State Entropy Maximization in POMDPs](https://mlsanity.com/paper/2406.02295/) (2024)
- [Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction](https://mlsanity.com/paper/2407.13364/) (2024)
- [MARL with General Utilities via Decentralized Shadow Reward Actor-Critic](https://mlsanity.com/paper/2106.00543/) (2021)
- [Strongly-polynomial time and validation analysis of policy gradient methods](https://mlsanity.com/paper/2409.19437/) (2024)
- [Adaptive Multi-Goal Exploration](https://mlsanity.com/paper/2111.12045/) (2021)
- [Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Story](https://mlsanity.com/paper/2505.01336/) (2025)
- [Markov Decision Processes with Long-Term Average Constraints](https://mlsanity.com/paper/2106.06680/) (2021)
- [Policy Gradient with Tree Expansion](https://mlsanity.com/paper/2301.13236/) (2023)
- [Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluation](https://mlsanity.com/paper/2608.24146/) (2026)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)
- [From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPs](https://mlsanity.com/paper/2601.11890/) (2026)
- [Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigation](https://mlsanity.com/paper/2306.06192/) (2023)
- [A Theoretical Analysis of State Similarity Between Markov Decision Processes](https://mlsanity.com/paper/2512.17265/) (2025)
- [kappa-Explorer: A Unified Framework for Active Model Estimation in MDPs](https://mlsanity.com/paper/2602.20404/) (2026)

## Abstract (arXiv)

We introduce the active exploration problem in Markov decision processes (MDPs). Each state of the MDP is characterized by a random value and the learner should gather samples to estimate the mean value of each state as accurately as possible. Similarly to active exploration in multi-armed bandit (MAB), states may have different levels of noise, so that the higher the noise, the more samples are needed. As the noise level is initially unknown, we need to trade off the exploration of the environment to estimate the noise and the exploitation of these estimates to compute a policy maximizing the accuracy of the mean predictions. We introduce a novel learning algorithm to solve this problem showing that active exploration in MDPs may be significantly more difficult than in MAB. We also derive a heuristic procedure to mitigate the negative effect of slowly mixing policies. Finally, we validate our findings on simple numerical simulations.