Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

Abstract

We study the computational complexity of the infinite-horizon discounted-reward Markov Decision Problem (MDP) with a finite state space $|\mathcal{S}|$ and a finite action space $|\mathcal{A}|$. We show that any randomized algorithm needs a running time at least $\Omega (|\mathcal{S}{|}^2|\mathcal{A}|)$ to compute an $\epsilon$-optimal policy with high probability. We consider two variants of the MDP where the input is given in specific data structures, including arrays of cumulative probabilities and binary trees of transition probabilities. For these cases, we show that the complexity lower bound reduces to $\Omega \left(\frac{|\mathcal{S}||\mathcal{A}|}{\epsilon }\right)$. These results reveal a surprising observation that the computational complexity of the MDP depends on the data structure of input.

References in corpus (2)

• On the Complexity of Policy Iteration
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time

Cited by in corpus (5)

• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time
• Generalization Bounds for Stochastic Saddle Point Problems
• The Problem of Dynamic Programming on a Quantum Computer
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes