- AI, But Simple
- Posts
- Multi-Agent RL, Simply Explained
Multi-Agent RL, Simply Explained
AI, But Simple Issue #110
A single reinforcement learning (RL) agent learns in a closed feedback loop. It observes an environment, picks an action, and updates its policy based on the reward it receives.
The environment may be complex, but from the agent's point of view, it behaves consistently enough to learn useful patterns from.
Multi-agent reinforcement learning (MARL) is a field of RL that deals with environments that are not as stable, where multiple agents share and interact within the same environment.
In MARL, agents act in parallel in a single environment, trained on rewards that depend on what the other agents do.
Picture a self-driving car navigating an intersection, a robot-controlled warehouse, or traffic signals coordinating roads. These are all examples of MARL problems.
Most of MARL research (old and new) is about routing around a dynamic, complex environment without giving up what makes RL useful in the first place.
What You’ll Learn
Single-agent RL vs. Multi-agent RL
Formalizing the multi-agent problem (Dec-POMDPs and Markov games)
Multi-agent training and execution
The centralized training, decentralized execution (CTDE) loop
Recent MARL methods and research
What's Helpful to Know
Policy (π)
A function mapping an agent's observation to a probability distribution over possible actions.
Markov Decision Process (MDP)
The formalism for sequential decision-making under uncertainty. An MDP has 4 components: a state (s), an action (a), a transition function (that depends only on current state and action), and a reward (R).
Partial observability
When an agent only sees a local observation of the environment, not the full state. POMDPs are partially observable MDPs, which we discussed in the previous world models article.
Non-stationarity
When the environment's dynamics (from an agent's point of view) change over time due to other agents that are learning.
Advantage function (A)
How much “better” an action is than the policy's average action in a state, defined as A(s,a) = Q(s,a) - V(s)
The Problem With Non-Stationarity
A standard MDP demonstrates the Markov property, indicating that the transition function P(s′ | s, a) depends only on the current state and action, staying fixed for the entire training process.
This fixed quality is what lets popular RL algorithms like Q-learning prove convergence.
Add more agents into the same environment, and the transition becomes:
Here, ai is the action from the i-th agent.
The next state now depends on the joint action of every agent, not just one.
From agent i's perspective, every other agent's action is effectively part of the environment.
Since those other agents are also updating their own policies during training, the effective transition agent i experiences keeps shifting underneath it, update after update.
The same state and the same action from agent i can lead to different outcomes over time, purely because everyone else's behavior around it hasn't stayed still.
This is the non-stationarity property of MARL, and it's why convergence (for a single agent) is no longer guaranteed once a second learner is introduced.
Formalizing Multi-Agent Systems
Two formalisms extend the regular MDP to handle this. Fully cooperative problems, where agents share one team reward, are modeled as Dec-POMDPs:
N is the set of agents, S is the true global state, {Ai } is the agent i’s action space, P(s′ | s, a) is the joint transition function, R(s, a) is the shared team reward, {Ωi } is agent i's local observation space, and γ is the discount factor.
To illustrate, a global state can contain a position, nearby obstacles, and agent velocities. An action space might contain movements, picking things up, or even waiting. Rewards may be mapped so that an agent receives +5 for reaching the finish line and -5 for dying.
Mixed (competitive) problems, where agents can have different rewards, are modeled as a Markov game (stochastic game).
It shares the same tuple as the Dec-POMDP but with an individual reward function Ri for each agent so agents can be rewarded differently for the same joint outcome.
Cooperative Dec-POMDPs and zero-sum competitive games both sit inside this more general Markov game.
Centralized Training, Decentralized Execution (CTDE)
MARL typically deals with partial observability.
An agent has imperfect sensor inputs and other forms of noise that lead to incomplete observations. Other agents have varying plans and intentions, which are all hidden.
The dominant way to handle non-stationarity and partial observability together is centralized training, decentralized execution, or CTDE.
During training, each agent gets access to the full global state and every agent's action. All agents know what every other agent is going to do, and this information is only available in a simulator or lab setting.
At inference (execution) time, each agent acts using only local observations, matching how it will actually be deployed in the real world.
Simply put, agents get global information during training, then act using local information once deployed.
A good thing to note here is that CTDE doesn't stop other agents from changing. It simply injects enough information into the training process to explain those changes, so it doesn’t seem like the environment is changing unpredictably as other agents learn.
We’ll take a look at algorithms that have varying implementations that surround the CTDE idea.
If you enjoy our content and custom visuals, consider sharing this newsletter with others or upgrading so we can keep doing what we do.
Get full access with the PRO newsletter tier:
AI Bootcamp in Your Inbox (Hands-on Code tutorials, Practice Examples + Solutions)
Interview Questions and Cases (Tracked from 100+ Companies)
Full Article Access: More Visuals, More Explanations
Ad-Free Reading
The CTDE Loop (MADDPG)
Published by OpenAI in 2017, Multi-Agent Deep Deterministic Policy Gradient (MADDPG) is a foundational example of the CTDE loop, solving the problem of continuous action spaces with multiple agents.
The key idea is that for each agent, to split information between actors and critics. The actors shape the policy, while the critics are the value function (Q-value in this case).
Let’s walk through a step-by-step view of the algorithm:
Local observations. At timestep t, each agent receives its own local observation, oit which is a partial view of the true global state st. Agents cannot see what other agents observe and typically can't see st directly.
Local action selection. Each agent runs its own policy (actor) network (μθi) that outputs deterministic actions conditioned only on its own observation. All agents choose simultaneously, with zero visibility into other agents actions. The choices make up the joint action at, which is the tuple of all actions (a1t, …, ant).
Per-agent reward and environment transition. The environment applies the full joint action, transitions to the next state st+1 according to the transition function P(s′ | s, a), and returns a reward to each agent, Ri (st, at, st+1). In cooperative settings, this reward is usually the same across agents, while in mixed or competitive settings, it can differ.
Store the transition in a replay buffer. Each agent's observation, action, reward, and next observation, along with the global state if it's available, gets written to a shared replay buffer for off-policy training.
Centralized critic. For each agent i, a centralized critic Qi(x,a1 ,…,an ) is updated toward a temporal difference (TD) target using target networks.
Above, y represents a target Q-value, Qi’ is the target critic, x’ is the target observation, and the actions ai' are actions predicted by the target critics. So each agent has its own critic, but the critic has access to all other agents’ actions and observations (during training, not inference). The equation below calculates the MSE loss between the current critic and the target.
Decentralized actor update. Each actor updates through the deterministic policy gradient below:
The gradient backpropagates through the critic, then to the actor network. It’s important to note that although the actor uses this global gradient, an actor’s forward pass relies on local observation only.
Steps 1-4 repeat at every iteration until an episode finishes. An episode is a complete sequence of timesteps that ends when a terminal condition is reached (e.g., the agent wins or loses).
Steps 5 and 6 occur intermittently by sampling batches from the replay buffer to learn from.
Steps 1-6 define the training cycle, which loops for thousands of episodes until the policies converge.
After training, we discard the critics and keep the actors since the feedback is no longer required during execution. Each agent acts using only its own trained policy, μi(oi ).
Current MARL Techniques
MADDPG and similar value-decomposition methods (like QMIX) work, but they don’t guarantee that a training update actually improves the joint policy.
How can we guarantee an improvement? Single-agent trust region methods like TRPO and PPO are the solution, which was extended to multi-agent in 2021 by Kuba et al. with their algorithm, Heterogeneous-Agent Trust Region Policy Optimization (HATRPO).
For any ordering of agents i1, …, im:
This basically says the team's total advantage from a joint action splits into a chain. This holds for any joint policy.
Instead of agents updating simultaneously and possibly making the policy worse, they update sequentially.
For example:
Agent 1 looks at the baseline (in this case, the value function) and updates its policy to find a better action.
Agent 2 looks at the baseline plus Agent 1's new action (Q(s, a1)), and updates its policy.
Agent 3 looks at the baseline plus Agent 1 and 2's new actions (Q(s, a1, a2)), and updates its policy.
Each agent's update only needs the actions already chosen by earlier agents in that same step rather than a shared centralized critic.
This ensures that training updates never decrease the joint policy's expected return, which we call a provable monotonic improvement guarantee.
HATRPO also has a PPO version called HAPPO. Both methods outperformed MADDPG and QMIX on multi-agent benchmarks like StarCraft II and MuJoCo.
Heterogeneous-Agent Reinforcement Learning (HARL) (Zhong et al., 2024) is an extension that generalizes this into something called Heterogeneous-Agent Mirror Learning, strengthening the same guarantee.
Multi-agent decomposition lemma described in the HARL paper
A separate 2022 approach, the Multi-Agent Transformer (MAT) (Wen et al., 2022), uses the same HATRPO decomposition but implements the sequential update as an actual sequence model.
A transformer encoder reads all observations from agents, and a decoder generates each agent's action autoregressively, conditioned on the actions from earlier agents in the sequence.
MAT showed some impressive results at the time, attaining 100% win rates on SMAC's hardest maps where earlier baselines scored 0%.
Where MARL is Going
MARL is not exactly single-agent RL with more agents added on. Multiple simultaneous learners break the stationarity assumption that the MDP theory depends on.
Early algorithms like MADDPG's centralized critics laid out the fundamentals, but they struggled to guarantee that training actually helped.
Methods built on the multi-agent advantage decomposition now provide that guarantee, extending to transformers due to the sequential structure.
MARL is increasingly being integrated with LLMs to provide controller feedback and semantic vision reasoning. We also see an uptick of MARL systems acting in world models.
As the field continues to advance, it will be interesting to see what new directions MARL will take.
Here’s a special thanks to our biggest supporters:
If you enjoy our content, consider supporting us so we can keep doing what we do. Please share this with a friend!
Want to reach 8000+ ML engineers? Advertising Inquiries:
Feedback or inquiries? Send us an email at [email protected].
That’s it for this week’s issue of AI, but simple. See you next week!
—AI, but simple team