The Complexity of Decentralized Control of Markov Decision Processes
By Daniel S. Bernstein, Shlomo Zilberstein, Neil Immerman. 2000
1,758 citations recorded by the source corpus.
We consider decentralized control of Markov decision processes and give complexity bounds on the worst-case running time for algorithms that find optimal solutions. Generalizations of both the fully observable case and the partially observable case that allow for decentralized control are described. For even two agents, the finite-horizon problems corresponding to both of these models are hard for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov decision processes. In contrast to the problems involving centralized control, the problems we considerprovably do not admit polynomial-time algorithms. Furthermore, assuming EXP ? NEXP, the problems require superexponential time to solve in the worst case.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Reinforcement Learning, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Pieter Abbeel
- Yoshua Bengio
- Shimon Whiteson
- Mohit Bansal
- Ruslan Salakhutdinov
- Jianfeng Gao
- Percy Liang
In Computational Theory and Mathematics
- Shimon Whiteson
- Chris Amato
- Karl Tuyls
- Gerhard Neumann
- Frans Adriaan Oliehoek
- Sergey Levine
- Matthijs T. J. Spaan
- Peter Stone
In Computer Networks and Communications
- Frans Adriaan Oliehoek
- Chris Amato
- Shimon Whiteson
- Matthijs T. J. Spaan
- Gerhard Neumann
- Maximilian Hüttenrauch
- Adrian Šošić
- Peter Stone
In Reinforcement Learning
- Sergey Levine
- Shimon Whiteson
- Pieter Abbeel
- Yuxi Li
- Chelsea Finn
- Peter Stone
- Jakob N. Foerster
- Karl Tuyls
In Algorithms & Complexity
- Frans Adriaan Oliehoek
- Matthijs T. J. Spaan
- Nikos A. Vlassis
- Chris Amato
- Sven Seuken
- Sridhar Mahadevan
- Jonathan P. How
- Hongyuan Zha
Citations in the corpus
- Value-Decomposition Networks For Cooperative Multi-Agent Learning (2017, background): “…Q -learners cannot distinguish teammates’ exploration from stochasticity in the environment, and fail to solve even an apparently trivial, 2-agent, stateless, 3 × 3 -action problem and the general Dec-POMDP problem is known to be intractable (Bernstein et al., 2000; Oliehoek and Amato, 2016).”
- Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “Each MTMARL task is formalized as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP) (Bernstein et al., 2002), a general formulation for cooperative decision-making under uncertainty.”
- Episodic Exploration for Deep Deterministic Policies: An Application to StarCraft Micromanagement Tasks (2016, background): “Some work has looked at learning control policies for individual agents in a collaborative setting with communication constraints [38, 3], with applications such as soccer robot control [31], and methods such as hierarchical reinforcement learning for communicating high-level goals [12], or…”
- The Hanabi Challenge: A New Frontier for AI Research (2019, background): “Bernstein and colleagues [48] showed that solving DEC-MDPs is in the nondeterministic exponential time (NEXP) complexity class, i.”
- Hierarchical Cooperative Multi-Agent Reinforcement Learning with Skill Discovery (2019, methodology): “Inspired by training practices of real world professional sports teams, we create our method within the paradigm of centralized trainingwith decentralized execution [5].”
- Deep Reinforcement Learning for Swarm Systems (2018, background): “The swarm MDP can be regarded as a special case of a decentralized partially observable Markov decision process (Dec-POMDP) [Bernstein et al., 2002] and is constructed in two steps.”
- Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, methodology): “In this work we apply game-theoretic models to decision-theoretic planning for multiple agents.”
- Cooperative Inverse Reinforcement Learning (2016, background): “Unfortunately, D ec-POMDP s are NEXP-complete (Bernstein et al., 2000) so general D ec-POMDP algorithms have a computational complexity that is doubly exponential.”
- Human-level performance in 3D multiplayer games with population-based reinforcement learning (2018, methodology): “…reinforcement learning methods ( 45, 46 ) have so far not succeeded in training agents in multi-agent games that combine team and competitive play due to the high complexity of the learning problem ( 7, 43 ) that arises from the concurrent adaptation of other learning agents in the environment.”
- Multiagent Learning of Coordination in Loosely Coupled Multiagent Systems (2015, background): “In other situations, the Dec-MDPs problem becomes an NEXP-complete puzzle, even for the simplest two-agent scenario [28].”
- Batch Reinforcement Learning (2012, background): “The framework of decentralized Markov decision processes (DEC-(PO)MDP, [3]) is frequently used to address environments populated with independent agents that have access to local state information only and thus do not know about the full, global state.”
- Transfer Learning for Reinforcement Learning Domains: A Survey (2009, background): “The need for such speedups is particularly critical in distributed POMDPs, as solving them optimally as been shown to be NEXP-Complete (Bernstein et al., 2002).”
- Rollout Sampling Policy Iteration for Decentralized POMDPs (2010, background): “This is not surprising given that finite-horizon DECPOMDPs are NEXP-complete [2].”
- A Survey on Machine-Learning Techniques in Cognitive Radios (2013, methodology): “The optimal solution of the POMDP was derived in [98] by considering the POMDP as an Markov decision process (MDP) [88] with an infinite state space.”
- Multi-objective multi-agent decision making: a utility-based analysis and survey (2019, background): “Depending on the system, the agents can fully observe this state, or can only observe a local view si, in which case the problem becomes decentralised and therefore partially observable [15,17].”