Minimizing Expected Termination Time in One-Counter Markov Decision   Processes
  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. 
Tom\'a\v{s} Br\'azdil, Anton\'in Ku\v{c}era, Petr Novotn\'y, Dominik   Wojtczak
cs.FL cs.CC