SCIENCE@home

Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

Yichen Chen,Mengdi Wang

Published 2017 in arXiv.org

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.

PUBLICATION RECORD

  • Publication year

    2017

  • Venue

    arXiv.org

  • Publication date

    2017-05-20

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1705.07312
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-38 of 38 references · Page 1 of 1

CITED BY

Showing 1-19 of 19 citing papers · Page 1 of 1