Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

Yichen Chen, Mengdi Wang

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 $|…