Multi-Agent Reinforcement Learning, built up from a single robot

Picture a warehouse robot. Ten times a second it reads its sensors, picks a motor command, and the world responds: it moves, maybe bumps a shelf, maybe reaches the pick-up point. Nobody tells it the right command. It only gets a number, the reward, saying how good that moment was. Reinforcement learning (RL) is the engineering of turning those numbers into good behaviour.

# the loop every RL library implements (Gymnasium API)
obs, info = env.reset()
for t in range(T):
    action = policy(obs)                       # agent decides
    obs, reward, terminated, truncated, info = env.step(action)  # world responds
    if terminated or truncated:
        break

A car that only maximises this second's reward would floor the accelerator into a queue. We want it to care about the whole trip, but care a bit less about the far future, which is uncertain anyway. We get that with a discount factor \(\gamma\in[0,1)\).

The return from time \(t\) is the discounted sum of future rewards:

It satisfies a recursion that the rest of RL is built on:

If rewards are bounded, \(|r|\le R_{\max}\), the geometric series gives \(|G_t|\le R_{\max}/(1-\gamma)\), so the sum is finite. The effective horizon is about \(1/(1-\gamma)\) steps. Rule of thumb for robotics: horizon in seconds ≈ \(\frac{1}{1-\gamma}\cdot \Delta t\). Choose \(\gamma\) from the control frequency and how far ahead the task needs you to look. Don't pick it at random.

To reason about a robot mathematically, we describe its world as five objects: which situations exist, which actions exist, how actions change situations (with noise), what each outcome is worth, and how much we discount. That package is an MDP.

Markov property: the future depends only on the present state, not on how you got there: \(\Pr(s_{t+1}\mid s_t,a_t) = \Pr(s_{t+1}\mid s_0,a_0,\dots,s_t,a_t)\). For a car, position and velocity together are Markov; position alone is not.

Two value functions score how good things are under a policy \(\pi\):

\(V\) answers "how good is it to be here?" and \(Q\) answers "how good is it to do this here?". Once you know \(Q\), acting is easy: pick \(\arg\max_a Q(s,a)\).

Plug \(G_t = r_{t+1}+\gamma G_{t+1}\) into the definition and take expectations. You get a one-step consistency condition:

The optimal value replaces "average over the policy" with "take the best action":

Define the Bellman optimality operator \(\mathcal{T}\) as the right-hand side. It is a \(\gamma\)-contraction in the max-norm: \(\|\mathcal{T}V - \mathcal{T}U\|_\infty \le \gamma \|V-U\|_\infty\). By the Banach fixed-point theorem it has exactly one fixed point \(V^*\), and repeatedly applying it (value iteration) converges from any start. Each sweep shrinks the error by at least a factor \(\gamma\).

Monte Carlo (MC): drive the whole route, note the total reward, and average it over many trips. Temporal Difference (TD): after every single step, update your guess using the reward you just got plus your current guess for where you landed. TD learns while driving and doesn't need the trip to finish.

Both are "move the estimate a fraction \(\alpha\) toward a target". The difference is the target.

Between them sit n-step returns and TD(λ), which blend targets of every length. PPO's GAE (Chapter 6) is exactly this idea applied to advantages. Convergence: tabular TD(0) converges to \(V^\pi\) under Robbins–Monro step sizes (\(\sum\alpha_t=\infty,\ \sum\alpha_t^2<\infty\)).

Evaluating a fixed policy isn't enough. We want the robot to improve. Keep a table \(Q(s,a)\), usually act greedily, and sometimes try a random action (ε-greedy). If the robot never tries the unfamiliar route, it can never find out the route is better.

Q-learning is off-policy: it learns the value of the greedy policy while behaving ε-greedily, because of the \(\max\). SARSA is on-policy: it learns the value of what it actually does, exploration included, so near cliffs and pits it learns safer paths. That distinction comes up often in robot-safety discussions.

Tabular Q-learning converges to \(Q^*\) with probability 1 (Watkins & Dayan, 1992) if every state–action pair is visited infinitely often and step sizes satisfy Robbins–Monro. It is stochastic approximation of the Bellman optimality fixed point from Chapter 3. Keep this in mind: the proof assumes a stationary environment. In MARL, other learning agents are part of the environment, so this assumption breaks. That is the root problem of Chapter 7.

A car's state is continuous and high-dimensional, so no table can hold it. We replace the table with a neural network, \(Q_\theta(s,a)\) or \(\pi_\theta(a\mid s)\). Steering and throttle are continuous, which makes "max over actions" awkward, so we often learn the policy directly.

There are two stabilisers. A replay buffer \(\mathcal{D}\) breaks the correlation between consecutive samples. A target network \(\bar\theta\), a slowly updated copy, stops the target from chasing itself. Double DQN fixes max-overestimation. Instability comes from the deadly triad: function approximation + bootstrapping + off-policy data.

Maximise \(J(\theta)=\mathbb{E}_{\pi_\theta}[G_0]\) directly. The policy gradient theorem (Sutton et al., 2000) says:

In words: make actions that turned out better than average (\(A>0\)) more likely. REINFORCE uses \(G_t\) in place of \(A\), which is the MC idea and has high variance. Actor–critic learns a critic \(V_\phi\) and uses the TD error \(\delta_t\) as the advantage estimate, which is the TD idea. GAE blends them: \(\hat A_t=\sum_l (\gamma\lambda)^l \delta_{t+l}\).

Big policy steps can wreck performance. PPO (Schulman et al., 2017) limits how far the new policy moves from the one that collected the data, using the probability ratio \(\rho_t(\theta) = \pi_\theta(a_t\mid s_t)/\pi_{\text{old}}(a_t\mid s_t)\):

It's a cheap first-order approximation of TRPO's trust region (a KL constraint). PPO matters here because MAPPO, the strongest simple MARL baseline, is PPO with a centralised critic.

Continuous-control workhorses: DDPG → TD3 (twin critics, delayed actor) → SAC (maximum-entropy, very sample-efficient off-policy). On-policy PPO dominates massively parallel simulation (Isaac Gym-style legged robots). Off-policy SAC/TD3 is common when samples are expensive.

Put two self-driving cars at an unsignalised intersection. What's optimal for car 1 now depends on what car 2 does, and car 2 is also learning. From car 1's point of view the environment keeps changing its rules. A fleet of warehouse robots, a platoon of trucks and a drone swarm all have this structure.

Markov (stochastic) game (Shapley 1953; Littman 1994) with \(N\) agents:

Each agent's value depends on the joint policy \(\boldsymbol\pi=(\pi_1,\dots,\pi_N)\): \(V_i^{\boldsymbol\pi}(s)=\mathbb{E}_{\boldsymbol\pi}[\sum_k\gamma^k r_{i,t+k+1}\mid s_t=s]\). Robots and cars only see locally, and in cooperative tasks they share one team reward, so the standard model is the Dec-POMDP:

Here \(\tau_i\) is agent \(i\)'s own action–observation history. Finding an optimal finite-horizon Dec-POMDP policy is NEXP-complete (Bernstein et al., 2002), much harder than a single-agent MDP (P-complete). That's why practical MARL uses approximations and learning.

In general-sum games there's no single "optimal" policy. The central concept is the Nash equilibrium: no agent can do better by changing only its own policy.

Related concepts: best response \(\pi_i\in \arg\max V_i^{(\pi_i,\boldsymbol\pi_{-i})}\); Pareto optimality (no one can gain without someone losing); correlated equilibrium (a shared signal, like a traffic light, coordinates the agents). Nash exists in mixed strategies for finite games (Nash 1950), but can be Pareto-inefficient. The Prisoner's-dilemma preset below shows this. For zero-sum games there's minimax-Q (Littman 1994); for general-sum, Nash-Q (Hu & Wellman 2003), which needs strong assumptions to converge.

In simulation you can see everything: every car's position, every action. On the real road each car only has its own sensors and maybe a patchy V2V link. The dominant paradigm uses that asymmetry: train with global information, execute with local information.

Learn a team value \(Q_{tot}\) but factor it into per-agent utilities \(Q_i(\tau_i,a_i)\), so each agent can act greedily on its own and still pick the team's best joint action. This requirement is the IGM principle (Individual-Global-Max):

• VDN (Sunehag et al., 2018): \(Q_{tot}=\sum_i Q_i\). Simple, but can only represent additive team values.
• QMIX (Rashid et al., 2018): \(Q_{tot}=f_{mix}(Q_1,\dots,Q_N; s)\) with \(\frac{\partial Q_{tot}}{\partial Q_i}\ge 0\). Monotonicity is sufficient for IGM. The mixer's weights are generated from the global state by hypernetworks and kept non-negative (absolute value), so the state can shape the mixing while monotonicity holds.
• QTRAN, QPLEX, Weighted QMIX: relax monotonicity to represent richer (non-monotonic) coordination while keeping IGM.

MADDPG (Lowe et al., 2017): each agent has a deterministic actor \(\mu_i(o_i)\) and a centralised critic \(Q_i(\mathbf{x}, a_1,\dots,a_N)\) that sees everyone's observations and actions. It works for cooperative, competitive and mixed settings, and handles continuous control such as steering.

COMA (Foerster et al., 2018) targets credit assignment. It asks "how much better was my action than what I'd typically do, holding everyone else fixed?", using a counterfactual baseline:

MAPPO (Yu et al., 2022, "The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games"): PPO actors with parameter sharing plus a centralised value function \(V_\phi(s)\). It matches or beats more complex methods on SMAC, MPE and Google Research Football, and is the default strong baseline for robotics MARL. HAPPO/HATRPO (Kuba et al., 2022) update agents sequentially and come with a monotonic improvement guarantee for heterogeneous agents.

# MAPPO: the loop you should be able to sketch on a whiteboard
for iteration in range(K):
    for t in range(T):                            # rollout in parallel sims
        a_i, logp_i = actor_θ(o_i)  for each agent i     # shared weights + agent-ID
        s', o', r, done = env.step(a_1..a_N)
        buffer.add(o_i, a_i, logp_i, s, r, done)
    A_i  = GAE(r, V_φ(s), γ, λ)                   # centralised critic sees global state
    for epoch in range(E):
        θ ← θ + ∇ L_CLIP(θ; A_i)                   # PPO clip per agent sample
        φ ← φ − ∇ (V_φ(s) − R̂)²
# deploy: only actor_θ(o_i) runs on each robot

• Parameter sharing: one network for all homogeneous agents, with an agent-ID in the input. Sample-efficient, and the standard choice for fleets.
• Mean-field MARL (Yang et al., 2018): approximate the others by their average action, \(Q_i(s,a_i,\bar a_{-i})\). This scales to hundreds of agents (dense traffic, swarms).
• Graph neural networks / attention: agents are nodes, neighbours within sensing range are edges. They handle a variable number of cars and are permutation-invariant.
• Learned communication: CommNet (Sukhbaatar et al., 2016), DIAL (Foerster et al., 2016), TarMAC (Das et al., 2019, targeted attention messages). The V2V analogue.

This is what a strong seminar slide on "how I'd formulate the problem" looks like. Scenario: N connected AVs negotiating an unsignalised intersection with human-driven traffic.

• Highway merging and lane changing: negotiation with cooperative and human vehicles. Shalev-Shwartz et al. (2016) framed safe multi-agent driving as RL plus hard safety constraints.
• Intersections and roundabouts: signal-free coordination; also traffic-signal control, where each light is an agent.
• Platooning / cooperative adaptive cruise control: string stability, fuel savings.
• Mixed autonomy: a few AVs smoothing stop-and-go waves for the human traffic (Wu et al., Flow framework on SUMO).
• Social driving: Social Value Orientation, estimating how selfish or altruistic other drivers are (Schwarting et al., PNAS 2019).
• Multi-robot navigation: decentralised collision avoidance from raw LiDAR with PPO and a shared policy (Long et al., ICRA 2018); warehouse fleets; multi-drone coverage; multi-arm manipulation.

• Safety with guarantees: constrained MARL, shielding, CBFs in multi-agent settings; verification of learned policies.
• Sim-to-real: domain randomisation, system identification, robustness to sensor noise and latency. The multi-agent gap is bigger, because other agents' behaviour also shifts.
• Human interaction: modelling heterogeneous human drivers, zero-shot coordination / ad hoc teamwork with unknown partners.
• Scalability and variable N: graph/attention policies that generalise from 5 cars in training to 50 in testing.
• Communication under constraints: bandwidth, delay and dropouts in V2V; what to communicate.
• Robustness and adversaries: adversarial agents for stress-testing AV stacks (a competitive MARL use).
• Offline MARL: learning from logged fleet data without risky online exploration.
• Evaluation: seeds, scenario diversity, standardised metrics. The field has real reproducibility issues.

• Motivation: driving is inherently multi-agent; single-agent RL treats other cars as noise.
• Formalism: MDP → Markov game → Dec-POMDP (one slide, three tuples).
• Why it's hard: non-stationarity, credit assignment, \(|\mathcal A|^N\), partial observability.
• CTDE and the key families: value decomposition (QMIX, IGM) vs centralised critics (MAPPO, MADDPG).
• Application: the intersection formulation table from Chapter 10.
• Open problems and your angle: safety, sim-to-real, human interaction, scalability.

Score: 0 / 0