Recursive stochastic games with positive rewards
DOI10.1016/j.tcs.2018.12.018zbMath1431.91022OpenAlexW2907632475WikidataQ128668778 ScholiaQ128668778MaRDI QIDQ2422034
Mihalis Yannakakis, Dominik Wojtczak, Kousha Etessami
Publication date: 18 June 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://www.pure.ed.ac.uk/ws/files/78236933/Recursive_Stochastic_Games_with_Positive_Rewards.pdf
linear programmingmulti-type branching processesstochastic context-free grammarsrecursive Markov chainstotal expected rewardpolicy iteration and strategy improvement algorithmsprobabilistic pushdown systemsrecursive Markov decision processesrecursive simple stochastic games
Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15) Markov and semi-Markov decision processes (90C40) Algorithmic game theory and complexity (91A68)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Qualitative reachability in stochastic BPA games
- Runtime analysis of probabilistic programs with unbounded recursion
- Reachability in recursive Markov decision processes
- How easy is local search?
- The complexity of stochastic games
- Undecidable problems for probabilistic automata of fixed dimension
- Greatest fixed points of probabilistic min/max polynomial equations, and reachability for branching Markov decision processes
- Recursive Markov Decision Processes and Recursive Stochastic Games
- Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
- On the Complexity of Nash Equilibria and Other Fixed Points
- Minimizing Expected Termination Time in One-Counter Markov Decision Processes
- Random walks with “back buttons” (extended abstract)
- An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms
- Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
- Settling the complexity of computing two-player Nash equilibria
- Recursive Stochastic Games with Positive Rewards
- Exponential Lower Bounds for Policy Iteration
- Growth Optimality for Branching Markov Decision Chains
- Optimization of Multitype Branching Processes
- Biological Sequence Analysis
- The determinacy of Blackwell games
- Expected Termination Time in BPA Games
- The Complexity of Computing a Nash Equilibrium
- Branching Processes
- Model Checking Probabilistic Pushdown Automata
- On Nonterminating Stochastic Games
- Discrete Dynamic Programming with Sensitive Discount Optimality Criteria
