TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 24231

Stochastic Games

( Jun 02 – Jun 07, 2024 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/24231

Organizers

Contact

Shared Documents


Schedule

Summary

The Dagstuhl Seminar on Stochastic Games brought together leading researchers and practitioners in the field to discuss recent advances, challenges, and future directions. The seminar featured a series of tutorials, invited talks, and contributed talks, which provided a comprehensive overview of the latest developments in Markov decision processes, reinforcement learning, and stochastic game theory. Key results from the seminar include novel insights into branching stochastic games, the development of new algorithms for solving concurrent and population games, and advancements in the theoretical understanding of efficient solutions for Markov decision processes. The seminar fostered lively discussions during open problem sessions and working groups, culminating in a collaborative exploration of open questions and potential research directions.

Overview of the Invited Talks and Tutorials:

  • Yinyu Ye: „Progresses and Open Questions on the Markov Decision / Game Process“ - Discussed recent advancements and open problems in the field of Markov decision processes and games.
  • Dave Parker: „PRISM-games“ - Provided a tutorial on PRISM-games, a tool for modeling and analyzing probabilistic systems.
  • Kousha Etessami: „Branching MDPs, Branching Stochastic Games, and Generalizations of Newton’s Method“ - Explored branching Markov decision processes and games, and introduced generalizations of Newton’s method for these models.
  • Aaron Sidford: „Theoretical Advances in Efficiently Solving Markov Decision Processes“ - Highlighted recent theoretical progress in solving Markov decision processes more efficiently.
  • Sven Schewe: „Automata for Profit and Pleasure“ - Discussed the applications of automata theory in both practical and theoretical contexts.

Overall, the seminar was a highly productive event, advancing the collective understanding of stochastic games and fostering future research collaborations.

Copyright Nathanaël Fijalkow, Jan Kretinsky, and Ann Nowé

Motivation

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.
Copyright Nathanaël Fijalkow, Jan Kretínský, Ann Nowé, and Uri Zwick

Participants

Please log in to DOOR to see more details.

  • Marianne Akian (Inria & CMAP, Ecole polytechnique - Palaiseau, FR) [dblp]
  • Xavier Allamigeon (INRIA & Ecole Polytechnique - Palaiseau, FR) [dblp]
  • Guy Avni (University of Haifa, IL) [dblp]
  • Christel Baier (TU Dresden, DE) [dblp]
  • Gabriel Bathie (University of Bordeaux, FR) [dblp]
  • Eline Bovy (Radboud University Nijmegen, NL) [dblp]
  • Antonio Casares (University of Bordeaux, FR) [dblp]
  • Florent Delgrange (Free University of Brussels, BE) [dblp]
  • Dani Dorfman (Tel Aviv University, IL) [dblp]
  • Kousha Etessami (University of Edinburgh, GB) [dblp]
  • Nathanaël Fijalkow (CNRS - Talence, FR) [dblp]
  • Stéphane Gaubert (INRIA & CMAP, Ecole polytechnique - Palaiseau, FR) [dblp]
  • Kristoffer Arnsfelt Hansen (Aarhus University, DK) [dblp]
  • Sebastian Haslebacher (ETH Zürich, CH) [dblp]
  • Sebastian Junges (Radboud University Nijmegen, NL) [dblp]
  • Marcin Jurdzinski (University of Warwick - Coventry, GB) [dblp]
  • Jan Kretinsky (Masaryk University - Brno, CZ) [dblp]
  • Antonin Kucera (Masaryk University - Brno, CZ) [dblp]
  • Karoliina Lehtinen (Aix-Marseille University, FR) [dblp]
  • Georg Loho (FU Berlin, DE & University of Twente - Enschede, NL) [dblp]
  • James C. A. Main (F.R.S.-FNRS & UMONS - University of Mons, BE) [dblp]
  • Corto Mascle (University of Bordeaux, FR) [dblp]
  • Théo Matricon (University of Bordeaux, FR) [dblp]
  • Petr Novotný (Masaryk University - Brno, CZ) [dblp]
  • Ann Nowé (Free University of Brussels, BE) [dblp]
  • David Parker (University of Oxford, GB) [dblp]
  • Guillermo A. Pérez (University of Antwerp, BE) [dblp]
  • Jakob Piribauer (TU Dresden, DE) [dblp]
  • Roxana Radulescu (VU - Brussels, BE) [dblp]
  • Sven Schewe (University of Liverpool, GB) [dblp]
  • Guruprerana Shabadi (IMDEA Software Institute - Madrid, ES)
  • Aaron Sidford (Stanford University, US) [dblp]
  • Mateusz Skomra (LAAS - Toulouse, FR) [dblp]
  • Yann Strozecki (University of Versailles, FR) [dblp]
  • Marnix Suilen (Radboud University Nijmegen, NL) [dblp]
  • K. S. Thejaswini (IST Austria - Klosterneuburg, AT) [dblp]
  • Patrick Totzke (University of Liverpool, GB) [dblp]
  • Pierre Vandenhove (University of Bordeaux, FR) [dblp]
  • Muthukumar Vidya (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Maximilian Weininger (IST Austria - Klosterneuburg, AT) [dblp]
  • Yinyu Ye (Stanford University, US & Shanghai JiaoTong University, CN) [dblp]

Classification
  • Artificial Intelligence
  • Computational Complexity
  • Computer Science and Game Theory

Keywords
  • Stochastic Games
  • Reinforcement Learning
  • Optimisation
  • Multi-agent Systems