首次给出导航停止算法的非渐近样本复杂度保证，揭示其性能受马尔可夫决策过程结构影响。
Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
- 提出非渐近分析框架，评估导航停止算法在有限步内的最优策略识别能力
- 证明样本复杂度依赖于特征时间、状态连通性及最优特征时间曲率等实例相关量
- 为在线强化学习中的策略识别提供可计算、可验证的理论保障，适合理论研究者
本文研究在线、表格型强化学习中的最优策略识别（BPI）问题。这是一个主动序列假设检验任务，目标是在高置信度下识别马尔可夫决策过程（MDP）中的最优策略，同时最小化所需样本数量。考虑确定性奖励的在线设置，智能体必须策略性地遍历MDP以有效探索。现有文献虽提出渐近最优方法（如导航与停止，NaS及其变体），但分析仍局限于渐近情形。本文填补该空白，首次为NaS算法提供非渐近样本复杂度保证，表明其样本复杂度不仅取决于特征时间，还受底层MDP连通性、最优特征时间曲率及其他实例相关量的影响。我们明确识别这些因素，并量化其对整体样本复杂度的贡献。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。