Minimizing expected termination time in one-counter Markov decision processes

DOI10.1007/978-3-642-31585-5_16MaRDI QIDQ3167006zbMATH OpenOpenAlexFDO

Authors Tomáš Brázdil, Petr Novotný, Dominik Wojtczak, Antonin Kučera

Publication date 1 November 2012

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.1473

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: 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.

Recommendations

• One-counter Markov decision processes
• Approximating the termination value of one-counter MDPs and stochastic games
• Approximating the termination value of one-counter MDPs and stochastic games
• One-counter stochastic games
• Maximizing the conditional expected reward for reaching the goal

Cited in

(8)

• Approximating the termination value of one-counter MDPs and stochastic games
• Computing expected runtimes for constant probability programs
• Recursive stochastic games with positive rewards
• Approximating the termination value of one-counter MDPs and stochastic games
• Deciding fast termination for probabilistic VASS with nondeterminism
• Maximizing the conditional expected reward for reaching the goal
• One-counter Markov decision processes
• Positivity-hardness results on Markov decision processes

This page was built for publication: Minimizing expected termination time in one-counter Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167006)