Approximating the Termination Value of One-Counter MDPs and Stochastic Games

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRÁZDIL Tomáš BROŽEK Václav ETESSAMI Kousha KUČERA Antonín

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

Faculty of Informatics

Citation
Field Informatics
Keywords stochastic games; one-counter automata
Description We show that all quantitative approximation problems for the termination value for one-counter MDPs and one-counter stochastic games are computable. Specifically, given a one-counter game, and given e > 0, we can compute a value v that approximates the value of the termination game within additive error e, and furthermore we can compute e-optimal strategies for both players in the game.
Related projects:

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