Optimistic and topological value iteration for simple stochastic games

DOI10.1007/978-3-031-19992-9_18MaRDI QIDQ6160920zbMATH OpenOpenAlexFDO

Authors Muqsit Azeem, Alexandros Evangelidis, Jan Křetínský, Alexander Slivinskiy, Maximilian Weininger

Publication date 2 June 2023

Published in Automated Technology for Verification and Analysis (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Abstract: While value iteration (VI) is a standard solution approach to simple stochastic games (SSGs), it suffered from the lack of a stopping criterion. Recently, several solutions have appeared, among them also "optimistic" VI (OVI). However, OVI is applicable only to one-player SSGs with no end components. We lift these two assumptions, making it available to general SSGs. Further, we utilize the idea in the context of topological VI, where we provide an efficient precise solution. In order to compare the new algorithms with the state of the art, we use not only the standard benchmarks, but we also design a random generator of SSGs, which can be biased towards various types of models, aiding in understanding the advantages of different algorithms on SSGs.

Recommendations

• Characterization and simplification of optimal strategies in positive stochastic games
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Simplifying Optimal Strategies in Stochastic Games
• Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games
• Simplifying optimal strategies in \(\limsup\) and \(\liminf\) stochastic games
• Optimization models for a class of structured stochastic games
• Relative Value Iteration for Stochastic Differential Games
• Juegos estocasticos continuos: Valor y estrategias optimas

Cites work

• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• A reduction from parity games to simple stochastic games
• Automatic verification of competitive stochastic systems
• Comparison of algorithms for simple stochastic games
• Ensuring the reliability of your model checker: interval iteration for Markov decision processes
• Interval iteration algorithm for MDPs and IMDPs
• On Nonterminating Stochastic Games
• Optimistic value iteration
• Quantitative verification and strategy synthesis for stochastic games
• Robot motion planning: A game-theoretic foundation
• Sound value iteration
• The complexity of solving stochastic games on graphs
• The complexity of stochastic games
• Topological value iteration algorithms
• Value Iteration
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Verification of Markov decision processes using learning algorithms
• Widest paths and global propagation in bounded value iteration for stochastic games

Cited in

(6)

• Widest paths and global propagation in bounded value iteration for stochastic games
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• Value iteration for simple stochastic games: stopping criterion and learning algorithm
• A practitioner's guide to MDP model checking algorithms
• Certificates for probabilistic pushdown automata via optimistic value iteration

This page was built for publication: Optimistic and topological value iteration for simple stochastic games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6160920)