On the Performance Evaluation of Algorithms for Stochastic Games

Stochastic games (SGs) (with a reachability objective) are considered a fundamental construct both from a theoretical and a practical point of view. Regarding one aspect of their practical importance is that SGs serve as a standard model in the quantitative verification and strategy synthesis for complex systems, since they are able to express both stochastic and non-stochastic uncertainty. As a result, solving these types of games is an important problem which has gained a lot of interest over the years. The most common solution techniques for reachability problems for SGs fall under the scope of the dynamic (e. g. value/strategy iteration, or extensions thereof) and quadratic programming paradigms [1]. However, the performance of these algorithms is often sensitive to the underlying graph structure of the models and assessing their performance can be challenging [2]. In addition, in certain cases, worst-case analysis can be pessimistic and does not provide any practical guidance over which algorithm to choose for a particular type of model. Moreover, the limited availability of realistic case studies renders the performance assessment of these algorithms based on experimental analysis not a viable alternative. In addition, the few specialized handcrafted reachability models which are available can be misleading in accurately evaluating the performance of algorithms over more general problems, since only extreme cases are considered. We address these issues by developing an automated approach for the experimental comparison of algorithms by giving the ability to the users to emphasize towards specific model structures (e. g. amount of strongly connected components, etc.). This is based on our random SG generator and its extensions which facilitate the performance evaluation of algorithms for solving SGs, by allowing the user to analyze the sensitivity of the algorithms against several model parameters. In this talk, I will first address the model-sensitive nature of these algorithms with respect to their performance, and then how our approach could help in tackling this issue. This is joint work with Muqsit Azeem, Jan Křetínský, Alexander Slivinskiy and Maximilian Weininger.

Authors

• Alexandros Evangelidis

Keywords

No keywords are indexed for this paper.