License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.102
URN: urn:nbn:de:0030-drops-106782
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10678/
Go to the corresponding LIPIcs Volume Portal

Balaji, Nikhil ; Kiefer, Stefan ; Novotný, Petr ; Pérez, Guillermo A. ; Shirmohammadi, Mahsa

On the Complexity of Value Iteration

pdf-format:
LIPIcs-ICALP-2019-102.pdf (0.5 MB)

Abstract

Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal n-step payoff by iterating n times a recurrence equation which is naturally associated to the MDP. At the same time, value iteration provides a policy for the MDP that is optimal on a given finite horizon n. In this paper, we settle the computational complexity of value iteration. We show that, given a horizon n in binary and an MDP, computing an optimal policy is EXPTIME-complete, thus resolving an open problem that goes back to the seminal 1987 paper on the complexity of MDPs by Papadimitriou and Tsitsiklis. To obtain this main result, we develop several stepping stones that yield results of an independent interest. For instance, we show that it is EXPTIME-complete to compute the n-fold iteration (with n in binary) of a function given by a straight-line program over the integers with max and + as operators. We also provide new complexity results for the bounded halting problem in linear-update counter machines.

BibTeX - Entry

@InProceedings{balaji_et_al:LIPIcs:2019:10678,
  author =	{Nikhil Balaji and Stefan Kiefer and Petr Novotn{\'y} and Guillermo A. P{\'e}rez and Mahsa Shirmohammadi},
  title =	{{On the Complexity of Value Iteration}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{102:1--102:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10678},
  URN =		{urn:nbn:de:0030-drops-106782},
  doi =		{10.4230/LIPIcs.ICALP.2019.102},
  annote =	{Keywords: Markov decision processes, Value iteration, Formal verification}
}

Keywords: Markov decision processes, Value iteration, Formal verification
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI