Stochastic games

By ∗. NathanaëlFijalkow, ∗. JanKretinsky, ∗. AnnNowé, †. GabrielBathie, Ann Nowé License, M. Akian, Dani Dorfman, Haim Kaplan, Uri Zwick, David Parker and 5 more. 2019

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. The seminar fostered lively discussions during open problem sessions and working groups, culminating in a collaborative exploration of open questions and potential research directions. Seminar June 2–7, 2024 – https://www.dagstuhl.de/24231 2012 ACM Subject Classification Theory of computation → Algorithmic game theory and mechanism design; Theory of computation → Convergence and learning in games; Theory of computation → Probabilistic computation; Theory of computation → Representations of games and their complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Scaling Multi-Agent Reinforcement Learning with Selective Parameter Sharing (2021, background): “Markov Games: A Markov game (e.g. (Littman, 1994); also known as a stochastic game (Shapley, 1953)) with partial observability is deﬁned by the tuple ( N , S , { O i } i ∈N , { A i } i ∈N , P , { R i } i ∈N ) , with agents i ∈ N = { 1 , . . . , N } , state space S , joint observation space O = O 1…”
Mean Field Multi-Agent Reinforcement Learning (2018, background): “The marriage of the two gives rise to the general framework of stochastic game (Shapley, 1953).”
Emergent Coordination Through Competition (2019, background): “MARL is typically modelled as a Markov game (Shapley, 1953; Littman, 1994), which comprises: a state space S, n agents with observation and action sets O(1), .”
Multi-Agent Connected Autonomous Driving using Deep Reinforcement Learning (2019, methodology): “tion: [[32, [8, 8], 4], [64, [4, 4], 2], [64, [3, 3], 1]] followed Fig.”
Local Information Agent Modelling in Partially-Observable Environments (2021, methodology): “We model the problem as a Partially-Observable Stochastic Game (POSG) [Shapley, 1953, Hansen et al., 2004] which consists of N agents I = { 1 , 2 , ..., N } , a state space S , the joint action space A = A 1 × ... × A N , a transition function P : S × A × S → [0 , 1] specifying the transition…”
Adversarial Policies: Attacking Deep Reinforcement Learning (2019, methodology): “We model the victim as playing against an opponent in a two-player Markov game (Shapley, 1953).”
Multiagent Bidirectionally-Coordinated Nets for Learning to Play StarCraft Combat Games (2017, methodology): “We formulate it as a zero-sum Stochastic Game (SG) [28, 38, 39], i.”
Rethinking Formal Models of Partially Observable Multiagent Decision Making (2019, background): “Multiagent Reinforcement Learning Separate, but recently converging lines of research can be traced to Markov Decision Processes (MDPs) (Bellman, 1957) and Stochastic Games (SGs) (Shapley, 1953).”
Applications of Deep Reinforcement Learning in Communications and Networking: A Survey (2018, background): “2) Markov Games: In game theory, a Markov game, or a stochastic game [16], is a dynamic game with probabilistic transitions played by multiple players, i.”
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play (2020, methodology): “…Tennenholtz, 2002), and is conceptually appealing for multi-agent RL too since the multi-agent structure does not add complexity onto the model estimation part and only requires an appropriate multi-agent planning algorithm (such as value iteration for games (Shapley, 1953)) in a black-box fashion.”
From Motor Control to Team Play in Simulated Humanoid Football (2021, methodology): “Wemodel each of the 𝐾 tasks (the football game and the training drills) as a multi-agent reinforcement learning (MARL) problem using the framework of 𝑛-player Stochastic Games (58) (see Appendix B.1 for more detail).”
Edge Learning for B5G Networks With Distributed Signal Processing: Semantic Communication, Edge Computing, and Wireless Sensing (2022, unknown): “Unlike single-agent RL, MARL is usually modeled as a Markov game (MG) or stochastic game (SG) [93].”
Maintaining cooperation in complex social dilemmas using deep reinforcement learning (2017, methodology): “We can extend standard game theoretic deﬁnitions to the Markov Decision Problem (MDP) setups as follows: Deﬁnition 2 (Shapley (1953)) A (2-player) Markov game consists of which tells us the probability distribution on the next state as a function of current state and actions which tells us the…”
PettingZoo: Gym for Multi-Agent Reinforcement Learning (2020, unknown): “This model is very similar to, and strictly more general than, multi-agent MDPs [Boutilier, 1996], Dec-POMDPs [Bernstein et al., 2002], and Stochastic (“Markov”) games [Shapley, 1953]).”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, background): “We focus on the special case of two-player zero-sum Markov games (Shapley, 1953; Littman, 1994), a generaliztion of Markov Decision Processes (MDPs) to the two-player setting.”
Action Robust Reinforcement Learning and Applications in Continuous Control (2019, background): “Maitra & Parthasarathy (1970) generalized result of Shapley 1Our code can be found in the following repository: https://github.com/tesslerc/ActionRobustRL (1953) and established that, under proper conditions, the zero sum game has value for any s ∈ S, i.e., v∗(s) = max π∈P(Π) min π̄∈Π Eπ,π̄[ ∞∑ t=0…”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, unknown): “sumption 1, for any policy pair (π,ν)and any h ∈ [H], there exists a vector wπ,ν h ∈R d such that Qπ,ν h (x,a,b)= φ(x,a,b),wπ,ν h , ∀(x,a,b)∈S×A×A. 1This holds, e.g., when the state space is compact (Maitra and Parthasarathy, 1970, 1971). 6 Proof. By Bellman equation and linearity of r h and P h, we”