Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
Joseph Lazzaro, Alessio Russo, Aldo Pacchiano
stat.ML, cs.LG
Submitted: 2026-07-19
Comments: 64 pages, 2 figures
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning.
Terminology
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.
Sources
- Policy Testing in Markov Decision Processes
- The regret lower bound for communicating Markov Decision Processes
- Thresholding Bandit for Dose-ranging: The Impact of Monotonicity
- Optimal Best Arm Identification under Differential Privacy
- Non-Asymptotic Analysis of (Sticky) Track-and-Stop
- Pure Exploration with Infinite Answers
- Adaptive Exploration for Multi-Reward Multi-Policy Evaluation
- Pure Exploration with Feedback Graphs
- Asymptotically Optimal Sequential Testing with Markovian Data
Related papers
- Behavior of prediction performance metrics with rare events
- Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
- A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
- Scalable Posterior Uncertainty for Flexible Density-Based Clustering
- A Transport Geometry of Benign Overfitting
- Efficient quadratic entropy with distance sketches