Publication details

Minimizing Expected Termination Time in One-Counter Markov Decision Processes

Authors

BRÁZDIL Tomáš KUČERA Antonín NOVOTNÝ Petr WOJTCZAK Dominik

Year of publication 2012
Type Article in Proceedings
Conference Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-31585-5_16
Field Informatics
Keywords one-counter automata; markov decision processes
Attached files
Description We consider the problem of computing the value and an optimal strategy for minimizing the expected termination time in one-counter Markov decision processes. Since the value may be irrational and an optimal strategy may be rather complicated, we concentrate on the problems of approximating the value up to a given error epsilon > 0 and computing a finite representation of an epsilon-optimal strategy. We show that these problems are solvable in exponential time for a given configuration, and we also show that they are computationally hard in the sense that a polynomial-time approximation algorithm cannot exist unless P=NP.
Related projects: