On the Complexity of Value Iteration

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00107669" target="_blank" >RIV/00216224:14330/19:00107669 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102" target="_blank" >10.4230/LIPIcs.ICALP.2019.102</a>

Result language
angličtina
Original language name
On the Complexity of Value Iteration
Original language description
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.
Czech name
—
Czech description
—

Project
<a href="/en/project/GJ19-15134Y" target="_blank" >GJ19-15134Y: Verification and Analysis of Probabilistic Programs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
ISBN
9783959771092
ISSN
1868-8969
e-ISSN
—
Number of pages
15
Pages from-to
„102:1“-„102:15“
Publisher name
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Patras, Řecko
Event date
Jan 1, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)