Research map / Multi-agent systems and games / Cooperative multi-agent RL
Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency
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-OSMA and MA-OSEA, projection-based and projection-free multi-agent online algorithms using a multi-linear extension surrogate gradient, achieving a (1-e^{-c})/c approximation with regret O(sqrt(C_T T/(1-beta))) over connected sparse networks, validated on simulated multi-target tracking.
Problem
Multi-agent online submodular maximization where agents have disjoint action sets, limited marginal-gain feedback, and must coordinate; prior OSG gives only 1/(1+c) approximation and requires a complete communication graph.
Approach
Apply multi-linear extension with a curvature-dependent surrogate gradient (weight e^{c(z-1)}) so stationary points give (1-e^{-c})/c approximation; run decentralized mirror ascent with consensus over a connected graph, and a projection-free entropic variant with uniform mixing for KL divergence.
Key results
- MA-OSMA and MA-OSEA achieve regret O(sqrt(C_T T/(1-beta))) against a (1-e^{-c})/c-approximation comparator, improving OSG's 1/(1+c) approximation.
- In simulated multi-target tracking with 20 agents and 30 targets, MA-OSMA and MA-OSEA have higher running average utility than OSG across target mixes (averaged over 5 runs).
- Random-graph (average degree 4) variants perform comparably to complete-graph variants.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the curvature-aware surrogate gradient instead of optimizing the original multilinear extension | stationary points of the multilinear extension · monotone submodular maximization | approximation ratio: \frac{1}{1+c} -> \frac{1-e^{-c}}{c} | Helped |
| replace OSG with MA-OSMA | MA-OSM · connected communication graph | approximation ratio: \Big(\frac{1}{1+\alpha(G)}\Big) -> \Big(\frac{1-e^{-c}}{c}\Big) | Helped |
| replace OSG with MA-OSMA | multi-target tracking · simulated scenarios with different target-type proportions | running average utility | Helped |
| replace OSG with MA-OSEA | multi-target tracking · simulated scenarios with different target-type proportions | average number of targets within 5 units | Helped |
| use MA-OSMA or MA-OSEA instead of OSG | multi-target tracking · simulated scenarios with different target-type proportions | average distance | Helped |
| use a random graph instead of a complete graph | MA-OSMA and MA-OSEA · multi-target tracking | running average utility | No clear effect |
Surprising findings
- Random sparse communication graphs perform comparably to complete graphs in the experiments.
Limitations
- Assumes a static, undirected network topology.
- Requires knowledge of the curvature c (algorithms depend on it).
- Experiments are limited to simulated multi-target tracking; no noisy marginal-gain evaluation.
Experimental setup
Datasets: simulated multi-target tracking scenarios
Benchmarks: simulated multi-target tracking
Metrics: average cumulative utility average number of targets within 5 units average distance of Top-5 nearest targets
Baselines: OSG
Builds on: OSG (online sequential greedy) online mirror ascent non-oblivious search continuous greedy
Closest papers by meaning
- Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives (NeurIPS 2025 · similarity 0.90)
- Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.85)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.85)
- Gradient Methods for Online DR-Submodular Maximization with Stochastic Long-Term Constraints (NeurIPS 2024 · similarity 0.85)
- Online Submodular Maximization via Online Convex Optimization (AAAI 2024 · similarity 0.84)
- POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding (ICLR 2025 · similarity 0.84)
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.