Journal
MATHEMATICS OF OPERATIONS RESEARCH
Volume 27, Issue 4, Pages 819-840Publisher
INFORMS
DOI: 10.1287/moor.27.4.819.297
Keywords
computational complexity; Markov decision process; decentralized control
Ask authors/readers for more resources
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 consider provably do not admit polynomial-time algorithms. Furthermore, assuming EXP not equal NEXP, the problems require superexponential time to solve in the worst case.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available