# Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

arXiv: https://arxiv.org/abs/1705.07312 · HTML: https://mlsanity.com/paper/1705.07312/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2017.

## Built on by (most cited first, 3 of 3)

- [On the Hardness of Reinforcement Learning with Transition Look-Ahead](https://mlsanity.com/paper/2510.19372/) (2025)
- [Doubly-Asynchronous Value Iteration: Making Value Iteration Asynchronous in Actions](https://mlsanity.com/paper/2207.01613/) (2022)
- [Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead](https://mlsanity.com/paper/2609.11807/) (2026)

## Abstract (arXiv)

We study the computational complexity of the infinite-horizon discounted-reward Markov Decision Problem (MDP) with a finite state space |S| and a finite action space |A|. We show that any randomized algorithm needs a running time at least Omega(|S|2|A|) to compute an ε-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 Omegaleft( frac|S| |A|ε right). These results reveal a surprising observation that the computational complexity of the MDP depends on the data structure of input.