Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation

Actor-critic (AC) 是强化学习中学习最优策略的一种强大方法，其中 critic 使用算法（例如带有函数逼近的时间差分学习）来评估当前策略，actor 利用来自 critic 的信息沿着近似梯度方向更新策略。本文提供了 AC 和 natural AC (NAC) 算法的最紧密的非渐近收敛界限。具体而言，现有研究表明 AC 收敛到静态点的 $\epsilon + \varepsilon_{\text{critic}}$ 邻域，具有已知的最佳样本复杂度 $\mathcal{O}(\epsilon^{-2})$（加上对数因子），而 NAC 收敛到全局最优解的 $\epsilon + \varepsilon_{\text{critic}} + \sqrt{\varepsilon_{\text{actor}}}$ 邻域，具有已知的最佳样本复杂度 $\mathcal{O}(\epsilon^{-3})$，其中 $\varepsilon_{\text{critic}}$ 是 critic 的逼近误差，$\varepsilon_{\text{actor}}$ 是由参数化策略类的不充分表达能力引起的逼近误差。本文分析了具有兼容函数逼近的 AC 和 NAC 算法的收敛性。我们的分析消除了误差界限中的 $\varepsilon_{\text{critic}}$ 项，同时仍然实现了已知的最佳样本复杂度。此外，我们专注于具有单个马尔可夫样本轨迹的具有挑战性的单循环设置。我们的主要技术创新在于分析由于策略相关和时变的兼容函数逼近在 critic 中引起的随机偏差，并处理由于单个马尔可夫样本轨迹的非遍历性而导致的 MDP 非遍历性。附录中还提供了数值结果。

本论文旨在提供Actor-Critic算法的最紧密的非渐进收敛界限，并分析其解决的问题是如何在单个马尔可夫采样轨迹的情况下，利用兼容函数逼近解决MDP问题。

本文提出了一种新的方法，通过分析策略相关的函数逼近的随机偏差和MDP的非遍历性来消除演员-评论家算法中的批评家的逼近误差项，从而实现了更好的收敛性能。

本文提供了Actor-Critic算法和Natural Actor-Critic算法的最紧密的非渐进收敛界限，并分析了兼容函数逼近的随机偏差和MDP的非遍历性。实验结果表明，该方法在某些情况下比现有的方法更有效。

在相关研究方面，最近的研究集中在Actor-Critic算法和其变体上，例如Natural Actor-Critic算法。