Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations

DOI10.1007/978-3-642-31594-7_27zbMath1272.68458OpenAlexW1493119321MaRDI QIDQ2843258

Mihalis Yannakakis, Kousha Etessami, Alistair Stewart

Publication date: 12 August 2013

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

Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (8)

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations ⋮ Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes ⋮ A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars ⋮ Recursive stochastic games with positive rewards ⋮ A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Recursive Markov Decision Processes and Recursive Stochastic Games

This page was built for publication: Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations