# Off-Belief Learning

Hengyuan Hu  Adam Lerer  Brandon Cui  Luis Pineda  David Wu  Noam Brown  Jakob
Foerster

###### Abstract

The standard problem setting in Dec-POMDPs is self-play, where the goal is to
find a set of policies that play optimally together. Policies learned through
self-play may adopt arbitrary conventions and rely on multi-step
counterfactual reasoning based on assumptions about other agents’ actions and
thus fail when paired with humans or independently trained agents. In
contrast, no current methods can learn optimal policies that are fully
grounded, _i.e._ , do not rely on counterfactual information from observing
other agents’ actions. To address this, we present _off-belief learning_
(OBL): at each time step OBL agents assume that all _past actions_ were taken
by a given, fixed policy ($\pi_{0}$), but that _future actions_ will be taken
by an optimal policy under these same assumptions. When $\pi_{0}$ is uniform
random, OBL learns the optimal grounded policy. OBL can be iterated in a
hierarchy, where the optimal policy from one level becomes the input to the
next. This introduces counterfactual reasoning in a controlled manner. Unlike
independent RL which may converge to any equilibrium policy, OBL converges to
a unique policy, making it more suitable for zero-shot coordination. OBL can
be scaled to high-dimensional settings with a _fictitious transition_
mechanism and shows strong performance in both a simple toy-setting and the
benchmark human-AI/zero-shot coordination problem Hanabi.

Machine Learning, ICML

##  1 Introduction

An important goal of multi-agent reinforcement learning (MARL) research is to
develop AI systems that can collaborate with novel partners, such as humans or
other artificial agents unseen at training time. However, the standard problem
setting in cooperative MARL is _self-play_ (SP), where a team of agents is
trained to play well together, without considering performance with other
agents. In SP settings, the goal is to find optimal policies that achieve the
highest scores when all parties follow such policies faithfully. As a result,
a strong policy often relies on efficient, yet arbitrary conventions and
inflexible assumptions that other agents will adhere to their side of the
policy (Foerster et al., 2019).

Although SP agents achieve high scores among themselves, they often fail when
paired with humans because they cannot infer human intentions, and vice versa
(Carroll et al., 2019; Bard et al., 2020; Hu et al., 2020). In imperfect
information settings, agents rely on the actions of others to communicate
information and update their beliefs about unobserved features of the
environment, and expect other agents to do the same, a phenomenon as known as
_counterfactual reasoning_ (Foerster et al., 2019). Agents trained via self-
play implicitly use the policies of the agents they’re trained with to update
their beliefs, which over many cycles of reinforcement learning may be nested
and iterated to arbitrary levels of cognitive depth, leading to highly-
incorrect beliefs and poor outcomes when paired with an agent not sharing a
compatible policy.

By contrast, humans across a wide variety of competitive and collaborative
games are often observed to limit themselves to a cognitive depth of one or
two levels (Camerer et al., 2003), and fewer when other agents are anticipated
to be less experienced (Agranov et al., 2012). When collaborating with unknown
partners for the first time, humans may still successfully communicate by
means of simple factual information sharing, without making fragile inferences
based on their partner’s unknown policy, even while further planning ahead
their own actions effectively and assuming that other players will do the
same. This is a behavior that current methods cannot replicate.

In this paper, we present _off-belief learning_ (OBL), a MARL algorithm that
addresses this problem by controlling the counterfactual reasoning depth,
which prevents the use of arbitrary conventions while allowing for optimal
planning. At the most basic level, OBL agents assume that all past actions
were taken by a given, fixed policy ($\pi_{0}$), but that future actions will
be taken by an optimal policy under these same assumptions. OBL can also be
applied iteratively to obtain a hierarchy of policies that converges to a
unique solution, making it a natural candidate for solving zero-shot
coordination problems.

We first characterize OBL theoretically, showing that unlike SP it converges
to a unique policy, and that it’s an $\epsilon$-policy improvement operator.
We further show that when $\pi_{0}$ doesn’t depend on private information, OBL
will produce a fully _grounded_ policy. We then introduce two algorithms for
computing an OBL policy in complex environments such as Hanabi (Bard et al.,
2020).

We evaluate OBL in both a toy setting and Hanabi. In the toy setting, we
demonstrate that OBL learns the optimal grounded policy while other existing
methods such as SP and k-level reasoning fail to do so. In the Hanabi
experiments, OBL finds fully-grounded policies that reach a score of 20.92 in
SP without relying on conventions, a significant data point for this important
benchmark environment. OBL also performs strongly in zero-shot coordination
settings. It plays well with an agent trained by imitation learning from human
data and two distinct bots trained with reinforcement learning. All of them
are unseen at training time.

##  2 Related Work

This work is inspired by the notion of Cognitive Hierarchies (CH) (Camerer et
al., 2004) and k-level reasoning. CH is a framework for decision-making in
multi-agent settings. Like OBL, CH starts with an ‘uninformative’ level-0
policy and constructs a hierarchy of policies assuming that other agents play
the policies at lower levels. However, in contrast to OBL, CH doesn’t
differentiate between reasoning about other agents’ _past behavior_ and the
expected _future behavior_ of the other agent. In other words, assuming that
$\pi_{0}$ is a uniform random policy, $\pi_{1}$ is simply a _best response_ to
a random player. While this seems like a very reasonable default, it has some
rather drastic consequences. In particular, in many settings it is
_impossible_ for CH to learn optimal grounded policies. The intuition here is
very simple: Only the first CH level, the best response to a random agent,
interprets actions as entirely grounded, _i.e._ , without any counterfactual
reasoning. However, the first level also assumes that the future behavior of
the partner is entirely random, which means it cannot learn strategies that
require the partner to cooperate. One class of behavior that is immediately
affected is _grounded signaling_ , where an agent can reveal information to
another agent through a costly action, as we show in Section 5.

The striking difference between OBL and CH can also be illustrated in fully
observable turn-based settings. While OBL learns the optimal policy at the
first level, CH will in general need as many levels as there are timesteps in
the episode to converge to an optimal policy. Another difference is the role
of $\pi_{0}$: While in CH the exact $\pi_{0}$ can change the final policy
being learned, in OBL only the conditional probabilities (beliefs) induced by
$\pi_{0}$ matter. Therefore, any policy $\pi_{0}$ that ignores the private
observation will result in the same, perfectly uninformative belief and lead
to the same OBL policy $\pi_{1}$.

OBL is conceptually related to the Rational Speech Acts (RSA) framework (Frank
& Goodman, 2012). RSA assumes a speaker-listener setting with grounded hints
and starts out with a _literal listener_ (LL) that only considers the grounded
information provided. Like CH, RSA then introduces a hierarchy of speakers and
listeners, each level defined via Bayesian reasoning (_i.e._ , a best
response) given the level below. Clearly, OBL allows us to train an analogous
hierarchy and thus introduce pragmatic reasoning in a controlled fashion.
However, while RSA is mostly a conceptual framework that is focused on simple
communication tasks, OBL is designed to deal with high-dimensional, complex
Dec-POMDPs in which agents have to both act and communicate through their
actions. The fact that RSA has been able to explain a large amount of human
communication behavior supports the importance of OBL.

There is a large body of work on coordination in the area of behavioral game
theory. One of the most well-known frameworks here are focal points
(Schelling, 1980), _i.e._ , common knowledge labels in the environment that
allow agents to coordinate on a joint action. In contrast to this line of work
we address the _zero-shot coordination_ setting (Hu et al., 2020), where the
structure of the Dec-POMDP itself needs to be used for coordination and
players specifically cannot coordinate on labels.

In this setting _Other-play_ (OP) (Hu et al., 2020) has been proposed as a
method to prevent agents from learning an arbitrary joint policy out of a set
of equivalent but mutually incompatible ones. OP focuses on enforcing
equivariance to symmetries in the DEC-POMDP, which must be provided as an
input to the algorithm. While OP prevents agents from breaking symmetries of
the environment to encode conventions, it does not prevent all counterfactual
convention formation. On the other hand, OBL, by starting from grounded
information, does avoid both symmetry-breaking and counterfactual convention
formation when run with an appropriate $\pi_{0}$, and unlike OP also does not
require those symmetries to be manually identified. Additionally, OBL
specifically addresses how agents _communicate_ information through their
actions, and is tailored for turn-based interactions rather than those with
simultaneous moves. The differences between OP and OBL are highlighted by the
different playing strategies that the OBL and OP bot develop in Hanabi, see
Section 6. OP learns policies that use rank-hints for signalling, while OBL
agents learn more human-compatible, grounded behavior.

##  3 Background

Dec-POMDPs. We consider Dec-POMDP environments $G$ with states $s$, actions
$a$, observation function $\Omega^{i}(s)$ and transition function
$\mathcal{T}(s,a)$. Players receive a common reward $R(s,a)$. We denote the
historical trajectory of states as $\tau$ and action-observation history (AOH)
for player $i$ as $\tau^{i}$:
$\tau_{t}^{i}=(\Omega^{i}(s_{1}),a_{1},...,a_{t-1},\Omega^{i}(s_{t}))$
encoding the trajectory from that player’s point of view. A policy
$\pi^{i}(a|\tau_{t}^{i})$ for player $i$ takes as input an AOH and outputs a
distribution over actions . We denote the joint policy as $\pi$. We remark
that while the value $V^{\pi}(\tau)$ of policy $\pi$ from any state $s$ is
well-defined, the value of playing $\pi$ from an AOH $\tau^{i}$ is not well-
defined unless you specify what policy was played leading to $\tau^{i}$,
because it affects the distribution of world states you may be in at
$\tau^{i}$.

In this work, we restrict ourselves to bounded-length, turn-based Dec-POMDPs.
Formally, we assume that $G$ reaches a terminal state after at most $t_{max}$
steps, and that only a single agent acts at each state $s$ (other agents have
a null action). See Section 4.4 for a discussion of turn-based vs.
simultaneous-action environments.

Deep MARL has been successfully applied in many Dec-POMDP settings (de Witt et
al., 2019; Foerster et al., 2019). The specific OBL algorithm to be introduced
later uses Recurrent Replay Distributed Deep Q-Network (R2D2) (Kapturowski et
al., 2019) as backbone. In Q-learning (Mnih et al., 2015) the agent learns to
predict the expected total return for each action given AOH,
$Q(\tau^{i}_{t},a)=E_{\tau\sim P(\tau|\tau^{i})}R_{t}(\tau)$.
$R_{t}(\tau)=\sum_{t^{\prime}=t}^{\infty}\gamma^{(t^{\prime}-t)}r_{t^{\prime}}$
is the forward looking return from time $t$ where $r_{t^{\prime}}$ is reward
at step $t^{\prime}$ with $a_{t}=a$ and
$a_{t^{\prime}}=\mathop{\mathrm{argmax}}_{a^{\prime}}Q(\tau_{t^{\prime}},a^{\prime})$
for $t^{\prime}>t$ and $\gamma$ is an optional discount factor. The state-of-
the-art R2D2 algorithm incorporates 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., 2016), distributed
training setup with parallel running environments (Horgan et al., 2018) and
recurrent neural network for handling partial observability.

The straightforward way to apply deep Q-learning to Dec-POMDP settings is
Independent Q-Learning (IQL) (Tan, 1993) where each agent treats other agents
as part of the environment and learns an independent estimate of the expected
return without taking other agents’ actions into account in the bootstrap
process. Many methods (Sunehag et al., 2017; Rashid et al., 2018) have been
proposed to learn joint Q-functions to take advantage of the centralized
training and decentralized control structure in Dec-POMDPs. In this work,
however, we use the IQL setup with shared neural network weights $\bm{\theta}$
for simplicity and note that improvements on the RL algorithm used are
orthogonal to our contribution.

Zero-Shot Coordination. The most common problem setting for learning in Dec-
POMDPs is _self-play_ (SP) where a team of agents is trained and tested
together. Optimal SP policies typically rely on _arbitrary conventions_ ,
which the entire team can jointly coordinate on during training. However, many
real-world problems require agents to cooperate with other, unknown AI agents
and humans at test time. This desiderata was formalized as the _Zero-Shot
Coordination_ (ZSC) setting by Hu et al. (2020), where the goal is stated as
finding algorithms that allow agents to coordinate with _independently
trained_ agents at test time. ZSC immediately rules out _arbitrary
conventions_ as optimal solutions and instead requires learning algorithms
that produce robust and, ideally, unique solutions across multiple independent
runs.

##  4 Off-Belief Learning

One of the big challenges for ZSC in partially observable settings is how to
_interpret_ the actions of other agents and to account for how they will
interpret our actions in turn. In the following we will introduce OBL, a
method that allows us to solve this problem by learning optimal _grounded_
policies, which simply do not interpret actions of other agents at all and
assumes other agents will do the same to their actions.

OBL is introduced both as a formal method with corresponding proofs and as a
scalable algorithm based on a _fictitious transition_ mechanism applicable to
the deep RL setting.

###  4.1 Beliefs, Counterfactuals, and the OBL Operator

If a common knowledge policy $\pi_{0}$ is played by all agents up to
$\tau^{i}$, then the agent can compute a belief distribution
$\mathcal{B}_{\pi_{0}}(\tau|\tau^{i})=P(\tau|\tau^{i},\pi_{0})$ conditional on
their AOH. This belief distribution fully characterizes the effect of the
history on the current state, i.e.
$P(\tau|\mathcal{B}_{\pi_{0}},\tau^{i})=P(\tau|\mathcal{B}_{\pi_{0}})$. Notice
that the return for (both players) playing a ‘counterfactual’ policy $\pi_{0}$
to $\tau^{i}$ and $\pi_{1}$ thereafter, which we denote
$V^{\pi_{0}\to\pi_{1}}(\tau^{i})$, is precisely the return of sampling
$\tau\sim\mathcal{B}_{\pi_{0}}(\tau^{i})$ and all players playing $\pi_{1}$
from this trajectory. Therefore we define a counterfactual value function as
follows:

$V^{\pi_{0}\to\pi_{1}}(\tau^{i})=\mathbb{E}_{\tau\sim\mathcal{B}_{\pi_{0}}(\tau^{i})}\left[V^{\pi_{1}}(\tau)\right].$
(1)

We can similarly define counterfactual $Q$ values as

$Q^{\pi_{0}\to\pi_{1}}(a|\tau_{t}^{i})=\sum_{\tau_{t},\tau_{t+1}}R(s_{t},a)\\\
\hskip
56.9055pt+\mathcal{B}_{\pi_{0}}(\tau_{t}|\tau_{t}^{i})\mathcal{T}(\tau_{t+1}|\tau_{t})V^{\pi_{1}}(\tau_{t+1}).$
(2)

$Q^{\pi_{0}\to\pi_{1}}$ is the return from playing $a$ at $\tau^{i}$, assuming
$\pi_{0}$ was played to reach $\tau^{i}$ and $\pi_{1}$ is played subsequently.

The OBL operator maps an initial policy $\pi_{0}$ to a new policy $\pi_{1}$ as
follows:

$\pi_{1}(a|\tau^{i})=\frac{\exp(Q^{\pi_{0}\to\pi_{1}}(a|\tau^{i})/T)}{\sum_{a^{\prime}}\exp(Q^{\pi_{0}\to\pi_{1}}(a^{\prime}|\tau^{i})/T)}$
(3)

for some temperature hyperparameter $T$.

###  4.2 Properties of Off-Belief Learning

######  Theorem 1.

For any $T>0$ and starting policy $\pi_{0}$, OBL computes a unique policy
$\pi_{1}$.

Proof in the Appendix.

######  Corollary 1.

For any $T>0$ and starting policy $\pi_{0}$, $N$ agents independently
computing OBL policies $\\{\pi_{1}^{i}\\}$ and playing their part of it will
achieve the same return as if they had computed a centralized $\pi_{1}$ policy
(zero-shot coordination).

###### Proof.

Since all $\pi_{1}^{i}$ are identical, this follows trivially. ∎

Theorem 1 is trivial in a single-agent context, but illustrates a substantial
departure from traditional multi-agent learning rules, under which
independently computed policies for each agent are typically not unique or
compatible due to the presence of multiple equilibria, a particularly severe
example of which is the formation of ‘arbitrary’ conventions for communication
in a game like Hanabi (Bard et al., 2020).

######  Theorem 2.

For every policy $\pi_{1}$ generated by OBL from $\pi_{0}$, $J(\pi_{1})\geq
J(\pi_{0})-eTt_{max}$, i.e. OBL is a policy improvement operator except for a
term that vanishes as $T\to 0$.

Proof in the Appendix.

Notably, unlike standard MARL, the fixed points of the OBL learning rule are
not guaranteed to be equilibria of the game. However, we have the theorem:

######  Theorem 3.

If repeated application of the OBL policy improvement operator converges to a
fixed point policy $\pi$, then $\pi$ is an $\epsilon$-subgame perfect
equilibrium of the Dec-POMDP, where $\epsilon=et_{max}T$.

Proof in the Appendix.

###  4.3 Optimal Grounded Policies

In multi-agent cooperative settings with imperfect information, the optimal
policy for an agent depends not only on assumptions about the future policy,
but also on counterfactual assumptions about other agents’ policies - i.e.
what does that agents prior action say about the hidden info? Making wrong
assumptions is a source of coordination failure and we thus would like to
consider grounded policies that avoid counterfactual reasoning about partners’
actions altogether.

To do so, we define the grounded belief $\mathcal{B}_{G}$ as the one that
conditions only on the observations but not the partner actions, i.e.

$\mathcal{B}_{G}(\tau|\tau^{i})=\frac{P(\tau)\prod_{t}{P(o_{t}^{i}|\tau)}}{\sum_{\tau^{\prime}}P(\tau^{\prime})\prod_{t}{P(o_{t}^{i}|\tau^{\prime})}}.$

The optimal grounded policy $\pi_{G}$ plays the action that maximizes expected
reward at each AOH $\tau^{i}$ assuming the state distribution at $\tau^{i}$ is
drawn from the grounded beliefs, and assuming that $\pi_{G}$ is played
thereafter.

######  Theorem 4.

Application of OBL with temperature $0$ to any constant policy
$\pi_{0}(a|\tau^{i})=f(a)$ \- or in fact any policy that only conditions on
public state - yields an optimal grounded policy.

While being able to learn the optimal grounded policy is crucial in many
settings, clearly there are some settings where counterfactual reasoning helps
improve performance. In humans this ability is commonly described as _theory
of mind_ and a variety of experimental studies (Camerer et al., 2003; Agranov
et al., 2012; Kleiman-Weiner et al., 2016) have shown that humans typically
carry out a limited number of counterfactual reasoning steps, depending on the
exact setting.

The repeated application of OBL allows us to directly control for the number
of counterfactual reasoning loops to be carried out by our agent. As a crucial
difference to the cognitive hierarchies framework, at each level the agent
plays optimal assuming optimal game play in the future, rather than one level
below. Therefore it is possible to vary the overall _quality_ of the policy
independently of the depth of _counterfactual reasoning_.

Figure 1: Comparison of independent Q learning (left) with LB-OBL (right). In
LB-OBL, the target value for an action $a^{i}_{t}$ is computed by first
sampling a state from a belief model $\hat{B}_{\pi_{0}}$ that assumes
$\pi_{0}$ has been played, and then simulating play (blue) from that state to
$i$’s next turn using the current policy $\pi_{1}$.

###  4.4 Simultaneous-action vs turn-based environments

In section 3 we restricted ourselves to turn-based games in which a single
agent acts at each state. If two players acted simultaneously, then OBL
couldn’t guarantee convergence to a unique policy (Thm 1); for example,
consider a one-step coordination game with payoff matrix $[[1,0],[0,1]]$
(which is a single-state, single-step Dec-POMDP). OBL is identical to self-
play in a one step game, and could thus converge to either equilibrium.

This may seem like a strong restriction of OBL to turn-based games. However,
any simultaneous-action game can be converted to an equivalent stage game by
ordering the simultaneous actions into separate timesteps and only letting
players observe the actions of others once the timesteps corresponding to the
simultaneous actions have completed. An OBL policy can be generated for this
equivalent turn-based game. The ordering of players’ actions solves the
equilibrium selection problem, because the player who acts second assumes that
the other player acted according to $\pi_{0}$. The player order we use to
convert the simultaneous-action game to a turn-based one may change the OBL
policy.

###  4.5 Algorithms for Off-Belief Learning

Equation 3 immediately suggests a simple algorithm for computing an OBL policy
in small tabular environments: compute $\mathcal{B}_{\pi_{0}}(\tau^{i})$ for
each AOH, and then compute $Q^{\pi_{0}\to\pi_{1}}(\tau^{i})$ for each AOH in
‘backwards’ topological order. However, such approaches for POMDPs are
intractable for all but the smallest size problems.

In order to apply value iteration methods, we can write the Bellman equation
for $Q^{\pi_{0}\to\pi_{1}}$ for each agent $i$ as follows:

$\begin{split}&Q^{\pi_{0}\to\pi_{1}}(a_{t}|\tau_{t}^{i})\\\
=~{}&\mathbb{E}_{\tau_{t}\sim\mathcal{B}_{\pi_{0}}(\tau^{i}_{t}),\tau_{t+k}\sim(\mathcal{T},\pi_{1})}\Big{[}\sum_{t^{\prime}=t}^{t+k-1}R(\tau_{t^{\prime}},a_{t^{\prime}})+\\\
&\sum_{a_{t+k}}\pi_{1}(a_{t+k}|\tau_{t+k}^{i})Q^{\pi_{0}\to\pi_{1}}(a_{t+k}|\tau_{t+k}^{i})\Big{]}\end{split}$
(4)

where $\tau_{t+k}$ is the next history at which player $i$ acts and
$\tau_{t+k}\sim(\mathcal{T},\pi_{1})$ denotes that $\tau_{t+k}$ is sampled
from the distribution of successor states where all (other) players play
according to $\pi_{1}$.

Now, how will we perform the Bellman iteration in Eq. 4? One approach, which
we will denote _Q-OBL_ , is to perform independent $Q$ learning where each
player uses $\pi_{0}$ as the exploration policy111In single-agent Q learning,
the optimal policy is independent of the exploration policy, but that’s not
true in MARL.. This would guarantee that
$\tau_{t}\sim\mathcal{B}_{\pi_{0}}(\tau_{t}^{i})$. However in order to compute
the value for playing $\pi_{1}$ in the future, we must simulate the transition
$\tau_{t+k}\sim(\mathcal{T},\pi_{1})$ by having the other players playing
according to their current $\pi_{1}$. This is guaranteed to converge to the
OBL policy (in the tabular case) as long as $\forall\tau^{i}\ \forall a\
\pi_{0}(a|\tau^{i})>0$, by the same inductive argument used in Theorems 1 and
2, since $Q$ and $\pi_{1}$ at each AOH only depend on $Q$ and $\pi_{1}$ at
successor AOHs.

In practice, this approach has a downside: the states reached by $\pi_{1}$ may
be reached with very low probability under $\pi_{0}$,222The bound is
$P(\tau|\pi_{0})/P(\tau|\pi_{1})\geq(\min_{a}P(a))^{t}$ so this procedure will
have low sample efficiency.

Figure 2: Cross-play matrix for each of the different algorithms in the toy
communication game. 10 agents were independently trained with each method;
each cell (i, j) of the matrix represents the average score of the $i$th and
$j$th agent. OBL with a depth of 1 (b) achieves a higher score than CH (e) by
learning optimal grounded communication, while avoiding arbitrary handshakes
that lead to the poor XP performance of SP (a) or deep counterfactual
reasoning (d, g).

Instead, we first learn an approximate belief $\hat{\mathcal{B}}_{\pi_{0}}$
that takes an AOH $\tau^{i}$ and can sample a trajectory from an approximation
of $P(\tau|\tau^{i},\pi_{0})$. We compute this belief model following the
procedure described in Hu et al. (2021). We then perform Q learning with a
modified rule for computing the target value for $Q(a|\tau_{t}^{i})$: we re-
sample a new $\tau^{\prime}$ from $\hat{B}_{\pi_{0}}(\tau_{t}^{i})$, simulate
a transition to $\tau_{t+1}^{i^{\prime}}$ with other agents play their policy
$\pi_{1}$, and use $\max_{a}Q(a|\tau_{t+1}^{i})$ as the target value. We refer
to this variant as Learned-belief OBL (LB-OBL).

An illustration comparing the LB-OBL algorithm with independent Q-learning
(IQL) is shown in Figure 1. In both cases, we assume a two player setting with
shared Q-function and 2-step Q-learning, i.e. $k=2$ in Equation 4. In IQL,
each player simply observes the world at each time-step and takes turns to
act. The target is computed on the actual trajectory with $r_{t}$, $r_{t+1}$
and $\max_{a}Q(a|\tau_{t+2})$ using target network $Q^{i}$. By contrast, LB-
OBL involves extra _fictitious transitions_. For the active player $i$, we
first decide the action $a_{t}^{i}$ given AOH $\tau_{t}^{i}$. However, in
addition to applying $a_{t}^{i}$ to the actual environment state $S_{t}$, we
also apply $a_{t}^{i}$ to a fictitious state $S^{\prime}_{t}$ sampled from the
learned belief model $B_{i}$ and forward the fictitious environment to
$S^{\prime}_{t+1}$. Note that the action $a_{t}^{i}$ can be directly applied
to the fictitious state because the observation from the fictitious state is
the same as that of the real state. Next, we need to evaluate the partner’s
policy to produces a fictitious action $a^{-i\prime}_{t+1}$ on
$\tau^{-i\prime}_{t+1}=[\tau_{-i};\Omega^{-i}(S^{\prime}_{t+1})]$. The
learning target in LB-OBL is the sum of _fictitious_ rewards $r^{\prime}_{t}$,
$r^{\prime}_{t+1}$ and _fictitious_ bootstrapped value
$\max_{a}Q(a|\tau^{\prime}_{t+2})$. We also note that it is not possible to
simply train a Q-learning agent that takes the _grounded beliefs_ as an input.
The agents would still develop conventions and the _grounded belief_ would
simply lose its semantic meaning.

##  5 Experiments in a Toy Environment

Figure 3: Toy cooperative communication game: Alice (left) observes the pet
and can either signal to Bob by turning on the light-bulb, pay 5 to remove the
barrier, so that Bob can see the pet, or bail out for a reward of 1. Bob then
needs to guess the identity of the pet or can bail out for a reward of 0.5.

We first test OBL in a simple fully cooperative toy environment that includes
both a cheap-talk channel and a grounded communication channel: As shown in
Figure 3, Alice observes a random binary variable,
$\text{pet}\in\\{\text{cat},\text{dog}\\}$, and has four possible actions. She
can either turn on the light bulb, bail out of the game with fixed reward of 1
or remove a barrier to let Bob see the pet, which will cost them 5. After
Alice takes her action, Bob observes the outcome and has three options. He can
either bail for a fixed reward of 0.5 or guess the identity of the pet. If the
guess is correct, they obtain an additional $10$, otherwise they lose $10$.

Results. We run three different algorithms on this simple toy game: SP, OBL
and cognitive hierarchies (CH). Figure 2 shows the cross-play (XP) results for
10 independent runs for each of the methods as a matrix, where the entry $i,j$
is the reward obtained from pairing the first agent (Alice) from run $i$ with
the second agent (Bob) from run $j$. As can be seen from the checkerboard-like
pattern, the SP agents learn to use the cheap-talk channel, obtaining $+10$ in
about half the cases and $-10$ in the others. Clearly, these agents have
developed an arbitrary handshake where “on” / “off” correspond to dog / cat or
vice versa, each incompatible with the other half of the agents that made the
opposite choice. In contrast, OBL learns the optimal _grounded policy_ at the
first level, choosing to remove the barrier which results in a reward of $+5$,
both in XP and SP. The CH agents at level 1 learn to simply bail out of the
game, since there is no way to win when playing with a random agent. They also
fail to discover the grounded solution in between and proceed straight to an
arbitrary handshake for higher levels, as is indicated by the $+10/-10$
rewards.

At higher levels, our OBL implementation starts to diverge between different
runs. Although theoretically the OBL policy is unique, some environment states
do not occur very often and the noise is amplified higher up. This could be
addressed with higher temperature or increased regularization if desired. All
results can be reproduced in our notebook implementation
https://bit.ly/3cIia6z.

##  6 Hanabi Experiments

Method | Self-Play | Cross-Play | w/ Other-Play | w/ Other-Play | w/ Clone Bot
---|---|---|---|---|---
(Rank Bot) | (Color Bot)
SAD(*) | 23.97 $\pm$ 0.04 | 2.52 $\pm$ 0.34 | 7.29 $\pm$ 1.40 | 0.18 $\pm$ 0.06 | 0.83 $\pm$ 0.31
Other-Play | 24.14 $\pm$ 0.03 | 21.77 $\pm$ 0.68 | 22.81 $\pm$ 0.87 | 4.05 $\pm$ 0.37 | 8.55 $\pm$ 0.48
K-Level | 16.97 $\pm$ 1.19 | 17.17 $\pm$ 0.98 | 14.80 $\pm$ 1.77 | 12.36 $\pm$ 1.44 | 13.03 $\pm$ 1.91
OBL (level 1) | 20.92 $\pm$ 0.07 | 20.85 $\pm$ 0.03 | 10.83 $\pm$ 0.26 | 13.21 $\pm$ 0.34 | 13.80 $\pm$ 0.19
OBL (level 2) | 23.41 $\pm$ 0.03 | 23.24 $\pm$ 0.03 | 15.99 $\pm$ 0.30 | 18.74 $\pm$ 0.46 | 15.61 $\pm$ 0.10
OBL (level 3) | 23.93 $\pm$ 0.01 | 23.68 $\pm$ 0.05 | 15.61 $\pm$ 0.34 | 20.68 $\pm$ 0.44 | 16.02 $\pm$ 0.26
OBL (level 4) | 24.10 $\pm$ 0.01 | 23.76 $\pm$ 0.06 | 14.46 $\pm$ 0.59 | 21.78 $\pm$ 0.42 | 16.00 $\pm$ 0.13
Table 1: Average scores in 2-player Hanabi for different pairings of agents.
SP indicates play between an agent and itself. XP indicates play between
agents from different independently-trained runs of the same algorithm. The
other columns indicate play with agents from different algorithms. We evaluate
each model on 5000 games and aggregate results of 5 different training runs
(seeds). (*) We use the 12 SAD agents obtained from (Hu et al., 2020) which
uses different network architectures. Thus the numbers are not directly
comparable.

We now test our methods in the more complex domain of Hanabi. Hanabi is a
fully-cooperative multiplayer partially-observable board game. It has become a
popular benchmark environment (Bard et al., 2020) for MARL, theory of mind,
and zero-shot coordination research.

Hanabi is a 2-5 player card game. The deck is composed of 50 cards, split
among five different colors (suits) and ranks, with each color having three
1s, two 2s and 3s and 4s, and one 5. In a 2-player game, each player maintains
a 5-card hand. Players can see their partner’s hand but not their own. The
goal of the team is to play one card of each rank in each color in order from
1 to 5. The team shares 8 hint tokens and 3 life tokens. Taking turns, each
turn a player can play or discard a card in their hand, or spend a hint token
to give a hint to their partner. Playing a card succeeds if it is the lowest-
rank card in its color not yet played, otherwise it fails and loses a life
token. Giving a hint consists of choosing a rank or a color that a partner’s
hand contains and indicating _all_ cards in the partner’s hand sharing that
color or rank. Discarding a card or successfully playing a 5 regains one hint
token. The team’s score is zero if all life tokens are lost, otherwise it is
equal to the number of cards successfully played, giving a maximum possible
score of 25.

Experimental Setup. In Hanabi, we implement LB-OBL using distributed deep
recurrent Q-learning with prioritized experience replay (Kapturowski et al.,
2019). Training consists of a large number of parallel environments that
invoke a deep neural network to approximate the Q function at each time step
to generate trajectories, a prioritized experience replay buffer to store the
trajectories, and a training loop that updates the neural network using
samples from the replay buffer. The queries from different environments are
dynamically batched together to run efficiently on GPUs (Espeholt et al.,
2020). A similar setting was first used in the Hanabi environment by (Hu &
Foerster, 2020). Please refer to appendix for more details and comparisons
against previous implementations.

Our policy (Q-function) is parameterized by a deep recurrent neural network
$\bm{\theta}$. As illustrated in Figure 1, we should sample trajectory $\tau$
from replay buffer and update the neural network with TD-error:

$\mathcal{L}(\bm{\theta}|\tau)=\frac{1}{2}\sum_{t=1}^{T}[r^{\prime}_{t}+r^{\prime}_{t+1}+\max_{a}Q_{\hat{\bm{\theta}}}(a|\tau^{\prime}_{t+2})-Q_{\bm{\theta}}(a_{t}|\tau_{t})]^{2}$
(5)

where $Q_{\hat{\bm{\theta}}}$ is the target network that uses a slightly
outdated version of $\bm{\theta}$ for stability reasons. In normal Q-learning
with RNNs, the target $Q_{\hat{\bm{\theta}}}(a_{t}|\tau_{t})$ for
$t=1,2,\dots,T$ can be re-computed efficiently by passing the sequence $\tau$
to the RNN at once. However, this is no longer feasible in OBL as each
$\tau^{\prime}_{t}$ contains unique fictitious transitions. To solve this
problem, we pre-compute the target
$G^{\prime}_{t}=r^{\prime}_{t}+r^{\prime}_{t+1}+\max_{a}Q_{\hat{\bm{\theta}}}(a|\tau^{\prime}_{t+2})$
during rollouts and store the sequence of $\\{{G^{\prime}_{t}}\\}$ along with
the real trajectory $\tau$ into the replay buffer. Although this might cause
stability issues if the stored target was computed using a very old target
network, in practice we find it to be fairly stable because the replay buffer
gets refreshed quickly thanks to the fast trajectory generation speed of our
training infrastructure. On average, a trajectory is used 4-5 times before it
gets evicted from the buffer.

We set up the belief training following Hu et al. (2021). The belief model is
trained to predict the player’s hand given $\tau^{i}$, which is the only
missing information needed to produce fictitious game states in Hanabi. It
takes as input $\tau^{i}$ and predicts each of the player’s cards auto-
regressively from the oldest to the newest. The belief model is an RNN trained
via supervised learning:

$\mathcal{L}(\bm{h}|\tau^{i}_{t})=-\sum_{k=1}^{n}\log
p(h_{k}|\tau^{i}_{t},h_{1:k-1}),$ (6)

where $h_{k}$ is the $k$th card in hand and $n$ is the hand size.

To compare the zero-shot coordination performance of OBL against previous
methods, we train three categories of policies with existing methods to serve
as the unseen partner for OBL models. “Rank-Bot” is trained with Other-Play.
Empirically, Other-Play in Hanabi consistently converges to using almost only
rank-based conventions to communicate to a partner to play a card, hence the
name. “Color Bot” is roughly the color equivalent of “Rank Bot”, induced by
adding extra reward for hinting color at the early stage of training. “Clone
Bot” is trained with supervised learning on human game data collected from an
online board game platform. When we pair Clone Bot with the Other-Play Bot
under the scoring system used by Hu et al. (2020), it achieves an average
score of $14.98\pm 0.34$, similar to the average score of $15.75$ that the
authors reported for an experiment of humans partnering with Other-Play. This
suggests that Clone Bot is a reasonable proxy for human play.

Similar to the toy example, we implemented a variant of Cognitive Hierarchies
(CH) called k-level reasoning as one of our baselines. The details of neural
network design, hyper-parameters and computation cost of OBL policies and
belief models, as well as those of Rank, Color, Clone Bot and K-Level can be
found in the appendix. We will open source our code and all models.

Figure 4: Grounded knowledge of cards played. OBL-1 mostly plays cards of
known rank and color. Iterated OBL converges to an even balance of color and
rank, similar to humans.

Grounded Policies in Hanabi. In this experiment, we empirically show that OBL
can indeed learn surprisingly strong grounded policies in Hanabi.

Although Theorem 4 states that applying OBL on any constant policy $\pi_{0}$
should yield an optimal grounded policy $\pi_{1}$, in practice we want the
trajectories generated by $\pi_{0}$ to be as diverse as possible to help train
a good belief model. Hence a simple choice is to make $\pi_{0}$ a uniform-
random policy. We first train a belief model $B_{\pi_{0}}$ till convergence
and then use $B_{\pi_{0}}$ to train the OBL policy. We repeat this training
procedure with five different seeds. The numerical results are shown in the
_OBL (level 1)_ row of Table 1. First of all, we learn that a policy with no
conventions and counterfactual reasoning can achieve nearly 21 points in SP,
which by itself is an important milestone for this popular benchmark
environment. The XP score, which is computed by pairing agents with different
seeds, is almost as high as the SP score, indicating that they indeed converge
to nearly identical policies. The slight gap between XP and SP scores may come
from the noise of belief and policy training.

One way to quantitatively show whether a policy is grounded in Hanabi is to
look at how much the active player knows about a card before playing it.
Playing a card unsuccessfully is costly, and therefore playing it without high
confidence that it will succeed is usually suboptimal. Cards played can be
categorized into four groups. 1) Both color and rank of the card are known. 2)
Only color is known. 3) Only rank is known. 4) Neither is known. Here the
known information can be revealed by hints or deduced from card counts. The
result is shown in the _OBL L1_ column on Figure 4. More than 60% of the cards
played by this policy are completely known to the player, significantly higher
than for other agents, which may infer playability based on counterfactuals
rather than grounded knowledge. Although roughly 28% of the time the policy
plays cards only knowing the number, inspection showed that in those cases the
cards are safe to play regardless of color. These observations are consistent
with the theoretical prediction that OBL should converge to the optimal
_grounded_ policy in Hanabi.

OBL Hierarchy in Hanabi. We can repeat the OBL training process to get OBL
level $i+1$ using level $i$ as new $\pi_{0}$. In practice, we can drastically
speed up the training of next level belief and policy by loading weights from
the previous level as a start point. We train three additional levels and the
evaluation results are shown in Table 1 and Figure 4. For comparison, we show
results of Other-Play applied on the same network architecture as OBL. We see
from the table that both SP and XP of OBL gradually increase after each level.
The final SP performance is similar to that of Other-Play while the XP score
is significantly higher, showing that OBL is a better method for zero-shot
coordination. OBL also performs significantly better when playing with a
diverse set of unseen partners. Note that Other-Play gets high scores with
Rank Bot because Rank Bot is randomly chosen from the five Other-Play training
runs. Based on its performance with Clone Bot, it is probable that OBL would
achieve much better performance than Other-Play when paired with real humans.
From Figure 4, we can see that as we progress through OBL levels, the agents
play fewer grounded cards and start to form conventions and infer playability
based on counterfactuals. Unlike SP where conventions are formed implicitly
and may seem arbitrary, OBL exhibits a consistent path of evolution that can
be understood by reasoning through the behaviors of the lower level OBL
policy. The final level OBL policy is the most similar to Clone Bot in how it
decides to play cards.

##  7 Conclusion and Future Work

We present _off-belief learning_ , a new method that can train optimal
_grounded_ policies, preventing agents from exchanging information through
_counterfactual reasoning_. When used in a hierarchy, each level adds one step
of counterfactual reasoning, thus providing a controlled means of introducing
conventions and pragmatic reasoning into the learning process. Crucially, OBL
removes the ‘weirdness’ of learning in Dec-POMDPs, since each level has a
unique optimal policy, given the beliefs induced by the level below. As a
consequence, OBL at convergence can solve instances of the ZSC problem.

There are many avenues for future work. For example, we may extend OBL to two-
player zero-sum and general-sum settings by training _average beliefs_ and
sampling the fictitious partner move randomly from levels below.

##  8 Acknowledgement

We would like to thank Andrei Lupu and Michael Dennis for helpful discussions
and feedbacks on the ideas of OBL and the manuscript. We appreciate Broad Game
Arena (https://en.boardgamearena.com/) for providing us with anonymized Hanabi
game play data for this research.

## References

  * Agranov et al. (2012) Agranov, M., Potamites, E., Schotter, A., and Tergiman, C.  Beliefs and endogenous cognitive levels: An experimental study.  _Games and Economic Behavior_ , 75(2):449 – 463, 2012.  ISSN 0899-8256.  doi: https://doi.org/10.1016/j.geb.2012.02.002.  URL http://www.sciencedirect.com/science/article/pii/S089982561200022X.
  * 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.
  * Camerer et al. (2003) Camerer, C., Ho, T., and Chong, J.-K.  A cognitive hierarchy theory of one-shot games and experimental analysis.  08 2003.  URL https://ssrn.com/abstract=411061.
  * Camerer et al. (2004) Camerer, C. F., Ho, T.-H., and Chong, J.-K.  A cognitive hierarchy model of games.  _The Quarterly Journal of Economics_ , 119(3):861–898, 2004.
  * Carroll et al. (2019) Carroll, M., Shah, R., Ho, M. K., Griffiths, T., Seshia, S. A., Abbeel, P., and Dragan, A. D.  On the utility of learning about humans for human-ai coordination.  In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E. B., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , pp. 5175–5186, 2019.  URL https://proceedings.neurips.cc/paper/2019/hash/f5b1b89d98b7286673128a5fb112cb9a-Abstract.html.
  * de Witt et al. (2019) de Witt, C., Foerster, J., Farquhar, G., Torr, P., Boehmer, W., and Whiteson, S.  Multi-Agent Common Knowledge Reinforcement Learning.  In Wallach, H., Larochelle, H., Beygelzimer, A., d$\backslash$textquotesingle Alché-Buc, F., Fox, E., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 32, pp. 9927–9939. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/f968fdc88852a4a3a27a81fe3f57bfc5-Paper.pdf.
  * Espeholt et al. (2020) Espeholt, L., Marinier, R., Stanczyk, P., Wang, K., and Michalski, M.  Seed rl: Scalable and efficient deep-rl with accelerated central inference.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=rkgvXlrKwH.
  * 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.
  * Frank & Goodman (2012) Frank, M. C. and Goodman, N. D.  Predicting pragmatic reasoning in language games.  _Science_ , 336(6084):998–998, 2012.
  * Hendon et al. (1996) Hendon, E., Jacobsen, H. J., and Sloth, B.  The one-shot-deviation principle for sequential rationality.  _Games and Economic Behavior_ , 12(2):274–282, 1996.  ISSN 0899-8256.  doi: https://doi.org/10.1006/game.1996.0018.  URL https://www.sciencedirect.com/science/article/pii/S0899825696900184.
  * 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.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net, 2018.  URL https://openreview.net/forum?id=H1Dy---0Z.
  * Hu & Foerster (2020) Hu, H. and Foerster, J. N.  Simplified action decoder for deep multi-agent reinforcement learning.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020.  URL https://openreview.net/forum?id=B1xm3RVtwB.
  * Hu et al. (2020) Hu, H., Peysakhovich, A., Lerer, A., and Foerster, J.  “other-play”for zero-shot coordination.  In _Proceedings of Machine Learning and Systems 2020_ , pp. 9396–9407. 2020.
  * Hu et al. (2021) Hu, H., Lerer, A., Brown, N., and Foerster, J. N.  Learned belief search: Efficiently improving policies in partially observable settings, 2021.  URL https://openreview.net/forum?id=xP37gkVKa_0.
  * Kapturowski et al. (2019) Kapturowski, S., Ostrovski, G., Quan, J., Munos, R., and Dabney, W.  Recurrent experience replay in distributed reinforcement learning.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.  URL https://openreview.net/forum?id=r1lyTjAqYX.
  * Kleiman-Weiner et al. (2016) Kleiman-Weiner, M., Ho, M. K., Austerweil, J. L., Littman, M. L., and Tenenbaum, J. B.  Coordinate to cooperate or compete: abstract goals and joint intentions in social interaction.  In _CogSci_ , 2016.
  * Küttler et al. (2019) Küttler, H., Nardelli, N., Lavril, T., Selvatici, M., Sivakumar, V., Rocktäschel, T., and Grefenstette, E.  TorchBeast: A PyTorch Platform for Distributed RL.  _arXiv preprint arXiv:1910.03552_ , 2019.  URL https://github.com/facebookresearch/torchbeast.
  * 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., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 02 2015.  URL http://dx.doi.org/10.1038/nature14236.
  * Rashid et al. (2018) Rashid, T., Samvelyan, M., de Witt, C. S., Farquhar, G., Foerster, J. N., and Whiteson, S.  QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning.  In Dy, J. G. and Krause, A. (eds.), _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , volume 80 of _Proceedings of Machine Learning Research_ , pp. 4292–4301. PMLR, 2018\.  URL http://proceedings.mlr.press/v80/rashid18a.html.
  * Schaul et al. (2016) Schaul, T., Quan, J., Antonoglou, I., and Silver, D.  Prioritized experience replay.  In Bengio, Y. and LeCun, Y. (eds.), _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.  URL http://arxiv.org/abs/1511.05952.
  * Schelling (1980) Schelling, T. C.  _The strategy of conflict_.  Harvard university press, 1980.
  * Sunehag et al. (2017) Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V. F., Jaderberg, M., Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., and Graepel, T.  Value-decomposition networks for cooperative multi-agent learning.  _CoRR_ , abs/1706.05296, 2017.  URL http://arxiv.org/abs/1706.05296.
  * 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.
  * van Hasselt et al. (2016) van Hasselt, H., Guez, A., and Silver, D.  Deep reinforcement learning with double q-learning.  In Schuurmans, D. and Wellman, M. P. (eds.), _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA_ , pp. 2094–2100. AAAI Press, 2016.  URL http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12389.
  * Wang et al. (2016) Wang, Z., Schaul, T., Hessel, M., van Hasselt, H., Lanctot, M., and de Freitas, N.  Dueling network architectures for deep reinforcement learning.  In Balcan, M. and Weinberger, K. Q. (eds.), _Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016_ , volume 48 of _JMLR Workshop and Conference Proceedings_ , pp. 1995–2003. JMLR.org, 2016.  URL http://proceedings.mlr.press/v48/wangf16.html.

##  Appendix A Proofs of Theorems

We first prove two lemmas that will be necessary for the proofs of the main
theorems.

######  Lemma 1.

For any policies ($\pi_{0},\pi_{1},\pi$),

$\sum_{\tau_{t}\in
T_{t}}P(\tau_{t}|\pi_{0})\sum_{a_{t}}\pi(a_{t}|\tau_{t}^{i})\left(R(s_{t},a_{t})+\sum_{s_{t+1}}\mathcal{T}(s_{t+1}|s_{t},a_{t})V^{\pi_{1}}(\tau_{t+1})\right)\\\
=\sum_{\tau_{t}^{i}\in
T_{t}^{i}}P(\tau_{t}^{i}|\pi_{0})\sum_{a_{t}}\pi(a_{t}|\tau_{t}^{i})Q^{\pi_{0}\to\pi_{1}}(a_{t}|\tau_{t}^{i})$
(7)

This Lemma shows an equivalence between an expected value integrated over all
trajectories of length $t$, and expected value integrated over all AOHs of
length $t$.

###### Proof.

$\displaystyle\sum_{\tau_{t}\in
T_{t}}P(\tau_{t}|\pi_{0})\sum_{a_{t}}\pi(a_{t}|\tau_{t}^{i})\left(R(s_{t},a_{t})+\sum_{s_{t+1}}\mathcal{T}(s_{t+1}|s_{t},a_{t})V^{\pi_{1}}(\tau_{t+1})\right)$
(8) $\displaystyle=\sum_{\tau_{t}^{i}\in
T_{t}^{i}}P(\tau_{t}^{i}|\pi_{0})\sum_{\tau_{t}\in\tau_{t}^{i}}P(\tau_{t}|\tau_{t}^{i})\sum_{a_{t}}\pi(a_{t}|\tau_{t}^{i})\left(R(s_{t},a_{t})+\sum_{s_{t+1}}\mathcal{T}(\tau_{t+1}|\tau_{t},a_{t})V^{\pi_{1}}(\tau_{t+1})\right)$
(9) $\displaystyle=\sum_{\tau_{t}^{i}\in
T_{t}^{i}}P(\tau_{t}^{i}|\pi_{0})\sum_{a_{t}}\pi(a_{t}|\tau_{t}^{i})\sum_{\tau_{t}\in\tau_{t}^{i}}P(\tau_{t}|\tau_{t}^{i})\left(R(s_{t},a_{t})+\sum_{s_{t+1}}\mathcal{T}(s_{t+1}|s_{t},a_{t})V^{\pi_{1}}(\tau_{t+1})\right)$
(10) $\displaystyle=\sum_{\tau_{t}^{i}\in
T_{t}^{i}}P(\tau_{t}^{i}|\pi_{0})\sum_{a_{t}}\pi(a_{t}|\tau_{t}^{i})Q^{\pi_{0}\to\pi_{1}}(a_{t}|\tau_{t}^{i})$
(11)

∎

######  Lemma 2.

The softmax policy with temperature $T$ is worse than the optimal policy by at
most $eT$. Formally, for any $x_{1}\ldots x_{N}\in\mathbb{R}^{N}$,

$\frac{\sum_{i=1}^{N}\exp(x_{i}/T)x_{i}}{\sum_{j=1}^{N}\exp(x_{j}/T)\hskip
8.53581pt}\geq\max\limits_{i}x_{i}-eT$ (12)

###### Proof.

Let $x_{1}\geq x_{2}\geq\ldots\geq x_{N}$ w.l.o.g. So
$\max\limits_{i}x_{i}=x_{1}$. Let $y_{i}=x_{i}-x_{1}$.

$\displaystyle\frac{\sum_{i=1}^{N}\exp(x_{i}/T)x_{i}}{\sum_{j=1}^{N}\exp(x_{j}/T)\hskip
8.53581pt}$
$\displaystyle=\frac{\sum_{i=1}^{N}\exp(x_{1}/T)\exp(y_{i}/T)(y_{i}+x_{1})}{\sum_{j=1}^{N}\exp(x_{1}/T)\exp(y_{j}/T)\hskip
36.98857pt}$ (13)
$\displaystyle=x_{1}+\frac{\sum_{i=1}^{N}\exp(y_{i}/T)y_{i}}{\sum_{j=1}^{N}\exp(y_{j}/T)}$
(14) $\displaystyle\geq x_{1}+\frac{\sum_{i=1}^{N}\exp(y_{i}/T)y_{i}}{N}$
$\displaystyle\text{since }y\leq 0$ (15) $\displaystyle\geq
x_{1}+\min\limits_{z\leq 0}\exp(z/T)z$ (16)

To compute the minimum of $\exp(z/T)z$ in $(-\infty,0]$,

$\displaystyle f(z)=\exp(z/T)z$ (17)
$\displaystyle\frac{df}{dz}=\exp(z/T)(1+z/T)=0$ (18) $\displaystyle z=-T$ (19)
$\displaystyle f(z)=-\exp(-1)T=-eT$ (20)

The value of $f(z)$ at both endpoints is 0. Therefore, $\min\limits_{z\leq
0}\exp(z/T)z=-eT$, which when substituted into Equation 16 proves the theorem.

∎

See 1

###### Proof.

Since AOHs cannot repeat (a successor AOH is always longer than its
predecessor) and the game has bounded length, the AOHs of acting players form
a DAG with edges from each AOH to all possible successor AOHs for the next
acting player. Ordering AOHs topologically s.t. successor AOHs precede their
predecessors, we prove by induction.

In the base case, the first AOH in the topological ordering is a terminal AOH
$\tau_{\epsilon}$, so $Q^{\pi_{0}\to\pi_{1}}(\cdot|\tau_{\epsilon})=0$.

For the inductive case, we must show that if
$Q^{\pi_{0}\to\pi_{1}}(a|\tau_{t+1}^{j})$ is unique for every $\tau_{t+1}^{j}$
that is a successor of $\tau_{t}^{i}$, then
$Q^{\pi_{0}\to\pi_{1}}(a|\tau_{t}^{i})$ is unique (where $j$ is the player to
act at the successor trajectory).

$\pi_{1}(a|\tau_{t}^{i})$ is a function of
$Q^{\pi_{0}\to\pi_{1}}(\cdot|\tau_{t}^{i})$.

$Q^{\pi_{0}\to\pi_{1}}(a|\tau_{t}^{i})=\sum_{\tau_{t},\tau_{t+1}}R(s_{t},a)+\mathcal{B}_{\pi_{0}}(\tau_{t}|\tau_{t}^{i})\mathcal{T}(\tau_{t+1}|\tau_{t})V^{\pi_{0}\to\pi_{1}}(\tau_{t+1}^{j})$
(21)

The RHS of Eq. 21 only depends on $\pi_{1}$ at successor AOHs, which are
uniquely defined. ∎

See 2

###### Proof.

Let $J(\pi_{0}\xrightarrow{t}\pi_{1})$ be the expected return of playing
$\pi_{0}$ for the first $t-1$ timesteps and $\pi_{1}$ subsequently.

We prove by induction backwards in $t$ that

$J(\pi_{0}\xrightarrow{t}\pi_{1})\geq J(\pi_{0})-eT(t_{max}-t)$ (22)

for all $t$, which implies the theorem for $t=0$.

The base case of $t=t_{max}$ is trivially true because
$(\pi_{0}\xrightarrow{t_{max}}\pi_{1})\equiv\pi_{0}$.

For the inductive case, suppose that Eq. (22) holds for all $t>t^{\prime}$.
Let $T_{t}$ and $T_{t}^{i}$ be the set of all trajectories and AOHs of length
$t$, respectively.

$\displaystyle J(\pi_{0})-e(t_{max}-(t^{\prime}+1))T\leq
J(\pi_{0}\xrightarrow{t^{\prime}+1}\pi_{1})$ (23) $\displaystyle
J(\pi_{0}\xrightarrow{t^{\prime}+1}\pi_{1})$
$\displaystyle=\sum_{\tau_{t^{\prime}+1}\in
T_{t^{\prime}+1}}P(\tau_{t^{\prime}+1}|\pi_{0})V^{\pi_{1}}(\tau_{t^{\prime}+1})$
(24) $\displaystyle=\sum_{\tau_{t^{\prime}}\in
T_{t^{\prime}}}P(\tau_{t^{\prime}}|\pi_{0})\sum_{a_{t^{\prime}}}\pi_{0}(a_{t^{\prime}}|\tau_{t^{\prime}}^{i})\left(R(s_{t^{\prime}},a_{t^{\prime}})+\sum_{s_{t^{\prime}+1}}\mathcal{T}(s_{t^{\prime}+1}|s_{t^{\prime}},a_{t^{\prime}})V^{\pi_{1}}(\tau_{t^{\prime}+1})\right)$
(25) $\displaystyle=\sum_{\tau_{t^{\prime}}^{i}\in
T_{t^{\prime}}^{i}}P(\tau_{t^{\prime}}^{i}|\pi_{0})\sum_{a_{t^{\prime}}}\pi_{0}(a_{t^{\prime}}|\tau_{t^{\prime}}^{i})Q^{\prime}_{\pi_{0}}(a_{t^{\prime}}|\tau_{t^{\prime}}^{i})\hskip
28.45274pt\textrm{(Lemma \ref{lemma:tau})}$ (26)
$\displaystyle\leq\sum_{\tau_{t^{\prime}}^{i}\in
T_{t^{\prime}}^{i}}P(\tau_{t^{\prime}}^{i}|\pi_{0})\max\limits_{a_{t^{\prime}}}Q^{\prime}_{\pi_{0}}(a_{t^{\prime}}|\tau_{t^{\prime}}^{i})$
(27) $\displaystyle\leq\sum_{\tau_{t^{\prime}}^{i}\in
T_{t^{\prime}}^{i}}P(\tau_{t^{\prime}}^{i}|\pi_{0})\sum_{a_{t^{\prime}}}\pi_{1}(a_{t^{\prime}}|\tau_{t^{\prime}}^{i})Q^{\prime}_{\pi_{0}}(a_{t^{\prime}}|\tau_{t^{\prime}}^{i})+eT\hskip
28.45274pt\textrm{(Lemma \ref{lemma:softmax})}$ (28)
$\displaystyle=\sum_{\tau_{t^{\prime}}\in
T_{t^{\prime}}}P(\tau_{t^{\prime}}|\pi_{0})\sum_{a_{t^{\prime}}}\pi_{1}(a_{t^{\prime}}|\tau_{t^{\prime}}^{i})\left(R(s_{t^{\prime}},a_{t^{\prime}})+\sum_{s_{t^{\prime}+1}}\mathcal{T}(\tau_{t^{\prime}+1}|\tau_{t^{\prime}},a_{t^{\prime}})V^{\pi_{1}}(\tau_{t^{\prime}+1})\right)+eT\hskip
2.84544pt\textrm{(Lemma \ref{lemma:tau})}$ (29)
$\displaystyle=\sum_{\tau_{t^{\prime}}\in
T_{t^{\prime}}}P(\tau_{t^{\prime}}|\pi_{0})V^{\pi_{1}}(\tau_{t^{\prime}})+eT$
(30)
$\displaystyle=\mathbb{E}_{T_{t^{\prime}}}\left[V^{\pi_{1}}(\tau_{t^{\prime}})|\pi_{0}\right]+eT$
(31) $\displaystyle=J(\pi_{0}\xrightarrow{t^{\prime}}\pi_{1})+eT$ (32)

Lemmas 7 and 2 can be found above. ∎

Notably, unlike standard MARL, the fixed points of the OBL learning rule are
not guaranteed to be equilibria of the game.

See 3

###### Proof.

We’ll start with a proof sketch for a “temperature 0” policy
$\pi_{1}(\tau^{i})=\mathop{\mathrm{argmax}}\limits_{a}Q^{\pi_{0}\to\pi_{1}}(a|\tau^{i})$
and then deal with the softmax policy.

Suppose $\pi$ is a fixed point of the temperature-0 OBL operator. Then at
every AOH $\tau^{i}$,

$\displaystyle\pi(\tau^{i})$
$\displaystyle=\mathop{\mathrm{argmax}}\limits_{a}Q^{\pi\to\pi}(a|\tau^{i})$
(33) $\displaystyle=\mathop{\mathrm{argmax}}\limits_{a}Q^{\pi}(a|\tau^{i})$
(34)

By the one-shot deviation principle (Hendon et al., 1996), $\pi$ must be a
subgame-perfect equilibrium of $G$.

Now, we will need to reiterate the proof of the one-shot deviation principle
in order to modify it for softmax policies.

Suppose that $\pi$ be a fixed point of the OBL operator at temperature $T$. We
will show that for any $\pi^{\prime}_{i}$,

$V^{\pi}(\tau^{i})\geq
V^{\pi^{\prime}_{i},\pi_{-i}}(\tau^{i})-eT(|\tau^{i}|-t_{max}).$ (35)

which for $\tau^{i}=\emptyset$ reduces to $J(\pi)\geq
J(\pi^{\prime}_{i},\pi_{-i})-eTt_{max}$, proving the theorem.

We prove by induction over $i$’s AOHs, treating successor AOHs before
predecessors as before.

The base case at terminal AOHs holds trivially. Now suppose that (35) is true
for all successors of $\tau^{i}$. We know from Lemma 2 that

$\displaystyle\sum_{a}\pi(\tau^{i})Q^{\pi\to\pi}(a|\tau^{i})\geq\max\limits_{a}Q^{\pi\to\pi}(a|\tau^{i})-eT$
(36) $\displaystyle
V^{\pi}(\tau^{i})=\sum_{a}\pi(\tau^{i})Q^{\pi}(a|\tau^{i})\geq\max\limits_{a}Q^{\pi}(a|\tau^{i})-eT$
(37)

Let $P(\tau^{i^{\prime}}|\tau^{i},a,\pi_{-i})$ be the probability that player
$i$’s next AOH is $\tau^{i^{\prime}}$ after playing $a$ at $\tau^{i}$, and
assuming other players play $\pi_{-i}$.333Crucially, this transition
probability is not dependent on player $i$’s policy to reach $\tau^{i}$,
because AOH $\tau^{i}$ already specifies all of player $i$’s actions to reach
$\tau^{i}$. Then expanding out $Q^{\pi}$ in (37) leads to

$\displaystyle V^{\pi}(\tau^{i})$
$\displaystyle\geq\max\limits_{a}\sum_{\tau^{i^{\prime}}}P(\tau^{i^{\prime}}|\tau^{i},a,\pi_{-i})V^{\pi}(\tau^{i^{\prime}})-eT$
(38)
$\displaystyle\geq\max\limits_{a}\sum_{\tau^{i^{\prime}}}P(\tau^{i^{\prime}}|\tau^{i},a,\pi_{-i})\left(V^{\pi^{\prime}_{i},\pi_{-i}}(\tau^{i^{\prime}})-eT-
eT(|\tau^{i^{\prime}}|-t_{max})\right)$ (39)
$\displaystyle\geq\max\limits_{a}\sum_{\tau^{i^{\prime}}}P(\tau^{i^{\prime}}|\tau^{i},a,\pi_{-i})\left(V^{\pi^{\prime}_{i},\pi_{-i}}(a|\tau^{i^{\prime}})-eT(|\tau^{i}|-t_{max})\right)$
(40) $\displaystyle\geq
V^{\pi^{\prime}_{i},\pi_{-i}}(\tau^{i})-eT(|\tau^{i}|-t_{max})$ (41)

Eq. (38) just expands out the expectation for $Q^{\pi}$ over all possible next
AOHs that player $i$ may reach given the other players’ policies $\pi_{-i}$.

∎

See 4

###### Proof.

We need only show that any policy $\pi_{0}$ that conditions only on public
state yields a state distribution at each AOH that matches the grounded
beliefs $\mathcal{B}_{G}$; then the optimal grounded policy follows directly
from the definition of OBL (Eq. 3)

The true state distribution induced by $\pi_{0}$ at $\tau^{i}$ are

$\displaystyle
P(\tau|\tau^{i},\pi_{0})=\frac{P(\tau)\prod_{t}{P(o_{t}^{i}|\tau)}\pi_{0}(a_{t}|\tau_{t}^{-i})}{\sum_{\tau^{\prime}}P(\tau^{\prime})\prod_{t}{P(o_{t}^{i}|\tau^{\prime})}\pi_{0}(a_{t}|\tau_{t}^{\prime-i})}$
(42)

If $\pi_{0}$ is constant, i.e. $\pi_{0}(a_{t}|\tau^{i})=f(a_{t})$, then
$\pi_{0}$ in the numerator and denominator immediately cancel, yielding the
grounded beliefs

$\displaystyle
P(\tau|\tau^{i})=\frac{P(\tau)\prod_{t}{P(o_{t}^{i}|\tau)}}{\sum_{\tau^{\prime}}P(\tau^{\prime})\prod_{t}{P(o_{t}^{i}|\tau^{\prime})}}.$
(43)

If $\pi$ only depends on the public state, then the numerator and denominator
still cancel for all trajectories $\tau$ which contribute to the sum, since
any $\tau$ that doesn’t share a common public state with $\tau$ will lead to
different observations, by definition. ∎

##  Appendix B Qualitative Analysis of Learned Hanabi Agents

In this section we share more insights about the policies learned by different
methods through a series of qualitative analysis.

As we can see from Figure 4 the OBL L1 agent plays a significantly higher
percentage of grounded cards, _i.e._ cards of which both color and rank are
known. This supports our claim that OBL learns a grounded policy given a
constant $\pi_{0}$. However, it is worth mentioning that OBL L1 still plays a
fair number of cards when it only knows their rank. At first this may seem
contradictory to the grounded policy claim. However, as we analyze the games,
we find that in many cases the best grounded policy is to play those cards
even if the color is not known. For example, at an early stage of the game
when only a few cards have been played, knowing a card is 1 is sufficient to
play it. Moreover, the agent often knows that the card is of a “safe color”.
For example, when both red 2 and green 2 have been played, it will be safe to
play a card if we know that it is either a red 3 or a green 3. Playing such a
card will be classified as “only rank” in the figure. Furthermore, there are
multiple lives in Hanabi and sometimes it is worth taking a risk if the odds
are good. We observe that the OBL L1 agent sometimes plays a card blindly
without knowing any information about the card, as reflected in the figure by
the slightly higher percentage of “none” category than other OBL levels and
other agents except for SAD. This is because Hanabi is not designed to be a
game that can be mastered by a grounded policy, and therefore the number of
the remaining hint tokens are often low due to the aggressive hinting strategy
used by the policy. In this case, OBL L1 resorts to maximizing the utility of
the life tokens by playing one or two cards blindly in later stages of the
game when the chances that a newly drawn card could be useful is high and
remaining life tokens are abundant. Once there is only one life token left,
the agent becomes conservative and stops the gambling behavior.

The conventions in the high levels of OBL agents stem from the fact that OBL
L1 agents give hints about a card in certain orders based on the situations.
In some cases the OBL L1 agent first hints at the color of a card it wants the
partner to play while in other cases it hints rank first. The order depends on
the grounded probability of having a playable card in the partner’s hand after
giving the hint assuming only the public information. If the partner knowing
the color of some cards leads to a higher chance that they will have a
playable card in hand, then we should hint color first and vice versa. This
information gets picked up by the belief model and then taken advantaged by
the OBL in the next level to form conventions. The conventions gradually get
reinforced and lead to more nuanced conventions in the higher level of OBL
agents.

For reference, we can also see from the same Figure 4 that the Other-Play Rank
Bot and Color Bot have strong preferences to use only rank and only color to
exchange information respectively, making it difficult for them to coordinate
with each other. The Clone Bot uses both color and rank depending on the
situation, which is similar to the highest level OBL agent. The SAD agent,
which is trained in the typical self-play setting, seems to play “blindly” a
lot. However, the fact that such an agent achieves a high self-play score
indicates that it must be using some form of secretive conventions that are
not grounded at all, e.g. the conventions such as “hinting red means play the
second card”, which completely disregard the grounded meaning of the hint
actions. Since these conventions by definition assign arbitrary meaning to
actions, they are deemed to fail under zero-shot coordination setting and for
human-AI coordination.

##  Appendix C Experimental Details for Hanabi

###  C.1 Reinforcement Learning

Figure 5: Illustration of RL training setup. Some arrows linking _player 1_
and _batching layer_ are omitted for legibility.

We use a highly scalable setup as illustrated in Figure 5 to efficiently train
RL models in Hanabi using moderate computational resources (three GPUs). It
includes fours major components. The first one is a large number of parallel
thread workers that handle the interactions between environments and the
multiple players in each environment. The player often needs to invoke one or
more neural network inferences at each step to compute an action, which is
often computationally intensive and thus should be executed on GPUs. Here, we
take an asynchronous approach that instead of waiting for the neural network
calls to return, the thread worker immediately moves on to execute the next
set of environment and players after sending the neural network request to the
inference loop. This allows us to run multiple environments in a single thread
worker. On top of this, we also run multiple thread workers in parallel. The
combination of these two techniques allows us to run a massive amount of
environments and therefore generates a large amount of neural network
inference requests simultaneously. These requests are then batched together
before sending to an everlasting inference loop. The batched inference is
executed on GPUs and the inference loop may use multiple GPUs to distribute
workloads. Each player collects observation, action and reward at each step
and aggregates them into a trajectory at the end of an episode. The trajectory
is padded to a fixed length of 80 time-steps and then stored into the
prioritized replay buffer. A training loop, which runs completely in parallel
to all the procedures mentioned above, keeps sampling batches from the replay
buffer and updates the model with TD-error. The training loop sends a new copy
of the model to the inference loop to have the inference model synced every 10
gradient steps. This overall setup combines several techniques that have
appeared in previous literature (Espeholt et al., 2020; Hu & Foerster, 2020;
Küttler et al., 2019). In all of our RL experiments, i.e. both training OBL
agents and reproducing Other-Play agents, we run 80 thread workers and 80
environments in each thread worker. We use 2 GPUs for the inference loop and 1
GPU for the training loop. The entire workload runs on a single machine with
40 CPU cores and 3 GPUs.

We use the same network design as Hu et al. (2021) and follow most of their
practices excluding the search part since they achieved the SOTA self-play
performance. More specifically, the network uses a two-stream design where one
stream is a three-layer feed-forward network that takes the entire observation
as input while the other stream is a one-layer feed-forward network followed
by a two-layer LSTM and only takes the public portion of the observation as
input. The outputs of the two streams are fused with an element-wise
multiplication before feeding into a dueling architecture (Wang et al., 2016)
to get the final Q-values. It also uses double DQN (van Hasselt et al., 2016)
and prioritized experience replay (Schaul et al., 2016) with priority of the
trajectory computed the same way as (Kapturowski et al., 2019). We use the
exact same set of hyper-parameters as Hu et al. (2021) except for changing the
n-step Q-learning from 3 down to 1 to reduce the amount of fictitious
transitions required and using IQL instead of VDN as mentioned in our method
section. Please refer to their paper for an illustration of network design and
a table of hyper-parameters.

###  C.2 Belief Learning

Instead of creating a training/validation dataset, we use a similar setting as
the reinforcement learning training, where mini-batches are sampled from an
ever-changing replay buffer populated by thread workers. There are four main
differences. First, the inference loop uses a pretrained fixed policy instead
of syncing with a training policy periodically. Second, we store the true hand
of the player alongside the trajectories which will be used as training
targets for our belief model. Third, a normal experience replay buffer without
priority is used. Finally, the training loop trains an auto-regressive model
that predicts cards in hand one-by-one from the oldest to the latest with
supervised learning. The belief model is the same as the one used in (Hu et
al., 2021).

###  C.3 Other Models

To test the performance of OBL when paired with unseen partners (_ad-hoc_
teamplay), we train three types of policies with existing methods.

The first one is trained with the Other-Play (OP) (Hu et al., 2020) technique.
The majority of policies trained with OP use a rank-based convention where
they predominantly hint for ranks to indicate a playable card. For example, in
a case where “Red 1” and “Red 2” have been played and the partner just draw a
new “Red 3”, the other agent will hint 3 and then partner will play that card
deeming that 3 being a red card based on the convention and counterfactual
reasoning. We refer to this category of agents as “Rank Bot”.

Equivalently, one can also expect a color-based policy that will hint red for
that latest card instead. In fact, such color-based policy was also appeared
in the original Other-Play paper as the worst partner of the reset of the
Other-Play policies. However, they are generally hard to reproduce as only 1
out of the 12 their training runs ended up with such policy. We use a simple
reward shaping technique to produce similar policies reliably where we give
each “hint color” move an extra reward during the first half of the training
process and then disable the extra reward in the second half to wash out any
artifacts. However, the reward shaping introduces undesired side effects that
lead to arbitrary conventions. In practice, we find that hiding the _last
action_ field of the input observation will make training outcomes more
consistent. The reward shaping and feature engineering techniques are only
used for producing this specific policy, which we refer to as “Color Bot”.

One of the goals of the Hanabi challenge (Bard et al., 2020) is to develop
artificial agents that can collaborate with humans. To understand how well our
models can collaborate with humans without resorting to costly experiments, we
train a behavior clone bot mimicking human behaviors to serve as a proxy. We
collect 208,974 games from the online game platform “Board Game
Arena”444https://en.boardgamearena.com/

and convert it to a dataset for supervised learning. The model takes in the
trajectory of an entire game from the perspective of a single player and
predicts its action at each time-step. This is similar to the independent
Q-learning setting in the multi-agent RL context. We use a similar network
design as our policy network in OBL but replace the dueling architecture with
a single linear layer followed by a softmax activation layer to output a
distribution over actions. The agent is trained by minimizing the cross-
entropy loss. At test time, the agent selects the action with the highest
probability at each step. We pick the model that achieves the highest self-
play score during training as our final “Clone Bot”. The Clone Bot achieves
19.38 $\pm$ 0.11 points in self-play.