Optimistic and topological value iteration for simple stochastic games

DOI10.1007/978-3-031-19992-9_18zbMATH Open1522.68295arXiv2207.14417OpenAlexW4312411454MaRDI QIDQ6160920FDOQ6160920

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)

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.

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

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

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)

Cites Work

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

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)