Research map / Multi-agent systems and games / Cooperative multi-agent RL
Factored Online Planning in Many-Agent POMDPs
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.
Combines weighted particle filtering and coordination-graph value factorization for online planning in many-agent MPOMDPs, yielding FS/FT variants of W-POMCP and Sparse-PFT.
Problem
Online planning in centralized multi-agent POMDPs (MPOMDPs) suffers from exponentially growing joint action and observation spaces, making both value estimation and belief estimation ineffective when many agents are present.
Approach
Tackles value and belief estimation jointly: adds importance-weighted particle filtering to POMCP and Sparse-PFT, factorizes action statistics over coordination-graph edges (factored statistics and factored trees), and introduces an ensemble of per-edge local particle filters that use local observation likelihoods.
Key results
- Factored algorithms (FS-W-POMCP, FT-PFT) scale to 64 agents on FireFightingGraph, versus 10 for prior single-agent-joint baselines, and to 6 agents on Multi-agent RockSample instead of 2.
- FS-W-POMCP outperforms FS-POMCP consistently across all three benchmarks, showing benefit of offline weighted particle filtering.
- Single-agent algorithms (Sparse-PFT, POMCP, W-POMCP) are outscaled by factored variants on FFG and MARS when many agents are present, while joint planning performs best with few agents.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add offline weighted particle filtering to FS-POMCP (ablation) | FS-POMCP · FireFightingGraph, Multi-Agent RockSample, CaptureTarget | return | Helped |
| add weighted particle filtering to FT-POMCP (ablation) | FT-POMCP · FireFightingGraph | return | Helped |
| add weighted particle filtering to FT-POMCP (ablation) | FT-POMCP · CaptureTarget | return | Helped |
| add weighted particle filtering to FT-POMCP (ablation) | FT-POMCP · Multi-Agent RockSample | return | Mixed |
| factorize value estimation with coordination graphs | online planners · FireFightingGraph and Multi-Agent RockSample, many-agent settings | scalability | Helped |
| factorize value estimation with coordination graphs | online planners · FireFightingGraph and Multi-Agent RockSample, few-agent settings | return | Hurt |
| use coordination graphs for value factorization (ablation) | Sparse-PFT · FireFightingGraph and Multi-Agent RockSample, many-agent settings | scalability | Helped |
| use coordination graphs for value factorization (ablation) | Sparse-PFT · FireFightingGraph and Multi-Agent RockSample, few-agent settings | return | Mixed |
| use an arbitrary sparse static coordination graph | factored online planners · Multi-Agent RockSample and CaptureTarget | planning performance | Helped |
| use Variable Elimination instead of Max-Plus for action selection | factored planners · Multi-Agent RockSample and CaptureTarget | return | Helped |
| use Max-Plus instead of Variable Elimination for action selection | factored planners · FireFightingGraph | return | Helped |
| use particle-belief tree planning instead of POMCP variants | Sparse-PFT variants · CaptureTarget | return | Hurt |
Surprising findings
- Static, sparse coordination graphs act as a useful heuristic even in MARS and CT where agents move and do not naturally form sparse graphs.
- FT-PFT and FS-PFT perform poorly on CaptureTarget due to the O(C) cost increase of simulation steps and required search depth.
Limitations
- Local filters are biased toward the posterior conditioned on local observations and cannot recover a joint belief depending on all agents.
- Planning on the joint value performs better when few agents are involved; factored variants are comparable or worse in small settings.
- Factored tree variants lack convergence guarantees (FT-POMCP may diverge with c=0).
Experimental setup
Datasets: FireFightingGraph Multi-agent RockSample CaptureTarget
Benchmarks: FireFightingGraph Multi-agent RockSample CaptureTarget
Metrics: average return
Baselines: POMCP FS-POMCP FT-POMCP W-POMCP POMCPOW Sparse-PFT
Builds on: POMCP POMCPOW Sparse-PFT factored-value POMCP max-plus variable elimination
Closest papers by meaning
- Adaptive Online Packing-guided Search for POMDPs (NeurIPS 2021 · similarity 0.91)
- Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practice (AAAI 2024 · similarity 0.88)
- Belief-State Query Policies for User-Aligned POMDPs (NeurIPS 2024 · similarity 0.87)
- RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation (NeurIPS 2024 · similarity 0.86)
- Multi-Environment POMDPs with Finite-Horizon Objectives (NeurIPS 2026 · similarity 0.86)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · 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.