Recursive Markov Decision Processes and Recursive Stochastic Games

DOI10.1145/2699431zbMath1333.91005OpenAlexW2220995138MaRDI QIDQ2796398

Mihalis Yannakakis, Kousha Etessami

Publication date: 24 March 2016

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2699431

zbMATH Keywords

Markov decision processesstochastic gamesmultitype branching processesstochastic context-free grammarsrecursive stochastic processes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15) Markov and semi-Markov decision processes (90C40) Grammars and rewriting systems (68Q42) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs, Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations, Model-free reinforcement learning for branching Markov decision processes, A denotational semantics for low-level probabilistic programs with nondeterminism, Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes, Recursive stochastic games with positive rewards, Probabilistic total store ordering, Unnamed Item, Unnamed Item, The uniform measure of simple regular sets of infinite trees, Optimally Resilient Strategies in Pushdown Safety Games, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars
• On the undecidability of probabilistic planning and related stochastic optimization problems
• Positional strategies for mean payoff games
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• The complexity of stochastic games
• The complexity of mean payoff games on graphs
• Undecidable problems for probabilistic automata of fixed dimension
• Quantitative solution of omega-regular games
• Finitely additive stochastic games with Borel measurable payoffs
• Concurrent reachability games
• An inequality for the discriminant of a polynomial
• Totally expanding multiplicative systems
• A lattice-theoretical fixpoint theorem and its applications
• Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
• Model Checking of Recursive Probabilistic Systems
• Computing the Least Fixed Point of Positive Polynomial Systems
• On the Complexity of Nash Equilibria and Other Fixed Points
• Random walks with “back buttons” (extended abstract)
• A Turnpike Theorem For A Risk-Sensitive Markov Decision Process with Stopping
• 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
• The complexity of quantitative concurrent parity games
• Matrix Analysis
• Growth Optimality for Branching Markov Decision Chains
• Optimization of Multitype Branching Processes
• Introduction to Matrix Analytic Methods in Stochastic Modeling
• The determinacy of Blackwell games
• The complexity of probabilistic verification
• Markov decision processes and regular events
• Termination of Probabilistic Concurrent Program
• Branching Processes
• Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
• Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games
• On the Existence of Stationary Optimal Strategies
• Automata, Languages and Programming
• Multiplicative Systems
• Stochastic Games
• Recursive Concurrent Stochastic Games
• Branching processes in biology
• Handbook of Markov decision processes. Methods and applications