The complexity of decentralized control of Markov decision processes
成果类型：
Article
署名作者：
Bernstein, DS; Givan, R; Immerman, N; Zilberstein, S
署名单位：
University of Massachusetts System; University of Massachusetts Amherst; Purdue University System; Purdue University
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.27.4.819.297
发表日期：
2002
页码：
819-840
关键词：
摘要：
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.