Research map / Reinforcement learning / Visual and representation RL
Multiagent Gumbel MuZero: Efficient Planning in Combinatorial Action Spaces
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.
Extends AlphaZero/MuZero-style Gumbel search to cooperative multiagent MDPs with combinatorial joint action spaces, using stochastic beam search to sample top-k joint actions without replacement and a sample-based policy improvement operator.
Problem
Planning with MuZero/AlphaZero-style search is sample-hungry and becomes infeasible when joint action spaces grow exponentially with the number of agents in cooperative multiagent control.
Approach
Combine Gumbel-top-k search (sequential halving, exact regularized policy improvement) with stochastic beam search to sample top-k joint actions without replacement from an autoregressive or factorized joint policy, and compute importance-weighted sample-based policy targets, giving MA Gumbel AlphaZero (known model) and MA Gumbel MuZero (learned model).
Key results
- On Switch4 with 2 simulations, MA Gumbel AlphaZero reaches good performance where MA Sampled AlphaZero performs significantly worse across all simulation budgets from 2 to 32.
- Sampling without replacement finds the optimal joint action in the 2-player and 3-player cooperative matrix games, outperforming Monte Carlo sampling with replacement and MAPPO.
- The paper claims reduction of environment interactions by up to an order of magnitude versus model-free approaches.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| sample joint actions without replacement instead of with replacement | MA Gumbel AlphaZero (SWOR) vs. Monte Carlo (MC) · 2-player 3-action matrix game | mean test reward | Helped |
| sample joint actions without replacement instead of with replacement | MA Gumbel AlphaZero (SWOR) vs. Monte Carlo (MC) · 2-player 3-action matrix game | optimal action percentage | Helped |
| use MA Gumbel AlphaZero instead of MAPPO | 2-player 3-action matrix game · 2-player 3-action matrix game | mean test reward | Helped |
| use MA Gumbel AlphaZero instead of MAPPO | 2-player 3-action matrix game · 2-player 3-action matrix game | optimal action percentage | Helped |
| sample joint actions without replacement instead of with replacement | MA Gumbel AlphaZero (SWOR) vs. Monte Carlo (MC) · 3-player 2-action matrix game | mean test reward | Helped |
| sample joint actions without replacement instead of with replacement | MA Gumbel AlphaZero (SWOR) vs. Monte Carlo (MC) · 3-player 2-action matrix game | optimal action percentage | Helped |
| use MA Gumbel AlphaZero instead of MAPPO | 3-player 2-action matrix game · 3-player 2-action matrix game | mean test reward | Helped |
| use MA Gumbel AlphaZero instead of MAPPO | 3-player 2-action matrix game · 3-player 2-action matrix game | optimal action percentage | Helped |
| use sampling without replacement and the exact policy target instead of sampling with replacement and the visit-count policy target | MA Gumbel AlphaZero vs. MA Sampled AlphaZero · Switch4 | mean episode length | Helped |
| use sampling without replacement and the exact policy target instead of sampling with replacement and the visit-count policy target | MA Gumbel AlphaZero vs. MA Sampled AlphaZero · Switch4 | mean episode reward | Helped |
| use MA Gumbel AlphaZero with 2 simulations | MA Gumbel AlphaZero · Switch4 (nsim=2) | mean episode reward | Helped |
Limitations
- Evaluated only on cooperative multiagent control tasks (matrix games, Switch4, StarCraft Multiagent Challenge) rather than combinatorial optimization or LLM fine-tuning.
- Relies on the independent factorization in experiments, and MA Gumbel AlphaZero assumes a perfect environment model.
Experimental setup
Datasets: MA-Gym Switch4 StarCraft Multiagent Challenge two cooperative matrix games
Benchmarks: MA-Gym Switch4 StarCraft Multiagent Challenge cooperative matrix games
Metrics: mean episode length mean episode reward percentage of optimal actions
Baselines: MA Sampled AlphaZero MAPPO Sampled MuZero Gumbel MuZero MuZero model-free baselines
Builds on: Gumbel MuZero Sampled MuZero AlphaZero MuZero MAPPO
Closest papers by meaning
- Efficient Multi-agent Reinforcement Learning by Planning (ICLR 2024 · similarity 0.88)
- MALinZero: Efficient Low-Dimensional Search for Mastering Complex Multi-Agent Planning (NeurIPS 2025 · similarity 0.88)
- POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding (ICLR 2025 · similarity 0.87)
- FightLadder: A Benchmark for Competitive Multi-Agent Reinforcement Learning (ICML 2024 · similarity 0.86)
- Sable: a Performant, Efficient and Scalable Sequence Model for MARL (ICML 2025 · similarity 0.86)
- Revisiting Multi-Agent World Modeling from a Diffusion-Inspired Perspective (NeurIPS 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.