The Hitchiker’s Guide to Stochastic Games

This is the web-page for our work on solving stochastic games in a sound and efficient way through value iteration and partial exploration. In case you have any questions, please contact me or Maxi (click to write an email).

Theory: Should I Stay or Should I Go?

Our paper “Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives” by Jan Křetínský, Tobias Meggendorfer, and Maximilian Weininger (LICS 2023), presents a sound stopping criterion for value iteration in stochastic games in a unified way. The central slogan is to ask “Should I stay or should I go?”, which neatly identifies and fixes the core convergence problem of (interval) value iteration, namely spurious fixed points.

Click any of the buttons below to access the relevant details:

To cite, you can use the following BibTeX entry (or download it here):

@inproceedings{DBLP:conf/lics/KretinskyMW23,
  author       = {Jan K{\v{r}}et{\'{\i}}nsk{\'{y}} and
                  Tobias Meggendorfer and
                  Maximilian Weininger},
  title        = {Stopping Criteria for Value Iteration on Stochastic Games with Quantitative
                  Objectives},
  booktitle    = {{LICS}},
  pages        = {1--14},
  year         = {2023},
  doi          = {10.1109/LICS56636.2023.10175771}
}

Practice: Partial Exploration Tool 2.0

In our paper “Playing Games with your PET: Extending the Partial Exploration Tool to Stochastic Games” by Tobias Meggendorfer and Maximilian Weininger (CAV 2024), we implement the above algorithms in our tool PET (partial exploration tool). Furthermore, PET also extends partial exploration to stochastic games and comes with many engineering improvements. The artefact obtained both the available and reusable badge.

Click any of the buttons below to access the relevant details:

Cite information will be added once the paper is published.