The Complexity of Decentralized Control of Markov Decision Processes

TLDR

The paper studies decentralized control of Markov decision processes and derives worst‑case complexity bounds for optimal solution algorithms. The authors generalize fully observable and partially observable MDPs to decentralized settings and analyze algorithmic complexity for optimal solutions. Even with two agents, finite‑horizon decentralized MDPs are NEXP‑hard, precluding polynomial‑time solutions and requiring superexponential time under EXP ≠ NEXP, highlighting a stark contrast with centralized control.

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 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 ≠ NEXP, the problems require superexponential time to solve in the worst case.