Active Exploration in Markov Decision Processes

Abstract

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.

Cited by in corpus (11)

• Beyond Ads: Sequential Decision-Making Algorithms in Law and Public Policy
• Constrained episodic reinforcement learning in concave-convex and knapsack settings
• Exploration-Exploitation Trade-off in Reinforcement Learning on Online Markov Decision Processes with Global Concave Rewards
• MARL with General Utilities via Decentralized Shadow Reward Actor-Critic
• A Successive-Elimination Approach to Adaptive Robotic Sensing
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Active Model Estimation in Markov Decision Processes
• Markov Decision Processes with Long-Term Average Constraints
• Adaptive Multi-Goal Exploration
• Adaptive Sampling for Estimating Distributions: A Bayesian Upper Confidence Bound Approach
• Learning Multiple Markov Chains via Adaptive Allocation