mlsanityData to 7 Oct 2026

Active Exploration in Markov Decision Processes

arXiv 1902.11199 ↗First posted 28 Feb 2019stat.ML cs.LGcited by 27

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 5; 2023: 6; 2024: 4; 2025: 3; 2026: 3.

27 papers.

Sort:

By area:

  1. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 71
  2. 2022The Importance of Non-Markovianity in Maximum State Entropy Explorationcited by 35
  3. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 29
  4. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  5. 2023Maximum State Entropy Exploration using Predecessor and Successor Representationscited by 23
  6. 2023Submodular Reinforcement Learningcited by 23
  7. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  8. 2022Pretraining in Deep Reinforcement Learning: A Surveycited by 18
  9. 2021Unsupervised Reinforcement Learning in Multiple Environmentscited by 17
  10. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  11. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  12. 2021Learning Altruistic Behaviours in Reinforcement Learning without External Rewardscited by 8
15 more
  1. 2024How to Explore with Belief: State Entropy Maximization in POMDPscited by 6
  2. 2024Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstractioncited by 6
  3. 2021MARL with General Utilities via Decentralized Shadow Reward Actor-Criticcited by 5
  4. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  5. 2024Strongly-polynomial time and validation analysis of policy gradient methodscited by 5
  6. 2021Adaptive Multi-Goal Explorationcited by 4
  7. 2025Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Storycited by 4
  8. 2021Markov Decision Processes with Long-Term Average Constraintscited by 3
  9. 2023Policy Gradient with Tree Expansioncited by 3
  10. 2025Near-Optimal Clustering in Mixture of Markov Chainscited by 1
  11. 2026From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPscited by 1
  12. 2026Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluationcited by 1
  13. 2023Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigationcited by 0
  14. 2025A Theoretical Analysis of State Similarity Between Markov Decision Processescited by 0
  15. 2026kappa-Explorer: A Unified Framework for Active Model Estimation in MDPscited by 0