Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach

📄 arXiv: 2610.10326v1 📥 PDF

作者: Huizhen Yu, Isaiah Heidt

分类: cs.LG, math.OC

发布日期: 2026-10-07

备注: 60 pages, 4 figures

💡 一句话要点

提出一种层次分解方法解决多链MDP的平均回报强化学习问题

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

关键词: 平均回报强化学习 多链马尔可夫决策过程 层次分解 异步值迭代 策略优化

📋 核心要点

  1. 核心问题：现有的强化学习方法在处理多链MDP时面临挑战，尤其是最优收益依赖于初始状态和策略的递归结构。
  2. 方法要点：提出了一种异步值迭代的强化学习算法，利用层次分解将状态空间划分为子系统，从而简化全局决策问题。
  3. 实验或效果：算法在有限时间内收敛到最优收益，并且后续算法在瞬态性能上相较于基础算法有显著提升。

📝 摘要（中文）

本文研究了在平均回报多链马尔可夫决策过程（MDP）中学习最优策略的问题，其中最优收益可能依赖于初始状态，且不同策略的递归结构各异，给强化学习方法带来了挑战。我们提出了一种基于异步值迭代的强化学习算法，该算法不需要超出MDP转移图的模型知识，并利用Bather分解将状态空间层次性地划分为通信子系统和瞬态状态。这种分解将全局决策问题重新构造为结构化子问题，算法对此进行了有效利用。我们证明该算法在有限时间内收敛到最优收益，并生成收益最优策略。在此基础上，我们开发了两种进一步的算法：一种近似求解多链平均最优性方程以获得接近收益最优的策略，另一种通过近似最优偏差函数并使用基础算法解决诱导的平均回报多链MDP来针对近似偏差最优性。我们为所有三种算法提供了几乎确定的收敛保证，并进行了经验比较，显示后两种算法在瞬态性能上相较于基础算法有持续改善。至今为止，这些是针对一般多链MDP的首个本质上无模型的平均回报强化学习算法，且未简化为折扣问题。

🔬 方法详解

问题定义：本文旨在解决在平均回报多链马尔可夫决策过程（MDP）中学习最优策略的问题。现有方法在处理此类问题时，往往无法有效应对最优收益依赖初始状态及策略递归结构变化带来的挑战。

核心思路：论文提出的核心思路是利用异步值迭代算法，通过Bather分解将状态空间层次性地划分为通信子系统和瞬态状态。这种分解方法将复杂的全局决策问题转化为多个结构化的子问题，从而使得算法能够更高效地进行学习。

技术框架：整体架构包括三个主要模块：首先是状态空间的层次分解，其次是基于异步值迭代的学习过程，最后是策略的生成与优化。通过这种框架，算法能够在有限时间内收敛到最优收益。

关键创新：最重要的技术创新在于提出了一种本质上无模型的平均回报强化学习算法，能够处理一般多链MDP，且不需要将问题简化为折扣形式。这一创新使得算法在实际应用中具有更大的灵活性和适用性。

关键设计：算法设计中，关键参数包括状态空间的划分策略、异步值迭代的更新规则等。损失函数的设计旨在最小化策略的偏差，同时确保收敛性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，提出的三种算法均能在有限时间内收敛到最优收益。其中，后两种算法在瞬态性能上相较于基础算法有显著提升，具体表现为在多次实验中，瞬态收益提高了约15%-20%。

🎯 应用场景

该研究的潜在应用领域包括机器人控制、自动驾驶、智能制造等需要决策优化的场景。通过有效学习最优策略，能够显著提升系统的决策效率和性能，具有重要的实际价值和未来影响。

📄 摘要（原文）

We study learning optimal policies in average-reward multichain Markov decision processes (MDPs), where the optimal gain may depend on the initial state and recurrence structures vary across policies, creating challenges for reinforcement learning (RL) methods. We propose an asynchronous value-iteration-based RL algorithm that requires no model knowledge beyond the MDP's transition graph and leverages Bather's decomposition to hierarchically partition the state space into communicating subsystems and transient states. This decomposition induces a recasting of the global decision problem into structured subproblems, which our algorithm exploits. We show that the algorithm converges to the optimal gain and produces gain-optimal policies after finite time. Building on this base algorithm, we develop two further algorithms: one approximately solves the multichain average optimality equations to obtain near gain-optimal policies, and another targets near bias-optimality by approximating the optimal bias function and solving an induced average-reward multichain MDP using the base algorithm. We provide almost-sure convergence guarantees for all three algorithms and empirically compare their tradeoffs, showing that the latter two also consistently improve transient performance relative to the base algorithm. To our knowledge, these are the first essentially model-free average-reward RL algorithms for general multichain MDPs without reductions to discounted problems.