# Symmetry-Breaking Augmentations for Ad Hoc Teamwork

Ravi Hammond  Dustin Craggs  Mingyu Guo  Jakob Foerster  Ian Reid

###### Abstract

In many collaborative settings, artificial intelligence (AI) agents must be
able to adapt to new teammates that use unknown or previously unobserved
strategies. While often simple for humans, this can be challenging for AI
agents. For example, if an AI agent learns to drive alongside others (a
training set) that only drive on one side of the road, it may struggle to
adapt this experience to coordinate with drivers on the opposite side, even if
their behaviours are simply flipped along the left-right symmetry. To address
this we introduce symmetry-breaking augmentations (SBA), which increases
diversity in the behaviour of training teammates by applying a symmetry-
flipping operation. By learning a best-response to the augmented set of
teammates, our agent is exposed to a wider range of behavioural conventions,
improving performance when deployed with novel teammates. We demonstrate this
experimentally in two settings, and show that our approach improves upon
previous ad hoc teamwork results in the challenging card game Hanabi. We also
propose a general metric for estimating symmetry-dependency amongst a given
set of policies.

Reinforcement Learning, Ad Hoc Teamwork, Multi Agent

##  1 Introduction

Humans and artificial agents alike use a diverse range of conventions when
interacting with one another. These conventions are used to communicate and
coordinate with others, and are crucial for effective teamwork in many multi-
agent settings. They range in complexity from knowing which side of the road
to drive on to coordinating using a shared language. For agents to effectively
coordinate with others, they must develop an understanding of their
conventions, especially when coordination failures can lead to severe
consequences such as vehicle collisions.

Figure 1: Augmenting conventions of other agents. The driver stops at red and
drives on green (top), but with SBA, our agent sees the driver stopping and
starting with many colours (bottom).

This problem of adapting to previously unseen teammates has been formalised as
ad hoc teamwork (AHT) (Stone et al., 2010). One method of training and
evaluating an AHT agent is to use reinforcement learning (RL) to learn a best
response (BR) to a training population of teammates (Fudenberg & Tirole, 1991)
(more formally defined in Section 2.2) and then evaluate against a test set of
held-out agents. The key challenge therefore is generalising to unseen
policies after only being exposed to a subset of possible strategies during
training. Furthermore, due to symmetries, the space of possible conventions is
often combinatorial even in simple environments, making it computationally
challenging to compute best responses even if the population of training
partners was sufficiently large to cover the distribution. Children reduce
this computational burden by transferring existing knowledge to equivalent
symmetries by utilising higher-level reasoning (Beasty, 1987). In contrast,
Chimpanzees have been observed to fail these symmetry tests (Dugdale & Lowe,
2000). AI agents also struggle with this, from computer vision models failing
to generalise to different coloured images (Galstyan et al., 2022), to
cooperative agents that cannot recognise when teammates are using symmetry-
equivalent conventions (Hu et al., 2020).

To address this, we introduce symmetry-breaking augmentations (SBA), a policy
augmentation technique that alters the behaviour of agents in the training
pool by making them break symmetries in different ways. SBA acts as an
operator that can be applied to other agents in an environment, flipping their
behaviours along environmental symmetries. When symmetries are present, this
combinatorially amplifies the range of conventions that the ad hoc agent is
exposed to. Thus, even with a relatively small training population, SBA allows
RL agents to learn to adapt to a much more diverse set of conventions during
training. When deployed, we show that SBA agents exhibit improved performance
when collaborating with previously unseen teammates.

For example, consider a traffic conductor learning to direct drivers.
Initially the conductor is unaware of what colour conventions drivers may use
for stop and go. As shown in Figure 1, SBA can be used to create new training
experiences by altering the observed colours. This prevents the conductor from
over-fitting to the potentially limited conventions of its training partners,
and provides experiences that enable adaptation to different conventions in
the future.

SBA is most effective when the agents in the training population use symmetry-
breaking conventions. For this we introduce the Augmentation Impact (AugImp)
metric, which measures the extent to which a specific augmentation alters
policies within a population. This enables us to analyse a population prior to
training to predict how effective an augmentation will be at improving AHT
performance.

We also introduce a proof-of-concept matrix game to demonstrate how SBA
improves performance in the presence of training partners that use symmetry-
based conventions. We also evaluate SBA in Hanabi (Bard et al., 2020), an
ideal environment for testing AHT adaptability to teammates with a variety of
conventions. In Hanabi, independently trained agents frequently develop
incompatible conventions, even when trained with the same algorithm (Hu et
al., 2020). A successful AHT Hanabi agent needs to quickly infer and adapt to
the conventions of its teammates while not triggering unexpected responses.

SBA amplifies the diversity of conventions agents are exposed to during
training, thus reducing the likelihood of overfitting to certain specific
conventions when the training population does not cover all possibilities. We
experiment by training an AHT agent with existing Hanabi populations of
simplified action decoder (Hu & Foerster, 2019) and independent Q-learning
(Tan, 1993) policies, with training populations of three different sizes each.
We show that in Hanabi, SBA leads to improvements of up to 17% game score when
adapting to previously unseen teammates from the same population.
Additionally, we show that SBA improves performance when generalising outside
of the training distribution to a population of Other Play agents (Hu et al.,
2020).

To summarise, our contributions are:

  * •

SBA, a general method of augmenting a training population for AHT which
amplifies the diversity of conventions the ad hoc agent is exposed to during
training.

  * •

A general metric that measures the effectiveness of policy augmentation
techniques for AHT by measuring how much they diversify behaviours in a
training population.

  * •

Evaluating SBA in Hanabi, and showing that it displays state-of-the-art
performance for AHT.

##  2 Background

###  2.1 Dec-POMDPs

We formalise the cooperative multi-agent setting as a decentralised partially-
observable Markov Decision Process (Dec-POMDP) (Nair et al., 2003). The Dec-
POMDP, $G$, is a 9-tuple
$(\mathcal{N},\mathcal{S},\\{\mathcal{A}^{i}\\}_{i=1}^{n},\\{\mathcal{O}^{i}\\}_{i=1}^{n},\mathcal{T},\mathcal{U},\mathcal{R},T,\gamma)$,
with finite sets
$\mathcal{N},\mathcal{S},\\{\mathcal{A}^{i}\\}_{i=1}^{n},\\{\mathcal{O}^{i}\\}_{i=1}^{n}$,
respectively denoting the set of agents, states, actions, and observations,
where $i$ denotes the set pertaining to agent
$i\in\mathcal{N}=\\{1,\dots,n\\}$. $\mathcal{A}^{i}$ and $\mathcal{O}^{i}$ are
the set of actions and observations for agent $i$, and
$a^{i}\in\mathcal{A}^{i}$ and $o^{i}\in\mathcal{O}^{i}$ are a specific action
and observation that agent $i$ may take and observe. We also write
$\mathcal{A}=\times_{i=1}^{n}A^{i}$ and $\mathcal{O}=\times_{i=1}^{n}O^{i}$,
as the sets of joint actions and observations, respectively.
$s_{t}\in\mathcal{S}$ is the state at time $t$, and $a_{t}\in\mathcal{A}$ is
the joint action of all agents at time $t$, which changes the state according
to the transition distribution $s_{t+1}\sim\mathcal{T}(\cdot|s_{t},a_{t})$.
The subsequent joint observation of the agents, $o_{t+1}\in\mathcal{O}$, is
distributed according to $o_{t+1}=\mathcal{U}(\cdot|s_{t+1},a_{t})$, where
$\mathcal{U}=\times_{i=1}^{n}\mathcal{U}^{i}$. At time $t$, the joint
observation $o_{t}$ is appended to the trajectory
$\tau_{t}=(o_{1},a_{1},\dots,o_{t-1},a_{t-1},o_{t})$, and each agent $i$
individually decides its own action $a_{t}^{i}$ based on its policy
$\pi^{i}(a_{t}^{i}|\tau_{t}^{j})$, which is conditioned on its action-
observation history (AOH)
$\tau_{t}^{i}=(o_{1}^{i},a_{1}^{i},\dots,o_{t-1}^{i}a_{t-1}^{i},o_{t}^{i})$.
$\pi^{i}$ represents agent $i$’s component of the decentralized joint policy
$\pi\in\Pi$, where $\Pi$ is the set of all possible joint-policies in the
environment $G$. When $G$ transitions to state $s_{t+1}$, all agents receive a
common reward $r_{t+1}\in\mathbb{R}$ according to the distribution
$r_{t+1}\sim\mathcal{R}(\cdot|s_{t+1},a_{t})$. The behaviour of a joint-policy
$\pi$ is characterised by the distribution of trajectories $\tau$ it produces,
and, taking into account the time horizon $T$ and discount factor
$\gamma\in[0,1]$, is optimal if it maximises the expected return:

$J(\pi)=\mathbb{E}_{\tau\sim\pi}[\sum_{t=1}^{T}{\gamma^{t-1}r_{t}}].$ (1)

###  2.2 Ad Hoc Teamwork

Ad hoc teamwork (AHT) is the problem of creating an agent that is able to
collaborate effectively with a group of novel teammates. This has been a long-
standing challenge in the field of artificial intelligence (Stone et al.,
2010; Bard et al., 2020).

We use $\pi_{A}$ to represent the AHT agent, and $\pi_{j}$ for the teammate’s
joint-policy. To evaluate the performance of our AHT joint-policy
$\pi_{A}=(\pi_{A}^{1},\dots,\pi_{A}^{n})$ and the teammate joint-policy
$\pi_{j}$, using Equation 1, we obtain the average expected AHT return by
matching each individual component of $\pi_{A}$, i.e. $\pi^{i}_{A}$, with all
other $n-1$ components of $\pi_{j}$, i.e. $\pi^{i}_{j}$. This objective is
formalised by:

$J_{AHT}(\pi_{A},\pi_{j})=\frac{1}{n}\big{(}J(\pi^{1}_{A},\pi^{2}_{j},\dots,\pi^{n}_{j})\\\
+\dots+J(\pi^{1}_{j},\dots,\pi^{n-1}_{j},\pi^{n}_{A})\big{)},$ (2)

A simple approach towards AHT is for the ad hoc agent $\pi_{A}$ to learn a
best-response policy $\pi_{A}^{*}$ to a training set $\Pi^{train}\in\Pi$ by
interacting with each policy $\pi_{j}\in\Pi^{train}$, and maximising Equation
2. We formally define this objective as:

$\pi_{A}^{*}(\Pi^{train})=\underset{\pi_{A}}{\text{argmax}}~{}\mathbb{E}_{\pi_{j}\sim\Pi^{train}}[J_{AHT}(\pi_{A},\pi_{j})],$
(3)

where $\pi_{j}$ is sampled uniformly from $\Pi^{train}$. The learned AHT
policy, $\pi_{A}^{*}(\Pi^{train})$, is then evaluated using the robustness
measure, $M_{\Pi^{eval}}(\pi_{A}^{*}(\Pi^{train}))$, which evaluates Equation
2 while interacting with previously unseen policies from the evaluation policy
set $\Pi^{eval}\in\Pi$. This measure is formally given by:

$M_{\Pi^{eval}}(\pi_{A}^{*}(\Pi^{train}))=\\\
\mathbb{E}_{\pi_{j}\sim\Pi^{eval}}J_{AHT}(\pi_{A}^{*}(\Pi^{train}),\pi_{j}),$
(4)

where $\pi_{j}$ is sampled uniformly from $\Pi^{eval}$.

###  2.3 Deep Multi-Agent RL

Deep Multi-Agent RL (MARL) has been successfully applied to a number of Dec-
POMDP settings including Starcraft II (Schroeder de Witt et al., 2019), Hanabi
(Foerster et al., 2019), and negotiation tasks (Zhou et al., 2023). In Hanabi,
our implementation of the SBA algorithm introduced later uses Recurrent Replay
Distributed Deep Q-Networks (R2D2) (Kapturowski et al., 2018) as its network
architecture. Deep Q-Learning (Mnih et al., 2015) is a training regime used in
RL where an agent learns to predict the expected total return
$Q^{*}(\tau_{t}^{i},a_{t}^{i})$ for each action $a_{t}^{i}$, given the action-
observation history $\tau_{t}^{i}$. This is formalised by:

$Q^{*}(\tau_{t}^{i},a_{t}^{i})=\mathbb{E}_{\tau_{t+1}^{i}\sim\pi}[r_{t}+\gamma\underset{a_{t+1}^{i}}{\text{argmax}}Q^{*}(\tau_{t+1}^{i},a_{t+1}^{i})].$
(5)

R2D2, which was state-of-the-art at some point, uses many modern best
practices such as double-DQN (Van Hasselt et al., 2016), dueling network
architecture (Wang et al., 2016), prioritized experience replay (Schaul et
al., 2015), distributed training with parallel environments (Horgan et al.,
2018), and a recurrent network to handle partial observability (Graves, 2012).

The straightforward way of applying Q-Learning to the Dec-POMDP setting is by
using Independent Q-Learning (IQL) (Tan, 1993), where an agent assumes that
all other teammates are a part of the environment, and independently learns to
estimate the expected return without taking any of the other agents actions
into account during the bootstrap process in Equation 5. Past work has
proposed that the Q-function can be learned by sharing neural network weights
$\theta$ for each policy component (Hu et al., 2021), while our AHT agent also
shares network weights, but disregards the transitions experienced by other
agents in the environment.

Figure 2: The $\phi$ operator converts green observations to red (left), and
$\phi^{-1}$ inversely converts red actions back to green (right). In this game
red and green are symmetrically-equivalent, so the application of $\phi$ and
$\phi^{-1}$ leaves the game unchanged up to relabelling.

###  2.4 Equivalence Mappings

To improve coordination with unseen teammates in the Dec-POMDP setting, domain
knowledge can be exploited to prevent agents from using polices that
arbitrarily break symmetries. One such example, other-play (OP) (Hu et al.,
2020), which is a method that we build our work on top of, achieves this by
training agents in self-play (Tesauro, 1994) to maximise expected return while
randomly matched with symmetry-equivalent polices of their training time
partners. The OP learning rule of a joint-policy $\pi$, is formalised by
maximising the following objective:

$\pi^{*}=\underset{\pi}{\text{argmax}}~{}\mathbb{E}_{\phi\sim\Phi}[J(\pi^{1},\phi(\pi^{2})],$
(6)

where $\phi$ is sampled uniformly from $\Phi$, which is the the class of
equivalence mappings (symmetries) for the given Dec-POMDP $G$, such that each
$\phi\in\Phi$ is an automorphism of $\mathcal{S}$, $\mathcal{A}$, and
$\mathcal{O}$ onto itself, and leaves $G$ unchanged up to relabeling. For ease
of notation, $\phi$ is shorthand for

$\phi\in\Phi=\\{\phi_{\mathcal{S}},\phi_{\mathcal{A}},\phi_{\mathcal{O}}\\},$
(7)

where each $\phi\in\Phi$ acts on the action-observation history as

$\phi(\tau_{t})=(\phi(o_{0}),\phi(a_{0}),\dots,\phi(a_{t-1}),\phi(o_{t})),$
(8)

and acts on policies as

$\hat{\pi}=\phi(\pi)\Longleftrightarrow\hat{\pi}(\phi^{-1}(a)|\phi(\tau))=\pi(a|\tau).$
(9)

Policies $\pi$, $\hat{\pi}$ in Equation 9 are said to be symmetry-equivalent
to one another with respect to $\phi$. Illustrated in Figure 2, using $\phi$,
the augmented policy $\hat{\pi}^{i}$ experiences a symmetrically-equivalent
version of $\tau_{t}^{i}$, and its actions are converted back to their
original mapping with $\phi^{-i}$. While OP uses $\phi$ to prevent symmetry-
breaking conventions for ZSC, our work applies $\phi$ to the AHT setting,
improving robustness (Equation 12) by increasing the variety of conventions
present in the training set $\Pi^{train}$.

##  3 Symmetry-Breaking Augmentations

One of the biggest challenges in AHT is predicting the conventions that test-
time policies will use and determining how a training population should be
selected so that its best response is robust to these conventions. In the
following, we introduce SBA, a method that addresses this problem by
augmenting the training population through the random matching of the AHT
agent with symmetry-equivalent policies of training teammates. We will discuss
SBA both as a formal method and as a scalable algorithm-agnostic framework
applicable to the deep RL setting.

###  3.1 SBA Objective

We start by introducing the SBA learning rule which uses the set of
equivalence mappings $\phi\in\Phi$ from Section 2.4 to diversify a training
population $\Pi^{train}$ such that the best-response is robust to a larger
variety of conventions.

The intuitive approach is to apply a different $\phi$ to each teammate
$\pi^{i}_{j}$ to maximise the variety of teams encountered. However, in a
fully-collaborative Dec-POMDP, using different $\phi$’s breaks coordination
between teammates, so the same $\phi$ needs to applied to each $n-1$ component
of $\pi_{j}$. An operation of order $O(n)$. Moreover, if $\pi^{i}_{j}$ is a
physical agent acting in the real world, then $\phi$ can’t even be applied
because we don’t have access to its actions and observations.

Since there exists an inverse $\phi^{-1}\in\Phi$ for each $\phi\in\Phi$,
applying $\phi$ to the AHT agent $\pi_{A}$ is equivalent to applying
$\phi^{-1}$ to $\pi_{j}$, where from $\pi_{A}$’s perspective, the teammate
policy’s conventions are altered in the same way. Consequently, the AHT
expected returns (Equation 2) are equivalent:

$J_{AHT}(\phi(\pi_{A}),\pi_{j})\Longleftrightarrow
J_{AHT}(\pi_{A},\phi^{-1}(\pi_{j})).$ (10)

By applying $\phi$ to $\pi_{A}$, we’re guaranteed to always be able to alter
$\pi_{j}$’s perceived conventions, and its application is of order $O(1)$.
With this, our AHT agent $\pi_{A}$ learns the optimal best-response
($SBA^{*}$) to $\Pi^{train}$ that has been augmented with $\Phi$, by
interacting with each policy $\pi_{j}\in\Pi^{train}$, applying $\phi\in\Phi$
to $\pi_{A}$, and maximising the expected AHT return (Equation 2). We formally
define this objective as:

$\pi_{A}^{*}(\Pi^{train})=\\\
\underset{\pi}{\text{argmax}}~{}\mathbb{E}_{\pi_{j}\sim\Pi^{train},\phi\sim\Phi}[J_{AHT}(\phi(\pi_{A}),\pi_{j})],$
(11)

where $\pi_{j}$ and $\phi$ are uniformly sampled from $\Pi^{train}$ and $\Phi$
respectively. To evaluate the robustness when interacting with an unseen
evaluation set $\Pi^{eval}$, we use the same robustness measure from Equation
12, $M_{\Pi^{eval}}(\pi_{A}^{*}(\Pi^{train}))$, and also apply equivalence
mappings to the evaluation policies to reduce the evaluation variance
(effectively generating a larger test-population). This measure is formally
given by:

$M_{\Pi^{eval}}(\pi_{A}^{*}(\Pi^{train}))=\\\
\mathbb{E}_{\pi_{j}\sim\Pi^{eval},\phi\sim\Phi}J_{AHT}(\phi(\pi_{A}^{*}(\Pi^{train})),\pi_{j}),$
(12)

where $\pi_{j}$ and $\phi$ are sampled uniformly from $\Pi^{eval}$ and $\Phi$.

###  3.2 Algorithm

$s_{t}$$s_{t+1}$$\dots$$s_{t+n-1}$$s_{t+n}$$\pi^{i}_{A}$$\pi^{i+1}_{j}$$\pi^{i+n-1}_{j}$$r_{t}$$r_{t+1}$$r_{t+n-1}$$r_{t+n}$$\phi(\tau_{t}^{i})$$\phi^{-1}(a_{t}^{i})$$\tau_{t+1}^{i+1}$$a_{t+1}^{i+1}$$\tau_{t+n-1}^{i+n-1}$$a_{t+n-1}^{i+n-1}$$r_{t}+\dots+r_{t+n}$,
$\phi(\tau_{t+n}^{i})$

Figure 3: Symmetry-breaking augmentations for an $n$-player Dec-POMDP. The
equivalence map $\phi$ is only applied to the observations and actions of our
AHT agent $\pi_{A}$, not the teammate policy $\pi_{j}$.

The idea behind SBA is simple: As shown in Figure 3, each of the AHT agents
observations $o^{i}_{t}$ are mapped with $\phi$ to an equivalent state with
relabelled symmetries, $\pi^{i}_{A}$ chooses an action $a^{i}_{t}$, and the
action is inversely relabelled with $\phi^{-1}$ before being applied to the
environment. The permuted observations and actions are appended to
$\pi^{i}_{A}$’s AOH $\tau^{i}$, which is used to update the model. Notice that
$\phi$ influences the agent’s actions and observations, not the environment
dynamics, and therefore any RL learning algorithm can be used to update the
model, like DQN (Mnih et al., 2015), DDPG (Lillicrap et al., 2015), A3C (Mnih
et al., 2016), or PPO (Schulman et al., 2017).

In the simplest version of our algorithm, all of the AHT agents transitions,
$\mathbb{T}=(\tau_{t}^{i},a_{t}^{i},r_{t:t+n},\tau_{t+n}^{i})$ are stored,
where $r_{t:t+n}=\sum_{t^{\prime}=t}^{t+n}r_{t^{\prime}}$ is the sum of all
rewards received between time step $t$ and $t+n$, and $\mathbb{T}$ is used to
update the model. See Algorithm 1 for a more formal description.

Algorithm 1 Symmetry-Breaking Augmentations

Input: algorithm $\mathbb{A}$, Dec-POMDP $G$, population $\Pi^{train}$

Initialise: $\mathbb{A}$, equivalence mappings $\Phi$ from $G$

for each episode do

$\pi_{j}\leftarrow$ teammate policy sampled from $\Pi^{train}$

$\phi\leftarrow$ equivalence mapping sampled from $\Phi$

$s_{0},\tau_{0}\leftarrow$ initial state and history

for each step $t$ do

append observation $o_{t}^{i}$ from $s_{t}$ to AOH $\tau_{t}^{i}$

$a_{t}^{i}\leftarrow$ sample action using the policy from $\mathbb{A}$:

$\phi^{-1}(\pi_{A}^{i}(\cdot|\phi(\tau_{t}^{i})))$

append action $a_{t}^{i}$ to AOH $\tau_{t}^{i}$

for each teammate component $\pi_{j}^{-i}$ do

append observation $o_{t}^{-i}$ from $s_{t}$ to AOH $\tau_{t}^{-i}$

$a_{t}^{-i}\leftarrow$ sample action from $\pi_{j}^{-i}(\cdot|\tau_{t}^{-i})$

append action $a_{t}^{-i}$ to AOH $\tau_{t}^{-i}$

end for

take joint-action $a_{t}$, observe $r_{t}$, and $s_{t+1}$

end for

for each AHT agent turn $t$ do

$r_{t:t+n}\leftarrow$ sum rewards from $r_{t}$ to $r_{t+n}$

$\mathbb{T}\leftarrow$ transition
$(\tau_{t}^{i},a_{t}^{i},r_{t:t+n},\tau_{t+n}^{i})$

perform one step of optimisation using $\mathbb{A}$ and $\mathbb{T}$

end for

end for

###  3.3 Augmentation Impact

We aim to increase the diversity of training partners by applying SBA to each
member of the training population, and hypothesize that this will lead to
better generalisation in the AHT setting. However, if the training agents
barely rely on symmetry-based conventions, SBA will have little effect, i.e.
$\phi(\pi_{j})\approx\pi_{j},\forall\pi_{j}\in\Pi^{train},\forall\phi\in\Phi$.

Since training an AHT agent can be expensive, it is useful to quantify how
much SBA will diversify a population prior to training. For this, we introduce
Augmentation Impact (AugImp), a metric that takes a population $\Pi$, a set of
equivalence mappings $\Phi$, and for each pair of policies
$\pi_{1},\pi_{2}\in\Pi$, measures the absolute difference of the crossplay
scores (Lupu et al., 2021) before and after each augmentation $\phi\in\Phi$.
AugImp is formalised by:

$\text{AugImp}(\Pi,\Phi)=\mathbb{E}_{\pi_{1}\sim\Pi,\pi_{2}\sim\Pi,\phi\sim\Phi}[\\\
|J_{\text{XP}}(\pi_{1},\pi_{2})-J_{\text{XP}}(\phi(\pi_{1}),\pi_{2})|],$ (13)

where $\pi_{1},\pi_{2}$, and $\phi$ are uniformly sampled from $\Pi$ and
$\phi$ respectively. The bigger the AugImp score, the more $\Pi$ is
diversified by $\Phi$, and the better effect that SBA will have when training
an AHT agent with that population.

##  4 Iterated Lever Game Experiments

We first test SBA in a simple fully cooperative environment where agents are
tasked to coordinate by pulling one of ten possible levers. As shown in Figure
4, a reward of $1$ is paid out if both players pick the same lever, otherwise
they get nothing. The game is played twice, but in the second round the
players are able to see what lever their partner previously pulled. If agents
could coordinate beforehand they would always pull the same lever, but when
playing with an unknown teammate there is no way to coordinate on the first
round. To apply SBA to the lever game, since a permutation of the levers
leaves the game unchanged, we use this as our class of symmetries.

$t=0$$t=1$1.01.01.01.01.01.01.01.01.01.01.01.0p11.01.01.01.0p21.01.01.01.0

Figure 4: In the iterated lever coordination game agents can see what actions
were previously taken. The game highlights the difficulty of adapting to
conventions not seen during training.

We train our AHT agent with a population of five different teammates that each
deterministically pull one of the levers, and evaluate with ten policies that
pull all ten levers. We refer to Appendix A for more details on the
implementation. The code is available online without downloading:
https://bit.ly/lever-game-sba.

Figure 5: Training curves for the iterated lever coordination game. Shown is
the mean, shading is the standard error of the mean, across $30$ different
seeds. SBA improves test performance because it exposes the agent to more
conventions during training.

The results are shown in Figure 5, where, as expected, all agents randomly
choose a lever in the first round. In the second round, during training the
baseline (BR) always successfully switches to the correct lever for a return
of $1.2$, but only scores $0.6$ at test time because it doesn’t expect the
other five levers to be pulled. Our SBA agent, however, experiences all levers
during training, so is able to adapt to all teammates for a total score of
$1.1$ in both training and testing.

##  5 Hanabi Experiments

We now test SBA in the more complex environment of Hanabi. Hanabi is a fully-
cooperative, partially-observable board game that has become a popular
benchmark (Bard et al., 2020) for MARL, theory of mind, and AHT research.

In Hanabi, each card has one of five colours and a number from one to five (a
“rank”). Players aim to stack these cards by colour in ascending order of rank
by playing cards from their hand. The twist is that players cannot observe
their own hands. Only your teammates can observe your hand, and they must
share information with you to inform your decisions. If a player attempts to
play a card that cannot contribute to any of the ordered stacks, a bomb is
triggered. Players ”bomb out” after three bombs are triggered, losing the game
and receiving a score of 0. Otherwise, the final score is the number of cards
successfully played, at most 25. Communication is restricted, making
conventions essential to consistently achieve a high score and avoid bombouts.

###  5.1 Teammate Selection

Before training our agent, a teammate policy population needs to be selected.
Since there exists a range of pre-trained Hanabi agent populations online, we
use AugImp (Equation 13) to guide the selection. We analyse the AugImp scores
for four populations: 13 simplified action decoder (SAD), 12 independent
Q-learning (IQL), 12 other-play (OP) models, and 5 off-belief learning (OBL)
models (pre-trained weights for these models are available on
GitHub111https://github.com/facebookresearch/hanabi_SAD222https://github.com/facebookresearch/off-
belief-learning).

Figure 6: Augmentation Impact (AugImp) for Hanabi populations. SAD and IQL
populations have a larger AugImp than OP and OBL, because they contain
policies with more symmetry-breaking conventions.

To calculate the crossplay scores for each pair of policies $\pi_{1}$ and
$\pi_{2}$ and each augmentation $\phi$, we take the mean score over 1000
games. Figure 6 shows the AugImp scores for each population. The scores for
SAD and IQL are much larger than OP and OBL, which is expected because OP and
OBL are designed to use conventions that don’t break symmetries. For a
complete breakdown of the AugImp score distributions for each policy pairing,
see Appendix B. Since SBA increases the diversity of SAD and IQL, we use these
populations for training because we expect the largest AHT performance
improvement.

###  5.2 Experiment Setup

SBA can be used to augment a training population for any AHT algorithm as long
as known symmetries exist within the environment and can be applied to the
data. In Hanabi, we implement SBA on top of independent Q-learning (IQL),
which has also been used as the foundation for other works that have
previously achieved SOTA performance in selfplay and crossplay (Hu & Foerster,
2019; Hu et al., 2020, 2021). Our implementation is based on the open-source
code for OBL2, which uses the R2D2 network (Kapturowski et al., 2018), and we
have extended to support training best response agents for AHT. See Appendix
C.1 for more details on the implementation.

###  5.3 Best response agents

We train AHT agents using the pre-trained SAD and IQL populations, and
evaluate their ad hoc generalisation to held-out partners. We create a number
of testing and training splits for each population (similarly to Muglich et
al. (2022b)). Each population is randomly divided into small, medium, or large
training/test splits: small splits have 1 training policy, medium splits have
6, and large training sets contain all but 2 policies from the population. The
remaining policies form the test set for that split. Smaller split sizes are
more challenging, as our AHT agents are exposed to a more limited set of
partners during training. We randomly sample 10 different partitions for
medium and large training sets, and run all possible partitions for small (13
for SAD and 12 for IQL). See Appendix C.2 for details on train-test splits.

###  5.4 Ad Hoc Teamwork Results

Here we examine the impact of SBA on AHT performance to the held-out test
agents for SAD and IQL. For each of the train/test splits outlined above, we
train a standard best response with and without SBA. Each agent is evaluated
on the held out test agents from its training split.

Train Size Agent SAD $\uparrow$ IQL $\uparrow$ small BR 8.15 $\pm$ 1.28 11.52
$\pm$ 1.08 SBA (ours) 9.12 $\pm$ 1.42 11.84 $\pm$ 0.99 medium Gen. Belief
12.47 $\pm$ 1.02 - BR 13.09 $\pm$ 0.49 15.04 $\pm$ 0.37 SBA (ours) 15.40 $\pm$
0.49 16.08 $\pm$ 0.42 large BR 14.69 $\pm$ 1.05 15.34 $\pm$ 0.80 SBA (ours)
16.34 $\pm$ 1.29 15.95 $\pm$ 0.71

Table 1: SBA performance in Hanabi for small, medium, and large training set
sizes. The reported score for generalized beliefs (Gen. Belief) on the SAD
medium split size. Shown is the standard error of the mean (s.e.m) across the
small, medium, and large training train-test splits respectively. The maximum
score in Hanabi is 25.

Table 1 outlines the mean performance for each of the populations and split
sizes. In all cases, SBA improves performance over the baseline. For the
medium SAD splits we also compare to the best result for this population from
Generalized Beliefs (see Section 6.1) (Muglich et al., 2022b). Our method
improves upon this previous state-of-the-art by an average of 2.93
points333Our baseline (BR) also outperforms Generalised Beliefs because we
base our work on the newer and more fine-tuned OBL implementation..

We perform two-tailed Monte Carlo permutation tests (Dwass, 1957) to estimate
whether there is a statistically significant difference between the baseline
and SBA. For medium and large split sizes, we find that SBA confers a
statistically significant advantage over the baseline to the level
$\alpha=0.01$. For small split sizes, we find that the improvement is
statistically significant to the level $\alpha=0.05$. This shows that applying
SBA while training an AHT agent in this context consistently improves
performance, making it essential for AHT when symmetry-based conventions exist
within the training population.

Figure 7: Frequency of the hint colour action played. SBA hints colours less
often when the training set uses symmetry breaking conventions.

We also examine the effect of SBA when applied to OP agents. We train baseline
and SBA agents on medium OP train/test splits. Intuitively, OP trains agents
to be equivariant under symmetries which should render SBA ineffective.
Indeed, the baseline agents achieve an average score of 19.27 $\pm$ 0.42 with
the held-out partners, while our SBA agents score 19.39 $\pm$ 0.42. We find
that this difference is not statistically significant, indicating that SBA
does not degrade performance even when applied to a population with lower
AugImp variance under colour permutation.

To gain insight into why SBA improves performance (whenever it does work!), we
analyse how often each agent gives colour hints (Figure 7). When an SBA agent
is trained with SAD and IQL splits, it hints colours significantly less often
compared to a baseline agent. Due to random symmetry breaking, hinting colours
risks eliciting an unexpected reaction from the teammate, and SBA learns to
avoid this. Instead it learns to use other means of hinting, such as using
rank. When trained with OP, however, given OP’s low AugImp variance (Figure
6), it hints colours roughly as often as the baseline.

###  5.5 Generalisation to Other Populations

Train Set Agent SAD $\uparrow$ IQL $\uparrow$ OP $\uparrow$ OBL $\uparrow$ SAD
BR - 15.22 $\pm$ 0.25 15.69 $\pm$ 0.26 4.51 $\pm$ 0.21 SBA (ours) 16.71 $\pm$
0.22 17.72 $\pm$ 0.26 3.85 $\pm$ 0.16 IQL BR 13.23 $\pm$ 0.15 - 15.71 $\pm$
0.24 5.73 $\pm$ 0.24 SBA (ours) 13.70 $\pm$ 0.19 16.42 $\pm$ 0.16 5.50 $\pm$
0.20

Table 2: Symmetry-Breaking Conventions performance in Hanabi for medium,
training set sizes, cooperating with out-of-distribution populations. Shown is
the standard error of the mean (s.e.m) across 13, 10, and 10 training splits
respectively.

The previous experiment examines how SBA affects generalisation to held-out
teammates from the same population as those used for training (either SAD or
IQL). Here, we investigate whether SBA is effective at creating policies that
can transfer to entirely different populations. We take the medium split size
agents from the previous experiment, and evaluate them when paired with
teammates from these different populations.

Table 2 outlines our results. SBA agents trained on SAD exhibit improved
transfer performance to the IQL and OP populations. Applying the same
significance testing as in the previous experiment, we find that these results
are significant to the level $\alpha=0.01$. Similarly for agents trained with
IQL partners, we find that SBA confers a statistically significant advantage
when playing with OP agents (to the level $\alpha=0.05$). Additional results
with all split sizes and OP-trained SBA and baseline agents are available in
Appendix D.

We also see that SBA can harm performance when transferring to the OBL
population. For SBA agents trained with SAD, we find this detrimental effect
to be statistically significant to the level $\alpha=0.01$. OBL policies
require explicit colour information approximately $65\%$ of the time for cards
that they play (Hu et al., 2021), and thus rely on colour hints. SBA agents
exhibit much lower frequency of providing these colour hints to the partner
(Figure 7). We hypothesize that this is one of the main reasons why SBA harms
performance in this case.

##  6 Related Work

###  6.1 Ad hoc Teamwork

There have been a number of works that address the Ad Hoc Teamwork (AHT)
problem. One such technique is Generalised Beliefs that uses belief models to
assist with generalisation (Muglich et al., 2022b). Belief models are used to
provide latent representations of trajectories to a policy model and assist
with search rollouts for action selection. They show that this leads to
improvements in AHT scores in Hanabi. This technique, however, requires an
additional step to train the belief model prior to AHT agent training.

Several approaches achieve generalisation to held-out policies by training a
best response to a diverse population (Lowe et al., 2017; Charakorn et al.,
2020; McKee et al., 2022), often by training this population using an approach
that encourages diversity. Approaches include minimising performance between
policies while maximising individual self-play scores (Charakorn et al., 2022;
Cui et al., 2022; Rahman et al., 2023b) and finding minimum coverage sets that
span the policy space (Rahman et al., 2023a; Lauffer et al., 2023). Canaan et
al. (2022) use hand-crafted rules to find diverse agents that have been
trained using genetic algorithms and Yu et al. (2023) introduce sub-optimal
biases into the reward function. While this ensures diversity in the training
teammates, training large enough populations can be prohibitively expensive
given the range of possible conventions.

###  6.2 Zero-shot Coordination

In zero-shot coordination (ZSC), agents must coordinate with new teammates
that are also optimised for ZSC. Example solution approaches to this problem
address symmetries in conventions by training agents in self-play with
symmetry-equivalent versions of themselves (Hu et al., 2020; Treutlein et al.,
2021), incorporating symmetrization into the network architecture (Muglich et
al., 2022a), or using belief models to find optimal grounded policies that
assume all previous actions were taken by the uniform random policy (Hu et
al., 2021). While these techniques achieve high scores in ZSC, they are
designed to avoid use of specialised conventions, and fail to coordinate with
policies that do use these conventions.

###  6.3 Social Conventions

Like humans who use social conventions to facilitate coordination (Hechter &
Opp, 2001; Lewis, 2008), artificial learning agents are also known to exploit
conventions to cooperate (Airiau et al., 2014). The issue, however, is that in
many collaborative settings there are multiple optimal strategies under self-
play (Tesauro, 1994), but no guarantee that two independently trained agents
will converge to policies with compatible conventions (Foerster et al., 2019;
Hu & Foerster, 2019; Hu et al., 2020).

Solutions have been proposed to encourage learning agents to better converge
to test-time conventions. Such as revealing test-time observations during
training (Lerer & Peysakhovich, 2019), learning with human behavioral-cloned
models to better coordinate with real humans (Carroll et al., 2019),
exploiting the similarity between action and observation features to take
human-like actions (Ma et al., 2023), and by training with teammates that have
hidden biases to better coordinate with sub-optimal humans (Yu et al., 2023).
While interesting directions, these methods make assumptions about what
conventions the test-time policies will use, whereas our approach exploits and
diversifies the conventions that already exist within a training population.

##  7 Conclusion

In this work we have shown that by applying a simple augmentation to the basic
AHT learning framework, which we call symmetry-breaking augmentations, we can
construct agents that are better able to coordinate in the AHT setting with
partners they have not seen before. Our method achieves state-of-the-art
performance when evaluated with a diverse collection of policies that,
especially the case of the SAD policies, were unable to collaborate well in
cross-play due to their high degree of symmetrical conventional
specialization. We have shown that SBA always improves performance, even with
varying sizes of training sets. We have defined SBA generally, shown how to
implement it with deep RL, and shown that through experiments in the
cooperative card game Hanabi, SBA can construct robust agents that can play
well with other artificial agents it has never seen before.

In future work we will investigate how SBA could be utilised in other
algorithmic innovations like search, shuffling symmetries in search rollouts
(Sutton & Barto, 2018) to create a more robust expectation of the teammate
policy’s future actions. We will also apply SBA to a larger variety of Dec-
POMDP’s, such as ones that have disjoint sets of equivalent states and even
agents that observe and act in the real work. Since there exist a large number
of symmetries in the real world, we believe that the key SBA ideas could be
used to augment the experiences of real-world agents.

## Impact Statement

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## References

  * Airiau et al. (2014) Airiau, S., Sen, S., and Villatoro, D.  Emergence of conventions through social learning.  _Autonomous Agents and Multi-Agent Systems_ , 28(5):779–804, 2014.
  * Bard et al. (2020) Bard, N., Foerster, J. N., Chandar, S., Burch, N., Lanctot, M., Song, H. F., Parisotto, E., Dumoulin, V., Moitra, S., Hughes, E., et al.  The hanabi challenge: A new frontier for ai research.  _Artificial Intelligence_ , 280:103216, 2020.
  * Beasty (1987) Beasty, A.  _The role of language in the emergence of equivalence relations: A developmental study._ PhD thesis, University College of North Wales, 1987.
  * Canaan et al. (2022) Canaan, R., Gao, X., Togelius, J., Nealen, A., and Menzel, S.  Generating and adapting to diverse ad-hoc partners in hanabi.  _IEEE Transactions on Games_ , 2022.
  * Carroll et al. (2019) Carroll, M., Shah, R., Ho, M. K., Griffiths, T., Seshia, S., Abbeel, P., and Dragan, A.  On the utility of learning about humans for human-ai coordination.  _Advances in neural information processing systems_ , 32, 2019.
  * Charakorn et al. (2020) Charakorn, R., Manoonpong, P., and Dilokthanakul, N.  Investigating partner diversification methods in cooperative multi-agent deep reinforcement learning.  In _Neural Information Processing: 27th International Conference, ICONIP 2020, Bangkok, Thailand, November 18–22, 2020, Proceedings, Part V 27_ , pp. 395–402. Springer, 2020.
  * Charakorn et al. (2022) Charakorn, R., Manoonpong, P., and Dilokthanakul, N.  Generating diverse cooperative agents by learning incompatible policies.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Cui et al. (2022) Cui, B., Lupu, A., Sokota, S., Hu, H., Wu, D. J., and Foerster, J. N.  Adversarial diversity in hanabi.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Dugdale & Lowe (2000) Dugdale, N. and Lowe, C. F.  Testing for symmetry in the conditional discriminations of language-trained chimpanzees.  _Journal of the experimental analysis of behavior_ , 73(1):5–22, 2000.
  * Dwass (1957) Dwass, M.  Modified randomization tests for nonparametric hypotheses.  _The Annals of Mathematical Statistics_ , pp. 181–187, 1957.
  * Foerster et al. (2019) Foerster, J., Song, F., Hughes, E., Burch, N., Dunning, I., Whiteson, S., Botvinick, M., and Bowling, M.  Bayesian action decoder for deep multi-agent reinforcement learning.  In _International Conference on Machine Learning_ , pp. 1942–1951. PMLR, 2019.
  * Fudenberg & Tirole (1991) Fudenberg, D. and Tirole, J.  _Game theory_.  MIT press, 1991.
  * Galstyan et al. (2022) Galstyan, T., Harutyunyan, H., Khachatrian, H., Steeg, G. V., and Galstyan, A.  Failure modes of domain generalization algorithms.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 19077–19086, 2022.
  * Graves (2012) Graves, A.  Long short-term memory.  _Supervised sequence labelling with recurrent neural networks_ , pp. 37–45, 2012.
  * Hechter & Opp (2001) Hechter, M. and Opp, K.-D.  Social norms.  2001\.
  * Horgan et al. (2018) Horgan, D., Quan, J., Budden, D., Barth-Maron, G., Hessel, M., Van Hasselt, H., and Silver, D.  Distributed prioritized experience replay.  _arXiv preprint arXiv:1803.00933_ , 2018.
  * Hu & Foerster (2019) Hu, H. and Foerster, J. N.  Simplified action decoder for deep multi-agent reinforcement learning.  _arXiv preprint arXiv:1912.02288_ , 2019.
  * Hu et al. (2020) Hu, H., Lerer, A., Peysakhovich, A., and Foerster, J.  “other-play” for zero-shot coordination.  In _International Conference on Machine Learning_ , pp. 4399–4410. PMLR, 2020.
  * Hu et al. (2021) Hu, H., Lerer, A., Cui, B., Pineda, L., Brown, N., and Foerster, J.  Off-belief learning.  In _International Conference on Machine Learning_ , pp. 4369–4379. PMLR, 2021.
  * Kapturowski et al. (2018) Kapturowski, S., Ostrovski, G., Quan, J., Munos, R., and Dabney, W.  Recurrent experience replay in distributed reinforcement learning.  In _International conference on learning representations_ , 2018.
  * Lauffer et al. (2023) Lauffer, N., Shah, A., Carroll, M., Dennis, M. D., and Russell, S.  Who needs to know? minimal knowledge for optimal coordination.  In _International Conference on Machine Learning_ , pp. 18599–18613. PMLR, 2023.
  * Lerer & Peysakhovich (2019) Lerer, A. and Peysakhovich, A.  Learning existing social conventions via observationally augmented self-play.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pp. 107–114, 2019.
  * Lewis (2008) Lewis, D.  _Convention: A philosophical study_.  John Wiley & Sons, 2008.
  * Lillicrap et al. (2015) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Lowe et al. (2017) Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I.  Multi-agent actor-critic for mixed cooperative-competitive environments.  _Advances in neural information processing systems_ , 30, 2017.
  * Lupu et al. (2021) Lupu, A., Cui, B., Hu, H., and Foerster, J.  Trajectory diversity for zero-shot coordination.  In _International Conference on Machine Learning_ , pp. 7204–7213. PMLR, 2021.
  * Ma et al. (2023) Ma, M., Liu, J., Sokota, S., Kleiman-Weiner, M., and Foerster, J. N.  Learning intuitive policies using action features.  In _International Conference on Machine Learning_ , pp. 23358–23372. PMLR, 2023.
  * McKee et al. (2022) McKee, K. R., Leibo, J. Z., Beattie, C., and Everett, R.  Quantifying the effects of environment and population diversity in multi-agent reinforcement learning.  _Autonomous Agents and Multi-Agent Systems_ , 36(1):21, 2022.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pp. 1928–1937. PMLR, 2016.
  * Muglich et al. (2022a) Muglich, D., Witt, C. S. d., van der Pol, E., Whiteson, S., and , J. N. F.  Equivariant networks for zero-shot coordination.  In _NeurIPS 2022_ , November 2022a.
  * Muglich et al. (2022b) Muglich, D., Zintgraf, L. M., De Witt, C. A. S., Whiteson, S., and Foerster, J.  Generalized beliefs for cooperative ai.  In _International Conference on Machine Learning_ , pp. 16062–16082. PMLR, 2022b.
  * Nair et al. (2003) Nair, R., Tambe, M., Yokoo, M., Pynadath, D., and Marsella, S.  Taming decentralized pomdps: Towards efficient policy computation for multiagent settings.  In _IJCAI_ , volume 3, pp. 705–711, 2003.
  * Rahman et al. (2023a) Rahman, A., Cui, J., and Stone, P.  Minimum coverage sets for training robust ad hoc teamwork agents.  _arXiv preprint arXiv:2308.09595_ , 2023a.
  * Rahman et al. (2023b) Rahman, A., Fosong, E., Carlucho, I., and Albrecht, S. V.  Generating teammates for training robust ad hoc teamwork agents via best-response diversity.  _Transactions on Machine Learning Research_ , 2023b.
  * Schaul et al. (2015) Schaul, T., Quan, J., Antonoglou, I., and Silver, D.  Prioritized experience replay.  _arXiv preprint arXiv:1511.05952_ , 2015.
  * Schroeder de Witt et al. (2019) Schroeder de Witt, C., Foerster, J., Farquhar, G., Torr, P., Boehmer, W., and Whiteson, S.  Multi-agent common knowledge reinforcement learning.  _Advances in neural information processing systems_ , 32, 2019.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _arXiv preprint arXiv:1707.06347_ , 2017.
  * Stone et al. (2010) Stone, P., Kaminka, G. A., Kraus, S., and Rosenschein, J. S.  Ad hoc autonomous agent teams: Collaboration without pre-coordination.  In _Twenty-Fourth AAAI Conference on Artificial Intelligence_ , 2010\.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tan (1993) Tan, M.  Multi-agent reinforcement learning: Independent vs. cooperative agents.  In _Proceedings of the tenth international conference on machine learning_ , pp. 330–337, 1993.
  * Tesauro (1994) Tesauro, G.  Td-gammon, a self-teaching backgammon program, achieves master-level play.  _Neural computation_ , 6(2):215–219, 1994.
  * Treutlein et al. (2021) Treutlein, J., Dennis, M., Oesterheld, C., and Foerster, J.  A new formalism, method and open issues for zero-shot coordination.  In _International Conference on Machine Learning_ , pp. 10413–10423. PMLR, 2021.
  * Van Hasselt et al. (2016) Van Hasselt, H., Guez, A., and Silver, D.  Deep reinforcement learning with double q-learning.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 30, 2016.
  * Wang et al. (2016) Wang, Z., Schaul, T., Hessel, M., Hasselt, H., Lanctot, M., and Freitas, N.  Dueling network architectures for deep reinforcement learning.  In _International conference on machine learning_ , pp. 1995–2003. PMLR, 2016.
  * Yu et al. (2023) Yu, C., Gao, J., Liu, W., Xu, B., Tang, H., Yang, J., Wang, Y., and Wu, Y.  Learning zero-shot cooperation with humans, assuming humans are biased.  _arXiv preprint arXiv:2302.01605_ , 2023.
  * Zhou et al. (2023) Zhou, X., Zhu, H., Mathur, L., Zhang, R., Yu, H., Qi, Z., Morency, L.-P., Bisk, Y., Fried, D., Neubig, G., et al.  Sotopia: Interactive evaluation for social intelligence in language agents.  _arXiv preprint arXiv:2310.11667_ , 2023.

##  Appendix A Iterated Lever Coordination Game Details

To emphasise the necessity of augmenting a training policy population with
symmetry-breaking augmentation, we have created the iterated lever-
coordination game. This game underscores the importance of exposing AHT agents
to conventions not initially present in the training population to facilitate
generalisation to a broader range of conventions at test-time. The neural
network employed in this experiment is a basic 2-layer fully connected network
with one hidden layer, utilising the sigmoid function as the activation
function. The training process takes place on a CPU with a single thread. We
present the crucial hyper-parameters in Table 3.

Hyper-parameters | Value
---|---
# Network |
hidden size | 20
activation | sigmoid
layers | 2
# Optimisation |
optimiser | Adam
lr | 0.05
eps | 0.9
batchsize | 10
# Training |
epochs | 1000
num runs | 30
Table 3: Hyper-Paramaters for iterated lever coordination game Reinforcment
Learning.

##  Appendix B Augmentation Impact Breakdown

Training an AHT agent in large Dec-POMDPs can be expensive, so it’s important
to determine whether an augmentation technique will meaningfully diversify a
population before training commences. SBA is a technique that will only change
the policies in the training population if they rely on symmetry-breaking
conventions. Therefore, before training, we can use Augmentation Impact
(AugImp) (Equation 14) to assess how much a given augmentation (in our case,
SBA) will diversify the policies in a population.

The AugImp calculates the absolute difference across all pairs of agents and
across all permutations. This metric combines all the information for a
population into a single value, but the information about the max and min
values is lost. To obtain a more thorough overview of the augmentations, we
examine all Augmentation Differences (AD) individually for each policy pair.
AD represents the Hanabi score difference between two agents from a population
before and after the permutation has been applied to one agent, and it is
defined as:

$AD(\pi_{1},\pi_{2},\phi)=J_{\text{XP}}(\pi_{1},\pi_{2})-J_{\text{XP}}(\phi(\pi_{1}),\pi_{2}).$
(14)

In Figure 8, we can observe the complete breakdown of all Augmentation
Differences (AD) for all four Hanabi populations: SAD, IQL, OP, and OBL. The
plot illustrates how different the augmentation scores are compared to no
augmentation (depicted as a black ’x’). As expected, the plot demonstrates
that SAD and IQL policy populations have a much larger spread than OP and OBL,
with SAD frequently reaching an Augmentation Difference of $\pm$ 8 points.
Interestingly, there exists one IQL pair that works together particularly well
when a specific color permutation is applied.

Figure 8: Augmentation Difference (Equation 14) scores for all pairs of SAD,
IQL, OP, and OBL. Each column of blue contains the score differences between
two policy pairs before and after applying an augmentation. The black x’s
represent the original non-augmented policies. It’s clear that the SBA
diversifies SAD and IQL populations much more than OP and OBL.

##  Appendix C Experiment Details for Hanabi

###  C.1 Reinforcement Learning

We employ a highly scalable training architecture illustrated in Figure 9,
built upon the framework implemented in the Off-Belief Learning Github
Repository (Hu et al., 2021). This architecture features multiple parallel
thread workers responsible for managing interactions across various Hanabi
environments and the agents operating within each environment. Each actor
initiates multiple inference calls to neural networks at every time step, with
each inference call executed on GPUs. When a player initiates an inference
call, the worker thread promptly proceeds to the next agent in the thread,
facilitating the simultaneous execution of multiple games and agents on a
single worker thread. Inferences invoked by different players are batched
together and processed on the GPU in parallel. This approach enables the
concurrent execution of a substantial number of games and environments,
generating a significant volume of data for training purposes.

At each time step, players collect observations, actions, and rewards, and
aggregate them into episodes. These trajectories are padded to 80 time steps
and stored in a priority replay buffer. The training loop, operating
independently of the aforementioned worker threads, continually samples
transitions from the buffer, using them to update the model. After every 10
gradient update steps, the new model synchronizes with all the models
conducting inference on GPUs.

We extended the training architecture to accommodate Ad Hoc Teamwork (AHT)
agents. In each game within every worker thread, one agent acts as our AHT
agent, learning from the experience, while the other agent sends inference
requests to a frozen set of pre-trained neural network weights. Each AHT agent
interacts with a distinct pre-trained model. When agents collect observations,
actions, and rewards for storage in the replay buffer, only the AHT agent’s
experience is used for optimization; teammates’ experiences are discarded. At
the episode’s start, a different policy augmentation permutation is chosen,
maintaining an unchanged teammate in the environment. To ensure an even
distribution of teammate policies, the number of games is selected to
perfectly divide the number of training agents, ensuring experiences are
evenly distributed across teammate policies.

Figure 9: Illustration of RL training setup for AHT using SBA. Some arrows
linking player 1 and batching layer are omitted for legibility. Note that the
experience of the teammates are not stored in the replay buffer, or used to
update the model in the training loop.

The architecture adheres to what was, at one point in time, a state-of-the-art
model—Recurrent Replay Distributed Deep Q-Networks (R2D2) (Kapturowski et al.,
2018)—which incorporates best practices such as double-DQN (Van Hasselt et
al., 2016), dueling network architecture (Wang et al., 2016), prioritized
experience replay (Schaul et al., 2015), distributed training with parallel
environments (Horgan et al., 2018), and a recurrent network to handle partial
observability (Graves, 2012). In all our experiments, we execute games and
players on 23 worker threads, with 80 games per thread, and allocate 1 thread
for training. For inferences, we employ three Nvidia GeForce RTX 3090 GPUs and
one for training, and the worker threads are executed on an AMD Ryzen
Threadripper 1920X 12-Core CPU. Our essential hyper-parameters are detailed in
Table 4.

Hyper-parameters | Value
---|---
# replay buffer related |
burn-in frames | 10,000
replay buffer size | 100,000
priority exponent | 0.9
priority weight | 0.6
max trajectory length | 80
# Optimisation |
optimiser | Adam
lr | 6.25e-05
eps | 1.5e-05
grad clip | 5
batchsize | 128
# Q learning |
n step | 3
discount factor | 0.999
target network sync interval | 2500
exploration $\epsilon$ | $\epsilon_{0}\dots\epsilon_{n},\text{where }\epsilon_{i}=0.1^{1+7_{i}/(n-1)},n=80$
Table 4: Hyper-Paramaters for Hanabi Reinforcment Learning.

###  C.2 Hanabi Training Population Splits

To gain a more accurate understanding of SBA’s performance when learning how
to generalize a held-out sets of evaluation policies, it is useful to observe
how much generalisation is affected by the size of the training set. Since SBA
combinatorially increases the number of partners encountered during training,
a performance improvement should still be observed when there is only one
policy in the training set. As there is a varying number of pre-trained
policies in each population, specifically 13 simplified action decoder (SAD),
12 independent Q-learning (IQL), and 12 other-play (OP), we have different
split sizes for small, medium, and large splits. Table 5 provides the exact
breakdown of these splits.

Population |  small splits |  medium splits |  large splits
---|---|---|---
SAD | 1 train/12 test | 6 train/7 test | 11 train/2 test
IQL | 1 train/11 test | 6 train/6 test | 10 train/2 test
OP | 1 train/11 test | 6 train/6 test | 10 train/2 test
Table 5: Breakdown of the train and test splits we use for Hanabi policy
populations.

##  Appendix D AHT Results

###  D.1 SAD Ad Hoc Teamwork

SAD (eval) w/ IQL w/ OP w/ OBL Split Agent Score $\uparrow$ Bombout
$\downarrow$ Score $\uparrow$ Bombout $\downarrow$ Score $\uparrow$ Bombout
$\downarrow$ Score $\uparrow$ Bombout $\downarrow$ small BR 8.15 $\pm$ 1.28
0.60 $\pm$ 0.03 10.78 $\pm$ 1.34 0.46 $\pm$ 0.06 10.85 $\pm$ 1.50 0.47 $\pm$
0.07 3.77 $\pm$ 0.39 0.70 $\pm$ 0.01 SBA (ours) 9.12 $\pm$ 1.42 0.57 $\pm$
0.03 11.53 $\pm$ 1.39 0.44 $\pm$ 0.06 12.19 $\pm$ 1.59 0.41 $\pm$ 0.07 3.65
$\pm$ 0.34 0.71 $\pm$ 0.01 medium Gen. Belief 12.36 $\pm$ 0.96 - - - - - - -
BR 13.09 $\pm$ 0.49 0.39 $\pm$ 0.04 15.22 $\pm$ 0.25 0.27 $\pm$ 0.01 15.69
$\pm$ 0.26 0.26 $\pm$ 0.01 4.51 $\pm$ 0.21 0.65 $\pm$ 0.01 SBA (ours) 15.40
$\pm$ 0.49 0.28 $\pm$ 0.04 16.71 $\pm$ 0.22 0.20 $\pm$ 0.01 17.72 $\pm$ 0.26
0.17 $\pm$ 0.01 3.85 $\pm$ 0.16 0.70 $\pm$ 0.01 large BR 14.69 $\pm$ 1.05 0.31
$\pm$ 0.05 16.61 $\pm$ 0.12 0.21 $\pm$ 0.01 16.78 $\pm$ 0.22 0.21 $\pm$ 0.01
4.56 $\pm$ 0.22 0.64 $\pm$ 0.02 SBA (ours) 16.34 $\pm$ 1.29 0.24 $\pm$ 0.06
17.40 $\pm$ 0.07 0.17 $\pm$ 0.00 17.81 $\pm$ 0.21 0.16 $\pm$ 0.01 4.36 $\pm$
0.20 0.65 $\pm$ 0.02

Table 6: Mean scores and bombout rates for BR and SBA in Hanabi with a SAD population. Models are trained with 1 train and 12 test policies, 6-7, and 11-2. Compared are the reported 6-7 split scores for Generalized Beliefs (gen. belief) (Muglich et al., 2022b) (gen. belief). Shown is the standard error of the mean (s.e.m) across 13, 10, and 10 training splits respectively. An AHT agent trained on a SAD policies significantly improves performance over the baseline. Splits | SAD (eval) | IQL | OP | OBL
---|---|---|---|---
1-12 | 0.021 | 0.019 | 0.002 | 0.648
6-7 | 0.002 | 0.002 | 0.002 | 0.006
11-2 | 0.002 | 0.002 | 0.002 | 0.438
Table 7: Monte carlo paired permutation test comparing SBA to BR trained on
SAD across different splits, and evaluating with different teammates. 100k
samples are taken. Calculated is the two-sided p-value.

Table 6 showcases the performance results of SBA and baseline (BR) agents,
both trained with SAD training populations of varying sizes: small, medium,
and large. The robustness of each AHT agent is assessed by evaluating them
with a held-out set of SAD agents, while their generalization is tested
through cooperation with three distinct algorithms—namely, IQL, OP, and
OBL—that were absent during training. In addition to the Hanabi scores, the
bombout rate is presented, where lower rates indicate superior performance.
The displayed standard error of the mean reflects the error across the
training splits.

Notably, when the SBA agent is evaluated in coordination with other held-out
SAD agents, as well as agents from IQL and OP populations, there is a
significant improvement in scores across all scenarios. The most substantial
improvement percentage is observed when SBA is trained with a medium-sized
training set, resulting in up to a 17% score improvement. Remarkably, even
when trained with just one agent in the training set, SBA still demonstrates
performance enhancement, highlighting the efficacy of symmetry-breaking
augmentations.

Interestingly, when SAD agents coordinate with OBL policies, the performance
declines. This can be attributed to the fact that, in approximately 60% of
instances, OBL plays a card only when it knows both the color and rank
information. Since SBA tends to provide color hints less frequently, it fails
to furnish OBL with sufficient information, resulting in a reduced frequency
of card plays and, consequently, diminished performance.

In determining statistical significance, we employ a Paired Monte-Carlo
Permutation test, and the corresponding results are presented in Table 7.
Notably, SBA demonstrates a significant performance enhancement when assessed
under SAD, IQL, and OP training policies. Conversely, its performance takes a
noticeable dip when the AHT agent engages with OBL, particularly for medium-
sized training sets. However, for both small and large training sets, the
outcomes remain inconclusive.

###  D.2 IQL Ad Hoc Teamwork

IQL (eval) w/ SAD w/ OP w/ OBL Split Agent Score $\uparrow$ Bombout
$\downarrow$ Score $\uparrow$ Bombout $\downarrow$ Score $\uparrow$ Bombout
$\downarrow$ Score $\uparrow$ Bombout $\downarrow$ 1-11 BR 11.52 ± 1.08 0.41 ±
0.05 8.49 ± 1.19 0.59 ± 0.05 11.52 ± 1.34 0.43 ± 0.06 5.19 ± 0.26 0.58 ± 0.02
SBA (ours) 11.84 ± 0.99 0.40 ± 0.04 8.32 ± 0.96 0.59 ± 0.04 11.91 ± 1.08 0.40
± 0.05 4.13 ± 0.33 0.66 ± 0.03 6-6 BR 15.04 $\pm$ 0.37 0.27 $\pm$ 0.02 13.23
$\pm$ 0.15 0.38 $\pm$ 0.01 15.71 $\pm$ 0.24 0.25 $\pm$ 0.01 5.73 $\pm$ 0.24
0.57 $\pm$ 0.02 SBA (ours) 16.08 $\pm$ 0.42 0.21 $\pm$ 0.02 13.70 $\pm$ 0.19
0.34 $\pm$ 0.01 16.42 $\pm$ 0.16 0.20 $\pm$ 0.01 5.50 $\pm$ 0.20 0.56 $\pm$
0.01 10-2 BR 15.34 ± 0.80 0.25 ± 0.03 13.81 ± 0.11 0.34 ± 0.00 16.06 ± 0.17
0.22 ± 0.01 5.97 ± 0.16 0.54 ± 0.01 SBA (ours) 15.95 $\pm$ 0.71 0.21 $\pm$
0.03 14.08 ± 0.16 0.33 ± 0.01 16.72 $\pm$ 0.11 0.20 $\pm$ 0.01 5.93 ± 0.16
0.55 ± 0.01

Table 8: Mean scores and bombout rates for BR and SBA in Hanabi with a IQL population. Models are trained with 1 train and 12 test policies, 6-7, and 11-2. Shown is the standard error of the mean across 13, 10, and 10 training splits respectively. Splits | IQL (eval) | SAD | OP | OBL
---|---|---|---|---
1-11 | 0.187 | 0.713 | 0.156 | 0.117
6-6 | 0.004 | 0.156 | 0.021 | 0.330
10-2 | 0.004 | 0.235 | 0.031 | 0.284
Table 9: Monte carlo paired permutation test comparing SBA to BR trained on
IQL across different splits, and evaluating with different teammates. 100k
samples are taken. Calculated is the two-sided p-value.

Table 8 presents the performance results of SBA and baseline (BR) agents, both
trained with IQL training populations of varying sizes: small, medium, and
large. The robustness of each AHT agent is assessed by evaluating them with a
held-out set of IQL agents, while their generalization is tested through
cooperation with three distinct algorithms—specifically, SAD, OP, and OBL—that
were absent during training. In addition to the Hanabi scores, the bombout
rate is provided, with lower rates indicating superior performance. The
displayed standard error of the mean reflects the error across the training
splits.

In contrast to when SBA is trained with a SAD population, its performance does
not exhibit the same level of strong improvement when trained with IQL. This
is expected due to the lower Augmentation Impact score it receives (Section
5.1). Nevertheless, this AHT agent still demonstrates statistically
significant performance on an IQL evaluation set for medium and large-sized
training sets, as well as when evaluated with OP policies for medium and large
training sets. However, when SBA is trained with a single IQL training
partner, it never shows statistically significant performance over the
baseline (BR). This is likely because the conventions present in a single IQL
agent are not strong enough for SBA to meaningfully create a diverse training
population.

Furthermore, as shown in Table 9, none of these SBA agents achieve
statistically significant improvements over the baseline when playing with SAD
agents. This is likely attributed to the fact that SAD conventions are much
stronger than IQL, and learning to adapt to IQL conventions alone is not
sufficient to adequately adjust to SAD.

###  D.3 OP Ad Hoc Teamwork

w/ OP (eval) w/ SAD w/ IQL w/ OBL Split Agent Score $\uparrow$ Bombout
$\downarrow$ Score $\uparrow$ Bombout $\downarrow$ Score $\uparrow$ Bombout
$\downarrow$ Score $\uparrow$ Bombout $\downarrow$ 6-6 BR 19.27 $\pm$ 0.42
0.14 $\pm$ 0.02 12.58 $\pm$ 0.18 0.40 $\pm$ 0.01 15.44 $\pm$ 0.07 0.25 $\pm$
0.00 7.27 $\pm$ 0.26 0.54 $\pm$ 0.01 SBA (ours) 19.39 $\pm$ 0.42 0.14 $\pm$
0.02 12.51 $\pm$ 0.24 0.40 $\pm$ 0.01 15.52 $\pm$ 0.13 0.24 $\pm$ 0.01 7.44
$\pm$ 0.39 0.53 $\pm$ 0.02

Table 10: Mean scores and bombout rates for BR and SBA in Hanabi with a OP population. Models are trained with 1 train and 12 test policies, 6-7, and 11-2. Shown is the standard error of the mean (s.e.m) across 13, 10, and 10 training splits respectively. Splits | OP (eval) | SAD | IQL | OBL
---|---|---|---|---
6-6 | 0.164 | 0.641 | 0.408 | 0.629
Table 11: Monte carlo paired permutation test comparing SBA to BR trained on
OP across different splits, and evaluating with different teammates. 100k
samples are taken. Calculated is the two-sided p-value.

Table 10 presents the performance results of both SBA and baseline (BR)
agents, trained with a medium-sized OP training population. The robustness of
each AHT agent is evaluated by assessing them with a held-out set of OP
agents. Generalization is tested by cooperation with three distinct
algorithms—specifically, SAD, IQL, and OBL—that were absent during training.
In addition to the Hanabi scores, the bombout rate is provided, where lower
rates indicate superior performance. The displayed standard error of the mean
(s.e.m) represents the error across the training splits.

Given that an agent trained with Other-Play aims to avoid symmetry-breaking
conventions, as supported by its low Augmentation Impact score in Section 5.1,
augmenting an OP policy with SBA is anticipated to have minimal impact on AHT
performance. The results presented in this section substantiate this
assertion, demonstrating that SBA does not exhibit any performance improvement
over the baseline. In certain cases, due to variance, it even performs
slightly worse than the baseline. This observation is further corroborated by
the Monte-Carlo Permutation Tests in Table 11, where SBA does not show any
significantly improved performance, with $p$-values ranging from 0.16 to 0.6.