mlsanityData to 7 Oct 2026

The Complexity of Decentralized Control of Markov Decision Processes

arXiv 1301.3836 ↗First posted 16 Jan 2013cs.AIcited by 225

Not on the map. Why?

Cited by 21 in LLM agents and tool use, but placed by its own abstract, which didn’t fit.

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.

Key facts. Cited by 225 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jan 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 2; 2019: 0; 2020: 0; 2021: 29; 2022: 26; 2023: 41; 2024: 38; 2025: 44; 2026: 45.

225 papers.

Sort:

By area:

  1. 2023SOTOPIA: Interactive Evaluation for Social Intelligence in Language Agentscited by 350
  2. 2018A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progresscited by 294
  3. 2023Building Cooperative Embodied Agents Modularly with Large Language Modelscited by 231
  4. 2024Exploring Large Language Model based Intelligent Agents: Definitions, Methods, and Prospectscited by 130
  5. 2022SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learningcited by 118
  6. 2021From Motor Control to Team Play in Simulated Humanoid Footballcited by 87
  7. 2022Partially Observable Markov Decision Processes in Robotics: A Surveycited by 81
  8. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 79
  9. 2023Heterogeneous-Agent Reinforcement Learningcited by 67
  10. 2022VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learningcited by 63
  11. 2023TorchRL: A data-driven decision-making library for PyTorchcited by 59
  12. 2023JaxMARL: Multi-Agent RL Environments and Algorithms in JAXcited by 59
38 more
  1. 2021ToM2C: Target-oriented Multi-agent Communication and Cooperation with Theory of Mindcited by 57
  2. 2021Episodic Multi-agent Reinforcement Learning with Curiosity-Driven Explorationcited by 49
  3. 2024COMBO: Compositional World Models for Embodied Multi-Agent Cooperationcited by 47
  4. 2024An Introduction to Centralized Training for Decentralized Execution in Cooperative Multi-Agent Reinforcement Learningcited by 46
  5. 2021Deep Multiagent Reinforcement Learning: Challenges and Directionscited by 42
  6. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  7. 2021Shapley Counterfactual Credits for Multi-Agent Reinforcement Learningcited by 37
  8. 2026τ-Knowledge: Evaluating Conversational Agents over Unstructured Knowledgecited by 35
  9. 2021Applications of Multi-Agent Reinforcement Learning in Future Internet: A Comprehensive Surveycited by 34
  10. 2023Heterogeneous Multi-Robot Reinforcement Learningcited by 34
  11. 2022K-level Reasoning for Zero-Shot Coordination in Hanabicited by 30
  12. 2023Multi-agent Reinforcement Learning: A Comprehensive Surveycited by 30
  13. 2023Decision-Oriented Dialogue for Human-AI Collaborationcited by 29
  14. 2023Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learningcited by 27
  15. 2023TASRA: a Taxonomy and Analysis of Societal-Scale Risks from AIcited by 25
  16. 2023Order Matters: Agent-by-agent Policy Optimizationcited by 24
  17. 2023ZSC-Eval: An Evaluation Toolkit and Benchmark for Multi-agent Zero-shot Coordinationcited by 23
  18. 2022What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?cited by 21
  19. 2021Emergent Discrete Communication in Semantic Spacescited by 20
  20. 2021Quasi-Equivalence Discovery for Zero-Shot Emergent Communicationcited by 19
  21. 2023TiZero: Mastering Multi-Agent Football with Curriculum Learning and Self-Playcited by 18
  22. 2022Generating Teammates for Training Robust Ad Hoc Teamwork Agents via Best-Response Diversitycited by 17
  23. 2024Mutual Theory of Mind in Human-AI Collaboration: An Empirical Study with LLM-driven AI Agents in a Real-time Shared Workspace Taskcited by 17
  24. 2026Colosseum: Auditing Collusion in Cooperative Multi-Agent Systemscited by 17
  25. 2021Causal Multi-Agent Reinforcement Learning: Review and Open Problemscited by 16
  26. 2022Grounding Aleatoric Uncertainty for Unsupervised Environment Designcited by 16
  27. 2018An Efficient, Generalized Bellman Update For Cooperative Inverse Reinforcement Learningcited by 15
  28. 2021Solving Common-Payoff Games with Approximate Policy Iterationcited by 15
  29. 2024N-Agent Ad Hoc Teamworkcited by 15
  30. 2025Social World Modelscited by 14
  31. 2022Answer Set Planning: A Surveycited by 12
  32. 2022A Survey on Reinforcement Learning Methods in Character Animationcited by 12
  33. 2022Autonomy and Intelligence in the Computing Continuum: Challenges, Enablers, and Future Directions for Orchestrationcited by 12
  34. 2022A Survey on Large-Population Systems and Scalable Multi-Agent Reinforcement Learningcited by 12
  35. 2022Pragmatics in Language Grounding: Phenomena, Tasks, and Modeling Approachescited by 12
  36. 2023System Neural Diversity: Measuring Behavioral Heterogeneity in Multi-Agent Learningcited by 12
  37. 2024CaPo: Cooperative Plan Optimization for Efficient Embodied Multi-Agent Cooperationcited by 12
  38. 2021Centralized Model and Exploration Policy for Multi-Agent RLcited by 11

50 most cited of 225 All 225 (JSON)