It is proved 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.
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 \emph{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 \emph{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.
This paper develops a multi-agent reinforcement learning-based (MARL) delegation training that enables agents to make sequential delegation decisions while minimizing the total execution cost and introduces two new frameworks for collaboration and delegation in multi-agent systems.
Ziqing Lu, Avinash Mudireddy, Sarra M. Alqahtani et al.· 0 citations
A neural scheduling framework for distributed multi-robot task allocation, consisting of a multi-decoder graph attention model (MDGAM) policy model and a critic-free group relative multi-agent policy gradient (GRMAPG) training algorithm, which improves task-completion performance over existing heuristic and learning-based methods.
This work proposes MARA, which predicts future loss trajectories with conditional flow matching and coordinates compute nodes through a cooperative multi-agent autoregressive policy and reduces remaining-resource prediction error relative to weighted least squares.
Hanye Zhao, Muning Wen, Yong Yu et al.· 0 citations
Multi-agent policy optimization, exemplified by PPO-based methods, is a key branch of cooperative Multi-Agent Reinforcement Learning (MARL). A central design question is how many neighboring agents\footnote{In this paper,"neighbors"refer not only to physical proximity but also to agents whose actions influence one another.} to aggregate in order to effectively utilize global information for cooperation. This decision must be made along two dimensions: in the advantage (which agents'rewards contribute to the credit signal) and in the ratio (which agents'likelihood ratios form the clipped importance weight). Existing methods occupy scattered, underexplored points on these two axes: IPPO treats both separately; MAPPO pairs a team-level advantage with per-agent ratios; HAPPO employs sequential ratios with per-agent advantages; and single-agent reductions operating on factorized joint policies aggregate both into fully joint products. We formalize these two design choices as support matrices $\SA$ and $\SR$, and prove a canonical structure: the expected multi-agent policy optimization objective depends on the pair $(\SA,\SR)$ only through their matrix product $\tS=\SR\SA$. This yields two key consequences: (i) Redundancy: the two support matrices are interchangeable with respect to the signal, meaning neither aggregation pattern is inherently superior.(ii) Variance Ordering: the advantage aggregates rewards as a sum (additive variance with an interior bias-variance optimum at the coupling neighborhood), whereas the ratio aggregates likelihood ratios as a product (multiplicative variance that grows exponentially with support size, with no accompanying bias reduction). The resulting design principle is unambiguous: aggregate neighbors in the advantage, sized to the coupling neighborhood, and keep the ratio per-agent.
Multi-agent path planning (MAPP) under partial observability requires agents to coordinate their movements and complete tasks efficiently without access to global information. The planning space and coordination complexity grow rapidly with increasing numbers of agents, targets, and obstacles. We formulate large-scale MAPP as a partially observable networked Markov decision process. Based on this formulation, we propose a decentralized model-based Actor-Critic using the Kronecker-factored trust region (DM-ACKTR) algorithm. The algorithm integrates local model learning with ACKTR-based policy optimization in an independent learning architecture. Each agent learns a local model to predict the next observation and reward. These predictions are used to construct additional transitions for Actor and Critic updates. A neighborhood-based communication mechanism incorporates information from nearby agents into value estimation. Region partitioning reduces each agent’s effective planning space. These improvements enable DM-ACKTR to continue outperforming the baseline algorithms as the scale of the MAPP problem increases. Experiments across three training and five evaluation scenarios show that DM-ACKTR achieves the best overall performance. Among the five evaluated algorithms, it consistently obtains the highest TCR and lowest CR, improving TCR by 2.06–4.35% and reducing CR by 11.26–25.95% relative to the respective best baselines.
Ye-Min Liu, Jinhao Yang, Xiang-Yu Ma et al.· Electronics· 0 citations
MA-USFA, a hierarchical method with two layers: a lower layer of universal successor feature approximators that predicts each agent's successor features while conditioned on its teammates' objectives, and an upper composer that selects, across agents, which library entry each agent should follow and supplies the cross-agent correction a per-agent value cannot represent.
Zijian Zhao, Sen Li· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
