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

Jing Liu; Luca Ballotta; Yangyang Yang; Fangfei Li; Yang Tang; Ruggero Carli

cs.MAAug 14, 2026

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

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

Organizations: School of Mathematics, East China University of Science and Technology, Shanghai 200237, China · Department of Information Engineering, University of Padova, 35131 Padova, Italy · School of Mathematics and the Key Laboratory of Smart Manufacturing in Energy Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China

Abstract

This paper studies policy learning for distributed task allocation in open multi-agent systems, where agents may join and leave in a time-varying fashion, with submodular stage team utilities. At each time, the active agents select actions from local categorical policies such that the feasible joint agent-action pairs form a partition matroid. Standard continuous relaxations of submodular set functions are based on independent Bernoulli sampling, making them inconsistent with agents' policies.To solve this mismatch, we propose the partition multilinear extension (PME), a policy-based relaxation whose continuous support matches feasible actions under categorical policies.We prove that the marginal gains of the stage utility provide an unbiased estimator of the gradient of the PME and that maximizing the PME over action distributions is equivalent to maximizing the stage utilities over agent actions, which are critical to devise principled policy gradient.Building on this, we design SubMAPL, a centralized-training decentralized-execution KL-mirror policy-learning method that uses local marginal gains as stochastic PME gradients during training. KL-mirror updates preserve categorical feasibility without Euclidean projection.In the case where agents run tabular-softmax policies, we introduce open policy migration and an open-system KL tracking variation to handle agent arrivals and departures. Using dynamic regret analysis, we establish a lower bound on the cumulative utility which accounts for the openness of the environment and for the gap between optimal stage-wise and global utilities. Simulations on multi-agent coverage demonstrate that SubMAPL outperforms policy-gradient and online-learning baselines.

Figures & tables

Symbol	Meaning
$\mathcal{M}$	Markov decision process in OMAS.
$\mathcal{N}_{t}$	Set of active agents at time $t$ .
$\mathcal{R}_{t}$	Set of agents active at both times $t-1$ and $t$ .
$\mathcal{N}_{t}^{\rm in}$	Set of agents arriving at time $t$ .
$\mathcal{N}_{t}^{\rm out}$	Set of agents departing at time $t$ .
$\mathcal{S}$	Global state space.

Table I : Main notation in the paper.

Figure 1: Open multi-agent task allocation with time-varying agent participation, dynamic tasks, and limited communication and sensing.

Figure 2: Coverage ratio under the controlled

5\to 2\to 5

active-agent profile. From left to right: uniform, mixture of two Gaussians, and Gaussian process fields. Curves show the means, and shaded regions denote

95\%

confidence intervals over shared evaluation scenarios.

Method	Uniform	Mixture of two Gaussians	Gaussian process	Average
SubMAPL	0.966	0.960	0.963	0.963
MA-SPL	0.939	0.914	0.918	0.924
MA-OSEA	0.843	0.775	0.831	0.816
REINFORCE	0.377	0.499	0.487	0.454
OSG	0.917	0.873	0.850	0.880

Table II : Normalized areas under the coverage curves in the open-system evaluation. Higher values indicate faster overall information acquisition.

Figure 3: Performance under random agent participation on the Gaussian-process field. Top: coverage ratios of the five methods. Bottom: the active-agent profile shared by all methods, reported as the mean with

95\%

confidence intervals over five shared evaluation scenarios.

Method	Normalized area	Final coverage	$95\%$ coverage successes	Mean $T_{0.95}$
SubMAPL	0.887	0.999	5/5	580
MA-SPL	0.844	0.989	5/5	904
MA-OSEA	0.683	0.894	0/5	–
REINFORCE	0.338	0.444	0/5	–
OSG	0.665	0.714	0/5	–

Table III : Performance under the random agent participation on the Gaussian-process information field.

Multi-Agent Systems

Multi-Agent Systems studies how autonomous agents coordinate, compete, communicate, and learn in shared or interdependent tasks.

See all 677 papers

Multi-Agent Reinforcement Learning with Submodular Reward
Mar 6, 2026Wenjing Chen, Chengyuan Qian, Shuo Xing +2Cooperative MARL Multi-Agent Reinforcement Learning
Department of Computer Science and Engineering, Texas A&M University
PLATO: Pointer Learner for Agent and Task Openness
Jul 27, 2026Alireza Saleh Abadi, Leen-Kiat Soh, Daniel Alan Redder +2Pointer Networks Multi-Agent Systems
School of Computing University of Nebraska-Lincoln · School of Computing University of Georgia · Oberlin College
Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning
Feb 23, 2026Shan Yang, Yang LiuCooperative MARL Multi-Agent Reinforcement Learning
National University of Singapore

Mar 6, 2026J/K move · Enter open · S save

Multi-Agent Reinforcement Learning with Submodular Reward

Wenjing Chen, Chengyuan Qian, Shuo Xing, Yi Zhou+1

Department of Computer Science and Engineering, Texas A&M University

Cooperative MARL Multi-Agent Reinforcement Learning Submodular Optimization

Open paper AskPDF arXiv

In this paper, we study cooperative multi-agent reinforcement learning (MARL) where the joint reward exhibits submodularity, which is a natural property capturing diminishing marginal returns when adding agents to a team. Unlike standard MARL with additive rewards, submodular rewards model realistic scenarios where agent contributions overlap (e.g., multi-drone surveillance, collaborative exploration). We provide the first formal framework for this setting and develop algorithms with provable guarantees on sample efficiency and regret bound. For known dynamics, our greedy policy optimization achieves a

1/2

-approximation with polynomial complexity in the number of agents

K

, overcoming the exponential curse of dimensionality inherent in joint policy optimization. For unknown dynamics, we propose a UCB-based learning algorithm achieving a

1/2

-regret of

O(H^2KS\sqrt{AT})

over

T

episodes.

Abstract

Multi-Agent Systems

Explore similar work

Multi-Agent Reinforcement Learning with Submodular Reward

PLATO: Pointer Learner for Agent and Task Openness

Descent-Guided Policy Gradient for Scalable Cooperative Multi-Agent Learning