The Complexity of Decentralized Control of Markov Decision Processes

Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The Complexity of Decentralized Control of Markov Decision Processes. Mathematics of Operations Research, 27(4):819-840, 2002.

Abstract

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 non-deterministic 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 consider provably do not admit polynomial-time algorithms. Furthermore, assuming EXP =/= NEXP, the problems require super-exponential time to solve in the worst case.

Bibtex entry:

@article{BGIZmor02,
  author	= {Daniel S. Bernstein and Robert Givan and Neil Immerman 
		   and Shlomo Zilberstein},
  title		= {The Complexity of Decentralized Control of {M}arkov
                   Decision Processes},
  journal	= {Mathematics of Operations Research},
  volume	= {27},
  number	= {4},
  year		= {2002},
  pages		= {819-840},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/BGIZmor02.html}
}

shlomo@cs.umass.edu