Multi-Agent Advantage Decomposition Theorem

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