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

DOI10.1287/moor.2018.0970zbMath1437.90157arXiv1202.4798OpenAlexW2993580538MaRDI QIDQ5108256

Mihalis Yannakakis, Kousha Etessami, Alistair Stewart

Publication date: 30 April 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

dynamic programmingMarkov decision processesgeneralized Newton methodpolynomial time algorithmsmultitype branching processesMarkovBellman optimality equationsanalysis of algorithms, programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Methods of quasi-Newton type (90C53) Markov and semi-Markov decision processes (90C40) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Model-free reinforcement learning for branching Markov decision processes

Cites Work

• Unnamed Item
• Unnamed Item
• Reachability in recursive Markov decision processes
• The complexity of stochastic games
• Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes
• Totally expanding multiplicative systems
• Recursive Markov Decision Processes and Recursive Stochastic Games
• Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
• Approximating the Termination Value of One-Counter MDPs and Stochastic Games
• Computing the Least Fixed Point of Positive Polynomial Systems
• Upper Bounds for Newton’s Method on Monotone Polynomial Systems, and P-Time Model Checking of Probabilistic One-Counter Automata
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations
• Recursive Stochastic Games with Positive Rewards
• On the Complexity of Numerical Analysis
• Matrix Analysis
• Growth Optimality for Branching Markov Decision Chains
• Optimization of Multitype Branching Processes
• Markov decision processes and regular events
• Branching Processes
• Model Checking Probabilistic Pushdown Automata
• A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes
• Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
• Branching processes in biology
• Handbook of Markov decision processes. Methods and applications

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