Factored Value Functions for Graph-Based Multi-Agent Reinforcement Learning

📄 arXiv: 2601.11401v1 📥 PDF

作者: Ahmed Rashwan, Keith Briggs, Chris Budd, Lisa Kreusser

分类: cs.LG

发布日期: 2026-01-16

💡 一句话要点

提出扩散价值函数（DVF）用于解决图结构多智能体强化学习中的信用分配问题

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

关键词: 多智能体强化学习 图神经网络 信用分配 扩散价值函数 分布式计算

📋 核心要点

  1. 多智能体强化学习中，大规模图结构下的信用分配是难题，现有全局价值函数信号弱，局部价值函数难以估计。
  2. 论文提出扩散价值函数（DVF），通过在影响图上传播奖励来分解价值，为每个智能体分配价值分量。
  3. 实验表明，基于DVF的DA2C算法在多个任务中优于局部和全局评论家网络基线，平均奖励提升高达11%。

📝 摘要（中文）

信用分配是多智能体强化学习（MARL）中的一个核心挑战，尤其是在具有结构化局部交互的大规模系统中。基于图的马尔可夫决策过程（GMDPs）通过影响图捕获此类设置，但标准评论家网络与此结构不太一致：全局价值函数提供微弱的个体智能体学习信号，而现有的局部结构难以估计，并且在无限视界设置中表现不佳。我们引入了扩散价值函数（DVF），这是一种用于GMDPs的分解价值函数，它通过在具有时间折扣和空间衰减的影响图上传播奖励，为每个智能体分配一个价值分量。我们证明了DVF是良好定义的，允许贝尔曼不动点，并通过平均属性分解全局折扣价值。DVF可以用作标准RL算法中的即插即用评论家网络，并可以使用图神经网络进行可扩展的估计。在DVF的基础上，我们提出了Diffusion A2C（DA2C）和一个稀疏消息传递actor，即Learned DropEdge GNN（LD-GNN），用于在通信成本下学习分散式算法。在消防基准和三个分布式计算任务（向量图着色和两个传输功率优化问题）中，DA2C始终优于局部和全局评论家网络基线，平均奖励提高了高达11%。

🔬 方法详解

问题定义：在图结构的MARL环境中，如何有效地进行信用分配是一个关键问题。传统的全局价值函数无法提供针对每个智能体的有效学习信号，而局部价值函数则难以准确估计，尤其是在无限视界的情况下。现有的方法难以兼顾学习效率和性能。

核心思路：论文的核心思路是利用图结构信息，通过扩散的方式将奖励分配给各个智能体。具体来说，就是设计一种扩散价值函数（DVF），它能够根据智能体在图中的位置和影响，将全局奖励分解为个体价值分量。这种分解方式既考虑了全局信息，又能够为每个智能体提供更具针对性的学习信号。

技术框架：整体框架包括以下几个主要部分：1）定义基于图的马尔可夫决策过程（GMDP）；2）引入扩散价值函数（DVF），作为critic网络；3）提出Diffusion A2C（DA2C）算法，结合DVF进行训练；4）设计稀疏消息传递actor，即Learned DropEdge GNN（LD-GNN），用于学习分散式策略。整个流程是，智能体通过LD-GNN生成动作，环境给出奖励，DVF评估价值，DA2C更新策略和价值函数。

关键创新：最重要的技术创新点在于扩散价值函数（DVF）的设计。DVF通过在影响图上传播奖励，实现了全局价值的分解，从而为每个智能体提供了更有效的学习信号。与传统的全局或局部价值函数相比，DVF能够更好地利用图结构信息，从而提高学习效率和性能。此外，LD-GNN的设计也考虑了通信成本，使得算法更适用于实际应用场景。

关键设计：DVF的关键设计包括：1）时间折扣因子，用于控制奖励的时间衰减；2）空间衰减因子，用于控制奖励在图上的传播范围；3）平均属性，保证DVF能够分解全局折扣价值。LD-GNN的关键设计包括：1）DropEdge机制，用于学习稀疏的通信连接；2）可学习的通信权重，用于控制消息传递的强度。DA2C算法使用标准的A2C框架，但将critic网络替换为DVF，并使用LD-GNN作为actor网络。

📊 实验亮点

实验结果表明，DA2C算法在消防基准和三个分布式计算任务（向量图着色和两个传输功率优化问题）中， consistently 优于局部和全局评论家网络基线，平均奖励提高了高达11%。这表明DVF能够有效地分解全局价值，并为每个智能体提供更有效的学习信号。LD-GNN的设计也使得算法在通信成本下具有更好的性能。

🎯 应用场景

该研究成果可应用于各种具有图结构交互的多智能体系统，例如：分布式计算、无线通信网络、交通控制、社交网络等。通过学习分散式的策略，可以有效地解决资源分配、优化控制等问题，提高系统的整体性能和效率。该方法在智能交通、智慧城市等领域具有广阔的应用前景。

📄 摘要（原文）

Credit assignment is a core challenge in multi-agent reinforcement learning (MARL), especially in large-scale systems with structured, local interactions. Graph-based Markov decision processes (GMDPs) capture such settings via an influence graph, but standard critics are poorly aligned with this structure: global value functions provide weak per-agent learning signals, while existing local constructions can be difficult to estimate and ill-behaved in infinite-horizon settings. We introduce the Diffusion Value Function (DVF), a factored value function for GMDPs that assigns to each agent a value component by diffusing rewards over the influence graph with temporal discounting and spatial attenuation. We show that DVF is well-defined, admits a Bellman fixed point, and decomposes the global discounted value via an averaging property. DVF can be used as a drop-in critic in standard RL algorithms and estimated scalably with graph neural networks. Building on DVF, we propose Diffusion A2C (DA2C) and a sparse message-passing actor, Learned DropEdge GNN (LD-GNN), for learning decentralised algorithms under communication costs. Across the firefighting benchmark and three distributed computation tasks (vector graph colouring and two transmit power optimisation problems), DA2C consistently outperforms local and global critic baselines, improving average reward by up to 11%.