Comparison of algorithms for simple stochastic games

DOI10.1016/j.ic.2022.104885OpenAlexW4214829027MaRDI QIDQ2105472

Jan Křetínský, Maximilian Weininger, Emanuel Ramneantu, Alexander Slivinskiy

Publication date: 8 December 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2022.104885

zbMATH Keywords

algorithmsquadratic programmingstochastic gamesformal methodsvalue iterationprobabilistic verificationstrategy iteration

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• GAVS
• GIST
• PRISM-games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantitative verification and strategy synthesis for stochastic games
• Strategy improvement for concurrent reachability and turn-based stochastic safety games
• A survey of stochastic \(\omega \)-regular games
• A game-based abstraction-refinement framework for Markov decision processes
• Another sub-exponential algorithm for the simple stochastic game
• The complexity of stochastic games
• The complexity of mean payoff games on graphs
• A subexponential randomized algorithm for the simple stochastic game problem
• Ensuring the reliability of your model checker: interval iteration for Markov decision processes
• Widest paths and global propagation in bounded value iteration for stochastic games
• Stochastic games with lexicographic reachability-safety objectives
• Optimistic value iteration
• Automatic verification of competitive stochastic systems
• The complexity of solving reachability games using value and strategy iteration
• Interval iteration algorithm for MDPs and IMDPs
• On Stochastic Games with Multiple Objectives
• Solving Simple Stochastic Games with Few Coin Toss Positions
• Verification of Markov Decision Processes Using Learning Algorithms
• Value Iteration
• The polynomial solvability of convex quadratic programming
• The complexity of probabilistic verification
• On the Complexity of Value Iteration
• Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes
• Approximating Values of Generalized-Reachability Stochastic Games
• Computationally Related Problems
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Model-Checking ω-Regular Properties of Interval Markov Chains
• On Nonterminating Stochastic Games
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Sound value iteration

This page was built for publication: Comparison of algorithms for simple stochastic games