# 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