To effectively design algorithms for multiple interacting agents, we need a framework that extends the familiar Markov Decision Process (MDP) used in single-agent RL. 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.