Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

In online Reinforcement Learning, the Best Policy Identification (BPI) problem asks how an agent can identify an optimal policy with high confidence using the minimum number of samples. While previous work established the Navigate-and-Stop (NaS) algorithm as asymptotically optimal, these guarantees only hold in the limit as the confidence parameter approaches zero. This paper addresses the gap in understanding the algorithm's performance in finite-time, non-asymptotic settings.

The authors analyze the NaS algorithm, which operates by iteratively estimating the MDP's transition dynamics, computing an optimal visitation frequency (allocation) based on that estimate, and navigating the environment to collect data. To provide non-asymptotic bounds, the authors:

1. Establish a finite-confidence sample complexity upper bound that accounts for the cost of estimating transitions and tracking optimal visitation frequencies.
2. Introduce a sharpness analysis to characterize how the flatness of the objective function near optimal allocations affects the convergence rate.
3. Develop technical tools to handle the stability of optimal allocation selectors under transition perturbations and the concentration of empirical visitation frequencies in non-homogeneous Markov chains.

The study proves that the sample complexity of the NaS algorithm depends on several instance-dependent quantities beyond the characteristic time, including the connectivity of the MDP, the mixing properties of the induced policies, and the geometry of the optimal allocation set. The authors provide an explicit expansion for the expected sample complexity, showing that it scales with the inverse of the confidence parameter while incorporating terms that account for the transient instability of sampling distributions when data is scarce.