Approximating the Termination Value of One-Counter MDPs and Stochastic Games

DOI10.1007/978-3-642-22012-8_26zbMath1334.68113arXiv1104.4978OpenAlexW2137464431MaRDI QIDQ3012931

Kousha Etessami, Václav Brožek, Tomáš Brázdil, Antonín Kučera

Publication date: 7 July 2011

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Stochastic games, stochastic differential games (91A15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations ⋮ Determinacy and optimal strategies in infinite-state stochastic reachability games ⋮ Deciding Fast Termination for Probabilistic VASS with Nondeterminism ⋮ Analyzing probabilistic pushdown automata ⋮ A Survey of Bidding Games on Graphs (Invited Paper) ⋮ Infinite-Duration Bidding Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• One-Counter Stochastic Games
• Qualitative Reachability in Stochastic BPA Games
• Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games
• A New Policy Evaluation Algorithm for Markov Decision Processes with Quasi Birth-Death Structure
• Automata, Languages and Programming
• Reachability in Recursive Markov Decision Processes