Minimizing Expected Termination Time in One-Counter Markov Decision Processes

Investor logo
Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
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:

You are running an old browser version. We recommend updating your browser to its latest version.