




Publications  On the Complexity of Value Iteration





Reference:
Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez, and Mahsa Shirmohammadi. On the complexity of value iteration. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), pages 102:1–102:15, 2019.
Abstract:
Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal nstep 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 EXPTIMEcomplete, 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 EXPTIMEcomplete to compute the nfold iteration (with n in binary) of a function given by a straightline program over the integers with max and + as operators. We also provide new complexity results for the bounded halting problem in linearupdate counter machines.
Suggested BibTeX entry:
@inproceedings{19BKNPSICALP,
author = {Nikhil Balaji and Stefan Kiefer and Petr Novotn{\'{y}} and Guillermo A. P{\'{e}}rez and Mahsa Shirmohammadi},
booktitle = {Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP)},
pages = {102:1102:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
title = {On the Complexity of Value Iteration},
year = {2019}
}




