提出一种基于图结构的值函数,解决多智能体强化学习中的信用分配难题。
Factored Value Functions for Graph-Based Multi-Agent Reinforcement Learning
- 通过图上扩散机制将奖励分布到各智能体,实现结构化信用分配
- 在消防与分布式计算任务中,平均奖励提升最高达11%
- 适合通信成本敏感的去中心化多智能体系统
信用分配是多智能体强化学习的核心挑战,尤其在具有结构化局部交互的大规模系统中。图基马尔可夫决策过程(GMDPs)通过影响图刻画此类场景,但传统价值函数与该结构不匹配:全局值函数提供的单个智能体学习信号较弱,而现有局部构造难以估计且在无限时域下表现不稳定。本文提出扩散值函数(DVF),一种针对GMDPs的因子化值函数,通过在影响图上结合时间折扣与空间衰减进行奖励扩散,为每个智能体分配一个值分量。我们证明DVF定义良好,存在贝尔曼不动点,并可通过平均性质分解全局折扣值。DVF可直接嵌入标准强化学习算法,利用图神经网络实现可扩展估计。基于DVF,我们提出扩散A2C(DA2C)和稀疏消息传递策略网络——学习丢弃边的图神经网络(LD-GNN),用于在通信成本约束下学习去中心化算法。在消防救援基准和三个分布式计算任务(向量图着色及两类发射功率优化问题)中,DA2C始终优于局部与全局基线,平均奖励提升最高达11%。
原文摘要 · Abstract (English)
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%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。