Double Successive Over-Relaxation Q-Learning with an Extension to Deep Reinforcement Learning

📄 arXiv: 2409.06356v2 📥 PDF

作者: Shreyas S R

分类: cs.LG, cs.AI

发布日期: 2024-09-10 (更新: 2025-05-15)

期刊: IEEE Transactions on Neural Networks and Learning Systems 2025

DOI: 10.1109/TNNLS.2025.3576581

💡 一句话要点

提出双重逐次超松弛Q学习算法，加速收敛并降低过估计偏差，并扩展到深度强化学习。

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

关键词: 强化学习 Q学习 逐次超松弛 双重Q学习 无模型学习 深度强化学习 过估计偏差

📋 核心要点

  1. 传统Q学习在折扣因子接近1时收敛缓慢，SOR Q学习虽能加速收敛，但依赖转移概率且存在过估计偏差。
  2. 论文提出一种基于采样的无模型双重SOR Q学习算法，旨在降低偏差并加速收敛，使其更适用于实际问题。
  3. 理论分析和实验结果表明，该算法在表格型和深度强化学习环境中均优于传统SOR Q学习，降低了偏差。

📝 摘要（中文）

Q学习是强化学习中一种广泛使用的算法，但其收敛速度可能很慢，尤其是在折扣因子接近于1时。逐次超松弛(SOR)Q学习通过引入松弛因子来加速收敛，但存在两个主要限制：在表格设置中，松弛参数依赖于转移概率，使其并非完全无模型，并且存在过估计偏差。为了克服这些限制，我们提出了一种基于采样的无模型双重SOR Q学习算法。理论和实验表明，该算法比SOR Q学习偏差更小。此外，在表格设置中，讨论了在迭代有界假设下的收敛性分析。所提出的算法使用深度强化学习扩展到大规模问题。最后，使用轮盘赌和网格世界环境比较了所提出算法的表格版本，而深度强化学习版本在最大化偏差示例和OpenAI Gym环境中进行了测试。

🔬 方法详解

问题定义：Q学习是一种常用的强化学习算法，但在高折扣因子的情况下收敛速度慢。SOR Q学习通过引入松弛因子加速收敛，但其松弛参数依赖于环境的转移概率，使其在一定程度上不是无模型的。此外，SOR Q学习还存在过估计偏差，影响学习效果。

核心思路：论文的核心思路是提出一种双重SOR Q学习算法，该算法基于采样，无需知道环境的转移概率，从而实现真正的无模型学习。同时，通过双重估计来降低Q值的过估计偏差，提高学习的稳定性和准确性。

技术框架：该算法首先使用采样数据更新Q值，然后使用SOR方法加速Q值的更新过程。为了降低过估计偏差，采用了双重Q学习的思想，即使用两个独立的Q函数来估计Q值，并选择较小的Q值进行更新。该算法可以分为表格型和深度强化学习两种实现方式。表格型适用于状态空间和动作空间较小的情况，而深度强化学习则适用于大规模问题。

关键创新：该算法的关键创新在于结合了SOR方法和双重Q学习的思想，提出了一种新的双重SOR Q学习算法。该算法不仅可以加速Q值的收敛速度，还可以降低过估计偏差，提高学习的稳定性和准确性。此外，该算法是无模型的，不需要知道环境的转移概率。

关键设计：在表格型实现中，需要设置松弛因子，该参数影响收敛速度。在深度强化学习实现中，可以使用各种深度神经网络作为Q函数的近似器，例如多层感知机、卷积神经网络等。损失函数可以使用均方误差损失函数，优化器可以使用Adam等常用的优化器。具体网络结构和参数需要根据具体问题进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的双重SOR Q学习算法在表格型环境中（轮盘赌和网格世界）和深度强化学习环境中（最大化偏差示例和OpenAI Gym）均优于传统的SOR Q学习算法。尤其是在存在过估计偏差的环境中，该算法的优势更加明显。具体的性能提升数据未知，但论文强调了该算法在降低偏差方面的有效性。

🎯 应用场景

该研究成果可应用于各种需要快速学习和高精度决策的强化学习任务中，例如机器人控制、游戏AI、自动驾驶、资源调度等。通过加速Q学习的收敛速度和降低过估计偏差，可以提高智能体的学习效率和决策质量，使其更好地适应复杂环境。

📄 摘要（原文）

Q-learning is a widely used algorithm in reinforcement learning (RL), but its convergence can be slow, especially when the discount factor is close to one. Successive Over-Relaxation (SOR) Q-learning, which introduces a relaxation factor to speed up convergence, addresses this issue but has two major limitations: In the tabular setting, the relaxation parameter depends on transition probability, making it not entirely model-free, and it suffers from overestimation bias. To overcome these limitations, we propose a sample-based, model-free double SOR Q-learning algorithm. Theoretically and empirically, this algorithm is shown to be less biased than SOR Q-learning. Further, in the tabular setting, the convergence analysis under boundedness assumptions on iterates is discussed. The proposed algorithm is extended to large-scale problems using deep RL. Finally, the tabular version of the proposed algorithm is compared using roulette and grid world environments, while the deep RL version is tested on a maximization bias example and OpenAI Gym environments.