Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
Machine Learning
Summary
The authors study how to quickly find the best way to act in a decision-making process where outcomes follow fixed rules and rewards are predictable. They focus on a particular algorithm called Navigate and Stop (NaS) that was known to work well over a long time but lacked precise short-term performance guarantees. The authors provide the first detailed analysis showing how the speed of finding the best policy depends not only on general difficulty measures but also on the structure and connections within the decision process itself. This helps better understand what affects the time it takes to confidently identify the best actions.
Authors
Joseph Lazzaro, Alessio Russo, Aldo Pacchiano
Abstract
In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning. This is an active sequential hypothesis testing problem in which the learner's objective is to identify an optimal policy in a Markov Decision Process (MDP) with high confidence, while minimizing the expected sample complexity to do so. We consider an online setting with deterministic rewards, where the agent must strategically navigate through the MDP in order to effectively explore. Previous works in the literature have provided asymptotically optimal methods for BPI, such as the Navigate and Stop (NaS) algorithm and its variants, however existing analysis remains asymptotic. In this work, we fill that gap by providing the first non-asymptotic sample complexity guarantees for NaS, showing that its sample complexity depends not only on the characteristic time, but also on the connectivity of the underlying MDP, the curvature of the optimal characteristic time, and other instance-dependent quantities. We identify these additional attributes and make explicit their contributions to the overall sample complexity.