# Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach

arXiv: https://arxiv.org/abs/2408.13139 · HTML: https://mlsanity.com/paper/2408.13139/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 23 Aug 2024.

## Builds on (most cited first, 12 of 12)

- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1905.05408/) (2019)
- [QPLEX: Duplex Dueling Multi-Agent Q-Learning](https://mlsanity.com/paper/2008.01062/) (2020)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00285/) (2021)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [Solving Common-Payoff Games with Approximate Policy Iteration](https://mlsanity.com/paper/2101.04237/) (2021)
- [Multiagent Value Iteration Algorithms in Dynamic Programming and Reinforcement Learning](https://mlsanity.com/paper/2005.01627/) (2020)
- [Incremental Clustering and Expansion for Faster Optimal Planning in Dec-POMDPs](https://mlsanity.com/paper/1402.0566/) (2014)
- [Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach](https://mlsanity.com/paper/2402.02954/) (2024)

## Built on by (most cited first, 2 of 2)

- [On Dynamic Programming Theory for Leader-Follower Stochastic Games](https://mlsanity.com/paper/2512.05667/) (2025)
- [ACPO: Agent-Chained Policy Optimization for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2606.30072/) (2026)

## Abstract (arXiv)

The centralized training for decentralized execution paradigm emerged as the state-of-the-art approach to ε-optimally solving decentralized partially observable Markov decision processes. However, scalability remains a significant issue. This paper presents a novel and more scalable alternative, namely the sequential-move centralized training for decentralized execution. This paradigm further pushes the applicability of the Bellman's principle of optimality, raising three new properties. First, it allows a central planner to reason upon sufficient sequential-move statistics instead of prior simultaneous-move ones. Next, it proves that ε-optimal value functions are piecewise linear and convex in such sufficient sequential-move statistics. Finally, it drops the complexity of the backup operators from double exponential to polynomial at the expense of longer planning horizons. Besides, it makes it easy to use single-agent methods, e.g., SARSA algorithm enhanced with these findings, while still preserving convergence guarantees. Experiments on two- as well as many-agent domains from the literature against ε-optimal simultaneous-move solvers confirm the superiority of our novel approach. This paradigm opens the door for efficient planning and reinforcement learning methods for multi-agent systems.