The Complexity of Decentralized Control of Markov Decision Processes

Understand

Planning for distributed agents with partial state information is considered from a decision- theoretic 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.