On the Complexity of Value Iteration

D 2019

On the Complexity of Value Iteration

BALAJI, Nikhil, Stefan KIEFER, Petr NOVOTNÝ, Guillermo A. PÉREZ, Mahsa SHIRMOHAMMADI et. al.

Základní údaje

Originální název

On the Complexity of Value Iteration

Autoři

BALAJI, Nikhil (356 Indie), Stefan KIEFER (276 Německo), Petr NOVOTNÝ (203 Česká republika, garant, domácí), Guillermo A. PÉREZ (340 Honduras) a Mahsa SHIRMOHAMMADI (364 Írán)

Vydání

Dagstuhl, Germany, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), od s. "102:1"-"102:15", 15 s. 2019

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/19:00107669

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-109-2

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102

Klíčová slova anglicky

Markov decision processes; probabilistic verification; value iteration

Štítky

core_A, firank_A, formela-ver

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 17. 4. 2020 12:16, doc. RNDr. Petr Novotný, Ph.D.

Anotace

V originále

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.

Návaznosti

GA19-15134Y, interní kód MU

Název: Verifikace a analýza pravděpodobnostních programů

Investor: Grantová agentura ČR, Verifikace a analýza pravděpodobnostních programů

GJ19-15134Y, projekt VaV

Název: Verifikace a analýza pravděpodobnostních programů

Citovat

BALAJI, Nikhil, Stefan KIEFER, Petr NOVOTNÝ, Guillermo A. PÉREZ a Mahsa SHIRMOHAMMADI. On the Complexity of Value Iteration. Online. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi. Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, s. "102:1"-"102:15", 15 s. ISBN 978-3-95977-109-2. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102.

@inproceedings{1561197,
   author = {Balaji, Nikhil and Kiefer, Stefan and Novotný, Petr and Pérez, Guillermo A. and Shirmohammadi, Mahsa},
   address = {Dagstuhl, Germany},
   booktitle = {Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102},
   editor = {Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi},
   keywords = {Markov decision processes; probabilistic verification; value iteration},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-109-2},
   pages = {"102:1"-"102:15"},
   publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
   title = {On the Complexity of Value Iteration},
   year = {2019}
}

TY  - JOUR
ID  - 1561197
AU  - Balaji, Nikhil - Kiefer, Stefan - Novotný, Petr - Pérez, Guillermo A. - Shirmohammadi, Mahsa
PY  - 2019
TI  - On the Complexity of Value Iteration
PB  - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
CY  - Dagstuhl, Germany
SN  - 9783959771092
KW  - Markov decision processes
KW  - probabilistic verification
KW  - value iteration
N2  - 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.
ER  -

BALAJI, Nikhil, Stefan KIEFER, Petr NOVOTNÝ, Guillermo A. PÉREZ a Mahsa SHIRMOHAMMADI. On the Complexity of Value Iteration. Online. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi. \textit{Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019, s.~''102:1''-''102:15'', 15 s. ISBN~978-3-95977-109-2. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102.

Podrobný výpis o publikaci