The Complexity of Decentralized Control of Markov Decision Processes

Planning for distributed agents with partial state information is considered from a decision theoretic perspective. We describe generaliza tions of both the MDP and POMDP models that allow for decentralized control. For even a small number of agents, the finite-horizon prob lems corresponding to both of our models are complete for nondeterministic exponential time. These complexity results illustrate a fundamen tal difference between centralized and decentral ized control of Markov processes. In contrast to the MDP and POMDP problems, the problems we consider provably do not admit polynomial time algorithms and most likely require doubly exponential time to solve in the worst case. We have thus provided mathematical evidence corre sponding to the intuition that decentralized plan ning problems cannot easily be reduced to cen tralized problems and solved exactly using estab lished techniques.