Submodular Multi-Agent Policy Learning for Online Distributed Task Allocation in Open Multi-Agent Systems

📄 arXiv: 2605.13269v1 📥 PDF

作者: Jing Liu, Yangyang Yang, Luca Ballotta, Fangfei Li, Yang Tang, Ruggero Carli

分类: eess.SY

发布日期: 2026-05-13

💡 一句话要点

提出SubMAPG算法，解决开放多智能体系统中在线分布式任务分配问题。

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

关键词: 多智能体强化学习 在线任务分配 子模优化 策略梯度 图神经网络

📋 核心要点

  1. 现有方法在多智能体在线任务分配中，无法有效处理智能体策略的类别特性，导致策略学习与实际执行不匹配。
  2. 论文提出划分多线性扩展（PME）来解决策略不匹配问题，并设计了基于子模差分奖励的策略梯度算法SubMAPG。
  3. 实验表明，SubMAPG在多机器人覆盖和多目标跟踪任务中，性能优于现有局部贪婪和共享奖励方法。

📝 摘要（中文）

本文研究了具有子模团队效用的多智能体强化学习，用于在线分布式任务分配。在此设置中，每个智能体从局部类别策略中选择一个动作，因此可行的联合动作构成智能体-动作对上的划分拟阵。经典的多线性扩展使用独立的伯努利采样，因此与分散智能体执行的类别策略不匹配。为了解决这种不匹配，我们引入了划分多线性扩展（PME），这是一种连续松弛，其值等于因子化类别策略下的预期团队效用。我们证明了子模差分奖励提供了无偏的PME边际梯度信息，并产生了一个阶段性的得分函数策略梯度估计器。基于这种联系，我们提出了SubMAPG，一个具有掩码类别策略和子模差分奖励训练信号的集中训练分散执行策略梯度框架。对于相关的PME边际空间投影随机梯度动态，我们证明了在缓慢变化的环境中，阶段性的1/2近似保证和次线性动态后悔，通过最优PME边际的路径长度来衡量。为了处理具有时变智能体和目标的开放系统，我们使用图神经网络策略实例化SubMAPG。在多机器人覆盖和多目标跟踪实验中，SubMAPG优于局部贪婪和共享奖励基线，并且与集中式近视贪婪策略具有竞争力。

🔬 方法详解

问题定义：论文旨在解决开放多智能体系统中在线分布式任务分配问题。现有方法，特别是基于多线性扩展的方法，在处理智能体采用类别策略（即每个智能体只能选择一个动作）时存在不足。传统的多线性扩展依赖于独立的伯努利采样，这与实际中智能体执行的类别策略不符，导致策略学习和执行之间存在差异。这种差异会影响学习到的策略的有效性。

核心思路：论文的核心思路是引入划分多线性扩展（Partition Multilinear Extension, PME），这是一种专门为类别策略设计的连续松弛方法。PME的值等于因子化类别策略下的预期团队效用，从而弥合了策略学习和执行之间的差距。此外，论文利用子模性，通过子模差分奖励来提供无偏的PME边际梯度信息，用于指导策略学习。

技术框架：论文提出的SubMAPG框架采用集中训练分散执行（CTDE）的范式。整体流程如下：1) 在集中训练阶段，使用子模差分奖励作为训练信号，利用PME边际梯度信息更新智能体的策略。2) 在分散执行阶段，每个智能体根据学习到的局部类别策略独立地选择动作。3) 为了处理开放系统，SubMAPG使用图神经网络（GNN）来编码智能体和目标的状态信息，并学习相应的策略。

关键创新：论文的关键创新在于提出了划分多线性扩展（PME），这是一种专门为类别策略设计的连续松弛方法。与传统的多线性扩展相比，PME能够更准确地反映智能体实际执行的类别策略，从而提高了策略学习的有效性。此外，利用子模差分奖励来提供无偏的PME边际梯度信息也是一个重要的创新。

关键设计：SubMAPG的关键设计包括：1) 使用掩码类别策略，确保每个智能体只能选择一个动作。2) 使用子模差分奖励作为训练信号，鼓励智能体选择能够最大化团队效用的动作。3) 使用图神经网络（GNN）来编码智能体和目标的状态信息，并学习相应的策略。4) 针对PME边际空间投影随机梯度动态，论文证明了阶段性的1/2近似保证和次线性动态后悔。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，SubMAPG在多机器人覆盖和多目标跟踪任务中，性能优于局部贪婪和共享奖励基线，并且与集中式近视贪婪策略具有竞争力。这验证了PME和子模差分奖励在多智能体在线任务分配中的有效性。具体性能提升数据未在摘要中给出，需查阅原文。

🎯 应用场景

该研究成果可应用于多机器人协同任务、智能交通调度、无线资源分配等领域。例如，在多机器人协同覆盖任务中，SubMAPG可以帮助机器人更有效地分配任务，提高覆盖效率。在智能交通调度中，SubMAPG可以用于优化车辆的行驶路线，减少交通拥堵。该研究对于提升多智能体系统的协作效率和鲁棒性具有重要意义。

📄 摘要（原文）

This paper studies multi-agent reinforcement learning with submodular team utilities for online distributed task allocation. In this setting, each agent selects one action from a local categorical policy, so feasible joint actions form a partition matroid over agent-action pairs. Classical multilinear extensions use independent Bernoulli sampling and therefore do not match the categorical policies executed by decentralized agents. To address this mismatch, we introduce the Partition Multilinear Extension (PME), a continuous relaxation whose value equals the expected team utility under factorized categorical policies. We prove that submodular difference rewards provide unbiased PME marginal-gradient information and yield a stagewise score-function policy-gradient estimator. Based on this connection, we propose SubMAPG, a centralized-training decentralized-execution policy-gradient framework with masked categorical policies and submodular difference-reward training signals. For the associated PME marginal-space projected stochastic-gradient dynamics, we prove a stagewise 1/2-approximation guarantee and sublinear dynamic regret in slowly varying environments, measured by the path length of the optimal PME marginals. To handle open systems with time-varying agents and targets, we instantiate SubMAPG with graph neural network policies. Experiments on multi-robot coverage and multi-target tracking show that SubMAPG outperforms local greedy and shared-reward baselines and is competitive with centralized myopic greedy strategies.