Minimizing Expected Termination Time in One-Counter Markov Decision Processes
| Authors | |
|---|---|
| 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 | |
| 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: |