ifaamas [AAMAS ’24]Proc. of the 23rd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2024)May 6 – 10, 2024 Auckland, New
ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.) 2024 2024 976
University of California, Berkeley Berkeley CA, USA The University of Texas at
Austin Austin TX, USA University of California, Berkeley Berkeley CA, USA
University of California, Berkeley Berkeley CA, USA University of California,
Berkeley Berkeley CA, USA University of California, Berkeley Berkeley CA, USA
University of California, Berkeley Berkeley CA, USA

# Quantifying Agent Interaction in Multi-agent Reinforcement Learning for
Cost-efficient Generalization

Yuxin Chen<EMAIL_ADDRESS>,  Chen Tang<EMAIL_ADDRESS>,
Ran Tian<EMAIL_ADDRESS>,  Chenran Li<EMAIL_ADDRESS>,
Jinning Li<EMAIL_ADDRESS>,  Masayoshi Tomizuka
<EMAIL_ADDRESS>and  Wei Zhan<EMAIL_ADDRESS>
###### Abstract.

Generalization poses a significant challenge in Multi-agent Reinforcement
Learning (MARL). The extent to which an agent is influenced by unseen co-
players depends on the agent’s policy and the specific scenario. A
quantitative examination of this relationship sheds light on effectively
training agents for diverse scenarios. In this study, we present the _Level of
Influence_ (LoI), a metric quantifying the interaction intensity among agents
within a given scenario and environment. We observe that, generally, a more
diverse set of co-play agents during training enhances the generalization
performance of the ego agent; however, this improvement varies across distinct
scenarios and environments. LoI proves effective in predicting these
improvement disparities within specific scenarios. Furthermore, we introduce a
LoI-guided resource allocation method tailored to train a set of policies for
diverse scenarios under a constrained budget. Our results demonstrate that
strategic resource allocation based on LoI can achieve higher performance than
uniform allocation under the same computation budget.

###### Key words and phrases:

Multi-agent reinforcement learning, Learning agent-to-agent interactions,
Multi-agent systems

none printacmref=false printfolios=true

##  1\. Introduction

Creating agents capable of effectively interacting with other agents, in
particular humans, has been a longstanding challenge Bard et al. (2020); Dafoe
et al. (2020). Agents trained with model-free reinforcement learning (RL) have
shown the potential to reach or surpass human-level performance through self-
play (SP) in both classical discrete board games Silver et al. (2017, 2018);
Zha et al. (2021) and continuous domains such as Dota Berner et al. (2019),
Starcraft Vinyals et al. (2019), and racing Fuchs et al. (2021). However, SP
agents typically undergo training with replicas of themselves, resulting in
limited adaptability and robustness when interacting with previously unseen
co-players exhibiting different behaviors Lowe et al. (2020); Bullard et al.
(2020); Strouse et al. (2021); McKee et al. (2022).

One promising solution to improve the policy robustness is _diversifying the
co-player distribution_. It has been shown that computationally hard problems
like chess and go could benefit from diversifying agents during training
Zahavy et al. (2023). Prior studies introduced and validated methods for more
complex games, such as population-based training Jaderberg et al. (2019);
Carroll et al. (2019); Jaderberg et al. (2017), league-based training Vinyals
et al. (2019), fictitious self-play Heinrich et al. (2015); Strouse et al.
(2021), and diversification of agent hyperparameters Hu et al. (2020); McKee
et al. (2020). However, it is important to note that a trade-off exists in
most of these methods, where enhancing generalization capabilities comes at
the cost of increased training resources and time.

Nevertheless, an important question remains: is diversifying the co-player
distribution during training always worthwhile? In practice, various real-
world applications require a set of tailored RL policies for diverse target
scenarios Lowe et al. (2017); Fuchs et al. (2021). Diversifying the co-player
distribution during training in all the target scenarios comes at a high
training cost, with the resulting benefits varying based on the specific
scenario. In particular, we argue that the benefits of introducing diverse co-
players depend on how _interactive_ a scenario is. For instance, consider
training agents for autonomous driving tasks. Enhanced generalization does not
provide substantial advantages on highways as it does in crowded intersections
and roundabouts. On highways, vehicles primarily focus on maintaining a
straight path and constant speed, involving fewer interactions. In contrast,
in roundabouts and intersections where agents’ paths are highly
interdependent, the presence of diverse surrounding agent behaviors has a much
more significant impact on the ego agent policy.

Our key insight is that, by quantifying the interaction intensity across
various scenarios, we can assess the necessity of diversifying co-player
policy distribution when training the ego agent policy as the effects of
environmental variation, and allocate the training resources strategically to
maximize the overall advantage.

We introduce the _Level of Influence_ (LoI), a metric quantifying the
interaction intensity among agents within a given scenario. We propose to
quantify the interaction intensity by how much the ego agent’s reward is
affected by the variation of non-ego agents’ behavior. Formally, inspired by
Jaques et al. (2019), we define LoI as the mutual information (MI) between the
ego agent’s expected reward and the non-ego agent’s policy selection. We
validate the effectiveness of using LOI for cost-efficient generalization by
training a set of policies with co-players of different diversities for groups
of scenarios and environments. We find that the LoI metric is highly
correlated with the benefits of having diverse co-player policy distribution
on the generalization of the ego agent within given scenarios, i.e., a higher
LoI value indicates a larger improvement can be achieved in the ego agent’s
performance when a more diverse set of co-play agents are encountered during
training.

Consequently, we design a LoI-guided resource allocation method to train a set
of policies for diverse scenarios under a limited training budget. We compare
the overall performance between the LoI-guided and uniform allocation schemes,
showcasing that the LoI-guided scheme consistently yields higher average
performance across a range of game settings.

We summarize the novel contributions of this paper as follows:

  1. 1.

We propose a novel metric, Level of Influence (LoI), to quantify the
interaction among agents in general multi-agent reinforcement learning
problems.

  2. 2.

We demonstrate that the LoI metric is highly correlated with the benefits of
having diverse co-player distribution on the generalization of the ego agent
within given scenarios.

  3. 3.

We propose a LoI-guided resource allocation method and show that it can
achieve a higher average reward than uniform allocation under the same
computation budget.

##  2\. Related Work

Ad-hoc Teamwork. Ad-hoc teamwork (AHT) Stone et al. (2010), also referred to
as zero-shot coordination (ZSC) Hu et al. (2020), involves training agents to
collaborate with co-players they have not encountered before. Early approaches
primarily focused on game-theoretic analysis within matrix games Stone et al.
(2009); Agmon and Stone (2012). Recently, multi-agent reinforcement learning
(MARL) has enabled ad-hoc teamwork in more intricate grid worlds and
continuous domains. Various works have explored hierarchical social intention
Kleiman-Weiner et al. (2016), social conventions Shih et al. (2021), shared
planning Ho et al. (2016), and theory of mind Choudhury et al. (2019) in this
context. In MARL, an agent’s learning is influenced by both other co-players
and the environment Littman (1994). However, most of the previously mentioned
works do not explicitly evaluate the impacts of environmental variations.
Carroll et al. Carroll et al. (2019) introduce the game Overcooked and
explicitly showcase that the environment configurations affect the robustness
of the trained agents when teamed with unknown human players. Subsequent
research includes diverse layout generation Fontaine et al. (2021); McKee et
al. (2022) and scalable evaluation Leibo et al. (2021). Nonetheless, these
works only provide _qualitative_ analyses of different environments and do not
_quantitatively_ measure such effects across scenarios.

Generalization in Multi-agent RL. In the field of MARL, various attempts have
been made to enhance agents’ adaptability to new co-players. Jaderberg et al.
Jaderberg et al. (2017, 2019) introduced population-based training (PBT) to
jointly optimize the performance of a population of models. Several variations
of PBT include the league-based training that masters the full game of
StarCraft II Vinyals et al. (2019), the fictitious co-play (FCP) that can
reach human-level performance Heinrich et al. (2015); Strouse et al. (2021),
and heterogeneous populations training with Social Value Orientation (SVO)
McKee et al. (2020). However, high-performing agents come at the cost of more
expensive training cost. Considering the varying benefits of generalization
across diverse environments, we aim to evaluate if the extra training cost for
enhanced generalization is justified. This area is relatively under-explored
in existing research.

Causal Influence. Our work shows a notable connection to Jaques et al. Jaques
et al. (2019), where a causal influence reward is incorporated as an intrinsic
motivation during the training of RL agents. This reward incentivizes agents
to maximize mutual information (MI) between their actions. The goal of
maximizing MI between actions is to encourage more coordinated behavior among
the agents. The causal influence is assessed using counterfactual reasoning
McAllister et al. (2022); Foerster et al. (2018); Pearl (2013) where an agent
simulates alternate, counterfactual _actions_ that it could have taken at
every time step. In contrast, we measure the mutual information between the
ego agent’s expected reward and the non-ego agent’s policy selection by
simulating counterfactual _policies_ that the non-ego agent would have chosen
within given scenarios.

##  3\. Preliminaries

###  3.1. Multi-agent MDP

An _n-player partially observable Markov game_ $\mathcal{M}$ Boutilier (1996);
McKee et al. (2022) is defined by tuple
$\mathcal{M}=\langle\mathcal{S},\mathcal{O},\\{\mathcal{A}_{i}\\}_{i\in\alpha},\mathcal{T},\\{r_{i}\\}_{i\in\alpha}\rangle$,
where $\mathcal{S}$ is the finite set of _states_ ,
$\mathcal{O}\colon\mathcal{S}\times\\{1,\dots,n\\}\mapsto\mathbb{R}^{d}$ is
the _observation_ function specifying each agent’s $d$-dimensional view on the
state space followed by their joint observation
$\@vec{o}=(o_{1},\dots,o_{n})$. Let $\alpha$ be a finite set of _agents_ ,
$\mathcal{A}_{i}$ is a finite set of discrete _actions_ available to agent
$i$. The joint action is defined as
$\@vec{a}=(a_{1},\dots,a_{n})\in\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{n}$.
The stochastic _transition function_
$\mathcal{T}\colon\mathcal{S}\times\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{n}\mapsto\Delta(\mathcal{S})$
determines the discrete probability distribution over the next state given the
current state and the joint action. Each agent $i$ receives its real-valued
_reward_ defined as
$r_{i}\colon\mathcal{S}\times\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{n}\mapsto\mathbb{R}$.

Each agent learns their policy in a _decentralized_ manner (i.e.,
independently learns a _policy_ $\pi_{i}(a_{i}|o_{i})$ based on its own
observation $o_{i}$ by optimizing its own individual reward $r_{i}$) without
direct communication with other agents. We use
$\@vec{\pi}=(\pi_{1},\dots,\pi_{n})$ to denote the joint policy. Let $\gamma$
denote the discount factor that discounts future reward, agent $i$ optimizes
for a policy that maximizes the long-term $\gamma$-discounted payoff McKee et
al. (2022) defined as

$V_{\pi_{i}}(s_{0})=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r_{i}(s_{t},\@vec{a}_{t})|\@vec{a}_{t}\sim\@vec{\pi}_{t},s_{t+1}\sim\mathcal{T}(s_{t},\@vec{a}_{t})\right].$
(1)

###  3.2. Multi-agent Reinforcement Learning

Self-play. Self-play (SP) is an online evolutionary algorithm in which agents
learn by playing against duplicates of themselves. Policies trained via SP
have succeeded in a variety of environments and game settings Silver et al.
(2018); Vinyals et al. (2019); Berner et al. (2019); Zha et al. (2021). In the
SP training, all the agents are initialized with random policies and we keep
updating the ego agent’s policy while fixing other agents’ policies.
Throughout the training phase, the policies of the ego agent are stored as
checkpoints periodically. Subsequently, following each checkpoint save, all
non-ego agents adopt the recently saved checkpoint as their updated policies.
(i.e., all non-ego agents become the latest duplicates of the ego agent). One
major drawback of SP is that the learning agent can not generalize well to new
partners outside of its own policy distribution Strouse et al. (2021); Bullard
et al. (2020, 2021); Lowe et al. (2020) as agents only learn how to
collaborate with themselves during training.

Population-play. Population-play (PP), on the other hand, keeps a population
of agents training in parallel Jaderberg et al. (2017). The environment and
its agents are initialized with $p$ different random seeds ($p$ is the number
of _population_), and each population follows the same training scheme as SP.
Instead of loading the recently saved checkpoints from their own population,
non-ego agents of each population randomly select a population and adopt this
population’s latest checkpoint as their updated policies. By mutating
different checkpoints across multiple populations, PP agents acquire better
generalization capabilities than SP as a wider range of behavioral
distribution has been covered during training Jaderberg et al. (2017); Carroll
et al. (2019); Strouse et al. (2021); McKee et al. (2022).

Training Algorithm. In multi-agent RL, agents’ policies are parameterized by
neural network models trained with various deep RL algorithms. In our case, we
use Proximal Policy Optimization (PPO) Schulman et al. (2017) for model
training.

##  4\. Methodology

We aim to study the potential impact of the diversity of co-play agents during
training on the generalization performance as the effects of environmental
variation. In MARL, the performance of a policy is measured by its expected
reward when pairing with different co-players, which is determined by the
reward design (i.e., payoff matrix). We use the term _environments_ to refer
to games that have distinct reward designs. Under the same reward design, one
can create different environmental variations by changing the map layout
(e.g., map size, map shape, obstacle locations, and more). We use the term
_scenarios_ to refer to distinct map layouts within the same _environment_.
Enhanced generalization yields varied levels of performance improvements for
the agent in different scenarios. Intuitively, this is because agents in
different scenarios have different interaction intensities, and the
generalization performance as measured by the expected reward depends greatly
on the interaction pattern and frequency. Therefore, we aim to find a metric
that quantifies the interaction between agents as a way to predict the
potential generalization improvement by having a more diverse set of co-player
policies during training.

Algorithm 1 Level of Influence calculation

1:# Alice policies $a$, # Bob policies $b$, # Alice checkpoints per policy
$m$, # Bob checkpoints per policy $n$, Alice sampling probability
$P_{\varphi}$, Bob sampling probability $P_{\vartheta}$, # game per Alice-Bob
pair $g$

2:Train $a$ Alice policies with SP and save checkpoints pool $\Phi_{i}$

3:Train $b$ Bob policies with SP and save checkpoints pool $\Theta_{j}$

4:Initialize set of index $\mathcal{I}\leftarrow\\{\\}$

5:for i=1:a do

6: Sample $m$ Alice checkpoints $\phi_{i,k}\sim\Phi_{i}$ with $P_{\varphi}$

7: for k=1:m do

8: for j=1:b do

9: Sample $n$ Bob checkpoints $\theta_{j,l}\sim\Theta_{j}$ with
$P_{\vartheta}$

10: Initialize set of distribution $\mathcal{P}\leftarrow\\{\\}$

11: for l=1:n do

12: $P_{R_{i,k}|\vartheta=\theta_{j,l},\leavevmode\nobreak\
\varphi=\phi_{i,k}}\leftarrow$ Distribution($\phi_{i,k}$, $\theta_{j,l}$, $g$)

13: $\mathcal{P}\leftarrow\mathcal{P}\cup
P_{R_{i,k}|\vartheta=\theta_{j,l},\leavevmode\nobreak\ \varphi=\phi_{i,k}}$

14: end for

15:
$P_{R_{i,k}|\varphi=\phi_{i,k}}\leftarrow$Marginal_Distribution($\mathcal{P}$,
$P_{\vartheta}$)

16:$\triangleright$ Eq. (3)

17: $I_{i,j,k}\leftarrow$Mutual_Information($P_{R_{i,k}|\varphi=\phi_{i,k}}$,
$\mathcal{P}$)

18:$\triangleright$ Eq. (4d)

19: $\mathcal{I}\leftarrow\mathcal{I}\cup I_{i,j,k}$

20: end for

21: end for

22:end for

23:$\bar{I}\leftarrow$ Average($\mathcal{I}$)

24:$\bar{I}$

25:function Distribution($\phi$, $\theta$, $g$)

26: Initialize set of reward $\mathcal{R}\leftarrow\\{\\}$

27: for i=1:g do

28: Game between $\phi$ and $\theta$ to collect reward $r$

29: $\mathcal{R}\leftarrow\mathcal{R}\cup r$

30: end for

31: $P_{R|\vartheta=\theta,\varphi=\phi}\leftarrow$ Histogram($\mathcal{R}$)

32: return $P_{R|\vartheta=\theta,\varphi=\phi}$

33:end function

###  4.1. Level of Influence

In order to quantitatively describe the interaction intensity between each
agent in a certain _scenario_ as its intrinsic property, we take inspiration
from causal influence Jaques et al. (2019) and define a new metric named
_Level of Influence_ (LoI). For simplicity, consider a symmetric game with two
agents named Alice and Bob. Alice is the algorithm-controlled agent (i.e., ego
agent), and Bob can be another algorithm-controlled agent with an unknown
policy or human player (i.e., non-ego agent). We would like to quantify the
expected impact of Bob’s behavior on Alice’s performance within this scenario.

Suppose Alice and Bob are algorithm-controlled agents with policy
$\phi\in\Phi$ and $\theta\in\Theta$, respectively, where $\Phi$ is a policy
class of size $m$ and $\Theta$ is a policy class of size $n$. Alice and Bob
choose their policy following the policy distribution of
$P_{\varphi}(\phi)=\mathbb{P}[\varphi=\phi]$ and
$P_{\vartheta}(\theta)=\mathbb{P}[\vartheta=\theta]$. Let $r\in\mathbb{R}$
denote the total reward of Alice paired with Bob. Under the two-agent game
setting, Alice’s reward is affected by both agents’ policy choices, and the
conditional reward distribution of Alice given Alice’s policy $\varphi=\phi$
and Bob’s policy $\vartheta=\theta$ can be represented as

$P_{R|\vartheta,\varphi}(r|\theta,\phi)=\mathbb{P}[R=r|\vartheta=\theta,\varphi=\phi].$
(2)

Here we use $R$, $\varphi$ and $\vartheta$ to denote the random variable of
$r$ $\phi$, and $\theta$, respectively. We can then get Alice’s marginal
reward distribution as

$P_{R|\varphi}(r|\phi)=\sum_{\theta\in\Theta}P_{R,\vartheta|\varphi}(r,\theta|\phi)=\sum_{\theta\in\Theta}P_{R|\vartheta,\varphi}(r|\theta,\phi)P_{\vartheta|\varphi}(\theta|\phi).$
(3)

The discrepancy between the marginal reward distribution and the conditional
reward distribution is a measure of the interaction level. Intuitively, we
want the LoI to measure the degree to which Alice’s reward distribution
changes induced by Bob’s policy choice, given Alice’s own policy choice.
Therefore, the LoI is defined as the conditional mutual information of Alice’s
reward and Bob’s policy with respect to Alice’s policy:

$\displaystyle I(R;\vartheta|\varphi)$
$\displaystyle=\mathbb{E}_{\varphi}\left[D_{\mathrm{KL}}\left(P_{R,\vartheta|\varphi}\|P_{R|\varphi}P_{\vartheta|\varphi}\right)\right]$
(4a)
$\displaystyle=\sum_{\phi\in\Phi}P_{\varphi}(\phi)D_{\mathrm{KL}}\left(P_{R,\vartheta|\varphi=\phi}\|P_{R|\varphi=\phi}P_{\vartheta|\varphi=\phi}\right)$
(4b)
$\displaystyle=\sum_{\phi\in\Phi}P_{\varphi}(\phi)\mathbb{E}_{\vartheta}\left[D_{\mathrm{KL}}\left(P_{R|\vartheta,\varphi=\phi}\|P_{R|\varphi=\phi}\right)\right]$
(4c)
$\displaystyle=\sum_{\phi\in\Phi}P_{\varphi}(\phi)\sum_{\theta\in\Theta}P_{\vartheta}(\theta)D_{\mathrm{KL}}\left(P_{R|\vartheta=\theta,\varphi=\phi}\|P_{R|\varphi=\phi}\right).$
(4d)

It is worth noting that when $I(R;\vartheta|\varphi)=0$, Alice’s total reward
will not be affected by Bob’s policy choice at all under the given scenario,
thus there is little value for training Alice’s policy with diverse opponent’s
policy. The higher this value becomes, the more significant impact Bob’s
policy will have on Alice’s expected reward; consequently, encountering a more
diverse Bob’s policy when training Alice’s policy can help improve performance
when paired with unseen partners and more training budget is well justified.

(a) Small

(b) Medium

(c) Large

(d) Obstacle

Figure 1. We investigate the influence between agents under ⋆ in the Matrix
game setting across four distinct 2-player scenarios: (a) Small, (b) Medium,
(c) Large, and (d) Obstacle. Brown hollow stars denote the random spawn spots
for both agents. Single-color blocks (cyan and red) denote the fixed resource,
and mixed-color blocks denote the random resource, which can be changed during
each initialization.

###  4.2. Approximation

Since we do not have access to both agents’ full policy space $\Phi$ and
$\Theta$, it is computationally infeasible to calculate the ground truth LoI
following Eq. (4d). We need to approximate the LoI for the given scenario with
a small amount of computational resources. In practice, we train $a+b$ SP
policies, choose $a$ of them as Alice’s policies, and the rest $b$ policies as
Bob’s policies, randomly. Training a convergent SP policy gives us a pool of
checkpoints, including the early-, middle-, and late-stage generations, with
various skill levels and collaborating patterns. We choose $m$ checkpoints
from the late stage of each Alice policy as a group of Alice with slightly
different skills and choose $n$ checkpoints from all stages of each Bob policy
as samples of Bob’s policy distribution. We summarize our LoI calculation in
Algorithm 1.

##  5\. Environments

We adopt DeepMind _Melting Pot_ environment Agapiou et al. (2022) for
evaluation. _Melting Pot_ is a multi-agent RL environment with different
_substrates_ (i.e., physical environment) of zero-sum, shared-reward, and
general-sum games. In our case, we choose the two-agent substrate named “ _⋆
in the Matrix_,” whose mechanism is introduced in Vezhnevets et al. (2019). In
this game, two agents can move around the map, collect $K$ different
resources, and fire “interaction beams.” Each agent has its inventory
$\rho\in\mathbb{R}^{K}$ to track the number of resources of each kind picked
up since the last re-spawn, i.e., $\rho_{i}$ denotes the number of the
$i^{\mathrm{th}}$ type of resources in its inventory. Inventory is only
visible to themselves.

An _interaction_ occurs whenever one agent zaps the other agent with their
interaction beam. The interaction is then resolved by a matrix game with the
payoff matrix $A$ describing the reward corresponding to the pure strategies
of the matrix game available to each agent. Each kind of resource maps one-to-
one to each pure strategy. During the interaction, each agent executes a mixed
strategy depending on the resources they picked up before the interaction. In
particular, an agent with inventory $\rho$ plays the mixed strategy with
weights $\nu=(\nu_{1},\dots,\nu_{K})$, where
$\nu_{i}=\rho_{i}/(\sum_{j=1}^{K}\rho_{j})$. Intuitively, the more resources
of a certain kind are picked up by an agent, the more likely this agent
executes the corresponding strategy of that kind of resource. Formally, during
the interaction, a pure strategy is sampled from each player’s mixed strategy
distribution defined by $\nu$. We represent the sampled strategies of the row
and column players as two one-hot vectors, denoted by
$r_{\mathrm{row}},r_{\mathrm{col}}\in\mathbb{R}^{K}$, respectively. Afterward,
the rewards that the row and column players obtain from the interaction,
denoted by $r_{\mathrm{row}}$ and $r_{\mathrm{col}}$ respectively, are
assigned via

$\displaystyle r_{\mathrm{row}}$
$\displaystyle=\nu_{\mathrm{row}}^{\top}A_{\mathrm{row}}\nu_{\mathrm{col}},$
(5a) $\displaystyle r_{\mathrm{col}}$
$\displaystyle=\nu_{\mathrm{row}}^{\top}A_{\mathrm{col}}\nu_{\mathrm{col}}.$
(5b)

After the interaction, both agents will re-spawn after 5 steps. Each game
lasts for 2000 steps.

Table 1. Payoff matrices $\mathbf{A_{\text{row}}}$ of the two-player ⋆ in the Matrix game. All four games are symmetric with $\mathbf{A_{\text{row}}={A_{\text{col}}}^{\top}}$. Chicken | Pure | Prisoners | Stag
---|---|---|---
Coordination | Dilemma | Hunt
$\begin{pmatrix}3&2\\\ 5&0\end{pmatrix}$ | $\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$ | $\begin{pmatrix}3&0\\\ 5&1\end{pmatrix}$ | $\begin{pmatrix}4&0\\\ 2&2\end{pmatrix}$

By changing the underlying payoff matrix, we are able to change the game
property of the substrate. Therefore, we define four different _environments_
with various game properties, namely _Chicken_ , _Pure Coordination_ ,
_Prisoners Dilemma_ , and _Stag Hunt_ Agapiou et al. (2022) with payoff
matrices defined in Table 1. All four environments are symmetric with 2 types
of resources ($K=2$) and we have
$\mathbf{A}_{\text{row}}={\textbf{A}_{\text{col}}}^{\top}$.

For each environment, we create four different _scenarios_ by changing the
size of the map as well as the layout of the resource and objects inside (see
Figure 1). From _Small_ to _Obstacle_ , the map sizes are $6\times 6$,
$7\times 8$, $9\times 13$, and $9\times 13$, respectively. We anticipate that
different map sizes may lead to varying levels of interaction intensity among
agents. The observation window of each agent is $5\times 5$ square centered at
the agent itself, which means agents in _Small_ is able to observe all the
resource at any spawn location.

##  6\. Experiments Design

We design a series of experiments to validate the effectiveness of using LOI
for cost-efficient generalization and demonstrate a useful application of LoI
in guiding resource allocation for cost-efficient policy training. In
particular, we would like to examine the following hypotheses.

Hypothesis 1. LoI is strongly correlated to the benefits of having diverse co-
player distribution on the generalization of the ego agent within given
scenarios (Section 6.1).

Hypothesis 2. Under the same computation budget, the set of ego agents trained
with LoI-guided resource allocation can achieve higher average performance
than uniform allocation (Section 6.2).

###  6.1. Validating the Level of Influence

As outlined in Section 4.1, our objective is to utilize LoI to predict the
benefits of having diverse co-player distribution during training on the
generalization. To validate this idea, we first evaluate the impact of
different co-player diversities on generalization performance within different
scenarios (Section 6.1.1). We then calculate the LoI of those scenarios
(Section 6.1.2), and find the correlation between the performance improvement
and the LoI conditioned on diversity (Section 6.1.3).

####  6.1.1. Fixed-Bobs Evaluation.

First, we evaluate the impact of different co-player diversities on
generalization performance within different scenarios. we train a set of
policies with different co-player diversities that we want to compare across
all environment-scenario combinations. We then assess these trained policies
against a set of predetermined agents for evaluation. Specifically, we train
one SP policy for 5M steps and save a new checkpoint every 200K steps. We
select four checkpoints at 1.4M, 2.6M, 3.8M, and 5M steps as a fixed group of
policies for evaluation, which we refer to as ” _Fixed-Bobs_ ”.

Afterward, we train 5 instances of SP policies with different random seeds
(SP), one set of PP policies with 3 populations (PP3), and one set of PP
policies with 5 populations (PP5). All policies are trained for 10M steps. We
choose the final checkpoint of each SP and each population of PP (i.e.,
checkpoints at 10M steps) and pair them with the aforementioned Fixed-Bobs.
Each game lasts for 2000 steps and repeats 10 times. We evaluate each training
method and report the average individual reward for each policy by aggregating
results across all 10 games, four Fixed-Bobs policies, and all populations (or
all seeds in the case of SP). To better compare the performance gap between
training methods across different scenarios, we normalize the previous results
by dividing each element by the corresponding reward value from SP of the same
environment and scenario.

(a) Chicken

(b) Pure Coordination

(c) Prisoners Dilemma

(d) Stag Hunt

Figure 2. _Top row:_ Fixed-Bobs evaluation of agents trained by self-play
(SP), population-play $\mathbf{p=3}$ (PP3), population-play $\mathbf{p=5}$
(PP5) across four scenarios: Small (S), Medium (M), Large (L), and Obstacle
(O). Each tile is the average over all populations and seeds (5 seeds for SP)
with 10 independent games between each Alice-Bob combination. _Bottom row:_
Percentage of improvement calculated by dividing each row by its first element
(SP). _Result:_ With a growing population, PP gains larger advantages over SP
in general. However, the percentage of increase varies across different
scenarios under the same environment, and the overall trend of improvement
varies across different environments.

####  6.1.2. LoI Calculation.

Second, we calculate the LoI introduced in Section 4.2 and Algorithm 1 for
each scenario and environment. Specifically, we train 1 Alice policy ($a=1$)
and 5 Bob policies ($b=5$) with different random seeds. We choose 4 late-stage
generations at 3.8M, 4.2M, 4.6M, and 5M steps from Alice’s checkpoint pool
($m=4$) and 9 all-stage generations at 0.2M, 0.6M, 1M, 1.4M, 1.8M, 2.6M, 3.4M,
4.2M, and 5M steps from Bob’s checkpoints pools ($n=9$) of every policy. To
compute the LoI, we model the policy distribution of Alice and Bob as a
uniform distribution defined over their sampled checkpoints (i.e.,
$P_{\varphi}=1/4$ and $P_{\vartheta}=1/9$). We perform 6 games per Alice-Bob
pair ($g=6$).

####  6.1.3. Correlation between LoI and Average Improvement.

We also calculate the average improvement between each training method for
each environment and scenario. Suppose the average individual reward for SP,
PP3, and PP5 are $r_{1}$, $r_{2}$, and $r_{3}$, respectively, then the average
improvement $\delta$ will be calculated as

$\delta=\frac{r_{2}-r_{1}}{2}+\frac{r_{3}-r_{2}}{2}=\frac{r_{3}-r_{1}}{2}.$
(6)

Last, we find the correlation between the aforementioned LoI and average
improvement on four scenarios within each environment. We apply the Pearson
correlation coefficient as the measurement of linear correlation. Suppose the
LoIs of four scenarios on the given environment are $I_{i}$ and the
corresponding average improvements are $\delta_{i}$. Let $\bar{I}$ and
$\bar{\delta}$ denote the mean LoI and mean average improvement over four
scenarios, respectively. The correlation coefficient is then calculated as

$\gamma=\frac{\sum_{i=1}^{4}(I_{i}-\bar{I})(\delta_{i}-\bar{\delta})}{\sqrt{\sum_{i=1}^{4}(I_{i}-\bar{I})^{2}}\sqrt{\sum_{i=1}^{4}(\delta_{i}-\bar{\delta})^{2}}}.$
(7)

Table 2. One-way ANOVA tests on fixed-Bobs evaluation. Each ANOVA is summarized with an F-statistic and a p-value. _Result:_ Reported ANOVAs confirm that SP, PP3, and PP5 have significant effect on individual rewards in all four specified scenarios under four different environments. | Chicken | Pure Coordination | Prisoners Dilemma | Stag Hunt
---|---|---|---|---
Scenario |  F-statistic |  p-value |  F-statistic |  p-value |  F-statistic |  p-value |  F-statistic |  p-value
Small | 8.338 | $3.46\times 10^{-4}$ | 238.9 | $5.19\times 10^{-51}$ | 72.48 | $1.01\times 10^{-23}$ | 97.51 | $2.83\times 10^{-29}$
Medium | 29.03 | $1.25\times 10^{-11}$ | 129.0 | $2.77\times 10^{-35}$ | 288.7 | $1.90\times 10^{-56}$ | 201.0 | $2.83\times 10^{-46}$
Large | 49.55 | $8.16\times 10^{-18}$ | 67.61 | $1.53\times 10^{-22}$ | 75.46 | $1.99\times 10^{-24}$ | 132.2 | $7.40\times 10^{-36}$
Obstacle | 6.115 | $2.70\times 10^{-3}$ | 5.495 | $4.84\times 10^{-3}$ | 43.89 | $3.31\times 10^{-16}$ | 20.80 | $7.72\times 10^{-9}$

###  6.2. Resource Allocation

We can utilize the proposed LoI for allocating training resource allocation
under a limited computation budget. Specifically, we would like to train a set
of policies tailored to manage diverse scenarios within a consistent game
setting, with the total computational resource fixed. Without extra
information, one may distribute resources uniformly across all scenarios. If
we attain LoI that bridges the expected performance improvement with
additional training cost, we can allocate the resource accordingly, i.e.,
train policies with larger populations for scenarios with higher LoI and vice
versa.

To demonstrate the proposed allocation strategy, we set a fixed training
budget of 120M steps for training four policies, each handling a specific
scenario. In the uniform allocation scenario, we train a 3-population PP
policy (PP3) for 10M steps per seed on each scenario, summing up to 120M steps
for all four scenarios. In the resource allocation approach, we calculate the
LoI for each scenario (as outlined in Section 6.1.2) and devise a _heuristic
method_ to allocate resources based on this metric. By default, we allocate
30M steps for each scenario (equivalent to the cost of training PP3 for 10M
steps) and compute the mean LoI across the four scenarios. Scenarios with LoI
greater than one standard deviation from the mean receive 50M steps (cost of
training PP5 for 10M), while those with LoI less than one standard deviation
get 10M steps (cost of training SP for 10M). Adjustments are made for
scenarios with LoI within one standard deviation to maintain the total budget
of 120M steps. For instance, if one scenario uses only 10M steps, the saved
20M steps are reallocated to the scenario with the highest LoI among the
remaining three, and vice versa (see Appendix C for further details).

We apply the Fixed-Bobs evaluation and compare the average normalized
individual reward (see Section 6.1.1) over all four scenarios between uniform
allocation and heuristic allocation.

##  7\. Results

In this section, we report the results and ablation studies of the experiments
introduced in Section 6.

###  7.1. Validating the Level of Influence

####  7.1.1. Fixed-Bobs Evaluation.

The full results of the Fixed-Bobs evaluation are shown in Figure 2. Across
all environments, individual rewards demonstrate an upward trend across
scenarios as the training population size increases. Notably, we can regard SP
as a specialized PP with a population size of 1. The absolute reward values
differ significantly among diverse environments, strongly influenced by the
unique game properties of each environment and the specific payoff matrix
(Figure 2, top row). This suggests that our scenario design gives rise to
varying levels of interaction intensity among agents in all environments.

If we normalize the individual rewards according to Section 6.1.1, we get the
percentage improvement to compare the generation performance between training
methods (Figure 2, bottom row). We can observe that the percentage improvement
with increasing co-player diversity during training differs for each scenario
within a specific environment, and the overall improvement trend varies across
diverse environments.

In _Chicken_ , we note that an increase on population size provides the most
substantial benefit in the Large scenario. However, this advantage is not as
prominent in the Small scenario and diminishes significantly in the Obstacle
scenario. In contrast, larger population size brings the highest improvement
in the Small scenario of _Pure Coordination_ and progressively decreases in
larger scenarios. _Prisoners Dilemma_ and _Stag Hunt_ share a similar trend
where the benefits are particularly prominent in the Medium scenario, compared
to the Obstacle one.

We perform the Analysis of Variance (ANOVA) analysis Edwards (2005) on the
results. The ANOVA method examines whether there are significant differences
in means among two or more groups. We report the $F$-statistic and a
corresponding $p$-value with a null hypothesis that there is no noteworthy
difference (Table 2). We confirm that changing the population size (i.e.,
diversity of co-play agent’s policy distribution) has a statistically
significant effect on the generalization performance within different
scenarios across all four environments. The results also validate that the
significance of the effects varies across different scenarios for a given
environment.

Table 3. LoI (and standard deviations, reported in parentheses) across four scenarios under four environments. Values are calculated over one Alice set ($\mathbf{m=4}$) and five Bob sets ($\mathbf{n=9}$) of different seeds, 10 independent games between each Alice-Bob combination. _Result:_ LoI exhibits varying trends across four specified scenarios in different environments. | Chicken | Pure | Prisoners | Stag
---|---|---|---|---
| Coordination | Dilemma | Hunt
Small | 1.291 (0.14) |  1.117 (0.12) | 1.377 (0.11) | 1.397 (0.14)
Medium | 1.364 (0.09) | 1.071 (0.15) |  1.385 (0.11) |  1.431 (0.13)
Large |  1.438 (0.09) | 0.976 (0.09) | 1.180 (0.09) | 1.424 (0.07)
Obstacle | 1.227 (0.17) | 0.976 (0.18) | 1.100 (0.12) | 1.063 (0.11)

####  7.1.2. LoI Calculation.

We calculate the mean LoI and standard deviation for each scenario and
environment, as detailed in Section 6.1.2. The comprehensive results are
presented in Table 3, with the maximum value in each environment highlighted
in bold. It exhibits varying trends across four scenarios in different
environments. In the _Chicken_ game, the four scenarios exhibit varying LoIs,
with the highest observed in the Large scenario. In the _Pure Coordination_
game, the Large and Obstacle scenarios demonstrate similar LoIs, while the
Small scenario has notably the highest LoI. For the _Prisoner’s Dilemma_ game,
the Small and Medium scenarios show comparable, significantly higher LoI
values compared to the Large and Obstacle scenarios. In the _Stag Hunt_ game,
the Small, Medium, and Large scenarios share similar LoI values, with the
highest in the Medium scenarios, while the Obstacle scenario has a remarkably
low LoI in comparison.

Table 4. Average improvement on individual reward between SP, PP3, and PP5 under each scenario and environment. _Result:_ The advantage of PP over SP varies across different scenarios, and the correlations between scenario and reward increment vary across different environments. | Chicken | Pure | Prisoners | Stag
---|---|---|---|---
| Coordination | Dilemma | Hunt
Small | 1.4130 | 1.7986 | 7.0535 | 5.1652
Medium | 3.8312 | 1.0248 | 9.4688 | 8.0993
Large | 4.9293 | 0.9117 | 3.7931 | 5.2341
Obstacle | 0.0789 | 0.3020 | 3.2389 | 1.9517

####  7.1.3. Correlation between LoI and Average Improvement.

Based on the individual rewards in Figure 2, we calculate the average
improvement following Section 6.1.3. The average improvements obtained are
presented in Table 4, with the highest value in each environment emphasized in
bold. It is evident that the trends in each environment align closely with the
LoI outcomes depicted in Table 3. This observation naturally sets the stage
for the correlation analysis discussed in the subsequent section.

Table 5. Pearson correlation coefficient between average improvement of PP over SP and LoI. _Result:_ It exhibits a strong correlation between the average improvement of PP over SP and LoI under all four environments. | Chicken | Pure | Prisoners | Stag
---|---|---|---|---
| Coordination | Dilemma | Hunt
Statistic | 0.98966 | 0.86309 | 0.93888 | 0.86631

We calculate the correlation coefficient as in Section 6.1.3, and the results
are shown in Table 5. The correlation coefficient ranges from $-1$ to $1$. An
absolute value of $1$ indicates a perfect linear relationship between two
groups, with all data points falling on a line. The results highlight a strong
positive correlation between the average improvement of PP over SP (increasing
population size) and LoI across all four environments. Consequently, we can
utilize LoI as a reference to predict whether implementing a more resource-
intensive training method (e.g., PP with a large population size) will yield a
substantial improvement in generalization over a more cost-effective training
method (e.g., SP or PP with a small population size) in a given scenario. Note
that this correlation is valid within a specific environment. Comparing two
scenarios across different environments is not meaningful in this context,
since the scale of the reward varies across environments.

Table 6. Allocated training resource according to the heuristic method introduced in Section 6.2. Each column adds up to 120M steps. | Chicken | Pure | Prisoners | Stag
---|---|---|---|---
| Coordination | Dilemma | Hunt
Small | 30M | 50M | 30M | 30M
Medium | 30M | 30M | 50M | 50M
Large | 50M | 30M | 30M | 30M
Obstacle | 10M | 10M | 10M | 10M

###  7.2. Resource Allocation

We utilize the LoI values provided in Table 3 for the heuristic method
described in Section 6.2. The allocated training resources for each scenario
are outlined in Table 6. Specifically, 10M, 30M, and 50M training steps
correspond to SP, PP3, and PP5, respectively. The total steps for each
environment sum up to 120M, adhering to the training budget cap.

Figure 3. Fixed-Bobs evaluation comparison of the set of agents trained with
uniformly allocated resource and LoI-guided heuristic allocation. Error bars
correspond to $\mathbf{95\%}$ confidence intervals calculated over all
populations across all four scenarios with 10 independent games between each
Alice-Bob combination. _Result:_ The set of agents trained with LoI-guided
resource allocation achieve higher overall performance under the same total
resource budget cap within all four different environments.

The comparison of Fixed-Bobs evaluation between uniform allocation and LoI-
guided heuristic allocation is depicted in Figure 3. Notably, the heuristic
allocation demonstrates a substantial improvement in the average performance
across all scenarios in the Chicken, Pure Coordination, and Stag Hunt
environments.

We apply the two-sample one-tailed $t$-test Student (1908) for statistical
analysis. It compares the means of two independent groups and determines if
one is significantly larger than the other. We provide the $t$-statistic and a
corresponding $p$-value with a null hypothesis that there is no noteworthy
difference (Table 7). We affirm that LoI-guided heuristic allocation exhibits
a significant advantage over uniform allocation in all scenarios except for
the Prisoners Dilemma, given the same resource budget cap. In conclusion,
leveraging LoI enables us to strategically allocate resources for training a
range of policies designed to handle diverse scenarios, resulting in improved
overall performance within the same resource limit.

Table 7. Two-Sample One-tailed t-Tests on resource allocation comparison. Each test is summarized with an t-statistic and a p-value. _Result:_ Reported tests suggest that except for the Prisoners Dilemma, LoI-guided heuristic allocation have a significant advantage over uniformly allocated case under the same total resource budget cap. Scenario |  t-statistic |  p-value
---|---|---
Chicken | 3.7649 | $1.050\times 10^{-4}$
Pure Coordination | 5.3175 | $1.211\times 10^{-7}$
Prisoners Dilemma | 0.7624 | $2.233\times 10^{-1}$
Stag Hunt | 2.6498 | $4.297\times 10^{-3}$

It’s important to highlight that the earlier discussed heuristic allocation is
based on calculating LoI using checkpoints from 1 Alice policy and 5 Bob
policies, with 5M steps per policy. Consequently, employing this heuristic
resource allocation necessitates an additional 30M steps beyond the 120M steps
budget ($25\%$ of the total budget). In Appendix B.2, we show that, while
augmenting the number of Bobs used in LoI computation significantly reduces
the estimation variance, the proposed heuristic resource allocation scheme is
less sensitive to the estimation noise. We can achieve comparable results as
shown in Figure 3 with LoI values estimated using only 1 Alice policy and 1
Bob policy, which requires only 10M extra training steps ($8.33\%$ of the
total budget). Nevertheless, we expect the estimation variance of LoI will
matter when it comes to guiding resource allocation in more complex
environments or other applications that require a more accurate estimation of
LoI.

##  8\. Discussion

###  8.1. Summary

In our study, we introduce the _Level of Influence_ (LoI) metric, a measure
that quantifies the interaction intensity between agents across varied
scenarios in multi-agent reinforcement learning. Our findings demonstrate that
policies trained with larger population sizes exhibit improved performance
when paired with unseen co-players in highly interactive scenarios. Our
proposed metric can effectively predict the potential generalization
improvement by having a more diverse set of co-player policy distribution
during training.

Our results strongly support the strategic allocation of resources for
training a tailored set of policies across diverse scenarios guided by the LoI
metric. This approach consistently yields higher average performance compared
to uniform allocation across different environments with distinct game
properties within the constraints of a limited computation budget.

###  8.2. Limitations and Future Work

Estimating LoI with self-play policies is susceptible to high variance. LoI
essentially gauges the extent to which Alice’s performance is influenced by
the policy distribution of Bob. We need a diverse set of policies (i.e.,
diverse Bobs) to cover its potential distribution as much as possible in
computing the LoI, while neither self-play nor population-play can guarantee
such diversity to exist under limited training complexity. Thus, a delicate
balance emerges between the expense of LoI estimation and its accuracy.
Although we demonstrate that a high variance in LoI estimation does not
necessarily hinder the effectiveness of the proposed resource allocation
scheme, there may exist other downstream applications of LoI that require LoI
estimation with substantially reduced variance. In future work, we aim to
address this problem by exploring both theoretical grounds and practical
algorithms to generate diversity guaranteed self-play policies with minimal
computation cost Rahman et al. (2023), so that we can accurately estimate LoI
in a sample-efficient manner.

Moreover, while LoI serves as a valuable metric for comparison within a set of
scenarios, it is environment-specific. Consequently, directly comparing the
numerical values of LoI between scenarios from different environments lacks
meaningful interpretation. In future work, we are interested in extending this
idea in a broader context of meta-learning, where cross-environment
comparisons are essential. Subsequent work may include generalizing the LoI
into a comprehensive metric with predefined value ranges and thresholds across
diverse environments.

We are deeply grateful to Jiaxun Cui and Arrasy Rahman for their helpful
discussions and support on this work. We also thank Micah Carroll for the
insightful discussion at the early stage of the project.

## References

  * (1)
  * Agapiou et al. (2022) John P Agapiou, Alexander Sasha Vezhnevets, Edgar A Duéñez-Guzmán, Jayd Matyas, Yiran Mao, Peter Sunehag, Raphael Köster, Udari Madhushani, Kavya Kopparapu, Ramona Comanescu, et al. 2022\.  Melting Pot 2.0.  _arXiv preprint arXiv:2211.13746_ (2022).
  * Agmon and Stone (2012) Noa Agmon and Peter Stone. 2012.  Leading ad hoc agents in joint action settings with multiple teammates.. In _AAMAS_. 341–348.
  * Bard et al. (2020) Nolan Bard, Jakob N Foerster, Sarath Chandar, Neil Burch, Marc Lanctot, H Francis Song, Emilio Parisotto, Vincent Dumoulin, Subhodeep Moitra, Edward Hughes, et al. 2020\.  The hanabi challenge: A new frontier for ai research.  _Artificial Intelligence_ 280 (2020), 103216.
  * Berner et al. (2019) Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. 2019\.  Dota 2 with large scale deep reinforcement learning.  _arXiv preprint arXiv:1912.06680_ (2019).
  * Boutilier (1996) Craig Boutilier. 1996\.  Planning, learning and coordination in multiagent decision processes. In _TARK_ , Vol. 96. Citeseer, 195–210.
  * Bullard et al. (2021) Kalesha Bullard, Douwe Kiela, Franziska Meier, Joelle Pineau, and Jakob Foerster. 2021.  Quasi-equivalence discovery for zero-shot emergent communication.  _arXiv preprint arXiv:2103.08067_ (2021).
  * Bullard et al. (2020) Kalesha Bullard, Franziska Meier, Douwe Kiela, Joelle Pineau, and Jakob Foerster. 2020.  Exploring zero-shot emergent communication in embodied multi-agent populations.  _arXiv preprint arXiv:2010.15896_ (2020).
  * Carroll et al. (2019) Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. 2019.  On the utility of learning about humans for human-ai coordination.  _Advances in neural information processing systems_ 32 (2019).
  * Choudhury et al. (2019) Rohan Choudhury, Gokul Swamy, Dylan Hadfield-Menell, and Anca D Dragan. 2019.  On the utility of model learning in hri. In _2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_. IEEE, 317–325.
  * Dafoe et al. (2020) Allan Dafoe, Edward Hughes, Yoram Bachrach, Tantum Collins, Kevin R McKee, Joel Z Leibo, Kate Larson, and Thore Graepel. 2020\.  Open problems in cooperative AI.  _arXiv preprint arXiv:2012.08630_ (2020).
  * Edwards (2005) Anthony WF Edwards. 2005\.  RA Fischer, statistical methods for research workers, (1925).  In _Landmark writings in western mathematics 1640-1940_. Elsevier, 856–870.
  * Foerster et al. (2018) Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. 2018\.  Counterfactual multi-agent policy gradients. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 32.
  * Fontaine et al. (2021) Matthew C Fontaine, Ya-Chuan Hsu, Yulun Zhang, Bryon Tjanaka, and Stefanos Nikolaidis. 2021.  On the importance of environments in human-robot coordination.  _arXiv preprint arXiv:2106.10853_ (2021).
  * Fuchs et al. (2021) Florian Fuchs, Yunlong Song, Elia Kaufmann, Davide Scaramuzza, and Peter Dürr. 2021.  Super-human performance in gran turismo sport using deep reinforcement learning.  _IEEE Robotics and Automation Letters_ 6, 3 (2021), 4257–4264.
  * Heinrich et al. (2015) Johannes Heinrich, Marc Lanctot, and David Silver. 2015\.  Fictitious self-play in extensive-form games. In _International conference on machine learning_. PMLR, 805–813.
  * Ho et al. (2016) Mark K Ho, James MacGlashan, Amy Greenwald, Michael L Littman, Elizabeth Hilliard, Carl Trimbach, Stephen Brawner, Josh Tenenbaum, Max Kleiman-Weiner, and Joseph L Austerweil. 2016.  Feature-based Joint Planning and Norm Learning in Collaborative Games.. In _CogSci_.
  * Hu et al. (2020) Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. 2020\.  “other-play” for zero-shot coordination. In _International Conference on Machine Learning_. PMLR, 4399–4410.
  * Jaderberg et al. (2019) Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. 2019\.  Human-level performance in 3D multiplayer games with population-based reinforcement learning.  _Science_ 364, 6443 (2019), 859–865.
  * Jaderberg et al. (2017) Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, Iain Dunning, Karen Simonyan, et al. 2017\.  Population based training of neural networks.  _arXiv preprint arXiv:1711.09846_ (2017).
  * Jaques et al. (2019) Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. 2019\.  Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In _International conference on machine learning_. PMLR, 3040–3049.
  * Kleiman-Weiner et al. (2016) Max Kleiman-Weiner, Mark K Ho, Joseph L Austerweil, Michael L Littman, and Joshua B Tenenbaum. 2016\.  Coordinate to cooperate or compete: abstract goals and joint intentions in social interaction. In _CogSci_.
  * Leibo et al. (2021) Joel Z Leibo, Edgar A Dueñez-Guzman, Alexander Vezhnevets, John P Agapiou, Peter Sunehag, Raphael Koster, Jayd Matyas, Charlie Beattie, Igor Mordatch, and Thore Graepel. 2021.  Scalable evaluation of multi-agent reinforcement learning with melting pot. In _International conference on machine learning_. PMLR, 6187–6199.
  * Littman (1994) Michael L Littman. 1994\.  Markov games as a framework for multi-agent reinforcement learning.  In _Machine learning proceedings 1994_. Elsevier, 157–163.
  * Lowe et al. (2020) Ryan Lowe, Abhinav Gupta, Jakob Foerster, Douwe Kiela, and Joelle Pineau. 2020.  On the interaction between supervision and self-play in emergent communication.  _arXiv preprint arXiv:2002.01093_ (2020).
  * Lowe et al. (2017) Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Advances in neural information processing systems_ 30 (2017).
  * McAllister et al. (2022) Rowan McAllister, Blake Wulfe, Jean Mercat, Logan Ellis, Sergey Levine, and Adrien Gaidon. 2022\.  Control-aware prediction objectives for autonomous driving. In _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 01–08.
  * McKee et al. (2020) Kevin R McKee, Ian Gemp, Brian McWilliams, Edgar A Duéñez-Guzmán, Edward Hughes, and Joel Z Leibo. 2020.  Social diversity and social preferences in mixed-motive reinforcement learning.  _arXiv preprint arXiv:2002.02325_ (2020).
  * McKee et al. (2022) Kevin R McKee, Joel Z Leibo, Charlie Beattie, and Richard Everett. 2022.  Quantifying the effects of environment and population diversity in multi-agent reinforcement learning.  _Autonomous Agents and Multi-Agent Systems_ 36, 1 (2022), 21\.
  * Pearl (2013) Judea Pearl. 2013\.  Structural counterfactuals: A brief introduction.  _Cognitive science_ 37, 6 (2013), 977–985.
  * Rahman et al. (2023) Arrasy Rahman, Jiaxun Cui, and Peter Stone. 2023.  Minimum Coverage Sets for Training Robust Ad Hoc Teamwork Agents.  _arXiv preprint arXiv:2308.09595_ (2023).
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ (2017).
  * Shih et al. (2021) Andy Shih, Arjun Sawhney, Jovana Kondic, Stefano Ermon, and Dorsa Sadigh. 2021.  On the critical role of conventions in adaptive human-AI collaboration.  _arXiv preprint arXiv:2104.02871_ (2021).
  * Silver et al. (2018) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. 2018\.  A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play.  _Science_ 362, 6419 (2018), 1140–1144.
  * Silver et al. (2017) David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. 2017\.  Mastering the game of go without human knowledge.  _nature_ 550, 7676 (2017), 354–359.
  * Stone et al. (2010) Peter Stone, Gal Kaminka, Sarit Kraus, and Jeffrey Rosenschein. 2010\.  Ad hoc autonomous agent teams: Collaboration without pre-coordination. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 24. 1504–1509.
  * Stone et al. (2009) Peter Stone, Gal A Kaminka, and Jeffrey S Rosenschein. 2009\.  Leading a best-response teammate in an ad hoc team. In _International Workshop on Agent-Mediated Electronic Commerce_. Springer, 132–146.
  * Strouse et al. (2021) DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett. 2021.  Collaborating with humans without human data.  _Advances in Neural Information Processing Systems_ 34 (2021), 14502–14515.
  * Student (1908) Student. 1908.  The probable error of a mean.  _Biometrika_ 6, 1 (1908), 1–25.
  * Vezhnevets et al. (2019) Alexander Sasha Vezhnevets, Yuhuai Wu, Remi Leblond, and Joel Z Leibo. 2019.  Options as responses: Grounding behavioural hierarchies in multi-agent RL.  _arXiv preprint arXiv:1906.01470_ (2019).
  * Vinyals et al. (2019) Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. 2019\.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ 575, 7782 (2019), 350–354.
  * Zahavy et al. (2023) Tom Zahavy, Vivek Veeriah, Shaobo Hou, Kevin Waugh, Matthew Lai, Edouard Leurent, Nenad Tomasev, Lisa Schut, Demis Hassabis, and Satinder Singh. 2023\.  Diversifying AI: Towards Creative Chess with AlphaZero.  _arXiv preprint arXiv:2308.09175_ (2023).
  * Zha et al. (2021) Daochen Zha, Jingru Xie, Wenye Ma, Sheng Zhang, Xiangru Lian, Xia Hu, and Ji Liu. 2021.  DouZero: Mastering DouDizhu with Self-Play Deep Reinforcement Learning.  arXiv:2106.06135 [cs.AI]

##  Appendix A Training

This section presents the hyperparameters used for training agents. We train
agents on MeltingPot substrates registered in Ray RLLib. We specify one PPO
policy per agent. The hyperparameters are reported in Table 8.

Table 8. Hyperparameters for RLLib PPO policies. Setting | Value
---|---
# rollout workers | 2
rollout fragment length | 100
train batch size | 1600
learning rate | 5e-5
# fully connected layers | (64, 64)
# post fcnet hiddens layers | 256
LSTM size | 256
SGD minibatch size | 128
# SGD iteration | 30
GAE lambda | 1
KL coefficient | 0.2
KL target | 0.01
clip parameter | 0.3
value function clip parameter | 10

##  Appendix B Additional Results

This section presents additional results and statistical analyses supporting
the results in the main text.

###  B.1. Fixed-Bobs Evaluation

A bar plot version of the Figure 2 bottom row is shown in Figure 4. The
numerical values are identical with additional error bars corresponding to
$95\%$ confidence intervals for better comparison. Conclusions are the same as
mentioned in Section 7.1.1.

(a) Chicken

(b) Pure Coordination

(c) Prisoners Dilemma

(d) Stag Hunt

Figure 4. Fixed-Bobs evaluation of agents trained by self-play (SP),
population-play $\mathbf{p=3}$ (PP3), population-play $\mathbf{p=5}$ (PP5)
across four scenarios. Error bars correspond to $\mathbf{95\%}$ confidence
intervals calculated over all populations and seeds (5 seeds for SP) with 10
independent games between each Alice-Bob combination. _Result:_ With a growing
population, PP gains a larger advantage over SP in general. However,
percentage increments vary across different scenarios under the same
environment, and the overall trends of improvement vary across different
environments.

###  B.2. Resource Allocation

In this section, we demonstrate the effect of Bob’s population number on LoI
approximation and resource allocation.

(a) Chicken

(b) Pure Coordination

(c) Prisoners Dilemma

(d) Stag Hunt

Figure 5. Effect of Bob’s population size $b$ on the variance of LoI
approximation. Variance is calculated on 5 individual tests. Result:
Increasing Bob’s population size lowers the LoI estimation variance across all
scenarios and environments.

Following Section 4.2 we estimate LoI by training $a+b$ SP policies with $a=1$
and $b\in\\{1,2,3,4\\}$. For each $b$, we train 5 independent sets of SP
policies (i.e., 5 different sets of $a+b$ SP policies) and compute the LoIs
for each set, respectively. Subsequently, We compute the variance of the
estimated LoIs and report the results in Figure 5.

We can observe that augmenting Bob’s population size leads to a notable
reduction in the variance of LoI estimation. This trend persists across all
scenarios and environments. However, this reduction comes at the expense of
additional computational resources.

Next, we proceed with the resource allocation test outlined in Section 6.2,
comparing the LoI-guided heuristic allocation and uniform allocation using the
previously calculated LoI values. We define _mean advantage_ as the disparity
in average normalized individual rewards between the heuristic and uniform
cases across 5 independent experiments. The results are reported in Figure 6.

Figure 6. Effect of Bob’s population size $b$ on the advantage of LoI-guided
heuristic allocation over uniform allocation. Error bars correspond to
$\mathbf{95\%}$ confidence intervals calculated over 5 independent
comparisons. Result: The increase in Bob’s population size does not impact the
advantage in the average performance of LoI-guided heuristic allocation over
uniform allocation.

It is evident that there is not a distinct correlation between Bob’s
population size used in LoI calculation and the advantage of LoI-guided
heuristic allocation over uniform allocation. (i.e., lower variance in LoI
approximation does not necessarily impact the performance of heuristic
allocation based on that index). As a result, a smaller population size for
LoI estimation can still attain comparable performance in the resource
allocation task using the proposed heuristic method.

##  Appendix C Methods

In this section we present the pseudocode for LoI-guided resource allocation
implementation (Algorithm 2).

Algorithm 2 LoI-guided resource allocation

1:# scenarios $n$, LoIs for given scenarios $I$

2:Get mean LoI across scenarios $\bar{I}\leftarrow\textsc{Mean}(I)$

3:$\sigma\leftarrow\textsc{STD}(I)$

4:$I_{\mathrm{l}}\leftarrow\bar{I}-\sigma$

5:$I_{\mathrm{u}}\leftarrow\bar{I}+\sigma$

6:Initialize set of training method $\mathcal{G}\leftarrow\\{\\}$

7:Initialize count $c\leftarrow 0$

8:for i=1:n do

9: if $I_{i}<I_{\mathrm{l}}$ then

10: $\mathcal{G}\leftarrow\mathcal{G}\cup\mathtt{{}^{\prime}SP^{\prime}}$

11: $c\leftarrow c+1$

12: else if $I_{i}>I_{\mathrm{u}}$ then

13: $\mathcal{G}\leftarrow\mathcal{G}\cup\mathtt{{}^{\prime}PP5^{\prime}}$

14: $c\leftarrow c-1$

15: else

16: $\mathcal{G}\leftarrow\mathcal{G}\cup\mathtt{{}^{\prime}PP3^{\prime}}$

17: end if

18:end for

19:if $c\neq 0$ then$\triangleright$ Adjust methods to keep the total budget

20: if $c>0$ then$\triangleright$ Need more ’PP5’

21: $k\leftarrow\textsc{ArgMax}(\mathcal{G})$

22: $\mathcal{G}_{k}\leftarrow\texttt{'PP5'}$

23: else$\triangleright$ Need more ’SP’

24: $k\leftarrow\textsc{ArgMin}(\mathcal{G})$

25: $\mathcal{G}_{k}\leftarrow\texttt{'SP'}$

26: end if

27:end if

28:$\mathcal{G}$