首个从单条轨迹学习平均奖励MDP策略的有限样本方法
Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
- 基于单条轨迹分析弱连通MDP动态，设计新无模型算法
- 值函数与策略方法分别达到1/ε²和1/ε⁴的样本复杂度
- 无需先验知识即可适用于连通MDP，适合强化学习初学者
尽管已有大量研究分析了折扣累积奖励MDP的样本复杂度，但针对平均奖励MDP的有限样本分析仍十分有限，且多数工作依赖于如遍历性或生成模型访问等严格假设。本文首次为弱连通平均奖励MDP建立了从单条轨迹出发的有限样本复杂度保证。我们研究了弱连通MDP中单条轨迹的动力学特性，并据此提出新颖的无模型方法。值得注意的是，我们的值函数方法与策略方法分别在弱连通MDP中实现了$ ilde{O}(1/\varepsilon^2)$和$ ilde{O}(1/\varepsilon^4)$的有限样本复杂度。此外，我们还提出了首个在连通MDP中无需先验问题相关量的无模型方法。
原文摘要 · Abstract (English)
While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of $\widetilde{O}(1/\varepsilon^2)$ and $\widetilde{O}(1/\varepsilon^4)$ from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we introduce the first model-free method that requires no prior knowledge of problem-dependent quantities for communicating MDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。