Average-reward reinforcement learning in semi-Markov decision processes via relative value iteration

📄 arXiv: 2512.06218v1 📥 PDF

作者: Huizhen Yu, Yi Wan, Richard S. Sutton

分类: cs.LG, math.OC

发布日期: 2025-12-05

备注: 24 pages. This paper presents the reinforcement-learning material previously contained in version 2 of arXiv:2409.03915, which is now being split into two stand-alone papers. Minor corrections and improvements to the main results have also been made in the course of this reformatting

💡 一句话要点

提出基于相对值迭代的平均奖励SMDP强化学习算法，并证明其收敛性。

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

关键词: 强化学习 平均奖励 半马尔可夫决策过程 相对值迭代 异步随机逼近

📋 核心要点

  1. 现有平均奖励强化学习方法在半马尔可夫决策过程（SMDP）中面临收敛性挑战，尤其是在异步更新的情况下。
  2. 本文提出了一种基于异步随机逼近的RVI Q-learning算法，利用Borkar-Meyn框架保证算法的收敛性。
  3. 通过引入新的单调性条件，扩展了算法框架，并提供了RVI Q-learning稳定性和收敛性的新颖分析。

📝 摘要（中文）

本文将作者近期关于Borkar-Meyn框架下异步随机逼近(SA)的研究成果应用于平均奖励半马尔可夫决策过程(SMDP)中的强化学习。我们证明了Schweitzer经典相对值迭代算法的异步SA模拟，即RVI Q-learning，在有限空间、弱连通SMDP中的收敛性。特别地，我们证明了该算法几乎必然收敛到平均奖励最优性方程解的紧致连通子集，并在额外的步长和异步条件下收敛到唯一的、依赖于样本路径的解。此外，为了充分利用SA框架，我们为RVI Q-learning中估计最优奖励率引入了新的单调性条件。这些条件极大地扩展了先前考虑的算法框架，并通过RVI Q-learning的稳定性和收敛性分析中的新颖论证来解决。

🔬 方法详解

问题定义：论文旨在解决平均奖励半马尔可夫决策过程(SMDP)中的强化学习问题。现有方法，特别是异步更新的强化学习算法，在SMDP中难以保证收敛性，这限制了它们在实际问题中的应用。

核心思路：论文的核心思路是将异步随机逼近(SA)理论应用于Schweitzer的相对值迭代(RVI)算法，构建RVI Q-learning算法。通过Borkar-Meyn框架，可以严格证明该算法在特定条件下的收敛性，从而克服传统方法的收敛性问题。

技术框架：整体框架基于异步随机逼近理论，将RVI算法转化为一个随机逼近过程。主要模块包括：状态-动作值函数(Q函数)的异步更新、平均奖励率的估计以及步长的选择。算法通过不断迭代更新Q函数和平均奖励率，最终收敛到最优策略。

关键创新：论文的关键创新在于将异步随机逼近理论与RVI算法相结合，并引入了新的单调性条件来估计最优奖励率。这些单调性条件扩展了算法框架，并为RVI Q-learning的稳定性和收敛性分析提供了新的视角。此外，证明了在弱连通SMDP下算法的收敛性。

关键设计：算法的关键设计包括：合适的步长选择策略，以保证随机逼近过程的收敛性；Q函数的异步更新方式，允许在不同时间更新不同的状态-动作对；以及新的单调性条件，用于更有效地估计平均奖励率。这些设计共同保证了算法在SMDP环境下的稳定性和收敛性。

📊 实验亮点

论文证明了RVI Q-learning算法在有限空间、弱连通SMDP中的收敛性，并给出了收敛到平均奖励最优性方程解的紧致连通子集的条件。通过引入新的单调性条件，扩展了算法框架，并为RVI Q-learning的稳定性和收敛性分析提供了新的视角。

🎯 应用场景

该研究成果可应用于各种需要长期决策优化的场景，例如机器人导航、资源调度、排队系统优化等。通过学习最优的平均奖励策略，可以提高系统的长期性能和效率，具有重要的实际应用价值和潜力。

📄 摘要（原文）

This paper applies the authors' recent results on asynchronous stochastic approximation (SA) in the Borkar-Meyn framework to reinforcement learning in average-reward semi-Markov decision processes (SMDPs). We establish the convergence of an asynchronous SA analogue of Schweitzer's classical relative value iteration algorithm, RVI Q-learning, for finite-space, weakly communicating SMDPs. In particular, we show that the algorithm converges almost surely to a compact, connected subset of solutions to the average-reward optimality equation, with convergence to a unique, sample path-dependent solution under additional stepsize and asynchrony conditions. Moreover, to make full use of the SA framework, we introduce new monotonicity conditions for estimating the optimal reward rate in RVI Q-learning. These conditions substantially expand the previously considered algorithmic framework and are addressed through novel arguments in the stability and convergence analysis of RVI Q-learning.