Other formats:
BibTeX
LaTeX
RIS
@inproceedings{991688,
author = {Brázdil, Tomáš and Kučera, Antonín and Novotný, Petr and Wojtczak, Dominik},
address = {Berlin},
booktitle = {Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)},
doi = {http://dx.doi.org/10.1007/978-3-642-31585-5_16},
keywords = {one-counter automata; markov decision processes},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin},
isbn = {978-3-642-31584-8},
pages = {141-152},
publisher = {Springer},
title = {Minimizing Expected Termination Time in One-Counter Markov Decision Processes},
year = {2012}
}
TY - JOUR
ID - 991688
AU - Brázdil, Tomáš - Kučera, Antonín - Novotný, Petr - Wojtczak, Dominik
PY - 2012
TI - Minimizing Expected Termination Time in One-Counter Markov Decision Processes
PB - Springer
CY - Berlin
SN - 9783642315848
KW - one-counter automata
KW - markov decision processes
N2 - 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.
ER -
BRÁZDIL, Tomáš, Antonín KUČERA, Petr NOVOTNÝ and Dominik WOJTCZAK. Minimizing Expected Termination Time in One-Counter Markov Decision Processes. In \textit{Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)}. Berlin: Springer, 2012. p.~141-152. ISBN~978-3-642-31584-8. doi:10.1007/978-3-642-31585-5\_{}16.
|
