26 Multi-Agent Reinforcement Learning

Core idea: a Markov decision process assumes that a single agent acts in an environment. Multi-agent reinforcement learning studies sequential decision problems in which several agents act at the same time, and each agent’s learning changes the effective environment seen by the others.

26.1 Learning goals

After reading this chapter, students should be able to:

define finite Markov games precisely;
distinguish cooperative, competitive, and general-sum objectives;
derive Bellman equations for fixed joint policies;
derive the Shapley optimality equation for two-player zero-sum Markov games;
compute mixed strategies in small matrix games;
explain why independent learners face a nonstationary environment;
compare independent learning, minimax learning, centralized training with decentralized execution, and mean-field approximation;
implement small multi-agent examples in Python.

26.2 23.1 From MDPs to Markov games

A finite discounted MDP has one decision maker. At each time \(t\), the agent observes \(S_t\), chooses \(A_t\), receives reward \(R_{t+1}\), and the next state is drawn from \(P(s' \mid s,a)\).

In a multi-agent problem, several agents choose actions simultaneously. For two agents, a finite discounted Markov game is a tuple

\[ M = (S, A_1, A_2, P, r_1, r_2, \gamma), \]

where:

\(S\) is a finite state space;
\(A_i\) is the finite action space of agent \(i\);
\(P(s' \mid s,a_1,a_2)\) is the controlled transition kernel;
\(r_i(s,a_1,a_2)\) is the expected one-step reward for agent \(i\);
\(0 \leq \gamma < 1\) is the discount factor.

The controlled Markov property is

\[ P(S_{t+1}=s' \mid H_t,A_{1,t}=a_1,A_{2,t}=a_2) = P(s' \mid S_t,a_1,a_2), \]

where \(H_t\) denotes the full history before time \(t\).

The key change from a single-agent MDP is that the transition and reward depend on a joint action

\[ a = (a_1,a_2) \in A_1 \times A_2. \]

For \(m\) agents, the joint action is

\[ a = (a_1,\ldots,a_m) \in A_1 \times \cdots \times A_m. \]

This joint-action dependence is mathematically simple but algorithmically difficult: the effective environment seen by agent \(i\) depends on the policies of all other agents.

26.3 23.2 Joint policies

A stationary randomized policy for agent \(i\) is a conditional distribution

\[ \pi_i(a_i \mid s), \]

with

\[ \pi_i(a_i \mid s) \geq 0, \qquad \sum_{a_i \in A_i}\pi_i(a_i \mid s)=1. \]

A joint policy is

\[ \pi = (\pi_1,\pi_2). \]

A common modeling assumption is that the agents randomize independently conditional on the state:

\[ \pi(a_1,a_2 \mid s) = \pi_1(a_1 \mid s)\pi_2(a_2 \mid s). \]

Under a fixed joint policy, the Markov game becomes an ordinary Markov reward process for each agent. The policy-induced transition matrix is

\[ P_\pi(s,s') = \sum_{a_1 \in A_1}\sum_{a_2 \in A_2} \pi_1(a_1 \mid s)\pi_2(a_2 \mid s)P(s' \mid s,a_1,a_2). \]

The policy-induced reward vector for agent \(i\) is

\[ r_{i,\pi}(s) = \sum_{a_1 \in A_1}\sum_{a_2 \in A_2} \pi_1(a_1 \mid s)\pi_2(a_2 \mid s)r_i(s,a_1,a_2). \]

Thus, for a fixed joint policy,

\[ V_i^\pi = r_{i,\pi}+\gamma P_\pi V_i^\pi, \]

and therefore

\[ V_i^\pi = (I-\gamma P_\pi)^{-1}r_{i,\pi}. \]

This is the first important reduction:

Fixed joint policy reduction. A Markov game plus a fixed joint policy becomes a Markov reward process for each agent.

26.4 23.3 Types of multi-agent objectives

Multi-agent problems are usually classified by the reward structure.

26.4.1 Fully cooperative games

In a fully cooperative game, all agents share the same reward:

\[ r_1(s,a_1,a_2)=r_2(s,a_1,a_2)=r(s,a_1,a_2). \]

The goal is to maximize a common return. This setting appears in distributed robotics, traffic control, multi-agent resource allocation, and team decision problems.

26.4.2 Two-player zero-sum games

In a two-player zero-sum game,

\[ r_1(s,a_1,a_2) = -r_2(s,a_1,a_2). \]

Agent 1 is the maximizer and agent 2 is the minimizer. This setting is mathematically clean because it leads to minimax Bellman equations and saddle-point values.

26.4.3 General-sum games

In a general-sum game, the rewards have no special relation. Agents may have partially aligned and partially conflicting objectives. This setting is the most realistic but also the most mathematically delicate because equilibrium selection becomes important.

26.5 23.4 Matrix games as one-state Markov games

Before studying dynamic games, it is useful to study a one-state simultaneous game. Suppose agent 1 chooses a row action and agent 2 chooses a column action. The payoff matrix for agent 1 is

\[ G = \begin{bmatrix} G_{11} & G_{12} \\ G_{21} & G_{22} \end{bmatrix}. \]

If the game is zero-sum, agent 2 receives payoff \(-G_{ij}\).

A mixed strategy for the row player is \(x \in \Delta(A_1)\) and a mixed strategy for the column player is \(y \in \Delta(A_2)\). The expected payoff to the row player is

\[ u(x,y)=x^TGy. \]

The value of the zero-sum matrix game is

\[ v^* = \max_{x \in \Delta(A_1)}\min_{y \in \Delta(A_2)} x^TGy. \]

Von Neumann’s minimax theorem says that, for finite zero-sum games,

\[ \max_x\min_y x^TGy = \min_y\max_x x^TGy. \]

This equality is not just an algebraic curiosity. It is the equilibrium condition that lets us write Bellman optimality equations for zero-sum Markov games.

26.5.1 Interactive: payoff landscape for a matrix game

The graph shows the expected payoff \(x^TGy\) as the two mixed strategies vary.

26.6 23.5 Solving a two-action zero-sum matrix game

For a \(2 \times 2\) zero-sum game, write the row player’s strategy as

\[ x = (p,1-p), \]

and the column player’s strategy as

\[ y = (q,1-q). \]

If the row player chooses \(p\), the expected payoff against column 1 is

\[ L_1(p)=pG_{11}+(1-p)G_{21}, \]

and against column 2 is

\[ L_2(p)=pG_{12}+(1-p)G_{22}. \]

The column player chooses the smaller of these two quantities, so the row player maximizes

\[ \min\{L_1(p),L_2(p)\}. \]

At an interior optimum, the two lines are equal:

\[ pG_{11}+(1-p)G_{21} = pG_{12}+(1-p)G_{22}. \]

Solving gives

\[ p^* = \frac{G_{22}-G_{21}}{G_{11}-G_{12}-G_{21}+G_{22}}, \]

provided this number lies in \([0,1]\). Boundary cases occur when the optimal strategy is pure.

26.6.1 Interactive: minimax line intersection

The lower envelope of two payoff lines determines the row player’s value.

26.7 23.6 Python example: a small matrix game

import numpy as np

G = np.array([[1.0, -1.0],
              [-1.0, 1.0]])   # matching pennies payoff for row player

ps = np.linspace(0, 1, 1001)
values = []
for p in ps:
    x = np.array([p, 1 - p])
    payoffs_against_columns = x @ G
    values.append(payoffs_against_columns.min())

best_index = int(np.argmax(values))
p_star = ps[best_index]
v_star = values[best_index]

print("Approximate optimal row probability p*:", round(p_star, 3))
print("Approximate game value:", round(v_star, 3))
x_star = np.array([p_star, 1 - p_star])
print("Expected payoff against each pure column action:", x_star @ G)

Approximate optimal row probability p*: 0.5
Approximate game value: 0.0
Expected payoff against each pure column action: [0. 0.]

In matching pennies, the equilibrium strategy is to randomize equally:

\[ x^* = (1/2,1/2), \qquad y^* = (1/2,1/2), \qquad v^* = 0. \]

The point is not the numerical value but the equilibrium principle: the row player chooses a strategy that maximizes the payoff guaranteed against the worst column response.

26.8 23.7 Zero-sum Markov games and the Shapley equation

For a discounted two-player zero-sum Markov game, let \(r(s,a_1,a_2)\) denote agent 1’s reward. Agent 2 receives \(-r(s,a_1,a_2)\).

If the current value estimate is \(V\), define the state-wise matrix

\[ M_V(s,a_1,a_2) = r(s,a_1,a_2) + \gamma\sum_{s' \in S}P(s' \mid s,a_1,a_2)V(s'). \]

This is the one-step reward plus the discounted continuation value. At state \(s\), the two players face a matrix game with payoff matrix \(M_V(s)\). The optimal Bellman-Shapley operator is

\[ (TV)(s) = \max_{x \in \Delta(A_1)}\min_{y \in \Delta(A_2)}x^T M_V(s)y. \]

The optimal value satisfies the Shapley equation

\[ V^* = TV. \]

More explicitly,

\[ V^*(s) = \max_{x \in \Delta(A_1)}\min_{y \in \Delta(A_2)} \sum_{a_1,a_2}x(a_1)y(a_2) \left[ r(s,a_1,a_2) + \gamma\sum_{s'}P(s' \mid s,a_1,a_2)V^*(s') \right]. \]

The operator \(T\) is a \(\gamma\)-contraction in the sup norm:

\[ \|TV-TW\|_\infty \leq \gamma\|V-W\|_\infty. \]

The reason is that changing \(V\) to \(W\) changes every entry of every continuation payoff matrix by at most \(\gamma\|V-W\|_\infty\). Taking a max-min value of a matrix cannot amplify entrywise perturbations. Therefore value iteration converges:

\[ V_{k+1}=TV_k, \qquad V_k \to V^*. \]

26.8.1 Interactive: value iteration for a zero-sum Markov game

This demonstration shows convergence of the Shapley value iteration in a small two-state game.

26.9 23.8 Python example: Shapley value iteration

The following code uses a grid search over mixed strategies for each state-wise \(2 \times 2\) matrix game. This is not the best method for large games, but it makes the mathematics transparent.

import numpy as np

nS = 2
nA1 = 2
nA2 = 2
gamma = 0.9

# r[s, a1, a2]
r = np.array([
    [[ 1.0, -1.0],
     [-0.5,  0.5]],
    [[ 0.2, -0.2],
     [-1.0,  1.0]]
])

# P[s, a1, a2, s_next]
P = np.zeros((nS, nA1, nA2, nS))
P[0, 0, 0] = [0.80, 0.20]
P[0, 0, 1] = [0.50, 0.50]
P[0, 1, 0] = [0.40, 0.60]
P[0, 1, 1] = [0.70, 0.30]
P[1, 0, 0] = [0.30, 0.70]
P[1, 0, 1] = [0.60, 0.40]
P[1, 1, 0] = [0.20, 0.80]
P[1, 1, 1] = [0.50, 0.50]


def matrix_game_value_2x2(G, grid_size=1001):
    ps = np.linspace(0, 1, grid_size)
    best_value = -np.inf
    best_p = None
    for p in ps:
        x = np.array([p, 1 - p])
        guaranteed = np.min(x @ G)
        if guaranteed > best_value:
            best_value = guaranteed
            best_p = p
    return best_value, best_p

V = np.zeros(nS)
history = []
for k in range(60):
    V_new = np.zeros(nS)
    policies = []
    for s in range(nS):
        Gs = np.zeros((nA1, nA2))
        for a1 in range(nA1):
            for a2 in range(nA2):
                Gs[a1, a2] = r[s, a1, a2] + gamma * P[s, a1, a2] @ V
        V_new[s], p_star = matrix_game_value_2x2(Gs)
        policies.append(p_star)
    history.append(V_new.copy())
    if np.max(np.abs(V_new - V)) < 1e-8:
        break
    V = V_new

print("Approximate zero-sum Markov-game value:", np.round(V, 4))
print("Approximate row-player mixed probabilities:", np.round(policies, 3))
print("Iterations:", len(history))

Approximate zero-sum Markov-game value: [-0.0045 -0.0043]
Approximate row-player mixed probabilities: [0.333 0.833]
Iterations: 60

The update has the same outer structure as ordinary value iteration, but the inner maximization over actions is replaced by the solution of a state-wise matrix game.

26.10 23.9 General-sum Markov games and Nash equilibria

In a general-sum game, each agent has its own reward. A joint policy \(\pi^*=(\pi_1^*,\pi_2^*)\) is a Markov perfect Nash equilibrium if, for every state \(s\),

\[ V_1^{\pi_1^*,\pi_2^*}(s) \geq V_1^{\pi_1,\pi_2^*}(s) \]

for every alternative policy \(\pi_1\), and

\[ V_2^{\pi_1^*,\pi_2^*}(s) \geq V_2^{\pi_1^*,\pi_2}(s) \]

for every alternative policy \(\pi_2\).

This means no agent can improve its own value by changing its policy alone. Unlike zero-sum games, there may be many Nash equilibria, and they may have different values. This creates an equilibrium-selection problem.

A one-state coordination game illustrates the issue. Suppose both players receive payoff \(1\) if they choose the same action and \(0\) otherwise. Both \((A,A)\) and \((B,B)\) are Nash equilibria. Learning dynamics may converge to either equilibrium depending on initialization, exploration, and noise.

26.10.1 Interactive: coordination and equilibrium selection

The graph shows how different initial conditions can lead to different equilibria in a simple coordination learning dynamic.

26.11 23.10 Independent learners and nonstationarity

A tempting approach is to let each agent ignore the learning process of the others and run a single-agent RL algorithm. For agent 1, the effective transition kernel under agent 2’s current policy is

\[ P^{\pi_2}(s' \mid s,a_1) = \sum_{a_2}\pi_2(a_2 \mid s)P(s' \mid s,a_1,a_2). \]

The effective reward is

\[ r_1^{\pi_2}(s,a_1) = \sum_{a_2}\pi_2(a_2 \mid s)r_1(s,a_1,a_2). \]

If \(\pi_2\) were fixed, agent 1 would face an ordinary MDP. But if agent 2 is also learning, then \(\pi_2\) changes with time. Therefore agent 1 does not observe data from a stationary MDP.

This is the basic nonstationarity problem in multi-agent reinforcement learning:

\[ P_t^{\pi_2}(s' \mid s,a_1) \quad\text{and}\quad r_{1,t}^{\pi_2}(s,a_1) \]

change as the other agent learns.

26.11.1 Interactive: independent learners in matching pennies

Independent learners may chase each other rather than converge to a fixed policy.

26.12 23.11 Independent Q-learning

For agent \(i\), independent Q-learning applies the ordinary Q-learning update to that agent’s own action-value table:

\[ Q_i(S_t,A_{i,t}) \leftarrow Q_i(S_t,A_{i,t}) + \alpha_t \left[ R_{i,t+1} + \gamma\max_{a_i'}Q_i(S_{t+1},a_i') - Q_i(S_t,A_{i,t}) \right]. \]

The update is simple and often useful in practice, but the usual single-agent convergence theorem no longer applies directly because the environment is nonstationary.

Independent Q-learning is best understood as a heuristic approximation. It can work when:

other agents change slowly;
the interaction is weak;
experience replay and parameter sharing stabilize learning;
a centralized training signal reduces nonstationarity.

It can fail when:

strategic coupling is strong;
multiple equilibria are present;
exploration by one agent changes the reward landscape for another;
agents overfit to each other’s transient behavior.

26.13 23.12 Centralized training with decentralized execution

In cooperative multi-agent RL, one important framework is centralized training with decentralized execution, often abbreviated CTDE.

During training, a centralized critic may use the full state and joint action:

\[ Q(s,a_1,\ldots,a_m). \]

During execution, each agent uses only local information, such as its observation \(o_i\):

\[ a_i \sim \pi_i(\cdot \mid o_i). \]

The mathematical advantage is that the critic can evaluate the joint effect of all actions while the final policies remain decentralized.

A typical actor update for agent \(i\) has the form

\[ \theta_i \leftarrow \theta_i + \alpha \widehat A_i \nabla_{\theta_i}\log \pi_{\theta_i}(A_i \mid O_i), \]

where \(\widehat A_i\) is an advantage estimate computed using a centralized critic.

26.14 23.13 Difference rewards and credit assignment

In a cooperative game with team reward \(R\), an individual agent may not know whether its action helped the team. This is the credit-assignment problem.

A difference reward compares the team reward with and without agent \(i\)’s contribution:

\[ D_i(z)=G(z)-G(z_{-i},c_i), \]

where \(z\) is the full system trajectory or state-action configuration, \(z_{-i}\) removes agent \(i\)’s contribution, and \(c_i\) is a baseline action or counterfactual contribution.

The purpose is to reduce variance while preserving the direction of useful improvement. This is closely related to baselines in policy-gradient methods.

26.15 23.14 Mean-field approximation

When the number of agents is large, the joint action space becomes enormous. If there are \(m\) agents and each has \(k\) actions, then the number of joint actions is

\[ k^m. \]

Mean-field methods approximate the influence of other agents by an aggregate distribution. Suppose agent \(i\) interacts with many statistically similar agents. Instead of conditioning on every other action, we use a mean action distribution

\[ \mu_t(a) \approx \frac{1}{m-1}\sum_{j \neq i}1\{A_{j,t}=a\}. \]

A mean-field action-value function has the form

\[ Q_i(s,a_i,\mu). \]

This reduces the dependence on the full joint action \((a_1,\ldots,a_m)\) to the dependence on one agent’s action and the empirical population distribution.

26.15.1 Interactive: mean-field approximation

The plot compares the exact empirical fraction of one action with its mean-field limit.

26.16 23.15 Python example: independent learners in a repeated game

The following example simulates two independent learners in matching pennies. The row player receives \(1\) if the actions match and \(-1\) otherwise. The column player receives the negative payoff.

import numpy as np

rng = np.random.default_rng(7339)
G = np.array([[1.0, -1.0],
              [-1.0, 1.0]])

T = 5000
alpha = 0.05
epsilon = 0.10
Q_row = np.zeros(2)
Q_col = np.zeros(2)
row_probs = []
col_probs = []


def epsilon_greedy(Q, epsilon, rng):
    if rng.random() < epsilon:
        return rng.integers(len(Q))
    best = np.flatnonzero(Q == Q.max())
    return rng.choice(best)

for t in range(T):
    a_row = epsilon_greedy(Q_row, epsilon, rng)
    a_col = epsilon_greedy(Q_col, epsilon, rng)
    r_row = G[a_row, a_col]
    r_col = -r_row
    Q_row[a_row] += alpha * (r_row - Q_row[a_row])
    Q_col[a_col] += alpha * (r_col - Q_col[a_col])
    row_probs.append(np.mean(np.array(Q_row) == Q_row.max()))
    col_probs.append(np.mean(np.array(Q_col) == Q_col.max()))

print("Final row Q:", np.round(Q_row, 3))
print("Final column Q:", np.round(Q_col, 3))
print("Best row action:", int(np.argmax(Q_row)))
print("Best column action:", int(np.argmax(Q_col)))

Final row Q: [-0.188 -0.25 ]
Final column Q: [ 0.296 -0.317]
Best row action: 0
Best column action: 0

This small example should not be interpreted as a stable algorithm for zero-sum games. It illustrates the difficulty: each learner treats the other learner as part of the environment, but that environment keeps changing.

26.17 23.16 Multi-agent policy gradients

For a joint stochastic policy

\[ \pi_\theta(a_1,\ldots,a_m \mid s) = \prod_{i=1}^m\pi_{\theta_i}(a_i \mid s), \]

we have

\[ \log \pi_\theta(a_1,\ldots,a_m \mid s) = \sum_{i=1}^m \log \pi_{\theta_i}(a_i \mid s). \]

For a cooperative objective \(J(\theta)\), the policy-gradient theorem suggests the update

\[ \nabla_{\theta_i}J(\theta) = \mathbb E_\pi \left[ \nabla_{\theta_i}\log\pi_{\theta_i}(A_i \mid S) Q^\pi(S,A_1,\ldots,A_m) \right]. \]

The centralized critic estimates the joint-action value, while each actor only differentiates its own policy.

For general-sum games, each agent has its own objective:

\[ J_i(\theta_1,\ldots,\theta_m). \]

The learning dynamics become a coupled system:

\[ \theta_{i,t+1} = \theta_{i,t} + \alpha_t \widehat{\nabla}_{\theta_i}J_i(\theta_{1,t},\ldots,\theta_{m,t}). \]

This is not ordinary gradient ascent on one scalar potential unless the game has special structure. Cycles can occur.

26.18 23.17 Statistical viewpoint

For MA Applied Math and MS Statistics students, several statistical issues are especially important.

First, the data are dependent because they come from trajectories. Second, the data are nonstationary because policies change during learning. Third, the target may be an equilibrium rather than a single optimum. Fourth, counterfactual estimation is difficult because each trajectory only contains one realized joint action at each time.

From a statistical perspective, the central questions are:

What distribution generated the data?
Is that distribution stationary?
Which policy profile is being evaluated?
What counterfactual action profiles are supported by the data?
Is the target a value, a best response, or an equilibrium?

These questions are often more important than the choice of algorithm.

26.19 23.18 AI-assisted learning components

26.19.1 AI-assisted derivation check

Ask an AI assistant to derive the fixed-joint-policy Bellman equation for agent \(i\) in a two-agent Markov game. Then check whether the derivation correctly sums over both agents’ actions and whether it distinguishes \(P_\pi\) from \(P(s' \mid s,a_1,a_2)\).

26.19.2 AI-assisted modeling critique

Describe a multi-agent system such as traffic lights, two trading algorithms, or teams of delivery robots. Ask an AI assistant to identify the state, observations, actions, rewards, and whether the problem is cooperative, competitive, or general-sum. Then critique whether the proposed state is Markov.

26.19.3 AI-assisted debugging task

Give an AI assistant code for independent Q-learning and ask it to explain why the single-agent Q-learning convergence theorem does not directly apply. A good answer should mention nonstationarity caused by changing policies of the other agents.

26.20 23.19 Summary

Multi-agent reinforcement learning generalizes MDPs by allowing several agents to act simultaneously. Under a fixed joint policy, a Markov game reduces to an MRP for each agent. In two-player zero-sum games, the Shapley optimality equation replaces the single-agent maximization with a state-wise minimax matrix game. In cooperative games, centralized critics can help solve credit assignment and nonstationarity during training. In general-sum games, Nash equilibria replace optimal policies, and equilibrium selection becomes a central issue.

The main mathematical lesson is that multi-agent RL is not just RL with more actions. The object of interest changes from a single optimal policy to a policy profile, equilibrium, or population-level fixed point.

26.21 Exercises

26.21.1 Conceptual exercises

Explain why a fixed joint policy turns a Markov game into an MRP for each agent.
Give one example of a cooperative Markov game, one zero-sum Markov game, and one general-sum Markov game.
Why does independent Q-learning violate the stationarity assumptions behind the usual single-agent convergence theorem?
Explain the difference between an optimal policy and a Nash equilibrium.
Why is equilibrium selection difficult in coordination games?

26.21.2 Mathematical exercises

Derive the expression for \(P_\pi(s,s')\) under a two-agent randomized stationary joint policy.
Derive the expression for \(r_{i,\pi}(s)\).
Prove that, for a fixed joint policy, \(V_i^\pi=(I-\gamma P_\pi)^{-1}r_{i,\pi}\).
For a \(2 \times 2\) zero-sum matrix game, derive the row player’s interior mixed strategy formula.
Prove that the Shapley operator for a discounted zero-sum Markov game is a \(\gamma\)-contraction in the sup norm.

26.21.3 Computational exercises

Implement exact fixed-joint-policy evaluation for a two-state, two-agent Markov game.
Implement Shapley value iteration for a two-state zero-sum Markov game using a grid search over mixed strategies.
Simulate independent Q-learning in a repeated coordination game. Study how the final equilibrium depends on initialization.
Compare independent Q-learning and minimax value iteration on a small zero-sum Markov game.
Simulate a mean-field population model and compare the empirical action distribution with its limiting deterministic update.

26.21.4 AI-assisted exercises

Ask an AI assistant to design a Markov game for classroom group work. Critique whether the reward structure is cooperative or general-sum.
Ask an AI assistant to explain CTDE to a statistics student. Improve the explanation by adding the conditional expectation view of a centralized critic.
Ask an AI assistant to write code for a matrix-game solver. Test it on matching pennies and a coordination game.
Ask an AI assistant to propose diagnostics for nonstationarity in multi-agent learning data.

26.22 Instructor notes

This chapter is best taught as a bridge between dynamic programming, game theory, and modern multi-agent learning. Students should first master the fixed-joint-policy reduction because it reuses Markov reward process theory. The zero-sum case gives the cleanest extension of Bellman optimality. General-sum games should be introduced carefully: the target is no longer simply \(\max_\pi J(\pi)\) but an equilibrium concept.