Other formats:
BibTeX
LaTeX
RIS
@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 and 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, p.~''102:1''-''102:15'', 15 pp. ISBN~978-3-95977-109-2. Available from: https://dx.doi.org/10.4230/LIPIcs.ICALP.2019.102.
|