Multi-Agent RL (CTDE)

MARL (Multi-Agent Reinforcement Learning) trains multiple agents simultaneously. From each agent's perspective the environment is non-stationary — other agents' policies keep evolving — so naively applying single-agent algorithms is unstable. The dominant paradigm is CTDE (Centralized Training, Decentralized Execution): training shares global information (global state, all agents' actions) for credit assignment, while execution only uses each agent's local observation $o_i$.

1. MAPPO: multi-agent PPO. Actors keep the policy-gradient clipped objective $\nabla_{\theta_i} J_i = \mathbb{E}[\nabla_{\theta_i}\log\pi_{\theta_i}(a_i|o_i)\hat{A}_i]$, but a shared centralized Critic $V_\phi(s)$ takes the global state, and the advantage $\hat{A}_i = r_i + \gamma V_\phi(s') - V_\phi(s)$ is computed from global information, strongly reducing non-stationarity bias; homogeneous agents often use parameter sharing (one network + one-hot identity), greatly improving sample efficiency; 2. MADDPG: a centralized extension of DDPG. Each agent has a centralized Critic $Q_i^{\mu}(s, a_1, \ldots, a_N)$ (taking all agents' actions, which freezes the environment dynamics given the joint action) while its Actor $\mu_i(o_i)$ executes with local observations only; during training, opponents' actions are estimated via fitted importance sampling of their policies to mitigate non-stationarity; 3. Core challenges and mitigations: non-stationarity (targets drift with opponents' policies) → CTDE/opponent modeling; credit assignment (team rewards are hard to attribute) → difference rewards $r_i = R - R_{-i}$, entropy incentives; joint action space growing exponentially in $N$ → value decomposition (VDN/QMIX), role/hierarchy structure.

robot cooperation, autonomous driving interaction, games (OpenAI Five, StarCraft), multi-agent LLM collaboration and games.

independent learners treat others as environment noise, and non-stationary targets break single-agent convergence guarantees; CTDE concentrates information during training while staying scalable at execution — the accuracy/compute trade-off shared by MAPPO, MADDPG, VDN and QMIX.

Explain CTDE: what do centralized training and decentralized execution mean, and why are they needed?

How does MAPPO's shared centralized Critic differ from single-agent PPO; how is the advantage computed?

How does MADDPG's centralized critic Q_i(s,a₁..a_N) mitigate non-stationarity, and how does it differ from MAPPO?

Whiteboard: write MAPPO's Actor gradient and advantage formula, and relate them to PPO / the policy gradient theorem.

The three MARL challenges — non-stationarity, credit assignment, exponential action space — and mitigations for each.