On the Complexity of Discounted Markov Decision Process

We provide the first sublinear running time upper bound and a nearly matching lower bound for the discounted Markov decision problem. In particular, we propose a randomized linear programming algorithm for approximating the optimal policy of the discounted Markov decision problem. We show that it finds an ε-optimal policy using nearly-linear running time in the worst case. For Markov decision processes that are ergodic under every stationary policy, we show that the algorithm finds an ε-optimal policy using running time linear in the total number of state-action pairs, which is sublinear in the input size. We establish computational lower bound on the run time of any randomized algorithm for solving the MDP, which suggests that the complexity of MDP depends on data structures of the input. These results provide new complexity benchmarks for solving stochastic dynamic programs. The proposed algorithm can be extended to apply to reinforcement learning and yield sharp PAC sample complexity.