Minimizing Expected Termination Time in One-Counter Markov Decision Processes

Abstract. We consider the problem of computing the value and an optimal strat-egy for minimizing the expected termination time in one-counter Markov deci-sion 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 ε> 0 and computing a finite representation of an ε-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.