Multi-Agent Reinforcement Learning is a Sequence Modeling Problem

year: 2022/05
paper: https://arxiv.org/abs/2205.14953
website: https://www.reddit.com/r/MachineLearning/comments/v2af3k/r_multiagent_reinforcement_learning_can_now_be/ | https://sites.google.com/view/multi-agent-transformer
code: https://github.com/PKU-MARL/Multi-Agent-Transformer
connections: MARL, transformer

---

Preliminaries

Multi-Agent Advantage Function

The advantage function $A_{\pi }^{i_{1:m}}(o,a^{j_{1:h}},a^{i_{1:m}})$ measures how much better (or worse) the joint value will be when a specific subset of agents $i_{1:m}$ take actions $a^{i_{1:m}}$, after another subset of agents $j_{1:h}$ have already committed to actions $a^{j_{1:h}}$:

$$A_{\pi }^{i_{1:m}}(o,a^{j_{1:h}},a^{i_{1:m}})=Q_{\pi }^{j_{1:h},i_{1:m}}(o,a^{j_{1:h}},a^{i_{1:m}})-Q_{\pi }^{j_{1:h}}(o,a^{j_{1:h}})$$

$Q_{\pi }^{j_{1:h},i_{1:m}}$ - The value when both groups of agents ($j_{1:h}$ and $i_{1:m}$) take their respective actions
$Q_{\pi }^{j_{1:h}}$ - The baseline value considering only the actions of agents $j_{1:h}$

When $h=0$ (no prior agents have committed actions), this reduces to comparing the value of actions $a^{i_{1:m}}$ against the baseline value of the whole team (expected return under the current policy).

Note: The advantage function doesn’t model some agents being “inactive” - rather, it measures the relative value of specific action choices by a subset of agents compared to letting all agents act according to their default policy behavior, the baseline Value $Q_{\pi }^{\varnothing }(o,\varnothing )$

Example

Consider a team of 3 agents where:
Agent 1 commits to action $a^1$ first ($j_{1:h}=\{1\}$) and we want to evaluate the advantage of agents 2 and 3’s joint action $(a^2,a^3)$ ($i_{1:m}=\{2,3\}$)
The advantage function would measure how much better/worse agents 2 and 3’s chosen actions are compared to the expected value after only agent 1’s action.

Multi-Agent Advantage Decomposition Theorem

Let $i_{1:n}$ be a permutation of agents. For any joint observation $o$ and joint action $a$:

$$A_{\pi }^{i_{1:n}}(o,a^{i_{1:n}})=\sum _{m=1}^n{A}_{\pi }^{i_m}(o,a^{i_{1:m-1}},a^{i_m})$$

The total advantage of a joint action can be decomposed into a sum of individual advantages, where each agent’s advantage is conditioned on the actions chosen by previous agents in the permutation.

This enables sequential decision making.

Agent $i_1$ goes first, picks an action with $a^{i_1}$ aiming for positive advantage $A_{\pi }^{i_1}(o,a^{i_1})>0$
Agent $i_2$, knowing $a^{i_1}$, chooses $a^{i_2}$ for positive $A_{\pi }^{i_2}(o,a^{i_1},a^{i_2})>0$
Agent $i_3$, knowing $(a^{i_1},a^{i_2})$, …

Instead of searching the entire joint action space ${\prod }_{i=1}^n|A^i|$, we can search each agent’s action space separately ${\sum }_{i=1}^n|A^i|$.
→ Each agent can make decisions based information about what others have done, incrementally improving actions.
→ The computational savings get more dramatic as you add more agents

Link to original

MAPPO objective

The objective of MAPPO is equivalent to that of PPO, but equipping each agent with one shared set of parameters, i.e. ${\theta }^i={\theta }^j,\forall i,j\in \mathcal{N}=\{1,\dots n\}$. It uses the agent’s combined trajectories for the shared policy’s update.
So the objective for optimizing the policy parameters ${\theta }_{k+1}$ at iteration $k+1$ is:

$$\sum _{i=1}^n{\mathbb{E}}_{\mathbf{o}\sim {\pi }_{{\theta }_k},\mathbf{a}\sim {\pi }_{{\theta }_k}}\left[\min \left(\frac{{\pi }_{\theta }({\mathbf{a}}^i|\mathbf{o})}{{\pi }_{{\theta }_k}({\mathbf{a}}^i|\mathbf{o})}{A}_{{\pi }_{{\theta }_k}}(\mathbf{o},\mathbf{a}),\text{clip}\left(\frac{{\pi }_{\theta }({\mathbf{a}}^i|\mathbf{o})}{{\pi }_{{\theta }_k}({\mathbf{a}}^i|\mathbf{o})},1\pm ϵ\right)A_{{\pi }_{{\theta }_k}}(\mathbf{o},\mathbf{a})\right)\right]$$

The constraint on the joint policy space imposed by shared parameters can lead to an exponentially-worse sub-optimal outcome (details; page 4).

Link to original

HAPPO vs MAPPO

MAPPO is a straightforward application of PPO to multi-agent settings, often forcing all agents to share one set of policy parameters. This can be suboptimal when agents need different behaviors.
HAPPO relaxes this constraint by:

1. Sequentially updating each agent in a random permutation $i_1,\dots ,i_n$, where agent $i_m$ updates using the newly updated policies of agents $i_{1:m-1}$.
2. Leveraging the Multi-Agent Advantage Decomposition Theorem, which yields a valid trust‐region update for each agent’s local advantage $A_{\pi }^{i_m}(o,a^{i_{1:m-1}},a^{i_m})$. Specifically, HAPPO applies the standard PPO (clipped) objective to each agent while treating previously updated agents’ policies as “fixed.” Because the decomposition theorem ensures the local advantage aligns with the global return, any PPO‐style step that respects the trust region (i.e., doesn’t deviate too far from the old policy) guarantees a monotonic improvement for the entire multi-agent policy.
3. Maintaining distinct policy parameters for truly heterogeneous capabilities.

This ensures a monotonic improvement guarantee for the joint return – something MAPPO’s parameter-sharing approach can’t guarantee. As a result, HAPPO typically performs better than MAPPO in scenarios where agents must learn different skillsets.
However, one drawback of HAPPO is that agent’s policies has to follow the sequential update scheme (in the permutation), thus it cannot be run in parallel.

Link to original

Implementation

Algorithm

Steps:

1. Generate encoded joint agents observations: $\hat{O}=\psi (O)$
2. Generate state-value estimates from observations: $V(O)=\text{MLP}(V(\hat{O}))$
3. Autoregressively decode agent actions, while cross-attending the encoded observations: $a^{i_{m+1}}=\theta (a^{i_{0:m}})$

Slap PPO on top… that’s it!