Approximating the Termination Value of One-Counter MDPs and Stochastic Games
| Authors | |
|---|---|
| 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 | |
| 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: |