Research map / Multi-agent systems and games / Cooperative multi-agent RL
MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning
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 MALinZero, a multi-agent MCTS method that models joint-action returns with a low-dimensional contextual linear bandit (LinUCT, convex mu-smooth loss, submodular action selection), evaluated on MatGame, SMAC and SMACv2.
Problem
Monte Carlo Tree Search in multi-agent planning suffers from a combinatorial joint action space whose branching factor grows exponentially with the number of agents, making efficient exploration and exploitation difficult.
Approach
Represent joint-action returns as a linear sum of latent per-agent action rewards, solve the resulting contextual linear bandit with a strongly convex, mu-smooth loss, and derive a LinUCT selection rule with dynamic node generation and a submodular (1-1/e) approximate action selection.
Key results
- On MatGame with 8 agents and 10 actions (linear, 2000 steps), MALinZero reaches 705.2 vs 692.7 for MAZero, and it outperforms all baselines in all 8 MatGame settings.
- On SMAC, MALinZero reaches over 95% win rate on all three maps and reaches MAZero's win rate with 50% to 70% fewer steps (claimed 2-3x speedup).
- On SMACv2, the paper reports roughly doubling win rate versus baselines on protoss, zerg and terran 5v5 maps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MALinZero instead of the strongest reported baseline | MatGame · MatGame results table settings | reward | Helped |
| Use MALinZero instead of MAZero | Multi-agent planning on SMAC · SMAC, 3 maps | win rate: 50\% to 70\% less steps/samples | Helped |
| Use MALinZero instead of the baselines | Multi-agent planning on SMACv2 · protoss_5_vs_5 and zerg_5_vs_5 | win rate: doubles | Helped |
| Remove Dynamic Node Generation (DNG) (ablation) | MALinZero · MatGame, medium and hard scenarios | reward | Hurt |
| Replace general convex loss f with Euclidean distance (ablation) | MALinZero LinUCT · MatGame, medium and hard scenarios | reward | Hurt |
| Remove both DNG and general convex loss f (ablation) | MALinZero · MatGame, medium and hard scenarios | reward | Hurt |
Surprising findings
- Gains over baselines are larger under non-linear MatGame reward structures (up to about 11%) than under linear ones.
Limitations
- Relies on a linear bandit formulation in the low-dimensional space; non-linear formulations are left open.
- Developing fully decomposable representations is stated as an open problem.
- Regret bound carries an extra sqrt(mu) factor relative to standard contextual bandit results.
Experimental setup
Datasets: MatGame SMAC SMACv2
Benchmarks: MatGame SMAC SMACv2
Metrics: win rate average return
Baselines: MAZero MAZero-NP MA-AlphaZero MAPPO QMIX
Builds on: MuZero Sampled MuZero MAZero LinUCB EfficientZero
Closest papers by meaning
- Multiagent Gumbel MuZero: Efficient Planning in Combinatorial Action Spaces (AAAI 2024 · similarity 0.88)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.88)
- Efficient Multi-agent Reinforcement Learning by Planning (ICLR 2024 · similarity 0.88)
- Online Robust Reinforcement Learning Through Monte-Carlo Planning (ICML 2025 · similarity 0.88)
- Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.86)
- Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves (AAAI 2025 · similarity 0.86)
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.