Multi-Agent RL

A robot learning to navigate a room is a single-agent RL problem. A soccer team is not. Neither is AlphaStar playing against StarCraft opponents, a marketplace of bidding agents, two cars negotiating a four-way stop, or any other many-on-many problem you can name.

In every multi-agent setting, from the perspective of any one agent, the other agents are part of the environment. As they learn and change their behavior, the environment becomes non-stationary — the ground keeps shifting while you're trying to stand on it. The Markov property (next state depends only on current state and my action) gets violated, because the next state also depends on what the other agents chose, and their policies are moving targets.

This breaks tabular convergence proofs: Q-learning's guarantee assumes a stationary environment. It breaks naive deep RL too. Agents chase each other in loops and never settle on a stable policy. You need multi-agent-specific techniques: centralized training with decentralized execution, counterfactual baselines, league play, self-play.

2026 applications include robot swarms, traffic routing, autonomous vehicle fleets, market simulators, multi-agent LLM systems (Phase 16), and any game with more than one intelligent player.

Formalism: Markov Game. A generalization of MDP: states S, a joint action a = (a_1, …, a_n), transition P(s' | s, a), and per-agent rewards R_i(s, a, s'). Each agent i maximizes its own return under its own policy π_i: identical rewards make the game fully cooperative, zero-sum rewards make it adversarial, and mixed rewards make it general-sum.

Core challenges:

• Non-stationarity. P(s' | s, a_i) from agent i's view depends on π_{-i}, which is changing.
• Credit assignment. With a shared reward, which agent caused it?
• Exploration coordination. Agents need to explore complementary strategies, not redundantly cover the same state.
• Scalability. The joint action space grows exponentially in n.
• Partial observability. Each agent sees only its own observation; the global state stays hidden.

Four dominant regimes:

1. Independent Q-learning / independent PPO (IQL, IPPO). Each agent learns its own Q-function or policy and treats everyone else as part of the environment. It's simple, and it sometimes works, especially when experience replay doubles as a smoothing trick for modeling the other agent. Theoretical convergence: none. In practice: fine for loosely-coupled tasks, bad for tightly-coupled ones.

2. Centralized training, decentralized execution (CTDE). The most common modern paradigm. Each agent has its own policy π_i that conditions on local observation o_i, the standard setup for decentralized execution at deployment. During training, a centralized critic Q(s, a_1, …, a_n) conditions on the full global state and joint action. Examples:

• MADDPG (Lowe et al. 2017): DDPG (a continuous-action actor-critic method) with a centralized critic per agent.
• COMA (Foerster et al. 2017): a counterfactual baseline. It asks what my reward would have been had I taken action a' instead, which isolates my individual contribution.
• MAPPO / IPPO with shared critic (Yu et al. 2022): PPO with a centralized value function. Dominant in 2026 for cooperative MARL.
• QMIX (Rashid et al. 2018): value decomposition (Q_tot(s, a) = f(Q_1(s, a_1), …, Q_n(s, a_n))) with monotonic mixing.

3. Self-play. Two copies of the same agent play against each other. The opponent's policy is my policy from a past snapshot. AlphaGo / AlphaZero / MuZero. OpenAI Five. Works best for zero-sum games, where the training signal stays symmetric.

4. League play. An extension of self-play to general-sum / adversarial environments: keep a population of past and current policies, sample an opponent from the league, train against them. Adds exploiters (specialize in beating the current best) and main exploiters (specialize in beating exploiters). AlphaStar (StarCraft II) needed this, because the game admits "rock-paper-scissors" strategy cycles.

Communication. Let agents send learned messages m_i to each other. This works in cooperative settings. Foerster et al. (2016) showed that differentiable inter-agent communication can be trained end-to-end. Today's LLM-based multi-agent systems (Phase 16) mostly communicate in natural language instead.

This lesson uses a 6×6 GridWorld with two cooperative agents. They start in opposite corners and must reach a shared goal. Shared reward: -1 per step while either agent is still moving, +10 when both arrive. See code/main.py.

Step 1: the multi-agent env

class CoopGridWorld:
    def __init__(self):
        self.size = 6
        self.goal = (5, 5)
 
    def reset(self):
        return ((0, 0), (5, 0))  # two agents
 
    def step(self, state, actions):
        a1, a2 = state
        new1 = move(a1, actions[0])
        new2 = move(a2, actions[1])
        done = (new1 == self.goal) and (new2 == self.goal)
        reward = 10.0 if done else -1.0
        return (new1, new2), reward, done

The joint action space is |A|² = 16. The global state is just two positions.

Step 2: independent Q-learning

Each agent keeps its own Q-table keyed on the joint state. Every step, both pick ε-greedy actions, the environment returns a joint transition, and each agent updates its own Q-table off the shared reward.

def independent_q(env, episodes, alpha, gamma, epsilon):
    Q1, Q2 = defaultdict(default_q), defaultdict(default_q)
    for _ in range(episodes):
        s = env.reset()
        while not done:
            a1 = epsilon_greedy(Q1, s, epsilon)
            a2 = epsilon_greedy(Q2, s, epsilon)
            s_next, r, done = env.step(s, (a1, a2))
            target1 = r + gamma * max(Q1[s_next].values())
            target2 = r + gamma * max(Q2[s_next].values())
            Q1[s][a1] += alpha * (target1 - Q1[s][a1])
            Q2[s][a2] += alpha * (target2 - Q2[s][a2])
            s = s_next

This works here because the rewards are dense and aligned. It fails on tightly-coupled tasks, where one agent has to wait for the other.

Step 3: centralized Q with a decomposed-value update

Use one Q over joint actions, Q(s, a_1, a_2), updated from the shared reward. Decentralize at execution time by marginalizing: π_i(s) = argmax_{a_i} max_{a_{-i}} Q(s, a_1, a_2). You trade an exponential joint action space for a correct global view.

Step 4: simple self-play (adversarial 2-agent)

Same agent, two roles. Train agent A against agent B, and every K episodes copy A's weights into B. Training stays symmetric and progress stays consistent. It's the AlphaZero recipe in miniature.

• Non-stationary replay. Experience replay is worse for independent agents than for a single agent, because old transitions came from opponents whose policies have since moved on. Relabel the stored transitions or weight them by recency.
• Credit assignment ambiguity. A shared reward lands at the end of a long episode with no clean way to say which agent caused it. Counterfactual baselines (COMA) or per-agent reward shaping are the usual fixes.
• Policy drift / chasing. Each agent's best response keeps shifting as the others update, so nobody settles. Use a centralized critic, slow the learning rate, or freeze one agent at a time.
• Reward hacking via coordination. Agents find coordinated exploits nobody designed for: auction agents converging to bid zero is the classic example. Careful reward design and behavioral constraints are the fix.
• Exploration redundancy. Both agents explore the same state-action pairs and waste the run. Per-agent entropy bonuses or role-conditioning fix that.
• League cycles. Pure self-play can get stuck in a dominance cycle. League play with diverse opponents breaks it.
• Sample explosion. n agents × state space × joint actions grows fast. Approximate it: function approximation, factored action spaces, one policy head per agent.

The 2026 MARL application map:

MARL's biggest growth area in 2026 is LLM-based: swarms of language-model agents negotiating, debating, and building software together. The RL there shows up as preference optimization on trajectory-level outputs, not token-level (Phase 16 · 03).

Save as outputs/skill-marl-architect.md:

---
name: marl-architect
description: Pick the right multi-agent RL regime (IPPO, CTDE, self-play, league) for a given task.
version: 1.0.0
phase: 9
lesson: 10
tags: [rl, multi-agent, marl, self-play]
---
 
Given a task with `n` agents, output:
 
1. Regime classification. Cooperative / adversarial / general-sum. Justify.
2. Algorithm. IPPO / MAPPO / QMIX / self-play / league. Reason tied to coupling tightness and reward structure.
3. Information access. Centralized training (what global info goes to the critic)? Decentralized execution?
4. Credit assignment. Counterfactual baseline, value decomposition, or reward shaping.
5. Exploration plan. Per-agent entropy, population-based training, or league.
 
Refuse independent Q-learning on tightly-coupled cooperative tasks. Refuse to recommend self-play for general-sum with cycle risks. Flag any MARL pipeline without a fixed-opponent eval (cherry-picked self-play numbers are common).

1. Easy. Train independent Q-learning on the 2-agent cooperative GridWorld. How many episodes does it take before mean return crosses 0? Plot the joint learning curve.
2. Medium. Add a "coordination" task where the goal only counts if both agents step onto it on the same turn. Does independent Q still converge? What breaks?
3. Hard. Implement a centralized critic for MAPPO-style training and compare its convergence speed to independent PPO on the coordination task.

• Lowe et al. (2017). Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments (MADDPG): CTDE with a centralized critic.
• Foerster et al. (2017). Counterfactual Multi-Agent Policy Gradients (COMA): counterfactual baselines for credit assignment.
• Rashid et al. (2018). QMIX: Monotonic Value Function Factorisation: value decomposition with monotonicity.
• Yu et al. (2022). The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games (MAPPO): PPO is surprisingly strong for MARL.
• Vinyals et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning (AlphaStar): league play at scale.
• Silver et al. (2017). Mastering the game of Go without human knowledge (AlphaGo Zero): pure self-play in zero-sum games.
• Sutton & Barto (2018), Ch. 15 (Neuroscience) and Ch. 17 (Frontiers): includes the textbook's short treatment of multi-agent settings and the non-stationarity problem that CTDE is designed to solve.
• Zhang, Yang & Başar (2021). Multi-Agent Reinforcement Learning: A Selective Overview: survey covering cooperative, competitive, and mixed MARL with convergence results.