Navigating to the Best Policy in Markov Decision Processes

Abstract

We investigate the classical active pure exploration problem in Markov Decision Processes, where the agent sequentially selects actions and, from the resulting system trajectory, aims at identifying the best policy as fast as possible. We propose a problem-dependent lower bound on the average number of steps required before a correct answer can be given with probability at least $1-\delta$. We further provide the first algorithm with an instance-specific sample complexity in this setting. This algorithm addresses the general case of communicating MDPs; we also propose a variant with a reduced exploration rate (and hence faster convergence) under an additional ergodicity assumption. This work extends previous results relative to the \emph{generative setting}~\cite{pmlr-v139-marjani21a}, where the agent could at each step query the random outcome of any (state, action) pair. In contrast, we show here how to deal with the \emph{navigation constraints}, induced by the \emph{online setting}. Our analysis relies on an ergodic theorem for non-homogeneous Markov chains which we consider of wide interest in the analysis of Markov Decision Processes.

References in corpus (10)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• Optimal Best Arm Identification with Fixed Confidence
• Fast active learning for pure exploration in reinforcement learning
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time
• Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Provably Correct Optimization and Exploration with Non-linear Policies

Cited by in corpus (2)

• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning
• Task-Optimal Exploration in Linear Dynamical Systems