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

  1. Sergey Levine
  2. Pieter Abbeel
  3. Yoshua Bengio
  4. Shimon Whiteson
  5. Mohit Bansal
  6. Ruslan Salakhutdinov
  7. Jianfeng Gao
  8. Percy Liang

In Computational Theory and Mathematics

  1. Shimon Whiteson
  2. Chris Amato
  3. Karl Tuyls
  4. Gerhard Neumann
  5. Frans Adriaan Oliehoek
  6. Sergey Levine
  7. Matthijs T. J. Spaan
  8. Peter Stone

In Computer Networks and Communications

  1. Frans Adriaan Oliehoek
  2. Chris Amato
  3. Shimon Whiteson
  4. Matthijs T. J. Spaan
  5. Gerhard Neumann
  6. Maximilian Hüttenrauch
  7. Adrian Šošić
  8. Peter Stone

In Reinforcement Learning

  1. Sergey Levine
  2. Shimon Whiteson
  3. Pieter Abbeel
  4. Yuxi Li
  5. Chelsea Finn
  6. Peter Stone
  7. Jakob N. Foerster
  8. Karl Tuyls

In Algorithms & Complexity

  1. Frans Adriaan Oliehoek
  2. Matthijs T. J. Spaan
  3. Nikos A. Vlassis
  4. Chris Amato
  5. Sven Seuken
  6. Sridhar Mahadevan
  7. Jonathan P. How
  8. Hongyuan Zha

Citations in the corpus