Multi-agent reinforcement learning

WHAT is MARL?

WHY this generalization? Because in the real world (auctions, traffic, games, markets) outcomes depend not just on your action but on everyone's simultaneous action. A single reward function can't capture conflicting or shared incentives.

The three reward regimes

Fully cooperative: all agents share one reward, $r^1=\dots=r^N=r$ . Goal: maximize team return.
Fully competitive (zero-sum, $N=2$ ): $r^1 = -r^2$ . One's gain is the other's loss.
Mixed / general-sum: anything in between (e.g. traffic — mostly cooperative but self-interested).

Figure — Multi-agent reinforcement learning

HOW do we define "optimal"? — Nash Equilibrium

WHY not just "maximize reward"? Because there is no single objective to maximize — each agent has its own $V^i$ . NE is the game-theoretic replacement for "optimal policy": a fixed point where everyone is simultaneously best-responding.

The CENTRAL problem: non-stationarity (derived)

Consequence: the Markov property $P(s'\mid s,a^i)$ being stationary — the assumption Q-learning's convergence proof needs — is violated. Each agent chases a moving target. This is the single most important thing to remember.

HOW we actually train: CTDE

WHY it works: the critic $Q^i(s,\mathbf{a})$ is a function of the full joint action, so from its perspective there is no hidden non-stationarity — everyone's action is an explicit input. This is the backbone of MADDPG, COMA, QMIX.

Formula MADDPG centralized critic gradient (derived from the policy gradient)

Start from single-agent deterministic policy gradient (DPG): $\nabla_\theta J = \mathbb{E}[\nabla_\theta \mu(s)\,\nabla_a Q(s,a)|_{a=\mu(s)}]$ . Generalize agent $i$ 's policy $\mu^i_{\theta_i}(o^i)$ and use a joint-action critic $Q^i_\phi(s, a^1,\dots,a^N)$ : $\nabla_{\theta_i} J^i = \mathbb{E}\Big[\nabla_{\theta_i}\mu^i(o^i)\,\nabla_{a^i} Q^i_\phi(s,a^1,\dots,a^N)\big|_{a^i=\mu^i(o^i)}\Big].$ Why each piece: $\nabla_{\theta_i}\mu^i$ = "how my action changes with my params"; $\nabla_{a^i}Q^i$ = "how the joint value changes with my action". Chain rule connects them. Because $Q^i$ knows all actions, its target is stationary → stable training.

Cooperative special case: value factorization (QMIX)

Worked examples

Recall Feynman: explain to a 12-year-old

Imagine you and your friends all playing the same video game at once, and each of you is also just learning to play. Every time your friend gets better, the game feels different to you — because what works depends on what they do. So you can't just practice alone pretending everyone stays the same; you'd learn the wrong lessons. The clever trick (CTDE) is: while practicing, a coach who can see everyone's moves helps each player; but during the real match, each player decides alone using only what they can see.

Active-recall flashcards

#flashcards/ai-ml

What tuple defines a Markov (stochastic) game?

\langle N,\mathcal{S},\{\mathcal{A}^i\},P,\{r^i\},\gamma\rangle

— transitions & rewards depend on the joint action.

What is the core difficulty of MARL?

Non-stationarity — each agent's effective environment changes as other agents learn.

Show why the environment is non-stationary for agent

i

Its effective transition

\tilde P^i(s'|s,a^i)=\sum_{\mathbf{a}^{-i}}\prod_{j\ne i}\pi^j(a^j|s)P(s'|s,a^i,\mathbf{a}^{-i})

depends on opponents' policies, which change.

Define a Nash equilibrium in a Markov game.

A joint policy where no agent can raise its own

V^i

by unilaterally changing its policy.

What does CTDE stand for and why use it?

Centralized Training, Decentralized Execution — a centralized critic sees joint actions (stationary target) while agents execute on local observations.

Why does independent DQN (IQL) break in MARL?

Convergence proof assumes stationary transitions; opponents learning violates that, and replay buffers store stale transitions.

State the IGM condition.

Joint argmax of

Q_{tot}

equals the tuple of per-agent argmaxes of

Q^i

How does QMIX guarantee IGM?

By making the mixing network monotonic:

\partial Q_{tot}/\partial Q^i\ge0

for all

i

Give MADDPG's centralized critic policy gradient.

\nabla_{\theta_i}J^i=\mathbb{E}[\nabla_{\theta_i}\mu^i(o^i)\,\nabla_{a^i}Q^i_\phi(s,a^1,\dots,a^N)|_{a^i=\mu^i}]

NE of Rock-Paper-Scissors?

Uniform mixed strategy

(1/3,1/3,1/3)

, game value

0

Three reward regimes in MARL?

Fully cooperative (shared

r

), fully competitive (zero-sum

r^1=-r^2

), mixed/general-sum.

Connections

Markov Decision Process — MARL reduces to this when $N=1$ .
Q-Learning — its stationarity assumption is what MARL breaks.
Policy Gradient Methods — MADDPG generalizes DPG to joint critics.
Game Theory & Nash Equilibrium — supplies the solution concept.
Actor-Critic Methods — the CTDE critic is a centralized actor-critic.
Self-Play — training method for competitive MARL (AlphaGo, OpenAI Five).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, single-agent RL me hum maante hain ki environment fixed hai — bas hum seekhte hain kaise best action lena hai. Lekin MARL me doosre agents bhi seekh rahe hote hain. Iska matlab tumhare liye environment badalta rehta hai, kyunki jo result milega wo sabke joint action pe depend karta hai. Isko hum Stochastic Game (Markov Game) kehte hain — ye MDP ka multi-agent version hai jahan transition aur reward puri joint action pe depend karte hain.

Sabse bada problem hai non-stationarity. Agent $i$ ke point of view se, effective transition me opponents ki policy ghusi hoti hai — aur wo policy time ke saath change hoti rehti hai. Isliye normal Q-learning ka convergence proof yahan fail ho jaata hai, aur replay buffer me purani (stale) data aa jaata hai. Yahi wajah hai ki sirf "har agent ke liye independent DQN" chala dena galat hai, bhale hi wo tempting lagta ho.

Solution ka naam hai CTDE — Centralized Training, Decentralized Execution. Training ke time ek centralized critic sab kuch dekhta hai (joint action), isliye uske liye target stationary rehta hai. Execution ke time har agent sirf apni local observation se decide karta hai. MADDPG, COMA, QMIX sab isi idea pe based hain. Cooperative case me QMIX monotonic mixing use karta hai taaki har agent ka local greedy choice hi global best ban jaaye (IGM condition).

Aur "optimal" ka matlab bhi badal jaata hai — kyunki har agent ka apna reward hai, hum Nash Equilibrium dhoondte hain: aisi joint policy jahan koi bhi agent akele apni policy badal ke apna faayda na badha sake. Rock-Paper-Scissors ka NE yaad rakho — $(1/3,1/3,1/3)$ , kyunki koi bhi fixed choice exploit ho jaata hai. Bas yahi core intuition hai: sab seekh rahe hain, isliye moving target ko handle karo aur equilibrium socho, na ki akela optimum.

WHAT is MARL?

The three reward regimes

HOW do we define "optimal"? — Nash Equilibrium

The CENTRAL problem: non-stationarity (derived)

HOW we actually train: CTDE

Cooperative special case: value factorization (QMIX)

Worked examples

Active-recall flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Deep & Advanced RL

Connections