The fundamental and simple model of Stochastic Games was introduced in the fifties by prominent mathematicians (Shapley, Bellman) and form today a well adopted and thoroughly studied notion, with applications in computer science, mathematics, economics, and beyond. This wide adoption implies that many different research communities are involved in the study of stochastic games, oftentimes with different but related goals. Each community develops different tools towards understanding stochastic games, leading to a very broad and diverse literature with a variety of techniques and approaches.

The goal of this Dagstuhl Seminar is to bring together researchers interested in the algorithmic aspects of Stochastic Games, from a theoretical as well as practical perspective. Towards this goal, we identify three research fields in which Stochastic Games play a prominent role and that have recently contributed to the understanding of Stochastic Games:

• Algorithms and Complexity theory, where the focus is on constructing efficient algorithms and relating the intrinsic complexity of solving stochastic games to other computational problems. Stochastic Games and variants are at the forefront of the most important open questions in the field and recent impressive results.
• Reinforcement Learning and Planning, which is concerned with solving Stochastic Games underlying an unknown environment. Reinforcement Learning, in particular through its interactions with Deep Learning, has seen tremendous success recently by achieving beyond human capabilities in a variety of domains. Yet many questions remain open, in particular towards making Reinforcement Learning techniques more robust and safe, providing formal guarantees on the obtained policy, as well as dealing efficiently with multiple objectives especially in multi-agent settings.
• Verification and Synthesis is concerned with modelling open systems involving competing agents, and uses Stochastic Games as an algorithmic back-end for certifying the properties of the system (Verification) or synthesizing controllers (Synthesis). Despite recent progress in constructing faster algorithms and abstractions, there is a growing need for more efficient algorithms for analyzing several variants of Stochastic Games.

Creative Commons BY 4.0

Nathanaël Fijalkow, Jan Kretínský, Ann Nowé, and Uri Zwick