Submodular Multi-Agent Reinforcement Learning for Effective Online Distributed Task Allocation

This paper studies multi-agent reinforcement learning with submodular team utilities, which models scenarios where $N$ agents solve a non-additive task allocation problem in a distributed manner online. Since each agent selects one action from a local categorical distribution at each time step, feasible joint actions form a partition matroid over agent-action pairs. The standard continuous relaxation of set utility functions, the Multilinear Extension, does not encode categorical constraints on factorized policies and may yield inconsistent gradient estimation. To remedy this, we propose the \emph{Partition Multilinear Extension}, a continuous relaxation that equals the expected team utility with factorized categorical policies under partition matroid constraint. We prove that submodular difference rewards provide unbiased PME marginal-gradient information and induce a stagewise score-function policy-gradient estimator for factorized categorical policies. Building on these results, we propose \emph{SubMAPG}, a centralized training with decentralized execution (CTDE) multi-agent policy-gradient framework that implements submodular difference-reward training signals and masked categorical policies for partition-feasible decentralized execution. For the associated PME marginal-space projected stochastic-gradient dynamics, we establish a stagewise $\frac{1}{2}$-approximation guarantee and sublinear dynamic regret under slowly varying environments, measured by the path length of the optimal PME marginals. Finally, to handle open systems where agents and targets may leave and join over time (e.g., modeling failure and recovery of robots or smart sensors), we implement SubMAPG with a graph neural network policy model. Numerical 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.