Research map / Multi-agent systems and games / Cooperative multi-agent RL
Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach
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 sequential-move centralized training for decentralized execution, reducing simultaneous-move Dec-POMDPs to sequential-move ones so that backups drop from double exponential to polynomial, and adapts oSARSA accordingly.
Problem
Optimally (epsilon-optimally) solving simultaneous-move Dec-POMDPs is not scalable because simultaneous-move joint decision rule backups are double exponential in agents and time.
Approach
Reformulates the simultaneous-move Dec-POMDP as a sequential-move Dec-POMDP where a central planner selects one agent's private decision rule at a time, defines sequential occupancy states as sufficient statistics, proves piecewise linear convexity of value functions over them, and derives polynomial-time backups usable by oSARSA.
Key results
- On boxpushing at horizon 100, oSARSA-seq reaches 2366.21 versus 1895.16 for oSARSA-sim.
- oSARSA-seq matches or beats FB-HSVI across two-agent domains, with the margin growing with horizon (boxpushing gap 304.79 at horizon 40).
- In many-agent domains, oSARSA-seq outperforms oSARSA-sim, A2C and IQL on all tested settings, where oSARSA-sim often times out.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sequential-move rather than simultaneous-move central planning in oSARSA | oSARSA · boxpushing, 2 agents, ℓ=100 | value: 1895.16 -> 2366.21 | Helped |
| Use sequential-move rather than simultaneous-move central planning in oSARSA | oSARSA · two-agent domains, except recycling and mabc | value | Helped |
| Use sequential-move rather than simultaneous-move central planning in oSARSA | oSARSA · recycling and mabc, two-agent domains | value | No clear effect |
| Use sequential-move rather than simultaneous-move central planning in oSARSA | oSARSA · many-agent domains | value | Helped |
Surprising findings
- oSARSA-sim runs out of time on mars and grid3x3 at large horizons even though it is competitive with FB-HSVI on most two-agent domains.
Limitations
- Planning horizon grows by a factor of n agents, lengthening trajectories.
- Experiments limited to small benchmark domains with fixed agent permutation.
Experimental setup
Datasets: mabc recycling grid3x3 boxpushing mars tiger gridsmall
Benchmarks: mabc recycling grid3x3 boxpushing mars tiger gridsmall
Metrics: expected cumulative discounted reward
Baselines: oSARSA-sim FB-HSVI A2C IQL
Builds on: oSARSA simultaneous-move occupancy states (oMDP) FB-HSVI
Closest papers by meaning
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.86)
- Factored Online Planning in Many-Agent POMDPs (AAAI 2024 · similarity 0.86)
- Multi-Environment POMDPs with Finite-Horizon Objectives (NeurIPS 2026 · similarity 0.85)
- A Surprisingly Simple Continuous-Action POMDP Solver: Lazy Cross-Entropy Search Over Policy Trees (AAAI 2024 · similarity 0.85)
- Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems (NeurIPS 2025 · similarity 0.85)
- Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach (ICML 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.