Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes

DOI10.1016/j.ic.2018.02.013zbMath1394.60085arXiv1502.05533OpenAlexW2790209383MaRDI QIDQ1641009

Alistair Stewart, Kousha Etessami, Mihalis Yannakakis

Publication date: 14 June 2018

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

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

zbMATH Keywords

greatest fixed pointBellman optimality equationsbranching Markov decision processesBellman optimalityprobabilistic polynomial system

Mathematics Subject Classification ID

Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (8)

Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations ⋮ Model-free reinforcement learning for branching Markov decision processes ⋮ Recursive stochastic games with positive rewards ⋮ A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate minimization of weighted tree automata

Cites Work

• Qualitative reachability in stochastic BPA games
• Reachability in recursive 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
• Model Checking Stochastic Branching Processes
• Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition
• 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
• Matrix Analysis
• Growth Optimality for Branching Markov Decision Chains
• Optimization of Multitype Branching Processes
• Markov decision processes and regular events
• Model Checking Probabilistic Pushdown Automata
• Analysis of Probabilistic Basic Parallel Processes
• Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
• Unnamed Item

This page was built for publication: Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes