arXiv:2409.19437v4 宣布类型: replace-cross 摘要：本文提出了一种新型终止标准，名为优势差距函数，适用于有限状态和行动马尔可夫决策过程（MDP）和强化学习（RL）。通过将这一优势差距函数引入步长规则的设计并推导出与最优策略的平稳状态分布无关的新线性收敛率，我们表明政策梯度方法可以在强多项式时间内解决MDP。据我们所知，这是首次为政策梯度方法建立如此强的收敛性质。此外，在随机环境下，仅能获得政策梯度的随机估计时，我们证明优势差距函数可为每个状态提供接近最优性的近似值，并在每个状态下表现出亚线性收敛率。在随机情况下，优势差距函数可以容易地进行估计，并且与可计算的政策值上界结合使用时，可以为政策梯度方法生成的解提供验证方法。因此，我们的发展为RL提供了有原则且可计算的最优性度量，而当前的做法往往依赖于算法间的比较或基线比较，缺乏最优性的证书。