将均场控制扩展到稀疏图,实现高效且理论可靠的多智能体决策。
Mean-Field Control on Sparse Graphs: From Local Limits to GNNs via Neighborhood Distributions
- 用邻域分布表示系统状态,捕捉局部异质性。
- 证明有限时域下策略仅依赖于(T-t)跳邻域,实现可计算性。
- 为图神经网络在强化学习中的应用提供理论支撑,适合复杂网络研究者。
均场控制(MFC)为多智能体系统提供了应对维数灾难的可扩展方案,但传统方法依赖于密集全连接交互的交换性假设。本文提出一种在大规模稀疏图上进行MFC的严格框架。我们将系统状态重新定义为带装饰的根邻域上的概率测度,有效捕捉局部异质性。核心贡献是为此设定建立了可扩展强化学习的理论基础。我们证明了时域相关的局部性:在有限时域问题中,时间t处智能体的最优策略仅依赖于其(T-t)跳邻域。该结果使无穷维控制问题变得可处理,并支撑了一个在邻域分布提升空间上的新型动态规划原理(DPP)。此外,我们从理论上和实验上验证了图神经网络(GNNs)在此场景下用于演员-评论家算法的有效性。该框架自然恢复经典MFC作为退化情形,同时支持在复杂稀疏拓扑上的高效、理论可信控制。
原文摘要 · Abstract (English)
Mean-field control (MFC) offers a scalable solution to the curse of dimensionality in multi-agent systems but traditionally hinges on the restrictive assumption of exchangeability via dense, all-to-all interactions. In this work, we bridge the gap to real-world network structures by proposing a rigorous framework for MFC on large sparse graphs. We redefine the system state as a probability measure over decorated rooted neighborhoods, effectively capturing local heterogeneity. Our central contribution is a theoretical foundation for scalable reinforcement learning in this setting. We prove horizon-dependent locality: for finite-horizon problems, an agent's optimal policy at time t depends strictly on its (T-t)-hop neighborhood. This result renders the infinite-dimensional control problem tractable and underpins a novel Dynamic Programming Principle (DPP) on the lifted space of neighborhood distributions. Furthermore, we formally and experimentally justify the use of Graph Neural Networks (GNNs) for actor-critic algorithms in this context. Our framework naturally recovers classical MFC as a degenerate case while enabling efficient, theoretically grounded control on complex sparse topologies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。