这篇论文给NaS算法提供了非渐近保证，解释了样本复杂度受哪些因素影响，做强化学习理论的朋友可以看看。
本文研究在线表格强化学习中的最佳策略识别问题，提出首个非渐近样本复杂度保证。算法Navigate and Stop (NaS)的样本复杂度依赖于特征时间、MDP的连通性、最优特征时间的曲率等实例相关量。研究填补了NaS算法在非渐近分析上的空白，明确了各因素对样本复杂度的贡献。
Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
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.