Open Access. Powered by Scholars. Published by Universities.®
![Digital Commons Network](http://assets.bepress.com/20200205/img/dcn/DCsunburst.png)
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
The Complexity Of Decentralized Control Of Markov Decision Processes, Daniel S. Bernstein, Shlolo Zilberstein, Neil Immerman
The Complexity Of Decentralized Control Of Markov Decision Processes, Daniel S. Bernstein, Shlolo Zilberstein, Neil Immerman
Neil Immerman
Planning for distributed agents with partial state information is considered from a decisiontheoretic perspective. We describe generalizations of both the MDP and POMDP models that allow for decentralized control. For even a small number of agents, the finite-horizon problems corresponding to both of our models are complete for nondeterministic exponential time. These complexity results illustrate a fundamental difference between centralized and decentralized control of Markov processes. In contrast to the MDP and POMDP problems, the problems we consider provably do not admit polynomialtime algorithms and most likely require doubly exponential time to solve in the worst case. We have thus …