Multi-Agent RL

"Every morning I wake up, study the environment, and find the best response. Every morning the environment has read yesterday's response and changed itself to punish it. We are two students cribbing from each other's exams, and neither of us will ever sit still long enough to finish the test."

An Agent Whose Environment Keeps Learning to Outsmart It

In Section 26.2 we learned a policy from a fixed logged dataset with no further interaction, still inside the one-agent frame where the environment holds still while the policy improves. This section breaks that frame deliberately. The moment two or more agents learn in a shared world, each agent's effective environment includes the others, and because the others are improving too, that environment is a moving target. The non-stationarity we are about to confront is not the gentle distribution drift of Chapter 20, where the world changes for reasons external to us; it is induced non-stationarity, caused by the very learning of the other agents, and it sits at the center of why multi-agent learning is hard. We use the unified notation of Appendix A: $s$ a state, $a^i$ agent $i$'s action, $r^i$ its reward, $\pi^i$ its policy, $\gamma$ the discount.

Why does this deserve its own section rather than a footnote reading "just run single-agent RL per agent"? Because that footnote is exactly the naive approach that fails, and understanding precisely why it fails is the entire intellectual content of multi-agent RL. Independent learners are simple, scalable, and sometimes effective, but they treat a non-stationary problem as if it were stationary, and the gap between those two assumptions is where the instability, the cycling, and the failure to converge all live. Every more sophisticated method in this section, every centralized critic and every self-play schedule, is a structured way of coping with the non-stationarity that independent learning ignores.

The competencies this section installs are these: to recognize when a decision problem is multi-agent and to classify it as cooperative, competitive, or mixed; to write it as a Markov game and state what a Nash equilibrium is and why convergence to one is hard; to explain why independent learners struggle and how centralized-training-decentralized-execution (CTDE) and self-play address the difficulty; to reason about credit assignment across agents sharing a reward; and to implement and compare independent versus centralized-critic learners, both from scratch and through a library. These are the load-bearing skills for the cooperative and competitive systems that recur through the rest of Part VI and into the temporal agents of Chapter 31.

1. When the Environment Keeps Learning: The Non-Stationarity Problem Beginner

Picture an electricity market where a dozen automated bidders each learn to submit prices that maximize their own profit. Bidder $A$ learns that undercutting the current clearing price wins more volume, so it lowers its bids. But every other bidder is running the same learning loop, so they lower theirs too, and the clearing price that $A$ optimized against last week no longer exists this week. $A$'s carefully learned policy is now optimal for a market that has vanished. The same story plays out in algorithmic trading, where each desk's strategy changes the order flow the others see; in traffic routing, where every navigation app rerouting cars around congestion creates congestion somewhere else; in supply-chain negotiation, where each party's concession reshapes what the others will accept. In all of these the defining feature is identical: the environment that each agent optimizes against is itself a set of learning agents, so it will not hold still.

Formally, fix attention on agent $i$ and lump every other agent into the environment. The transition that agent $i$ experiences is $P(s' \mid s, a^i, \mathbf{a}^{-i})$, where $\mathbf{a}^{-i}$ denotes the joint action of all other agents. As long as the others' policies $\boldsymbol{\pi}^{-i}$ are fixed, agent $i$ faces a perfectly ordinary, stationary Markov decision process: it can marginalize the others out and learn an optimal response. The instant the others learn, their policies $\boldsymbol{\pi}^{-i}$ change between updates, so the effective transition and reward functions that agent $i$ sees change too. The MDP that grounds every single-agent convergence guarantee (the stationary $P$ and $r$ of Chapter 22) no longer holds. This is the origin of induced non-stationarity, and it is worth pausing on the contrast with the drift studied earlier.

The practical symptom of induced non-stationarity is that a value or policy estimate which was accurate becomes wrong without the agent doing anything: its replay buffer fills with experience generated against opponents who no longer exist, its $Q$-values are calibrated to a world one update out of date, and the gradient it computes points toward a best response to yesterday's adversary. Stack two such agents and they can enter a limit cycle, each perpetually best-responding to the other's last move, neither ever converging, the joint behavior orbiting a fixed point it never reaches. We will see exactly this cycle in the code of subsection five. For now the headline is simple and it governs the whole section: in multi-agent RL the environment is non-stationary from each agent's view, and every design choice is a way of coping with that.

2. The Settings and the Game-Theoretic Frame Intermediate

Multi-agent problems split by how the agents' rewards relate. In a cooperative setting all agents share one reward (a team of warehouse robots maximizing total throughput); the challenge is coordination and credit assignment, not conflict. In a competitive setting one agent's gain is another's loss, the zero-sum case (two players in Go, a market maker versus an adverse trader); the challenge is robustness against an adversary that actively exploits your weaknesses. In a mixed (general-sum) setting rewards are partly aligned and partly opposed (negotiating parties who both prefer a deal to no deal but disagree on its terms, or autonomous cars that all want to avoid collisions yet each prefer to go first); these are the hardest and the most common, blending coordination and conflict. Recognizing which regime you are in is the first design decision, because it dictates both the solution concept and the algorithm family.

The formal object that unifies all three is the Markov game, also called a stochastic game, the multi-agent generalization of the MDP of Chapter 22. It is the tuple

where $\mathcal{N} = \{1, \dots, n\}$ is the set of agents, $\mathcal{S}$ the state space, $\mathcal{A}^i$ agent $i$'s action set, and the joint action is $\mathbf{a} = (a^1, \dots, a^n) \in \mathcal{A}^1 \times \cdots \times \mathcal{A}^n$. The transition $P(s' \mid s, \mathbf{a})$ depends on the joint action of all agents, and each agent has its own reward $r^i(s, \mathbf{a})$. A single MDP is the special case $n = 1$; a cooperative game (a Dec-POMDP when observation is partial, the partially-observed case of Chapter 23) is the case $r^1 = \cdots = r^n$; a two-player zero-sum game is $r^1 = -r^2$. Each agent seeks a policy $\pi^i(a^i \mid s)$ maximizing its own discounted return $\mathbb{E}\big[\sum_{t} \gamma^t r^i_t\big]$, but that return depends on the joint policy $\boldsymbol{\pi} = (\pi^1, \dots, \pi^n)$, so no single agent controls its own objective outright. This coupling, agent $i$'s value $V^i(s; \boldsymbol{\pi})$ depending on everyone's policy, is the formal face of the non-stationarity of subsection one.

Because each agent's payoff depends on the others, "optimal" loses its single-agent meaning: there is no policy that is best regardless of what the others do. The replacement solution concept is the Nash equilibrium: a joint policy $\boldsymbol{\pi}^\star = (\pi^{1\star}, \dots, \pi^{n\star})$ such that no agent can improve its own return by unilaterally changing its policy,

At a Nash equilibrium every agent is simultaneously playing a best response to all the others, so nobody has an incentive to move, and the joint behavior is self-consistent. The trouble is that learning toward such a point is genuinely hard for several compounding reasons. A game can have many Nash equilibria, and different agents learning independently may steer toward different ones and fail to coordinate. The best-response dynamics that each agent's learning approximates need not converge: in many general-sum and zero-sum games they cycle indefinitely (the canonical example is rock-paper-scissors, whose only equilibrium is a mixed strategy that pure best-response learning circles forever). And even when an equilibrium exists in mixed strategies, value-based learners that output deterministic greedy actions cannot represent it. So the comfortable single-agent picture, one optimum, monotone progress toward it, is replaced by a landscape of multiple equilibria, possibly cyclic dynamics, and no guarantee that decentralized learning lands anywhere at all.

3. The Algorithm Families: Independent, Centralized, Self-Play Intermediate

Three broad strategies have emerged, and each makes a distinct trade against the non-stationarity of subsection one.

Independent learners. The simplest idea: give every agent its own single-agent algorithm (independent Q-learning, IQL; or independent PPO, IPPO) and let each treat the others as part of the environment. The appeal is total: no new machinery, perfect scalability, complete decentralization. The flaw is exactly the non-stationarity we have belabored. Each agent's environment shifts as the others learn, so the convergence guarantees of the underlying algorithm evaporate, replay buffers go stale (the experience was generated against opponents who have since changed), and learning can oscillate or diverge. Independent learners nonetheless remain a strong, honest baseline and sometimes work well in practice, especially in loosely coupled problems where one agent's actions barely affect another's payoff. They are the control condition against which every fancier method must justify its complexity.

Centralized training, decentralized execution (CTDE). The dominant modern paradigm exploits an asymmetry: at training time, in a simulator, you can see everything (every agent's observation, action, and reward), even though at execution time each agent acts on only its own local observation. CTDE puts that extra training-time information into a centralized critic that conditions on the joint state and joint action, while keeping each agent's actor (the executable policy) decentralized and local. Because the centralized critic sees the other agents' actions, the environment looks stationary to the critic, which is the precise cure for the non-stationarity that wrecks independent learning. Three landmark instances span the settings. MADDPG (Lowe et al., 2017) gives each agent a deterministic actor and a centralized critic $Q^i(s, a^1, \dots, a^n)$, and works in cooperative, competitive, and mixed games. QMIX (Rashid et al., 2018) targets cooperative teams: it learns per-agent utilities and a monotonic mixing network that combines them into a joint $Q$, so decentralized greedy actions remain consistent with the centralized optimum (the value-decomposition idea behind multi-agent credit assignment in subsection four). MAPPO (Yu et al., 2021) is simply PPO with a centralized value function, and despite its simplicity it is a remarkably strong cooperative baseline. The shared mechanism is the same: centralize the critic to restore stationarity, decentralize the actor to keep execution local.

Self-play. In competitive, especially zero-sum, settings an agent can generate its own curriculum by playing against copies of itself, past versions of itself, or a population of variants. As the agent improves, its opponents (being itself) improve in lockstep, so the difficulty scales automatically and the agent is always trained against an adversary near its own skill. This is the lineage behind the most famous results in the field: TD-Gammon learned backgammon this way decades ago; AlphaGo and AlphaZero (Silver et al., 2016, 2018) reached superhuman Go, chess, and shogi through self-play plus search; AlphaStar (Vinyals et al., 2019) reached grandmaster StarCraft II using a league of diverse self-play agents to avoid the strategic cycling (the rock-paper-scissors trap of subsection two) that naive self-play falls into. Self-play's great strength, an opponent that grows with you, is also its great risk: without a population or past-version pool, two copies can chase each other into a narrow cycle and forget how to beat strategies they had already mastered, which is exactly why AlphaStar needed a league rather than a single mirror.

4. Emergent Behavior and Multi-Agent Credit Assignment Advanced

Two phenomena distinguish multi-agent learning from a stack of single-agent learners running side by side, and both arise from the coupling of the agents' objectives. The first is emergent behavior: coordination strategies that no agent was told to use and that no single agent could produce alone, arising purely from agents adapting to one another. Trained competitive agents discover tool use and shelter building (OpenAI's hide-and-seek agents famously invented ramp-jumping and box-locking that the designers never anticipated); cooperative agents invent communication protocols, division of labor, and formations. Emergence is the upside of the coupling we have otherwise treated as a problem: the same interdependence that destabilizes independent learning is what lets a team discover collective strategies far richer than any hand-designed policy.

The second phenomenon is the central difficulty of cooperative learning: multi-agent credit assignment. When a team shares one reward $r = r^1 = \cdots = r^n$, and the team wins, which agent's actions deserve the credit? A naive scheme that gives every agent the full team reward is the multi-agent lazy-agent trap: an agent that does nothing useful still receives the team's reward whenever its teammates succeed, so it never learns to contribute, and worse, an agent cannot tell whether a good outcome followed from its own action or from a teammate's. This is the temporal credit-assignment problem of single-agent RL (which past action earned this reward?) compounded by a structural one (which agent earned this reward?). Two ideas dominate the response. Value decomposition (VDN, then QMIX) factors the joint value into per-agent contributions so that each agent's local value reflects its own marginal effect; the monotonic mixing network of QMIX from subsection three is exactly such a factorization, engineered so that maximizing each local utility also maximizes the joint value. Difference rewards / counterfactual baselines (COMA, Foerster et al., 2018) give each agent a shaped signal comparing the actual team reward to what the reward would have been had that agent acted by default, isolating the agent's marginal contribution and so cutting through the lazy-agent trap directly.

The two phenomena are linked. Emergent coordination is most likely to appear precisely when credit assignment is solved well enough that each agent can perceive how its actions move the shared outcome; a team drowning in the lazy-agent trap rarely discovers anything interesting, because no agent gets a clean enough signal to specialize. So the engineering of the reward channel, decomposition or counterfactual differencing, is not a side concern but the enabling condition for the rich emergent behavior that makes multi-agent systems worth building in the first place.

5. Worked Example: Independent vs Centralized-Critic Learners Advanced

We now make the non-stationarity of subsection one visible and contrast the two learning styles concretely. The cleanest possible arena is a repeated $2\times 2$ matrix game: two agents, two actions each, each agent learning policy logits by policy gradient. We will use a coordination payoff where the agents should learn to match actions, watch independent learners cycle because each best-responds to a partner who is simultaneously moving, then give one variant a centralized view of the joint action and watch it stabilize. Code 26.3.1 builds the from-scratch independent learners.

import numpy as np

rng = np.random.default_rng(0)

# A 2x2 coordination game. Each agent picks action 0 or 1.
# Both are rewarded when they MATCH (a pure coordination payoff),
# but the two equilibria (0,0) and (1,1) pay differently, so the
# agents must agree on WHICH to coordinate -> a moving target.
#   payoff[a1, a2] is the shared-ish reward structure below.
R1 = np.array([[2.0, 0.0],     # agent 1 reward, rows = a1, cols = a2
               [0.0, 1.0]])
R2 = np.array([[2.0, 0.0],     # agent 2 reward (same matching structure)
               [0.0, 1.0]])

def softmax(z):
    z = z - z.max()
    e = np.exp(z)
    return e / e.sum()

def independent_step(theta1, theta2, lr=0.1):
    """One REINFORCE update per agent, each treating the other as fixed env."""
    p1, p2 = softmax(theta1), softmax(theta2)        # each agent's action probs
    a1 = rng.choice(2, p=p1)                          # sample joint action
    a2 = rng.choice(2, p=p2)
    r1, r2 = R1[a1, a2], R2[a1, a2]                   # rewards depend on BOTH actions
    # REINFORCE gradient g_a = (1{a}-p) * r ; agent 1 sees r1 as if env-given.
    g1 = (np.eye(2)[a1] - p1) * r1
    g2 = (np.eye(2)[a2] - p2) * r2
    return theta1 + lr * g1, theta2 + lr * g2, (a1, a2)

theta1 = rng.normal(0, 0.1, 2); theta2 = rng.normal(0, 0.1, 2)
joint_counts = np.zeros((2, 2))
for step in range(4000):
    theta1, theta2, (a1, a2) = independent_step(theta1, theta2)
    if step >= 3500:                                  # tally the last 500 joint actions
        joint_counts[a1, a2] += 1
print("independent learners, last-500 joint-action counts:")
print(joint_counts.astype(int))
print("agent1 P(action=0) = %.3f" % softmax(theta1)[0])

independent learners, last-500 joint-action counts:
[[171  88]
 [ 92 149]]
agent1 P(action=0) = 0.604

Now the centralized-critic remedy. The fix is conceptually small and matches CTDE from subsection three: instead of each agent treating its scalar reward as environment-given, we let the update condition on the joint action through a centralized advantage that subtracts a baseline computed over the partner's actual action distribution. Conditioning on the partner's action makes the reward signal stationary from the critic's view, which is precisely the cure. Code 26.3.2 implements it from scratch.

# Centralized-critic (CTDE-style) update: the advantage conditions on the
# JOINT action via a baseline over the partner's CURRENT policy, so the
# signal is stationary w.r.t. the partner instead of treating it as noise.
def centralized_step(theta1, theta2, lr=0.1):
    p1, p2 = softmax(theta1), softmax(theta2)
    a1 = rng.choice(2, p=p1)
    a2 = rng.choice(2, p=p2)
    # Centralized baseline: expected reward for agent 1's chosen a1,
    # MARGINALIZED over the partner's known current policy p2 (joint info).
    b1 = (R1[a1, 0] * p2[0] + R1[a1, 1] * p2[1])      # partner-aware baseline
    b2 = (R2[0, a2] * p1[0] + R2[1, a2] * p1[1])
    adv1 = R1[a1, a2] - b1                            # centralized advantage
    adv2 = R2[a1, a2] - b2
    g1 = (np.eye(2)[a1] - p1) * adv1
    g2 = (np.eye(2)[a2] - p2) * adv2
    return theta1 + lr * g1, theta2 + lr * g2, (a1, a2)

theta1 = rng.normal(0, 0.1, 2); theta2 = rng.normal(0, 0.1, 2)
joint_counts = np.zeros((2, 2))
for step in range(4000):
    theta1, theta2, (a1, a2) = centralized_step(theta1, theta2)
    if step >= 3500:
        joint_counts[a1, a2] += 1
print("centralized-critic learners, last-500 joint-action counts:")
print(joint_counts.astype(int))
print("agent1 P(action=0) = %.3f" % softmax(theta1)[0])

centralized-critic learners, last-500 joint-action counts:
[[498   0]
 [  0   2]]
agent1 P(action=0) = 0.991

The contrast between Output 26.3.1 and Output 26.3.2 is the whole lesson in two tables: the same game, the same policy-gradient skeleton, the same learning rate, and the only difference is whether the update treats the partner as opaque environment (independent, never commits) or conditions on the partner's action through a centralized baseline (CTDE, converges to the good equilibrium). Now the library equivalent. PettingZoo is the multi-agent counterpart to Gymnasium, supplying standardized multi-agent environments; paired with a MARL trainer it replaces the hand-rolled loop entirely. Code 26.3.3 wires the same kind of coordination game through PettingZoo's API.

from pettingzoo.mpe import simple_spread_v3   # a cooperative MPE coordination task

# PettingZoo's parallel API: all agents step at once, exactly the joint-action
# structure of a Markov game. This single env object replaces the entire
# hand-rolled matrix-game loop and generalizes to n agents and richer states.
env = simple_spread_v3.parallel_env(N=3, max_cycles=25, continuous_actions=False)
observations, infos = env.reset(seed=0)

for _ in range(25):
    # In practice the actions come from a CTDE trainer (e.g. MAPPO/QMIX);
    # here we sample to show the standardized joint-step interface.
    actions = {agent: env.action_space(agent).sample() for agent in env.agents}
    observations, rewards, terminations, truncations, infos = env.step(actions)
print("agents:", env.agents)
print("per-agent rewards this step:", {k: round(v, 3) for k, v in rewards.items()})
env.close()

agents: ['agent_0', 'agent_1', 'agent_2']
per-agent rewards this step: {'agent_0': -2.131, 'agent_1': -2.131, 'agent_2': -2.131}

from ray.rllib.algorithms.ppo import PPOConfig

# Multi-agent PPO: two named policies, and a mapping function that routes
# each agent_id to a policy. Here even-indexed agents share "policy_a" and
# odd-indexed agents share "policy_b" -> the Markov-game structure as config.
def map_agent_to_policy(agent_id, episode, **kwargs):
    return "policy_a" if int(agent_id.split("_")[1]) % 2 == 0 else "policy_b"

config = (
    PPOConfig()
    .environment("my_multiagent_env")          # a PettingZoo/Gym multi-agent env
    .multi_agent(
        policies={"policy_a", "policy_b"},      # two independent learners
        policy_mapping_fn=map_agent_to_policy,  # who learns from whose experience
    )
    .env_runners(num_env_runners=8)             # 8 parallel rollout workers
    .learners(num_learners=1, num_gpus_per_learner=1)   # multi-GPU = bump these
)

algo = config.build_algo()
for i in range(10):                             # the train() loop
    result = algo.train()                       # distributed rollouts + SGD step
    print("iter", i, "reward_mean", result["env_runners"]["episode_return_mean"])
algo.stop()

RLlib's distributed design pays off when a single machine's environment throughput, not the learning rule, is the bottleneck: large or slow simulators, expensive observations, or sample-hungry algorithms (IMPALA, APEX) that need tens of millions of steps benefit from spreading rollouts across many workers and machines. For the small matrix game and toy MPE tasks of this section a single-process library such as CleanRL or a hand-rolled loop is simpler and just as fast; the heavier orchestration RLlib carries only earns its keep once you are scaling out.

6. Exercises Intermediate

The exercises move from reasoning about equilibria, to implementing and instrumenting the learners of subsection five, to an open-ended investigation of self-play stability.

Conceptual

26.3.1. Consider the matching-pennies game: two players each choose Heads or Tails; player 1 wins (reward $+1$, player 2 gets $-1$) if the coins match, and player 2 wins if they differ. (a) Write the two payoff matrices $R^1$ and $R^2$ and confirm the game is zero-sum. (b) Show there is no pure-strategy Nash equilibrium by checking that from every one of the four pure joint actions, some player wants to deviate. (c) Verify that the mixed strategy "each player plays Heads with probability $1/2$" is a Nash equilibrium. (d) Explain, in terms of subsection two, why two independent value-based learners that always pick the greedy action cannot represent this equilibrium and will instead cycle through the four joint actions.

Implementation

26.3.2. Extend Code 26.3.1 and 26.3.2 to log the trajectory of each agent's action probability over all 4000 steps (store softmax(theta1)[0] and softmax(theta2)[0] each step) and plot both trajectories for the independent and the centralized variants on the same axes. (a) Confirm visually that the independent trajectories oscillate or wander while the centralized ones converge. (b) Measure the variance of each agent's action probability over the final 500 steps as a scalar instability score, and report the four numbers (two agents $\times$ two methods). (c) Sweep the learning rate over $\{0.02, 0.1, 0.5\}$ and describe how it changes the independent learners' instability; relate your finding to the best-response-cycling argument of subsection two.

26.3.3. Make the credit-assignment point of subsection four concrete with a two-agent shared-reward example. Let the team reward be $r = a^1 \cdot a^2$ where each $a^i \in \{0, 1\}$ is whether agent $i$ acted usefully, so only the joint action $(1,1)$ pays $r = 1$ and every other joint action pays $0$. (a) Show that the naive scheme giving each agent the full team reward $r$ cannot distinguish a diligent agent from a lazy one: when agent 2 always plays $1$, agent 1 sees reward $1$ for action $1$ and $0$ for action $0$, but when agent 2 always plays $0$, agent 1 sees reward $0$ for both, so its learning signal collapses. (b) Now compute the counterfactual / difference reward for agent 1, $D^1 = r(a^1, a^2) - r(0, a^2)$, which subtracts the reward agent 1 would have earned by defaulting to action $0$; tabulate $D^1$ over all four joint actions and confirm it is nonzero exactly when agent 1's action changed the outcome. (c) Explain in two sentences how this counterfactual baseline isolates agent 1's marginal contribution and so defeats the lazy-agent trap, connecting your table to the COMA idea of subsection four.

Open-ended

26.3.4. Investigate self-play cycling and the league cure. Implement a tiny self-play loop on rock-paper-scissors where a single policy is trained by playing against its most recent self, and track the policy's action distribution over training. (a) Show that naive self-play against the latest opponent cycles (the policy chases rock, then paper, then scissors, never settling on the uniform equilibrium). (b) Now train against a pool of the agent's past versions sampled uniformly, the simplified AlphaStar-league idea of subsection three, and show that the pooled opponent stabilizes the policy toward uniform. (c) Discuss what your toy result suggests about why AlphaStar needed a league rather than a single self-play mirror, and connect the cycling you observed to the non-convergence of best-response dynamics from subsection two.