MARL Problem Formulation: Stochastic Games

To effectively design algorithms for multiple interacting agents, a framework is needed that extends the Markov Decision Process (MDP) model, which is typically used in single-agent reinforcement learning. The standard mathematical model for multi-agent sequential decision-making under uncertainty is the Stochastic Game, also commonly referred to as a Markov Game. This formalism provides the foundation for understanding and tackling the complexities introduced by agent interactions.

A Stochastic Game (SG) generalizes the MDP by incorporating multiple agents whose actions collectively influence transitions and rewards. Let's define the components formally:

A finite set of agents, $\mathcal{N} = \{1, 2, ..., N\}$ , where $N \ge 2$ .
A state space, $\mathcal{S}$ , representing the possible configurations of the environment. This is typically assumed to be shared or fully observable by all agents, although partially observable extensions (POSGs or Dec-POMDPs) exist for more complex scenarios.
An action space for each agent, $\mathcal{A}_i$ . Each agent $i$ selects an action $a_i \in \mathcal{A}_i$ .
A joint action space, $\mathcal{A} = \mathcal{A}_1 \times \mathcal{A}_2 \times ... \times \mathcal{A}_N$ . A joint action $\mathbf{a} = (a_1, a_2, ..., a_N) \in \mathcal{A}$ consists of one action chosen by each agent.
A state transition probability function, $P: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]$ . This function defines the probability of transitioning to the next state $s' \in \mathcal{S}$ , given the current state $s \in \mathcal{S}$ and the joint action $\mathbf{a} \in \mathcal{A}$ . We write this as $P(s' | s, \mathbf{a})$ . Notice the critical difference from MDPs: the next state distribution depends on the actions taken by all agents, not just one.
A reward function for each agent, $R_i: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ . Each agent $i$ receives a reward $r_i$ based on the current state $s$ , the joint action $\mathbf{a}$ , and potentially the next state $s'$ . The reward $r_i = R_i(s, \mathbf{a}, s')$ is specific to agent $i$ and generally depends on what every agent did.
A discount factor, $\gamma \in [0, 1)$ , shared by all agents for calculating cumulative rewards.

Just as in MDPs, agents select actions based on policies. In MARL, we deal with a joint policy $\boldsymbol{\pi} = (\pi_1, \pi_2, ..., \pi_N)$ , where each $\pi_i$ is the policy for agent $i$ . Agent $i$ 's policy, $\pi_i: \mathcal{S} \rightarrow \mathcal{P}(\mathcal{A}_i)$ , maps states to probability distributions over its actions $\mathcal{A}_i$ . If the policies are deterministic, $\pi_i: \mathcal{S} \rightarrow \mathcal{A}_i$ .

Visualizing the Interaction

Imagine a simple scenario with two robots (Agent 1 and Agent 2) needing to coordinate pushing a box to a target location (State).

The diagram shows how the current state $s$ is observed by both agents. They independently choose actions $a_1$ and $a_2$ , forming a joint action $\mathbf{a}$ . This joint action, along with the state $s$ , dictates the transition probability to the next state $s'$ and determines the individual rewards $r_1$ and $r_2$ for each agent.

Non-Stationarity Explained Formally

The Stochastic Game formulation makes the non-stationarity problem, mentioned in the chapter introduction, explicit. Consider Agent $i$ 's perspective. It chooses action $a_i$ based on its policy $\pi_i(a_i | s)$ . The environment's response (next state $s'$ and reward $r_i$ ) depends on the joint action $\mathbf{a} = (a_i, \mathbf{a}_{-i})$ , where $\mathbf{a}_{-i}$ represents the actions of all other agents.

If the other agents' policies $\boldsymbol{\pi}_{-i}$ are changing (as they typically do during learning), then the effective transition dynamics $P(s' | s, a_i)$ and reward function $R_i(s, a_i)$ from Agent i's perspective are also changing, even if the underlying game dynamics $P(s' | s, \mathbf{a})$ and $R_i(s, \mathbf{a}, s')$ are fixed. This violates the Markov property assumption required by standard single-agent RL algorithms like Q-learning, making direct application problematic. The environment appears non-stationary because the behavior of other learning agents is part of Agent $i$ 's effective environment.

Types of Multi-Agent Interactions

Stochastic Games can model various interaction types, characterized by the agents' reward structures:

Fully Cooperative: All agents share the exact same reward function: $R_1 = R_2 = ... = R_N$ . Their goal is collective success. Examples include coordinating robot teams or synchronized tasks.
Fully Competitive (Zero-Sum): The agents have diametrically opposed goals. For two agents, $R_1 = -R_2$ . In general, $\sum_{i=1}^N R_i(s, \mathbf{a}, s') = 0$ for all $s, \mathbf{a}, s'$ . Classic board games like Chess or Go (ignoring draws) fall into this category.
Mixed (General-Sum): This is the most general case, encompassing situations with elements of both cooperation and competition. Agents have individual reward functions that are not necessarily aligned or directly opposed. Examples include traffic navigation, resource sharing, or economic markets.

Objective and Solution Concepts

In single-agent RL, the objective is typically to find a policy $\pi$ that maximizes the expected discounted cumulative reward, represented by the value function $V^{\pi}(s)$ or Q-function $Q^{\pi}(s, a)$ .

In MARL, the objective depends on the game type.

In cooperative settings, the goal is often to find a joint policy $\boldsymbol{\pi}$ that maximizes a common objective, like the shared expected return $\mathbb{E}[\sum_{t=0}^\infty \gamma^t R(s_t, \mathbf{a}_t, s_{t+1}) | s_0=s, \boldsymbol{\pi}]$ .
In competitive or mixed settings, the situation is more complex. Agents might aim to maximize their own reward, potentially leading to concepts from game theory like finding a Nash Equilibrium. A Nash Equilibrium is a joint policy $\boldsymbol{\pi}^* = (\pi_1^*, ..., \pi_N^*)$ such that no single agent $i$ can improve its expected return by unilaterally changing its policy $\pi_i^*$ , assuming all other agents $j \neq i$ keep their policies $\pi_j^*$ fixed.

We can define agent-specific value functions based on the joint policy $\boldsymbol{\pi}$ :

State-value function for agent $i$ : $V_i^{\boldsymbol{\pi}}(s) = \mathbb{E}_{\boldsymbol{\pi}}[\sum_{t=0}^\infty \gamma^t R_i(s_t, \mathbf{a}_t, s_{t+1}) | s_0=s]$
Action-value function for agent $i$ : $Q_i^{\boldsymbol{\pi}}(s, \mathbf{a}) = \mathbb{E}_{\boldsymbol{\pi}}[\sum_{t=0}^\infty \gamma^t R_i(s_t, \mathbf{a}_t, s_{t+1}) | s_0=s, \mathbf{a}_0=\mathbf{a}]$

Understanding the Stochastic Game framework is essential because it precisely defines the problem MARL algorithms aim to solve. It highlights the dependencies between agents and provides the mathematical structure needed to analyze agent interactions and the resulting non-stationarity challenge that subsequent sections will address.

Was this section helpful?

References

Stochastic Games, Lloyd S. Shapley, 1953 Proceedings of the National Academy of Sciences of the United States of America, Vol. 39 (National Academy of Sciences) DOI: 10.1073/pnas.39.10.1095 - Presents the seminal formal definition of stochastic games, establishing the theoretical framework for multi-agent sequential decision-making.
Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto, 2018 (MIT Press) - Provides a general introduction to reinforcement learning (2nd edition), including discussions on game theory and multi-agent aspects that offer fundamental context for MARL.
Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Yoav Shoham, Kevin Leyton-Brown, 2009 (Cambridge University Press) - This academic work offers a thorough treatment of multi-agent system foundations, detailed game theory, repeated games, and stochastic games.
Multi-Agent Reinforcement Learning: An Overview of Concepts and Applications, Lucian Buşoniu, Robert De Schutter, and Robert Babuška, 2010 (Springer) DOI: 10.1007/978-3-642-13627-1 - A dedicated text providing an overview of multi-agent reinforcement learning, focusing on the formulation of stochastic games and related solution concepts.
Multi-Agent Reinforcement Learning: A Comprehensive Survey, Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D’Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu and Sen Zhao, 2021 Foundations and Trends® in Machine Learning, Vol. 14 (now publishers) DOI: 10.1561/2200000083 - This extensive survey offers an up-to-date look at multi-agent reinforcement learning, covering stochastic games, non-stationarity, and current solution approaches.