A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach

📄 arXiv: 2407.18878v3 📥 PDF

作者: Swetha Ganesh, Washim Uddin Mondal, Vaneet Aggarwal

分类: cs.LG

发布日期: 2024-07-26 (更新: 2025-05-05)

备注: Accepted to the 42nd International Conference on Machine Learning (ICML), 2025

💡 一句话要点

提出MLMC-NAC算法，实现平均奖励强化学习$\tilde{\mathcal{O}}(1/\sqrt{T})$全局收敛，无需混合和命中时间知识。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 平均奖励强化学习 Actor-Critic 多层蒙特卡洛 全局收敛 自然梯度下降

📋 核心要点

  1. 现有平均奖励强化学习方法在状态空间大时扩展性差，迭代复杂度高，且依赖于混合时间和命中时间的先验知识。
  2. 论文提出一种基于多层蒙特卡洛的自然Actor-Critic (MLMC-NAC)算法，旨在解决上述问题，实现更快的全局收敛。
  3. 该算法在平均奖励MDP上实现了$\tilde{\mathcal{O}}(1/\sqrt{T})$的全局收敛速度，且不依赖于混合和命中时间的知识，适用于无限状态空间。

📝 摘要（中文）

本文研究了具有通用策略参数化的平均奖励强化学习。现有最先进的(SOTA)保证要么是次优的，要么受到多个挑战的阻碍，包括相对于状态-动作空间大小的可扩展性差、高迭代复杂性以及对混合时间和命中时间的依赖。为了解决这些限制，我们提出了一种基于多层蒙特卡洛的自然Actor-Critic (MLMC-NAC)算法。我们的工作首次实现了平均奖励马尔可夫决策过程(MDP)的$\tilde{\mathcal{O}}(1/\sqrt{T})$全局收敛速度(其中$T$是时间范围)，而无需混合和命中时间的知识。此外，收敛速度不随状态空间的大小而变化，因此甚至适用于无限状态空间。

🔬 方法详解

问题定义：论文旨在解决平均奖励强化学习中的全局收敛问题。现有方法存在对状态-动作空间大小的依赖性，导致在大规模问题中表现不佳。此外，许多算法需要预先知道混合时间和命中时间等信息，这在实际应用中通常是不可行的。这些限制阻碍了平均奖励强化学习在复杂环境中的应用。

核心思路：论文的核心思路是利用多层蒙特卡洛方法来降低方差，并结合自然Actor-Critic算法来提高策略更新的效率。通过多层蒙特卡洛方法，可以有效地估计价值函数和策略梯度，从而加速学习过程。自然Actor-Critic算法则通过使用Fisher信息矩阵来调整策略更新的方向，从而提高收敛速度和稳定性。

技术框架：MLMC-NAC算法的整体框架如下： 1. 环境交互：Actor与环境交互，收集状态、动作、奖励等数据。 2. 多层蒙特卡洛估计：使用多层蒙特卡洛方法估计价值函数和策略梯度。 3. 自然Actor-Critic更新：使用估计的价值函数和策略梯度，通过自然梯度下降更新Actor的策略。 4. 重复迭代：重复以上步骤，直到策略收敛。

关键创新：该论文的关键创新在于将多层蒙特卡洛方法与自然Actor-Critic算法相结合，实现了平均奖励强化学习的$\tilde{\mathcal{O}}(1/\sqrt{T})$全局收敛速度，且无需混合和命中时间的知识。这是首次在平均奖励强化学习中实现如此快的收敛速度，并且算法的收敛速度不依赖于状态空间的大小，使其适用于无限状态空间。与现有方法相比，该算法具有更好的可扩展性和更强的适用性。

关键设计：MLMC-NAC算法的关键设计包括： 1. 多层蒙特卡洛采样：使用不同精度的模型进行采样，以降低方差。 2. 自然梯度下降：使用Fisher信息矩阵来调整策略更新的方向。 3. 步长调整：使用适当的步长来保证算法的收敛性。 4. 奖励归一化：对奖励进行归一化处理，以提高算法的稳定性。

📊 实验亮点

该论文提出的MLMC-NAC算法首次实现了平均奖励MDP的$\tilde{\mathcal{O}}(1/\sqrt{T})$全局收敛速度，且不依赖于混合和命中时间的知识。重要的是，该收敛速度不随状态空间的大小而变化，使其适用于无限状态空间，相较于现有算法有显著提升。

🎯 应用场景

该研究成果可广泛应用于需要长期策略优化的领域，如机器人控制、资源管理、交通调度和金融交易等。通过更快的收敛速度和更强的可扩展性，该算法能够有效地解决复杂环境下的平均奖励强化学习问题，提升决策效率和系统性能，具有重要的实际应用价值和未来发展潜力。

📄 摘要（原文）

This work examines average-reward reinforcement learning with general policy parametrization. Existing state-of-the-art (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and dependence on knowledge of mixing times and hitting times. To address these limitations, we propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve a global convergence rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$ for average-reward Markov Decision Processes (MDPs) (where $T$ is the horizon length), without requiring the knowledge of mixing and hitting times. Moreover, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces.