# The Complexity of Decentralized Control of Markov Decision Processes

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

## Key facts

- Cited by 231 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2013.

## Built on by (most cited first, 30 of 231)

- [SOTOPIA: Interactive Evaluation for Social Intelligence in Language Agents](https://mlsanity.com/paper/2310.11667/) (2023)
- [A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress](https://mlsanity.com/paper/1806.06877/) (2018)
- [Building Cooperative Embodied Agents Modularly with Large Language Models](https://mlsanity.com/paper/2307.02485/) (2023)
- [Exploring Large Language Model based Intelligent Agents: Definitions, Methods, and Prospects](https://mlsanity.com/paper/2401.03428/) (2024)
- [SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2212.07489/) (2022)
- [From Motor Control to Team Play in Simulated Humanoid Football](https://mlsanity.com/paper/2105.12196/) (2021)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Federated Reinforcement Learning: Techniques, Applications, and Open Challenges](https://mlsanity.com/paper/2108.11887/) (2021)
- [Heterogeneous-Agent Reinforcement Learning](https://mlsanity.com/paper/2304.09870/) (2023)
- [VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learning](https://mlsanity.com/paper/2207.03530/) (2022)
- [JaxMARL: Multi-Agent RL Environments and Algorithms in JAX](https://mlsanity.com/paper/2311.10090/) (2023)
- [TorchRL: A data-driven decision-making library for PyTorch](https://mlsanity.com/paper/2306.00577/) (2023)
- [ToM2C: Target-oriented Multi-agent Communication and Cooperation with Theory of Mind](https://mlsanity.com/paper/2111.09189/) (2021)
- [An Introduction to Centralized Training for Decentralized Execution in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2409.03052/) (2024)
- [Episodic Multi-agent Reinforcement Learning with Curiosity-Driven Exploration](https://mlsanity.com/paper/2111.11032/) (2021)
- [COMBO: Compositional World Models for Embodied Multi-Agent Cooperation](https://mlsanity.com/paper/2404.10775/) (2024)
- [Deep Multiagent Reinforcement Learning: Challenges and Directions](https://mlsanity.com/paper/2106.15691/) (2021)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [τ-Knowledge: Evaluating Conversational Agents over Unstructured Knowledge](https://mlsanity.com/paper/2603.04370/) (2026)
- [Shapley Counterfactual Credits for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00285/) (2021)
- [Heterogeneous Multi-Robot Reinforcement Learning](https://mlsanity.com/paper/2301.07137/) (2023)
- [Applications of Multi-Agent Reinforcement Learning in Future Internet: A Comprehensive Survey](https://mlsanity.com/paper/2110.13484/) (2021)
- [Multi-agent Reinforcement Learning: A Comprehensive Survey](https://mlsanity.com/paper/2312.10256/) (2023)
- [K-level Reasoning for Zero-Shot Coordination in Hanabi](https://mlsanity.com/paper/2207.07166/) (2022)
- [Decision-Oriented Dialogue for Human-AI Collaboration](https://mlsanity.com/paper/2305.20076/) (2023)
- [Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning](https://mlsanity.com/paper/2310.01207/) (2023)
- [TASRA: a Taxonomy and Analysis of Societal-Scale Risks from AI](https://mlsanity.com/paper/2306.06924/) (2023)
- [Order Matters: Agent-by-agent Policy Optimization](https://mlsanity.com/paper/2302.06205/) (2023)
- [ZSC-Eval: An Evaluation Toolkit and Benchmark for Multi-agent Zero-shot Coordination](https://mlsanity.com/paper/2310.05208/) (2023)
- [What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?](https://mlsanity.com/paper/2212.02705/) (2022)

## Abstract (arXiv)

Planning for distributed agents with partial state information is considered from a decision- theoretic perspective. We describe generalizations of both the MDP and POMDP models that allow for decentralized control. For even a small number of agents, the finite-horizon problems corresponding to both of our models are complete for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov processes. In contrast to the MDP and POMDP problems, the problems we consider provably do not admit polynomial-time algorithms and most likely require doubly exponential time to solve in the worst case. We have thus provided mathematical evidence corresponding to the intuition that decentralized planning problems cannot easily be reduced to centralized problems and solved exactly using established techniques.