Research map / Multi-agent systems and games / Cooperative multi-agent RL
Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MA-SPL and a parameter-free MA-MPL for multi-agent online coordination via a policy-based continuous extension, achieving (1-c/e) for submodular and weakly submodular guarantees with dynamic regret bounds.
Problem
Multi-agent online coordination (MA-OC) maximizing time-varying set functions under local feedback, where existing methods only get (1-e^{-c})/c for submodular objectives and nothing for weakly submodular objectives.
Approach
A policy-based continuous extension where each agent holds a distribution over its own action set (plus empty action), which gives lossless rounding for any set function; surrogate functions with weighted averaging of gradients yield stationary points with tight approximation; MA-MPL uses meta-policy/Meta-Frank-Wolfe with max-consensus to remove parameter dependence.
Key results
- MA-SPL attains (1-c/e) approximation for monotone submodular objectives with dynamic regret O(sqrt(P_T T/(1-tau)))
- MA-MPL is parameter-free and keeps the same approximation ratio as MA-SPL with regret O(d(G) sqrt(P_T T))
- In simulations, MA-SPL significantly exceeds MA-OSMA and MA-OSEA in average utility, and both proposed algorithms beat the RANDOM baseline
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MA-SPL instead of MA-OSMA | Multi-agent online coordination · Submodular objectives | approximation ratio: (\frac{1-e^{-c}}{c}) -> (1-\frac{c}{e}) | Helped |
| use MA-SPL instead of MA-OSEA | Multi-agent online coordination · Submodular objectives | approximation ratio: (\frac{1-e^{-c}}{c}) -> (1-\frac{c}{e}) | Helped |
| use MA-SPL instead of OSG | Multi-agent online coordination · Submodular objectives | approximation ratio: (\frac{1}{1+c}) -> (1-\frac{c}{e}) | Mixed |
| use MA-SPL instead of MA-OSMA and MA-OSEA | Facility-location target tracking simulations · Facility-location objective with Random, Adversarial and Polyline targets | average utility | Helped |
| use MA-MPL instead of RANDOM | Multi-agent target tracking · Target tracking simulations | utility | Helped |
| use MA-SPL instead of RANDOM | Multi-agent target tracking · Target tracking simulations | utility | Helped |
Limitations
- MA-SPL requires knowledge of DR ratio and submodularity ratios to set the weight function
- Brute-force parameter search for alpha in experiments
- MA-MPL has higher communication and query complexity
Experimental setup
Datasets: simulated multi-target tracking scenarios
Benchmarks: multi-target tracking simulations (facility-location objective) Bayesian A-optimal target tracking
Metrics: running average utility dynamic regret
Baselines: OSG MA-OSMA MA-OSEA RANDOM
Builds on: multi-linear extension MA-OSMA MA-OSEA Meta-Frank-Wolfe distorted local search
Closest papers by meaning
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency (ICLR 2025 · similarity 0.90)
- Cooperative Policy Agreement: Learning Diverse Policy for Offline MARL (AAAI 2025 · similarity 0.87)
- Offline Multi-Agent Reinforcement Learning via In-Sample Sequential Policy Optimization (AAAI 2025 · similarity 0.86)
- Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.85)
- Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.