mlsanityData to 14 Oct 2026

Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

arXiv 2607.17201 ↗First posted 19 Jul 2026stat.ML cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 9 of its 35 references that are in the map. First posted on arXiv 19 Jul 2026.

Builds on

9 of 35 references.

References · 9

  1. 2017Thresholding Bandit for Dose-ranging: The Impact of Monotonicitycited by 16
  2. 2025Adaptive Exploration for Multi-Reward Multi-Policy Evaluationcited by 6
  3. 2025The regret lower bound for communicating Markov Decision Processescited by 4
  4. 2025Pure Exploration with Feedback Graphscited by 4
  5. 2025Policy Testing in Markov Decision Processescited by 2
  6. 2026Asymptotically Optimal Sequential Testing with Markovian Datacited by 2
  7. 2025Pure Exploration with Infinite Answerscited by 1
  8. 2025Non-Asymptotic Analysis of (Sticky) Track-and-Stopcited by 1
  9. 2025Optimal Best Arm Identification under Differential Privacycited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Average-Reward Policy Identification from a Single Continuing Trajectorycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  2. 2024Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning
  3. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
  4. 2026A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics
  5. 2025Improving Reinforcement Learning Sample-Efficiency using Local Approximation
  6. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
  7. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  8. 2025The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective