The Complexity of Markov Decision Processes

TLDR

All three variants of optimal policy computation in Markov decision processes—finite horizon, infinite horizon discounted, and infinite horizon average cost—were previously solvable in polynomial time by dynamic programming, linear programming, or successive approximation techniques. We investigate the complexity of the classical problem of optimal policy computation in Markov decision processes. We analyze the computational complexity of this problem across its three variants to determine their parallelizability and hardness. Our results show that optimal policy computation is P‑complete for all three variants, making efficient parallel algorithms unlikely; deterministic cases can be solved rapidly in parallel, while the partially observed variant is PSPACE‑complete and the fully unobservable variant is NP‑complete, indicating progressively greater computational difficulty.

Abstract

We investigate the complexity of the classical problem of optimal policy computation in Markov decision processes. All three variants of the problem (finite horizon, infinite horizon discounted, and infinite horizon average cost) were known to be solvable in polynomial time by dynamic programming (finite horizon problems), linear programming, or successive approximation techniques (infinite horizon). We show that they are complete for P, and therefore most likely cannot be solved by highly parallel algorithms. We also show that, in contrast, the deterministic cases of all three problems can be solved very fast in parallel. The version with partially observed states is shown to be PSPACE-complete, and thus even less likely to be solved in polynomial time than the NP-complete problems; in fact, we show that, most likely, it is not possible to have an efficient on-line implementation (involving polynomial time on-line computations and memory) of an optimal policy, even if an arbitrary amount of precomputation is allowed. Finally, the variant of the problem in which there are no observations is shown to be NP-complete.