$Id:espcrc1.tex,v1.22004/02/2411:22:11speppingExp$ On interval edge-colorings
of outerplanar graphsPetros A. Petrosyan

# On interval edge-colorings of outerplanar graphs

Petros A. Petrosyan email<EMAIL_ADDRESS>ysu.am, yahoo.com}
Department of Informatics and Applied Mathematics,
Yerevan State University, 0025, Armenia  Institute for Informatics and
Automation Problems,
National Academy of Sciences, 0014, Armenia

###### Abstract

An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is called an interval
$t$-coloring if all colors are used, and the colors of edges incident to any
vertex of $G$ are distinct and form an interval of integers. A graph $G$ is
interval colorable if it has an interval $t$-coloring for some positive
integer $t$. For an interval colorable graph $G$, the least value of $t$ for
which $G$ has an interval $t$-coloring is denoted by $w(G)$. A graph $G$ is
outerplanar if it can be embedded in the plane so that all its vertices lie on
the same (unbounded) face. In this paper we show that if $G$ is a
$2$-connected outerplanar graph with $\Delta(G)=3$, then $G$ is interval
colorable and

$w(G)=\left\\{\begin{tabular}[]{ll}$3$,&if $|V(G)|$ is even,\\\ $4$,&if
$|V(G)|$ is odd.\\\ \end{tabular}\right.$

We also give a negative answer to the question of Axenovich on the outerplanar
triangulations.

Keywords: edge-coloring, interval coloring, outerplanar graph, outerplanar
triangulation

##  1 Introduction

In this paper we consider graphs which are finite, undirected, and have no
loops or multiple edges. Let $V(G)$ and $E(G)$ denote the sets of vertices and
edges of a graph $G$, respectively. The degree of a vertex $v\in V(G)$ is
denoted by $d_{G}(v)$, the maximum degree of $G$ by $\Delta(G)$, and the
chromatic index of $G$ by $\chi^{\prime}\left(G\right)$. A graph $G$ is
outerplanar if it can be embedded in the plane so that all its vertices lie on
the same (unbounded) face. An outerplanar triangulation is an outerplanar
graph in which every bounded face is a triangle. An edge of the outerplanar
graph is internal if it does not belong to unbounded face. A separating
triangle of the outerplanar graph is a triangular face in which every edge is
internal. The terms and concepts that we do not define can be found in [10].

A proper edge-coloring of a graph $G$ is a coloring of the edges of $G$ such
that no two adjacent edges receive the same color. If $\alpha$ is a proper
edge-coloring of $G$ and $v\in V(G)$, then $S\left(v,\alpha\right)$ denotes
the set of colors of edges incident to $v$. A proper edge-coloring of a graph
$G$ with colors $1,\ldots,t$ is called an interval $t$-coloring if all colors
are used, and for any vertex $v$ of $G$, the set $S\left(v,\alpha\right)$ is
an interval of integers. A graph $G$ is interval colorable if it has an
interval $t$-coloring for some positive integer $t$. The set of all interval
colorable graphs is denoted by $\mathfrak{N}$. For a graph $G\in\mathfrak{N}$,
the least value of $t$ for which $G$ has an interval $t$-coloring is denoted
by $w\left(G\right)$.

The concept of interval coloring of graphs was introduced by Asratian and
Kamalian [1, 2]. In [1, 2], they proved that if $G$ is interval colorable,
then $\chi^{\prime}\left(G\right)=\Delta(G)$. They also showed that if a
triangle-free graph $G$ has an interval $t$-coloring, then
$t\leq\left|V(G)\right|-1$. In [6], Kamalian investigated interval colorings
of complete bipartite graphs and trees. In particular, he proved that the
complete bipartite graph $K_{m,n}$ has an interval $t$-coloring if and only if
$m+n-\gcd(m,n)\leq t\leq m+n-1$, where $\gcd(m,n)$ is the greatest common
divisor of $m$ and $n$. In [7], Petrosyan investigated interval colorings of
complete graphs and $n$-dimensional cubes. In particular, he proved that if
$n\leq t\leq\frac{n\left(n+1\right)}{2}$, then the $n$-dimensional cube
$Q_{n}$ has an interval $t$-coloring. Recently, Petrosyan, Khachatrian and
Tananyan [8] showed that the $n$-dimensional cube $Q_{n}$ has an interval
$t$-coloring if and only if $n\leq t\leq\frac{n\left(n+1\right)}{2}$. In [9],
Sevast’janov proved that it is an $NP$-complete problem to decide whether a
bipartite graph has an interval coloring or not.

Proper edge-colorings of outerplanar graphs were investigated by Fiorini in
[4]. In [4], he proved that if $G$ is an outerplanar graph, then
$\chi^{\prime}\left(G\right)=\Delta(G)$ if and only if $G$ is not an odd
cycle. Interval edge-colorings of outerplanar graphs were first considered by
Axenovich in [3]. In [3], she proved that all outerplanar triangulations with
more than three vertices and without separating triangles are interval
colorable. Later, interval edge-colorings of outerplanar graphs were
investigated by Giaro and Kubale in [5], where they proved that all
outerplanar bipartite graphs are interval colorable.

In the present paper we show that if $G$ is a $2$-connected outerplanar graph
with $\Delta(G)=3$, then $G$ is interval colorable and

$w(G)=\left\\{\begin{tabular}[]{ll}$3$,&if $|V(G)|$ is even,\\\ $4$,&if
$|V(G)|$ is odd.\\\ \end{tabular}\right.$

We also give a negative answer to the question of Axenovich on the outerplanar
triangulations.

##  2 Interval edge-colorings of subcubic outerplanar graphs

First we need the following lemma which was proved in [4].

###### Lemma 1

If $G$ is a $2$-connected outerplanar graph with $\Delta(G)=3$, then $G$ has
either (1) $u$ and $v$ adjacent vertices such that $d_{G}(u)=d_{G}(v)=2$, or
(2) $u,v$ and $w$ mutually adjacent vertices such that $d_{G}(u)=d_{G}(w)=3$
and $d_{G}(v)=2$.

Now we can prove our first result.

###### Theorem 2

If $G$ is a $2$-connected outerplanar graph $G$ with $\Delta(G)\leq 3$ and $G$
is not an odd cycle, then $G\in\mathfrak{N}$ and $w(G)\leq 4$.

  * Proof.

For the proof, it suffices to show that if $G$ is a $2$-connected outerplanar
graph $G$ with $\Delta(G)\leq 3$ and $G$ is not an odd cycle, then $G$ has an
interval coloring with no more than four colors.

We show it by induction on $|E(G)|$. The statement is trivial for the case
$|E(G)|\leq 5$. Assume that $|E(G)|\geq 6$, and the statement is true for all
$2$-connected outerplanar graphs $G^{\prime}$ with $\Delta(G^{\prime})\leq 3$
which are not odd cycles and $|E(G^{\prime})|<|E(G)|$.

Let us consider a $2$-connected outerplanar graph $G$ with $\Delta(G)\leq 3$
which is not an odd cycle. If $\Delta(G)=2$, then $G\in\mathfrak{N}$ and
$w(G)\leq 2$. Now suppose that $\Delta(G)=3$. By Lemma 1, $G$ has either $u$
and $v$ adjacent vertices such that $d_{G}(u)=d_{G}(v)=2$, or $u,v$ and $w$
mutually adjacent vertices such that $d_{G}(u)=d_{G}(w)=3$ and $d_{G}(v)=2$.
We consider two cases.

Case 1: $uv\in E(G)$ and $d_{G}(u)=d_{G}(v)=2$.

Clearly, in this case there are vertices $x,y$ ($x\neq y$) in $G$ such that
$ux\in E(G)$ and $vy\in E(G)$.

Case 1.1: $xy\notin E(G)$.

In this case let us consider a $2$-connected outerplanar graph
$G^{\prime}=(G-u-v)+xy$. By induction hypothesis, $G^{\prime}$ has an interval
coloring $\alpha$ with no more than four colors.

If $\alpha(xy)=1$, then we delete the edge $xy$ and color the edges $ux$ and
$vy$ with color $1$ and the edge $uv$ with color $2$. If $\alpha(xy)\geq 2$,
then we delete the edge $xy$ and color the edges $ux$ and $vy$ with color
$\alpha(xy)$ and the edge $uv$ with color $\alpha(xy)-1$. It is not difficult
to see that the obtained coloring is an interval coloring of the graph $G$
with no more than four colors.

Case 1.2: $xy\in E(G)$.

In this case let us consider a $2$-connected outerplanar graph
$G^{\prime}=G-u-v$. If $G^{\prime}$ is an odd cycle, then we color the edges
$xy$ with color $3$ and the edges of the $x,y$-path in $G^{\prime}-xy$
alternately with colors $1$ and $2$. Next, we color the edge $ux$ with color
$2$, the edge $uv$ with color $3$ and the edge $vy$ with color $4$. Clearly,
the obtained coloring is an interval $4$-coloring of the graph $G$.

Now we can suppose that $G^{\prime}$ is a $2$-connected outerplanar graph with
$\Delta(G^{\prime})\leq 3$ which is not an odd cycle. By induction hypothesis,
$G^{\prime}$ has an interval coloring $\alpha$ with no more than four colors.
Since $G$ is $2$-connected, we have $d_{G}(x)=d_{G}(y)=3$.

If $S(x,\alpha)=S(y,\alpha)=\\{c,c+1\\}$, then if $c=1$, then we color the
edges $ux$ and $vy$ with color $3$ and the edge $uv$ with the color $2$;
otherwise we color the edges $ux$ and $vy$ with color $c-1$ and the edge $uv$
with color $c$. If $S(x,\alpha)\cup S(y,\alpha)=\\{c,c+1,c+2\\}$, then without
loss of generality we may assume that $S(x,\alpha)=\\{c,c+1\\}$ and
$S(y,\alpha)=\\{c+1,c+2\\}$. We color the edge $ux$ with color $c+2$, the edge
$uv$ with color $c+1$ and the edge $vy$ with color $c$. Clearly, the obtained
coloring is an interval coloring of the graph $G$ with no more than four
colors.

Case 2: $uv,vw,uw\in E(G)$ and $d_{G}(u)=d_{G}(w)=3$ and $d_{G}(v)=2$.

In this case by contracting the $uvw$ triangle to a single vertex $v^{\star}$,
we obtain a $2$-connected outerplanar graph $G^{\prime}$ with
$\Delta(G^{\prime})\leq 3$. If $G^{\prime}$ is an odd cycle, then we color the
edge $uw$ with color $3$, the first edge of the $u,w$-path in $G$ with color
$4$ and the remaining edges alternately with colors $3$ and $2$. Next, we
color the edge $uv$ with color $2$ and the edge $vw$ with color $1$. Clearly,
the obtained coloring is an interval $4$-coloring of the graph $G$.

Now we can suppose that $G^{\prime}$ is a $2$-connected outerplanar graph with
$\Delta(G^{\prime})\leq 3$ which is not an odd cycle. By induction hypothesis,
$G^{\prime}$ has an interval coloring $\alpha$ with no more than four colors.

Let $S(v^{\star},\alpha)=\\{c,c+1\\}$. If $c=1$, then we color the edge $uw$
with color $3$ and the edges $uv$ and $vw$ with colors $1$ and $2$ or $2$ and
$1$ depending on the colors of the colored edges incident to vertices $u$ and
$w$; otherwise we color the edge $uw$ with color $c-1$ and the edges $uv$ and
$vw$ with colors $c$ and $c+1$ or $c+1$ and $c$ depending on the colors of the
colored edges incident to vertices $u$ and $w$. Clearly, the obtained coloring
is an interval coloring of the graph $G$ with no more than four colors.
$\square$

Figure 1: A 2-connected outerplanar graph $G$ with $\Delta(G)=4$ which has no
interval coloring.

Next we prove the following result:

###### Theorem 3

If $G$ is a $2$-connected outerplanar graph $G$ with $\Delta(G)=3$, then
$G\in\mathfrak{N}$ and

$w(G)=\left\\{\begin{tabular}[]{ll}$3$,&if $|V(G)|$ is even,\\\ $4$,&if
$|V(G)|$ is odd.\\\ \end{tabular}\right.$

  * Proof.

By Theorem 2, we have $G\in\mathfrak{N}$ and $w(G)\leq 4$. On the other hand,
since $\Delta(G)=3$, we obtain $3\leq w(G)\leq 4$. We consider two cases.

Case 1: $|V(G)|$ is even.

Since $G$ is $2$-connected and outerplanar, it is clear that $G$ is
Hamiltonian. Let $C$ be a Hamiltonian cycle in $G$. Since $|V(G)|$ is even,
clearly $|C|$ is even, too. Now we construct an interval $3$-coloring of the
graph $G$. First we color the edges of the cycle $C$ alternately with colors
$1$ and $2$. Next we color the edges from the set $E(G)\setminus E(C)$ by
color $3$. Since $E(G)\setminus E(C)$ is a matching in $G$, the obtained
coloring is an interval $3$-coloring of the graph $G$ and thus $w(G)=3$.

Case 2: $|V(G)|$ is odd.

For the proof, it suffice to show that $w(G)\geq 4$.

Suppose, to the contrary, that $G$ has an interval $3$-coloring $\alpha$. In
this case we consider the set $S(v,\alpha)$ for every $v\in V(G)$. Since $G$
is $2$-connected and outerplanar, we have $1\leq{\min}~{}S(v,\alpha)\leq 2$
for every $v\in V(G)$. This implies that the edges with color $2$ form a
perfect matching in $G$, but this contradicts the fact that $|V(G)|$ is odd.
Thus, $w(G)=4$. $\square$

On the other hand, there are $2$-connected outerplanar graphs $G$ with
$\Delta(G)=4$ which are not interval colorable. For example, the graph $G$
shown in Fig. 1 has no interval coloring. Now we show a more general result.
For that we define a triangle graph $T_{k,l,m}$ ($k,l,m\in\mathbb{N}$) as
follows:

$V\left(T_{k,l,m}\right)=\\{x,y,z,u_{1},\ldots,u_{2k-1},v_{1},\ldots,v_{2l-1},w_{1},\ldots,w_{2m-1}\\}$
and
$E\left(T_{k,l,m}\right)=\\{xy,xu_{1},u_{2k-1}y,yz,yv_{1},v_{2l-1}z,xz,xw_{1},w_{2m-1}z\\}\cup$

$\\{u_{i}u_{i+1}:1\leq i\leq 2k-2\\}\cup\\{v_{i}v_{i+1}:1\leq i\leq
2l-2\\}\cup\\{w_{i}w_{i+1}:1\leq i\leq 2m-2\\}$.

Clearly, $T_{k,l,m}$ is a $2$-connected outerplanar graph with
$\Delta\left(T_{k,l,m}\right)=4$.

###### Theorem 4

For any $k,l,m\in\mathbb{N}$, we have $T_{k,l,m}\notin\mathfrak{N}$.

  * Proof.

Suppose, to the contrary, that the graph $T_{k,l,m}$ has an interval
$t$-coloring $\alpha$ for some $t\geq 4$.

Since all degrees of vertices of the graph $T_{k,l,m}$ are even, the sets
$S(x,\alpha),S(y,\alpha)$ and $S(z,\alpha)$ contain two even colors and two
odd colors, and the sets $S(u_{i},\alpha),S(v_{j},\alpha)$ and
$S(w_{p},\alpha)$ contain one even color and one odd color for
$i=1,\ldots,2k-1,j=1,\ldots,2l-1,p=1,\ldots,2m-1$.

Consider the triangle $xyz$. Clearly, there is a vertex of the triangle for
which the colors of two incident edges of the triangle have the same parity.
Without loss of generality, we may assume that this vertex is $x$ and
$\alpha(xy)$ and $\alpha(xz)$ have the same parity. If $\alpha(xy)$ and
$\alpha(xz)$ are even colors, then $\alpha(xu_{1})$ and $\alpha(xw_{1})$ are
odd colors, and thus $\alpha(u_{2k-1}y)$ and $\alpha(w_{2m-1}z)$ are even
colors. This implies that $\alpha(yz)$, $\alpha(yv_{1})$ and
$\alpha(v_{2l-1}z)$ are odd colors. On the other hand, since $\alpha(yz)$,
$\alpha(yv_{1})$ are odd colors, we obtain $\alpha(v_{2l-1}z)$ is an even
color, which is a contradiction. Similarly, if $\alpha(xy)$ and $\alpha(xz)$
are odd colors, then $\alpha(xu_{1})$ and $\alpha(xw_{1})$ are even colors,
and thus $\alpha(u_{2k-1}y)$ and $\alpha(w_{2m-1}z)$ are odd colors. This
implies that $\alpha(yz)$, $\alpha(yv_{1})$ and $\alpha(v_{2l-1}z)$ are even
colors. On the other hand, since $\alpha(yz)$, $\alpha(yv_{1})$ are even
colors, we obtain $\alpha(v_{2l-1}z)$ is an odd color, which is a
contradiction. $\square$

##  3 Interval edge-colorings of outerplanar triangulations

In [3], Axenovich showed that all outerplanar triangulations with more than
three vertices and without separating triangles are interval colorable, and
also she posed the following

###### Question 1

Is it true that an outerplanar triangulation has an interval coloring if and
only if it does not have a separating triangle?

Figure 2: An interval $3$-coloring of $TF_{3}$, an interval $5$-coloring of
$TF_{5}$ and an interval $6$-coloring of $TF_{7}$.

In this section we give a negative answer to the question. For that we define
a triangular fan graph $TF_{n}$ ($n\geq 3$) as follows:

$V(TF_{n})=\\{u,v_{1},\ldots,v_{n-1},w_{1},\ldots,w_{n-2}\\}$ and
$E(TF_{n})=\\{uv_{i}:1\leq i\leq
n-1\\}\cup\\{v_{i}w_{i},w_{i}v_{i+1},v_{i}v_{i+1}:1\leq i\leq n-2\\}$.

Clearly, $TF_{n}$ is an outerplanar triangulation.

###### Theorem 5

For any $n\geq 3$, $TF_{n}$ has an interval $\Delta(TF_{n})$-coloring.

  * Proof.

We consider two cases.

Figure 3: Interval $5$-colorings of $TF_{4}$ and $TF_{6}$, and an interval
$7$-coloring of $TF_{8}$.

Case 1: $n$ is odd.

Fig. 2 gives an interval $3$-coloring of $TF_{3}$, an interval $5$-coloring of
$TF_{5}$ and an interval $6$-coloring of $TF_{7}$. Let $\alpha$ be an interval
$6$-coloring of $TF_{7}$ shown in Fig. 2. Now we define an edge-coloring
$\beta$ of the graph $TF_{n}$ as follows:

(1)

for every $e\in E(TF_{7})$, let $\beta(e)=\alpha(e)$;

(2)

for $i=3,\ldots,\frac{n-3}{2}$, let

$\beta(uv_{2i+1})=2i+2$ and $\beta(uv_{2i+2})=2i+1$,
$\beta(v_{2i+1}w_{2i})=\beta(w_{2i+1}v_{2i+2})=2i-1$,
$\beta(v_{2i+1}v_{2i+2})=\beta(v_{2i}w_{2i})=2i$, $\beta(v_{2i}v_{2i+1})=2i+1$
and $\beta(v_{2i+1}w_{2i+1})=2i-2$.

It is not difficult to see that $\beta$ is an interval
$\Delta(TF_{n})$-coloring of $TF_{n}$ for odd $n$.

Case 2: $n$ is even.

Fig. 3 gives interval $5$-colorings of $TF_{4}$ and $TF_{6}$, and an interval
$7$-coloring of $TF_{8}$. Let $\alpha$ be an interval $7$-coloring of $TF_{8}$
shown in Fig. 3. Now we define an edge-coloring $\beta$ of the graph $TF_{n}$
as follows:

(1)

for every $e\in E(TF_{8})$, let $\beta(e)=\alpha(e)$;

(2)

for $i=3,\ldots,\frac{n-4}{2}$, let

$\beta(uv_{2i+2})=2i+3$ and $\beta(uv_{2i+3})=2i+2$,
$\beta(v_{2i+2}w_{2i+1})=\beta(w_{2i+2}v_{2i+3})=2i$,
$\beta(v_{2i+2}v_{2i+3})=\beta(v_{2i+1}w_{2i+1})=2i+1$,

$\beta(v_{2i+1}v_{2i+2})=2i+2$ and $\beta(v_{2i+2}w_{2i+2})=2i-1$.

It is not difficult to see that $\beta$ is an interval
$\Delta(TF_{n})$-coloring of $TF_{n}$ for even $n$. $\square$

###### Corollary 6

For any $n\geq 3$, we have $TF_{n}\in\mathfrak{N}$ and
$w(TF_{n})=\Delta(TF_{n})$.

Clearly, $uv_{i}v_{i+1}$ is a separating triangle in $TF_{n}$ for
$i=2,\ldots,n-3$. Thus, for $n\geq 5$, $TF_{n}$ has $n-4$ separating
triangles.

## References

  * [1] A.S. Asratian, R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987), 25-34 (in Russian).
  * [2] A.S. Asratian, R.R. Kamalian, Investigation on interval edge-colorings of graphs, J. Combin. Theory Ser. B 62 (1994), 34-43.
  * [3] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002), 77-94.
  * [4] S. Fiorini, On the chromatic index of outerplanar graphs, J. Combin. Theory Ser. B 18 (1975), 35-38.
  * [5] K. Giaro, M. Kubale, Compact scheduling of zero-one time operations in multi-stage systems, Discrete Appl. Math. 145 (2004), 95-103.
  * [6] R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, preprint, Comp. Cen. of Acad. Sci. of Armenian SSR, Erevan, 1989 (in Russian).
  * [7] P.A. Petrosyan, Interval edge-colorings of complete graphs and $n$-dimensional cubes, Discrete Math. 310 (2010), 1580-1587.
  * [8] P.A. Petrosyan, H.H. Khachatrian, H.G. Tananyan, Interval edge-colorings of Cartesian products of graphs I, Discuss. Math. Graph Theory, 2013, to appear.
  * [9] S.V. Sevast’janov, Interval colorability of the edges of a bipartite graph, Metody Diskret. Analiza 50 (1990), 61-72 (in Russian).
  * [10] D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001.


# Learning Translations: Emergent Communication Pretraining
for Cooperative Language Acquisition

Dylan Cope111 Correspondence<EMAIL_ADDRESS>DC is supported by the
UKRI Centre for Doctoral Training in Safe and Trusted AI (EPSRC Project
EP/S023356/1). Preprint (under review).  &Peter McBurney King's College London

###### Abstract

In Emergent Communication (EC) agents learn to communicate with one another,
but the protocols that they develop are specialised to their training
community. This observation led to research into Zero-Shot Coordination (ZSC)
for learning communication strategies that are robust to agents not
encountered during training. However, ZSC typically assumes that no prior data
is available about the agents that will be encountered in the zero-shot
setting. In many cases, this presents an unnecessarily hard problem and rules
out communication via preestablished conventions. We propose a novel AI
challenge called a Cooperative Language Acquisition Problem (CLAP) in which
the ZSC assumptions are relaxed by allowing a `joiner' agent to learn from a
dataset of interactions between agents in a target community. We propose and
compare two methods for solving CLAPs: Imitation Learning (IL), and Emergent
Communication pretraining and Translation Learning (ECTL), in which an agent
is trained in self-play with EC and then learns from the data to translate
between the emergent protocol and the target community's protocol.

##  1 Introduction

Creating teams of artificial agents that can communicate and cooperate has
been a long-standing area of interest in multi-agent systems research.
Advances in multi-agent reinforcement learning have enabled researchers in the
field of Emergent Communication (EC) to train such teams in ever more complex
domains (Wagner et al.,, 2003; Foerster et al.,, 2016; Sukhbaatar et al.,,
2016; Jaques et al.,, 2019; Lazaridou and Baroni,, 2020). These agents are
typically trained by allowing discrete messages to be exchanged between
agents. Programmers do not assign meaning to the messages, rather, meaning
emerges via the training process as communicative conventions are developed in
service of solving the task. As such, the mapping between meanings and
messages is arbitrary, and any permutation of a learned protocol is equally
likely to appear across different training runs (Bullard et al.,, 2021). The
result is that the learned conventions established within a training community
will be very unlikely to work with new agents, and by default, the EC trained
agents will be incapable of adapting.

In response to this, many researchers have become interested in devising
methods in which agents learn communicative strategies that can adapt to this
Zero-Shot Coordination (ZSC) setting (Li et al.,, 2023; Hu et al.,, 2021,
2020; Ossenkopf,, 2020; Cope and Schoots,, 2020; Bullard et al.,, 2020). ZSC
algorithms typically aim to successfully communicate with an unknown agent on
the first encounter, without any prior information. But in many real-world
settings, this is an unnecessarily challenging assumption. If someone is
injured on a street in London, passing pedestrians can form an ad hoc team and
aid the patient by speaking to each other in English to coordinate a response.
Indeed, language is arguably the most critical set of conventions that such
teams can draw upon to efficiently work together.

The study of artificial agents that can form ad hoc teams is known as Ad Hoc
Teamwork (AHT) (Stone et al.,, 2010). Similarly to ZSC, most of these
algorithms aim to make as few assumptions as possible about the players that
an agent may form a team with. Notably, Sarratt and Jhala, (2015) applied this
minimalist approach to communication. Other work has relaxed this by assuming
a prior known communication protocol (Barrett et al.,, 2014; Mirsky et al.,,
2020).

In this work, we present a novel AI challenge that we call a Cooperative
Language Acquisition Problem (CLAP). Here by `language acquisition' we mean
learning the syntax and semantics of a preexisting communication system used
by a community. This class of problems is positioned between the challenges of
ZSC and AHT. In a CLAP, we are given a dataset of communication events between
speakers and listeners in a target community as they solve a problem. Our goal
is to construct a joiner agent that can communicate and cooperate with agents
from this community. This problem is also closely related to Imitation
Learning (IL), however, most work in IL is confined to the single agent
setting (Hussein et al.,, 2017). So to the best of our knowledge, this is the
first attempt to pose an IL problem for multi-agent communication within a
formal cooperative model.

Alongside defining CLAP, we outline two baseline solutions to this problem.
The first uses a simple imitation learning method. The second is a novel
algorithm called Emergent Communication pretraining and Translation Learning
(ECTL). We introduce two environments and train target communities of agents
that cooperate via a learned communication protocol. Data is then gathered
from these communities and then used to train joiner agents with ECTL and IL.
We demonstrate that ECTL is more robust than IL to expert demonstrations that
give an incomplete picture of the underlying problem and that ECTL is
significantly more effective than IL when communications data is limited.
Finally, we apply these methods to manually collected data and show that ECTL
can learn to communicate with a human to cooperatively solve a task.

##  2 Background

###  2.1 Decentralised POMDPs

A Decentralised Partially-Observable Markov Decision Process (Dec-POMDP) is a
formal model of a cooperative environment defined as a tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},T,r,\bm{\Omega},O)$ (Oliehoek and
Amato,, 2016), where $\mathcal{S}$ is a set of states, and
$\mathcal{A}=\prod_{i}\mathcal{A}_{i}$ is a product of individual agent action
sets. A joint action $\mathbf{a}\in\mathcal{A}$ is a tuple of actions from
each agent that is used to compute the environment's transition dynamics,
defined by a probability distribution over states
$T:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$. Team
performance is defined by a cooperative reward function
$r:\mathcal{S}\times\mathcal{A}\times\mathcal{S}$ over state transitions and
joint actions. $\bm{\Omega}=\\{\Omega_{i}\\}$ is a set of observation sets,
and $O:S\rightarrow\prod_{i}\Omega_{i}$ is an observation function.

Each agent $i$ follows a policy $\pi_{i}$ that maps an observation sequence
(or a single observation if $i$ is memoryless) to a distribution over its
actions. A trajectory for an agent $i$ is a sequence of observation-action-
reward tuples
$\tau_{i}\in\mathcal{T}_{i}=(\Omega_{i}\times\mathcal{A}_{i}\times\mathds{R})^{*}$.
For a set of policies $\Pi=\\{\pi_{i}\\}$, a joint trajectory is
$\bm{\tau}\in\mathcal{T}=(\bm{\Omega}\times\mathcal{A}\times\mathds{R})^{*}$,
and we can denote the distribution of joint trajectories for this set of
policies acting in the environment as $\mathcal{M}|_{\Pi}$. In this work, we
will only consider finite-horizon Dec-POMDPs, so the lengths of trajectories
will always be bounded. The total reward for this trajectory is the sum of
rewards along the sequence, denoted $R(\bm{\tau})$. The expected sum of
rewards for a set of policies will be denoted
$R(\Pi)=\mathds{E}_{\bm{\tau}\sim\mathcal{M}|_{\Pi}}[R(\bm{\tau})]$.

###  2.2 Emergent Communication

Emergent communication is the study of agents that learn (or evolve) to make
use of communication channels without previously established semantics. In a
typical set-up, each agent's action set in the Dec-POMDP can be expressed as
$\mathcal{A}_{i}=\mathcal{A}_{i}^{e}\times\mathcal{A}^{c}_{i}$, where
$\mathcal{A}_{i}^{c}$ is a set of communicative actions, and
$\mathcal{A}_{i}^{e}$ is a set of environment actions. The communicative
actions can further be written as the product of one-way communication
channels from $i$ to $j\in C_{i}$ using a discrete message alphabet $\Sigma$,
i.e. $\mathcal{A}^{c}_{i}=\Sigma^{|C_{i}|}$. These are cheap-talk channels,
meaning there is no cost to communication. This variant of a Dec-POMDP is
known as a Dec-POMDP-Com (Goldman and Zilberstein,, 2004, 2008; Oliehoek and
Amato,, 2016). The messages have no prior semantics as the transition function
of the Dec-POMDP only depends on the environment actions
${\mathcal{A}_{i}^{e}}$, and agents are not programmed to send messages with
any prescribed meaning. Rather, the semantics emerge through training.

For this paper, we will consider memoryless agents that communicate within a
centralised forward pass computing a joint action for the environment (similar
to Goldman and Zilberstein, 2003).

Policy Factorisation. We suppose that we can factor a memoryless communication
agent's policy $\pi_{i}$ into an environment-level policy
$\pi^{e}_{i}:\Omega_{i}\times\Sigma^{n_{s}}\rightarrow\mathcal{A}^{e}_{i}$,
where $n_{s}$ is the number of agents that send messages to agent $i$, and a
communication policy $\pi^{c}_{i}:\Omega_{i}\rightarrow\mathcal{A}^{c}_{i}$.
Therefore, given a joint observation
$\mathbf{o}=(o_{1},\ldots,o_{N})\in\prod_{i}\Omega_{i}$, the joint policy
$\bm{\pi}(\mathbf{o})$ is computed by first producing the outgoing messages
$M_{out}^{i}=\pi^{c}_{i}(o_{i})$ from each sender agent $i$ to each receiver
agent $j\in C_{i}$. A set of incoming messages $M^{i}_{in}$ is then
constructed for each agent $i$ by passing the messages for $i$ through a
communication channel function
$\sigma_{i}:\mathcal{A}^{c}_{i}\rightarrow\Sigma$. The final environment
actions are then given by $a_{i}=\pi^{e}_{i}(o_{i},M^{i}_{in})$.

Self-play. Emergent communication training is often done in self-play, where
parameters are shared between agents and centrally optimised (Hu et al.,,
2020). Communication can be hard to learn with Reinforcement Learning (RL) as
sending messages cannot provide reward unless listeners already know how to
use the information. This chicken-and-egg problem can be solved with
centralised training by allowing gradients to backpropagate through
communication channels. A Gumbel-Softmax (Jang et al.,, 2017; Maddison et
al.,, 2017) function is a popular choice as it facilitates backpropagation
during training and can be discretised during evaluation.

However, as Lowe et al., (2019) have shown, measuring whether or not agents
trained to communicate are doing so can be tricky for complex environments. To
remedy this, they introduced definitions of positive listening and positive
signalling. In short, to be positive listening/signalling; the listening agent
should change its actions according to the messages it receives and the
signalling agent should change its messages depending on what it observes.

###  2.3 Imitation Learning

(a) Joint agents architecture (two agents)
with communication.

(b) Illustration of the
gridworld environment (Section 5.1).

(c) Illustration of the
driving environment (Section 5.1).

Figure 1: (a) Agents architecture diagram for two agents (top and bottom) with
communication. (b) Illustration of the gridworld toy environment with two
agents, depicted with blue and green circles on a 5x5 grid. The green and blue
stars indicate the locations of each agents' respective goals. The cloud
thought bubble depicts the world as the green agent observes it. Note, each
agent does not see their own goal, and they are off-by-one square in their
knowledge of each other's goal. (c) Illustration of the driving environment
with two agents. The dark circle in the centre is the `pit'; the region in
which large negative penalties are given when agents enter. The stars indicate
goal locations, which can spawn in one of eight locations (the unused
locations indicated by the greyed-out stars). The continuous state space is
indicated with the grid axes. The agents are represented by arrowheads
indicating their current position and direction. Again, here agents do not
observe their own goals and therefore need to communicate, but unlike the
gridworld, they do have perfect knowledge of the other agent's goals.

Imitation Learning (IL) is a form of machine learning in which expert
demonstration data is used to construct a policy for solving a task. The data
is typically in the form of an observation $o$ and action $a$, and the
imitation learning problem is posed as supervised classification learning,
e.g. optimising $\theta$ to minimise the difference between $a$ and
$\hat{a}=\pi_{\theta}(o)$. See Hussein et al., (2017) for a more comprehensive
review of these methods.

##  3 Cooperative Language Acquisition

In this section, we introduce our definition of a Cooperative Language
Acquisition Problem (CLAP). A CLAP can be formulated from the simplest case
involving a preexisting target community of two agents, denoted
$\Pi=\\{A,B\\}$, that achieve some non-trivial performance in a Dec-POMDP-Com
$\mathcal{M}$. Consider an interaction at time $t$ in which $A$ is speaking
and $B$ is listening. While making the observation $o_{t}^{s}$, the speaker
emits a message $m_{t}$. Then, while observing $o_{t}^{r}$ and $m_{t}$, the
receiver takes the action $a_{i}$ in the environment. We are given access to
$\mathcal{M}$ and a dataset of such interactions, denoted
$(o_{t}^{s},m_{t},o_{t}^{r},a_{t}^{r})\in\mathcal{D}$, and our task is to
construct a joiner agent ${\mathcal{J}}$. In this paper, we focus on a
specific case of the task in which we aim to replace a target agent in $\Pi$
(so there is always a fixed number of players), which we call CLAP-Replace.
The agent ${\mathcal{J}}$ should be able to take on the role of a target agent
(e.g. either $A$ or $B$) and successfully communicate with the other, while
also acting in the environment to maximise the cooperative reward. The joiner
will be evaluated zero-shot, i.e. on the first joining event, so all learning
must be done beforehand.

The emphasis of the dataset is on learning the communication protocol as this
is assumed to be the key aspect of the community's strategy that cannot be
learned independently from observing their behaviour. As the communication
symbols have no prior semantics, any protocol could be equally successful if
the same meanings were assigned to a different permutation of the symbols. On
the other hand, there may be many `environment-level' behaviours that can be
learned without needing to know the specific strategies of a given community.
We will discuss disentangling these factors in Section 3.2.

###  3.1 Problem Definitions

The cooperative language acquisition task is to construct a joining agent
${\mathcal{J}}$ that learns from observing a target community $\Pi$. When
${\mathcal{J}}$ replaces an agent in $\Pi$, we have a CLAP-Replace task:

######  Problem 1 (CLAP-Replace).

Suppose there exists a Dec-POMDP-Com $\mathcal{M}$ and a set of policies
$\Pi=\\{\pi_{i}\\}$ trained in $\mathcal{M}$. Given a target policy
$\pi_{k}\in\Pi$ to replace, a dataset $\mathcal{D}_{k}$ of interactions
$(o_{t}^{s},m_{t},o_{t}^{r},a_{t}^{r})$ in which $\pi_{k}$ is either a speaker
or listener, the task is to construct a policy $\pi_{\mathcal{J}}$ such that:

$\displaystyle\pi_{{\mathcal{J}}}\in\operatorname*{arg\,max}_{\pi^{\prime}}R(\\{\pi^{\prime}\\}\cup\Pi^{-k})$
(1)

Where $\Pi^{-k}=\Pi\setminus\\{\pi_{k}\\}$. In other words, maximise the team
rewards when the joiner replaces $k$.

This can be decomposed into three related problems; a forward communication
(signalling), a backward communication (listening), and acting. More
precisely, ${\mathcal{J}}$ needs to learn to send messages that maximise the
expected sum of rewards for listening agents and interpret messages to
maximise the rewards of its trajectory. But the agent also needs to learn to
utilise information, both communicated and observed, for selecting actions.

If we were allowed to interact with the target community $\Pi$ before
evaluation, we could apply standard reinforcement learning tools. However, we
are interested in settings in which disrupting the community and jeopardising
performance to learn is not acceptable, so ${\mathcal{J}}$ needs to perform
well on the first actual joining episode.

###  3.2 Disentangling Environment-Level and Communicative Competencies

We assume that teams of agents can achieve a certain level of performance in
the environment by two categories of competencies: (1) `environment-level'
skills, and (2) communication strategies that rely on established conventions.
The key distinction we aim for is that the former should be learnable
independently of observing a target community's behaviour. We start by
defining that the team achieves an average total reward of $R$ when acting
together in the environment and communicating.

Measuring the _communicative competency_ (1) is relatively easy: if
communication is blocked and the team achieves a lower average total reward
$R^{\prime}<R$, and by assuming that the agents are engaged in positive
listening and signalling, we can attribute this drop in performance to a lack
of communication.

Figure 2: Illustration of the problem of compounding errors for Imitation
Learning. When IL agents exit the expert state distribution they are unable to
recover.

We evaluate the influence of _environment-level competencies_ (2) by similarly
hampering them, and investigating whether this leads to a drop in performance.
We will assume that each agent's observation can be partitioned into `private'
(or `local') and shared (or `global') components:
$o^{i}_{t}=(l^{i}_{t},g_{t})$, where $g_{t}$ is observed by both speakers and
listeners, but $l^{i}_{t}$ is private to $i$. To assess the contribution of
environment-level skills we restrict the environment-level policy by removing
private information, $o^{\prime}_{t}=(\mathbf{0},g_{t})$, and replacing each
$\pi_{i}$ with
$\pi^{\prime}_{i}(\mathbf{o}_{t},M_{t})=(\pi^{e}_{i}(o^{\prime}_{t},M_{t}),\pi^{c}_{i}(o_{t}))$.
We can then attribute a change $R^{\prime\prime}<R$ to the agent being
prevented from exercising environment-level skills. To understand this
intervention, consider the following points:

Figure 3: Training architecture diagrams for the Imitation Learning (IL) and
Emergent Communication pretraining and Translation Learning (ECTL) methods.
The forward and backward problems for each method are solved with supervised
learning. Circles are variables and trapezoids are functions. Dotted lines
indicate that gradients are blocked from backpropagating along a path. For the
ECTL diagrams the $enc$ and $\pi^{c}$ functions are learned during the
emergent communication pretraining phase. The variables
$o^{s}_{t},o^{r}_{t},m_{t},a_{t}$ are the sender/receiver agent observations,
the sender's message, and the receiver's action from the dataset of
interactions collected from the target community.

  1. 1.

We hamper environment-level skills by blocking private information from
$\pi^{e}$, but an agent must still be allowed to receive messages as this may
provide vital information for succeeding based on communication skills. Thus,
$\pi^{c}$ for the speaker must not be intervened with.

  2. 2.

Communication may rely on shared information, so removing the context by
blocking this information may interfere with measuring environment-level
skills.

  3. 3.

Information private to a recipient cannot have been used by the speaker to
create the messages, so if a drop in performance is seen when it is removed
from $\pi^{e}$, this can only be due to a loss in the recipient's capacity to
use that private information to contribute to the team's performance through
its actions (as opposed to its contributions through sending messages).
Recall, we are only obfuscating this information from $\pi^{e}$; $\pi^{c}$
still sees it.

  4. 4.

If no drop from blocking private information to $\pi^{e}$ is observed, it
implies one of two cases: (a) all of an agent's contribution to the collective
performance is the result of following direct orders from a speaker. Or, (b)
an agent's contribution is entirely contingent on global information.

Note that following 4b, the absence of a drop does not imply that the team
does not possess environment-level competencies, but the presence of a drop
does.

##  4 Methods for Constructing Joiners

In this section, we introduce two methods for constructing joiners for the
CLAP-Replace task. The first naively applies imitation learning, and the
second pretrains agents using emergent communication and then translates the
learned communication protocol to the target community's protocol. Each method
is decomposed into forward and backward problems, posed as supervised learning
tasks.

###  4.1 Imitation Learning (IL)

(a) Ablated agents in the target community.

(b) Mean reward for different teams.

Figure 4: Performance results from cases in which (a) the team is formed of a
variety of agents, comparing ECTL to imitation learning (IL) with unbiased and
biased data from the gridworld environment. And (b) the target community
agents ablated in different ways. All results are from 500 evaluation episodes
and the error bars show means within 95% confidence intervals.

In the set-up for CLAP-Replace we are given a dataset
$(o_{t}^{s},m_{t},o_{t}^{r},a_{t}^{r})\in\mathcal{D}_{k}$ of speaker and
listener observations, messages, and actions taken by the receiver. The
simplest baseline solution to this problem is to apply imitation learning
separately to the signalling and listening problems. The dataset is
partitioned into two datasets: a signalling dataset
$(o_{t}^{s},m_{t})\in\mathcal{D}^{s}_{k}$ where $k$ is the speaker and a
listening dataset $((o_{t}^{r},m_{t}),a_{t}^{r})\in\mathcal{D}^{r}_{k}$ where
$k$ is the receiver. These datasets are structured as input-label tuples to
learn communicative and environmental-level policy factors ($\pi_{il}^{c}$ and
$\pi_{il}^{e}$) of the overall imitation policy $\pi_{il}$. These are learned
with a categorical cross-entropy ($CCE$) loss between predicted and actual
labels. We will denote this imitator joiner ${\mathcal{J}}_{il}$. In Figure 3,
$\pi^{c}_{il}$ and $\pi^{e}_{il}$ are composed of encoder and
communication/action heads, with the same architecture as in Figure 1(a).

###  4.2 Emergent Communcation Pretraining and Translation Learning (ECTL)

(a) The mean CLAP-Replace performance on the Driving Game (No Pit) for ECTL
and IL, against the number data collection episodes ($N_{collect}$) from the
target community.

(b) Mean reward for each method normalised by the original team mean rewards.
Shows the impact of the pit on CLAP performance, highlighting IL's relative
fragility.

Figure 5: Comparisons between IL and ECTL on the Driving Communication
environment.

A well-known issue with imitation learning agents is that they can be brittle
given the natural biases in the expert demonstration data (Kumar et al.,,
2022). This problem is illustrated in Figure 2. Especially in more complex
domains, experts typically stay in the regions of state space in which they
get high rewards, which may only be a small portion of the possibilities. If
an imitator makes a mistake when attempting the task itself, it may enter into
unseen territory. Thus errors can compound as the agent has not learned what
to do and makes more mistakes, leading to degraded team performance in a
multi-agent cooperative setting.

This leads to the idea that the joiner could explore the state space of
$\mathcal{M}$ before joining $\Pi$, and thereby become a more reliable
cooperator. In general, pretraining may allow the agent to learn environment-
level skills that could be transferable to cooperating with any new team. To
this end, we propose the method Emergent Communication pretraining and
Translation Learning (ECTL). The first step of ECTL is to (pre)train a set of
agents $\Pi^{\prime}$ from scratch in $\mathcal{M}$ that we refer to as the EC
training community, where for each agent in $\Pi$ there is a corresponding
agent in $\Pi^{\prime}$.

The agents in $\Pi^{\prime}$ are composed of three components, illustrated in
Figure 1(a): an observation encoder $enc_{\theta}$, a communications head
$\pi^{c}_{\theta}$, and an action head $\pi^{e}_{\theta}$, parameterised by
$\theta$, and shared amongst the policies $\Pi^{\prime}$. For brevity and to
be consistent with the notation in previous sections we will omit the encoder
from our notation, and write $\pi^{c}_{\theta}(o)$ instead of
$\pi^{c}_{\theta}(enc_{\theta}(o))$. This training process could use any
viable multi-agent reinforcement learning algorithm, and which is most
suitable depends on the properties of the underlying environment and the
number of agents. In Section 5.2, we will outline the specific methods we used
for our experiments.

Agents in the EC training community learn to cooperate via an emergent
communication protocol over their message alphabet $\Sigma^{\prime}$. The next
step in ECTL towards building the joiner agent for $\Pi$ is to translate this
protocol to the one used by the target community. For a CLAP-Replace task with
target agent $\pi_{k}\in\Pi$, we select the equivalent pretrained
$\pi^{\prime}_{k}\in\Pi^{\prime}$ to use a starting point for translation
learning. We will refer to $\pi^{\prime}_{k}$ as the EC pretrained agent.

Once again, the target community data $\mathcal{D}_{k}$ is transformed into a
signalling dataset $(o_{t}^{s},m_{t})\in\mathcal{D}_{k}^{s}$ and a listening
dataset $((o_{t}^{r},m_{t}),m^{\prime}_{t})\in\mathcal{D}^{r}_{k}$. Note that
the ECTL signalling dataset is identical to the signalling dataset used for
imitation learning, but the listening dataset is different. Instead of the
label being an action, it is a message $m^{\prime}_{t}$ from the EC
pretraining message space $\Sigma^{\prime}$. To construct these labels we use
the speaker's observation from $\mathcal{D}_{k}$ and compute the message that
EC pretrained agent would have emitted that same situation, i.e.
$m^{\prime}_{t}=\pi^{c}_{\theta}(o^{s}_{t})$.

From these data, we learn translation functions for signalling and for
listening. A separate translation function can be learned for each
communication channel if there are multiple possible senders and/or receivers
for the target agent, or two models (one for each CLAP sub-problem) can be
used by providing the sender/receiver identifiers as input. For our
experiments, we will use the latter approach. However, for simplicity in the
following descriptions of how these functions are trained, we will assume one
sender and receiver for the target agent and omit agent identifiers.
Additionally, the training architectures for the translation functions are
illustrated by the two leftmost diagrams of Figure 3.

A signalling translation function
$\tau^{s}_{\phi}:\Omega_{k}\times\Sigma^{\prime}\rightarrow\Sigma$ maps from
the EC training community's communication protocol to the target community's
protocol, and is parameterised by $\phi$. Given an observation
$o_{t}^{s}\in\Omega_{k}$ and message $m_{t}\in\Sigma$ from
$\mathcal{D}^{s}_{k}$, we can compute the message
$m^{\prime}_{t}=\Sigma^{\prime}$ that the agent
$\pi^{\prime}_{k}\in\Pi^{\prime}$ would send in that situation. The
translation function is trained to predict the demonstrator agent's message:

$\displaystyle\phi^{*}\in\operatorname*{arg\,min}_{\phi}\sum_{(o_{t}^{s},m_{t})\in\mathcal{D}^{s}_{k}}CCE(m_{t},\hat{m}_{t})$
(2)
$\displaystyle\text{where}~{}\hat{m}_{t}=\tau^{s}_{\phi}(o^{s}_{t},m^{\prime}_{t}),\quad
m^{\prime}_{t}=\pi^{c}_{\theta}(o_{t}^{s})$ (3)

A listening translation function
$\tau^{r}_{\psi}:\Omega_{k}\times\Sigma\rightarrow\Sigma^{\prime}$ maps from
the target community's communication protocol to the EC training community's
protocol, and is parameterised by $\psi$. Note that, in general, $\tau^{r}$
and $\tau^{s}$ need not be inverses of one another, as two agents can use
arbitrarily different protocols in each direction.

To train $\tau^{r}_{\psi}$, we use the message that was received by the
listener (the target agent) $m_{t}$, the listener's observation $o^{r}_{t}$,
and the speaker's observation $o^{r}_{t}$. The translation function takes the
observation and the message and produces a new message in the EC training
community's message space:
$\tau^{r}_{\psi}(o^{r}_{t},m_{t})=\hat{m}^{\prime}_{t}\in\Sigma^{\prime}$. To
get the ground-truth label for this prediction, we find the message that the
EC pretrained agent would have sent in the target community speaker's
situation. The result is the following optimisation criterion:

$\displaystyle\psi^{*}\in\operatorname*{arg\,min}_{\psi}\sum_{((o_{t}^{r},m_{t}),m^{\prime}_{t})\in\mathcal{D}^{r}_{k}}CCE(m^{\prime}_{t},\hat{m}^{\prime}_{t})$
(4)
$\displaystyle\text{where}~{}\hat{m}^{\prime}_{t}=\tau^{r}_{\psi}(o^{r}_{t},m_{t}),\quad
m^{\prime}_{t}=\pi^{c}_{\theta}(o^{s}_{t})$ (5)

Finally, we can put together these pieces into a final translator joiner agent
${\mathcal{J}}_{ectl}$ composed of the following communication and
environment-level policy factors:

$\displaystyle\pi^{c}_{ectl}=\tau^{s}_{\phi}\circ\pi^{c}_{\theta}\quad\text{and}\quad\pi^{e}_{ectl}(o,m)=\pi^{e}_{\theta}(o,\tau^{r}_{\psi}(m))$
(6)

So when the joiner agent receives a message, it uses the listening translation
function to predict the message that it would have received from the
equivalent agent in its EC training community. When speaking, the agent first
computes the message that it would have sent in its original message space,
and then passes that through the signalling translation function before
finally sending it.

##  5 Experiments

###  5.1 Environments

In order to empirically investigate IL and ECTL for solving CLAP-Replace
tasks, we created two environments. Firstly, a simple gridworld toy
environment in which $N$ agents cooperate by communicating goal information.
Secondly, a `driving' communication problem in which agents must navigate a
continuous space to reach a goal, while potentially avoiding a pit in their
way. Again, the goal location is known by another agent so they need to
communicate to solve the problem.

Goal Communications Gridworld. Each agent has a goal square in the grid that
they need to reach that changes each episode. No agent observes its own goal
unless it is within one tile of it, but at all times it observes a `close
guess' (a location within one tile) of the goal of another of the agents in
the game. The environment is illustrated in Figure 1(b).

Goal Communications Driving Game. As discussed in Section 4.2, IL agents can
be brittle when regions of the state space are not present in the
demonstration data. To investigate this problem, we introduced this `driving'
environment in which the agent steers and accelerates a body in a continuous
grid (Figure 1(c)). This environment has two settings defined by the presence
or absence of a circular region in the centre of the world where a large
penalty is applied for every agent within the region. The agents must navigate
to one of eight fixed goal locations, known by their partner and selected at
random for each episode.

###  5.2 Creating Target Communities

Target communities $\Pi$ of three agents in the gridworld environment and two
agents in the driving environment were trained using Multi-Agent Proximal
Policy Optimisation (MAPPO) (Yu et al.,, 2022). For the policy networks we
used the architecture in Figure 1(a) with parameter sharing between agents.
The value network used a concatenation of all of the agents' observations as
input, meaning that we rely on centralisation for training. The value network
did not share any parameters with the policy networks. A Gumbel-Softmax (Jang
et al.,, 2017; Maddison et al.,, 2017) communication channel function was used
on communication channels. Further training details can be found in Appendix
A.

###  5.3 Ablating Target Community Agents

(a)

(b)

(c)

(d)

Figure 6: (a,b) Two-dimensional histograms visualising how much time the
agents spend in the different regions of the environment before reaching their
goals. Left and right show agents trained with/without pit penalties. The
radius of the pit is indicated with the dashed circle outline. We can see that
when the pit is present agents avoid that region. The goal locations are also
visible as we are not plotting positions after the goals are reached. (c) The
UI for the human to play the game as a listener. The top-left of the screen
shows messages from the other player. (d) The mean episode lengths when we
played this game with different agents. The goal is for us to navigate to our
goal location as quickly as possible (one of the grey stars) using the
messages. We see that only the ECTL agent was able to effectively communicate.

The gridworld environment was designed such that the agents need to use a
combination of communicative and individual skills in order to succeed. To
demonstrate how these skills contribute to the performance, we evaluate
ablated versions of the agents with the interventions discussed in Section
3.2. Figure 4(a) shows the results of these experiments. At the top, we show
the original unmodified performance for reference ($R(\Pi)$). The next two
bars, appearing roughly equal in size and variance, correspond to blocking
communications (bar 2) and `global'/`shared' information from $\pi^{e}$ (bar
3).

###  5.4 Gridworld CLAP-Replace

We train ECTL and IL agents after collecting interaction datasets from
$N_{collect}=100$ episodes of $\Pi$ acting in the environment. See Appendix A
for details on training hyperparameters and learning curves. Figure 4(b) shows
the results from forming teams of different compositions in the gridworld
environment. We see that ECTL and IL solve the CLAP-Replace task by achieving
the equivalent team performance as the original team ($R(\Pi)$).

Both methods have roughly the same performance, which is due to the fact that
there are not opportunities for errors to compound. The imitator will have
learned the experts' behaviour from any state as the agent starting positions
and goal positions are sampled from a uniform distribution over all grid
tiles. Therefore, if an imitator makes a mistake from any given position, it
will have seen during training how to recover in the next position.

So to investigate the effects of unseen states we bias the training data by
only including cases where the target agent was in one of the first two
columns of the grid. The results are also shown in Figure 4(b), and we see
that while ECTL maintains its performance, IL significantly degrades.

###  5.5 Driving Game CLAP-Replace

Moving on from the gridworld environment, we then performed a series of
experiments in the driving game. First, we trained four teams on the
environment, with two agents per training team. Two of the teams with the pit,
and the other two without the pit. Figures 6(a) and 6(b) visualise where in
the environment these agents spend their time (before reaching their goals),
illustrating how the expert demonstrations may not cover the pit region of
state space.

In Figure 5(a) we see the effect of the number of data collection episodes on
the driving game CLAP-Replace performance without the pit. We find that the
ECTL performance starts notably better than IL, and can do well with very
little data. However, as more data is gathered, eventually IL scales better
than ECTL. Yet, Figure 5(b) complicates this picture. Here we see the
normalised reward comparisons between ECTL and IL showing the effect of the
pit on performance. The pit does not have much impact on ECTL, but the
performance of IL drops by a large margin, even for the case with 1000 data
collection episodes – the setting in which IL outperforms ECTL when the pit is
not present.

###  5.6 Translating to an Interpretable Communication Protocol

After demonstrating that IL and ECTL could successfully solve CLAPs for target
communities of artificial agents, we investigated whether or not the same
methods could apply to data generated by humans. We developed an interactive
UI through which a user could simultaneously control two agents in the driving
game while observing the entire game state (i.e. both agent's goals). The user
observes the world through a top-down view like in Figure 1(c), with both
agents, the goal locations, and the pit visible. To control the first agent in
the game, the user presses the `W', `A', and `D' keys to accelerate, turn
anti-clockwise, and turn clockwise respectively. Likewise, the user controls
the second agent with the `Up Arrow', `Left Arrow', and `Right Arrow' keys.
Additionally, to make it easier to control both agents at the same time the
frame rate of the game was reduced to 2 frames per second. This was then used
to collect data from 70 episodes. Each row of data comprised the actions that
the user took for each agent and the agent-specific observations. Formally,
each row of data had the form $(o^{1}_{t},o^{2}_{t},a^{1}_{t},a^{2}_{t})$,
where $t$ is the time step that the data was collected, $o^{i}_{t}$ and
$a^{i}_{t}$ are the observations and actions for each agent $i$.

In its raw form, this data cannot be used to train CLAP agents as it lacks
messages. To remedy this we augmented the data by constructing messages on the
principle that each agent was following direct instructions from the other, so
each agent $i$'s action $a^{i}_{t}$ became agent $j$'s message
$m_{t}=a^{i}_{t}$ to agent $i$. Now each row of the data can be transformed
into two CLAP-Replace datasets rows, one dataset for each agent that could be
replaced: $(o^{1}_{t},m_{t}=a^{2}_{t},o^{2}_{t},a^{2}_{t})$ and
$(o^{2}_{t},m_{t}=a^{1}_{t},o^{1}_{t},a^{1}_{t})$.

Finally, we removed all rows where the user was not inputting one of the three
movement actions (turn clockwise/anti-clockwise or accelerate) as it was hard
to coherently press keys for both agents with exact simultaneity. Furthermore,
as each agent had the same observation space we could take each collected
episode and construct data for an alternative episode where the agent roles
were reversed, resulting in a final dataset of 140 episodes. Formally, for
each row of the original raw collected data
$(o^{1}_{t},o^{2}_{t},a^{1}_{t},a^{2}_{t})$, we construct another row
$(o^{2}_{t},o^{1}_{t},a^{2}_{t},a^{1}_{t})$.

With this data, ECTL and IL agents could now be trained in the same manner as
done for the MAPPO target communities. However, due to the lack of a well-
defined target community, the agents could not be evaluated in the same way.
So instead, we focused on specifically evaluating the signalling capabilities
of these agents with another UI that allows a user to view their agent, the
possible goal locations, and a message from one of the artificial agents
(Figure 6(c)). As the message space is the action space for the user, it is
inherently interpretable and could be rendered to the user as one of the
strings `Accelerate', `Turn Anti-Clockwise', or `Turn Clockwise'. We then set
up the UI to randomly switch the messenger agent each episode from a pool of
agents comprised of an ECTL agent, an IL agent, and an agent that sends a
random message. Thus the user was always unaware of which agent they were
playing with. This UI runs at 10 frames per second, but the message only
updates every half second (every 5 frames). This is to prevent it being too
obvious which is the random agent as the messages would change much more
frequently than for the other agents. Additionally, it gives the user more
time to read and react to the messages.

Figure 6(d) shows the results of this experiment, measured by the mean number
of timesteps that it took for the user to reach the goal location while using
the messages. It shows that only the ECTL agent was able to effectively
communicate with the user, with the IL agent conveying the same lack of
information as the random policy.

##  6 Conclusions

In this paper, we have posed a new problem for multi-agent communication
learning, namely the Cooperative Language Acquisition Problem (CLAP).
Positioned relative to Zero-Shot Coordination and Ad Hoc Teamwork, the CLAP
challenge is to build an agent that learns the communication strategy of a
target community via observational data. But can also leverage general
`environment-level skills' that transfer to any ad hoc team. We have proposed
two approaches to this problem: Imitation Learning (IL) and Emergent
Communication pretraining and Translation Learning (ECTL).

We have shown that ECTL can perform well in data scarce scenarios, including
learning to communicate with a human user. Additionally, it can effectively
compensate for expert demonstrations that only cover a limited distribution
over the environment state space. On the other hand, while IL is brittle, it
does have the potential to scale to large datasets. Further work should
investigate combining the strengths of these methods.

## References

  * Barrett et al., (2014) Barrett, S., Agmon, N., Hazon, N., Kraus, S., and Stone, P. (2014).  Communicating with unknown teammates.  In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, AAMAS '14, pages 1433–1434, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
  * Bullard et al., (2021) Bullard, K., Kiela, D., Meier, F., Pineau, J., and Foerster, J. (2021).  Quasi-Equivalence Discovery for Zero-Shot Emergent Communication.  arXiv:2103.08067 [cs].
  * Bullard et al., (2020) Bullard, K., Meier, F., Kiela, D., Pineau, J., and Foerster, J. (2020).  Exploring Zero-Shot Emergent Communication in Embodied Multi-Agent Populations.  arXiv:2010.15896.
  * Cope and Schoots, (2020) Cope, D. and Schoots, N. (2020).  Learning to Communicate with Strangers via Channel Randomisation Methods.  In The Emergent Communication Workshop at NeurIPS.
  * Foerster et al., (2016) Foerster, J., Assael, I. A., Freitas, N. d., and Whiteson, S. (2016).  Learning to Communicate with Deep Multi-Agent Reinforcement Learning.  In D. D. Lee and M. Sugiyama and U. V. Luxburg and I. Guyon and R. Garnett, editor, Advances in Neural Information Processing Systems 29, pages 2137–2145. Curran Associates, Inc.
  * Goldman and Zilberstein, (2003) Goldman, C. V. and Zilberstein, S. (2003).  Optimizing information exchange in cooperative multi-agent systems.  In Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 03), AAMAS '03, pages 137–144, New York, NY, USA. Association for Computing Machinery.
  * Goldman and Zilberstein, (2004) Goldman, C. V. and Zilberstein, S. (2004).  Decentralized control of cooperative systems: categorization and complexity analysis.  Journal of Artificial Intelligence Research, 22(1):143–174.
  * Goldman and Zilberstein, (2008) Goldman, C. V. and Zilberstein, S. (2008).  Communication-Based Decomposition Mechanisms for Decentralized MDPs.  Journal of Artificial Intelligence Research, 32:169–202.  arXiv:1111.0065 [cs].
  * Hu et al., (2021) Hu, H., Lerer, A., Cui, B., Wu, D., Pineda, L., Brown, N., and Foerster, J. (2021).  Off-Belief Learning.  In the 38th International Conference on Machine Learning, PMLR 139.  arXiv: 2103.04000.
  * Hu et al., (2020) Hu, H., Lerer, A., Peysakhovich, A., and Foerster, J. (2020).  “Other-Play” for Zero-Shot Coordination.  In Proceedings of the 37th International Conference on Machine Learning, pages 4399–4410. PMLR.  ISSN: 2640-3498.
  * Hussein et al., (2017) Hussein, A., Gaber, M. M., Elyan, E., and Jayne, C. (2017).  Imitation Learning: A Survey of Learning Methods.  ACM Computing Surveys, 50(2):21:1–21:35.
  * Jang et al., (2017) Jang, E., Gu, S., and Poole, B. (2017).  Categorical Reparameterization with Gumbel-Softmax.  In 5th International Conference on Learning Representations (ICLR 17).
  * Jaques et al., (2019) Jaques, N., Lazaridou, A., Hughes, E., Gulcehre, C., Ortega, P., Strouse, D., Leibo, J. Z., and Freitas, N. D. (2019).  Social Influence as Intrinsic Motivation for Multi-Agent Deep Reinforcement Learning.  In Proceedings of the 36th International Conference on Machine Learning, pages 3040–3049. PMLR.  ISSN: 2640-3498.
  * Kumar et al., (2022) Kumar, A., Hong, J., Singh, A., and Levine, S. (2022).  Should I Run Offline Reinforcement Learning or Behavioral Cloning?  In Proceedings of the International Conference on Learning Representations (ICLR 22).
  * Lazaridou and Baroni, (2020) Lazaridou, A. and Baroni, M. (2020).  Emergent Multi-Agent Communication in the Deep Learning Era.  arXiv:2006.02419 [cs].
  * Li et al., (2023) Li, Y., Zhang, S., Sun, J., Du, Y., Wen, Y., Wang, X., and Pan, W. (2023).  Cooperative Open-ended Learning Framework for Zero-Shot Coordination.  In Proceedings of the 40th International Conference on Machine Learning, pages 20470–20484. PMLR.  ISSN: 2640-3498.
  * Lowe et al., (2019) Lowe, R., Foerster, J., Boureau, Y.-L., Pineau, J., and Dauphin, Y. (2019).  On the Pitfalls of Measuring Emergent Communication.  In The 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
  * Maddison et al., (2017) Maddison, C. J., Mnih, A., and Teh, Y. W. (2017).  The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables.  In 5th International Conference on Learning Representations (ICLR 17), Palais des Congrès Neptune, Toulon, France.
  * Mirsky et al., (2020) Mirsky, R., Macke, W., Wang, A., Yedidsion, H., and Stone, P. (2020).  A Penny for Your Thoughts: The Value of Communication in Ad Hoc Teamwork.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pages 254–260. International Joint Conferences on Artificial Intelligence Organization.
  * Oliehoek and Amato, (2016) Oliehoek, F. A. and Amato, C. (2016).  A Concise Introduction to Decentralized POMDPs.  Springer International Publishing, Cham.  Series Title: SpringerBriefs in Intelligent Systems.
  * Ossenkopf, (2020) Ossenkopf, M. (2020).  CoMaze: A cooperative game for zero-shot coordination.  In The Emergent Communication Workshop at NeurIPS.
  * Sarratt and Jhala, (2015) Sarratt, T. and Jhala, A. (2015).  The Role of Models and Communication in the Ad Hoc Multiagent Team Decision Problem.  In Proceedings of the Third Annual Conference on Advances in Cognitive Systems.
  * Stone et al., (2010) Stone, P., Kaminka, G. A., Kraus, S., and Rosenschein, J. S. (2010).  Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination.  In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence.
  * Sukhbaatar et al., (2016) Sukhbaatar, S., Szlam, A., and Fergus, R. (2016).  Learning multiagent communication with backpropagation.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2252–2260, Barcelona, Spain. Neural Information Processing Systems.
  * Wagner et al., (2003) Wagner, K., Reggia, J. A., Uriagereka, J., and Wilkinson, G. S. (2003).  Progress in the Simulation of Emergent Communication and Language.  Adaptive Behavior, 11(1):37–69.  Publisher: SAGE Publications Ltd STM.
  * Yu et al., (2022) Yu, C., Velu, A., Vinitsky, E., Gao, J., Wang, Y., Bayen, A., and Wu, Y. (2022).  The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games.  In 36th Conference on Neural Information Processing Systems (NeurIPS 2022) Track on Datasets and Benchmarks., New Orleans, USA.

##  Appendix A Appendix

###  A.1 Environment Details

Goal Communications Gridworld. Each agent has a goal square in the grid that
they need to reach. At the start of each episode, this goal is sampled from a
uniform distribution over the squares. There are five actions: move up, down,
right, left, or stay put. Agents do not physically interact on the grid, and
so can be in the same positions. For each agent, if they have not reached
their goal then the team is deducted -1. When they reach the goal, a reward of
+1 is given, and if they have already reached it in the past then no penalty
or reward is given. An episode ends once all agents have reached their goals
or a time limit is reached. Each agent's observation is the concatenation of
the following vectors:

  * •

A binary vector of nine numbers, indicating if the goal is in one of the nine
squares near the agent.

  * •

One-hot encodings of the $(\hat{g}_{x},\hat{g}_{y})$ coordinates corresponding
to a `close guess' of another agent's goal. This close guess is sampled at the
start of an episode from a uniform distribution of locations within one tile
away from the true goal.

  * •

One-hot encodings of each of the $(p_{x},p_{y})$ position coordinates for each
agent in the environment.

(a) MAPPO hyperparameters for training teams on the gridworld problem. Hyperparameter | Value
---|---
Message dimension $(|\Sigma|)$ | $5$
Optimiser | Adam
Learning rate | $0.0005$
Adam Betas | (0.9, 0.999)
Gumbel-Softmax Temperature |  $2.0$ (no annealing)
SGD Minibatch Size | $2,048$
Training Batch Size | $10,000$
SGD Num Iterations | $5$
Value Function Clip Parameter | $10$
Value Function Loss Coef | $0.25$
Lambda (GAE/PPO) | $0.95$
KL Coef (PPO) | 0
$enc$ Hidden Layer Sizes | [256, 256]
$\pi^{e}$ Hidden Layer Sizes | [256]
$vf$ Hidden Layer Sizes | [256, 256]

(b) MAPPO hyperparameters for training teams on the driving problem. Hyperparameter | Value
---|---
Message dimension $(|\Sigma|)$ | $16$
Optimiser | Adam
Learning rate | $0.0005$
Adam Betas | (0.9, 0.999)
Gumbel-Softmax Temperature |  $5.0$ (no annealing)
SGD Minibatch Size | $2,048$
Training Batch Size | $200,000$
SGD Num Iterations | $10$
Value Function Clip Parameter | $10$
Value Function Loss Coef | $0.25$
Lambda (GAE/PPO) | $0.95$
KL Coef (PPO) | 0
$enc$ Hidden Layer Sizes | [256, 256]
$\pi^{e}$ Hidden Layer Sizes | [256]
$vf$ Hidden Layer Sizes | [256, 256]

For all experiments we keep the grid size fixed at $(5\times 5)$ and the
maximum number of timesteps at 10.

Goal Communications Driving Game. In this game, each agent steers and
accelerates a body in a continuous grid (Figure 1(c)). The agents must
navigate to one of eight fixed goal locations, known by their partner and
selected at random for each episode. Each agent observes the positions,
previous positions, angles, and velocities of all the agents, represented as
vectors $\mathds{R}^{2}$. Each agent observes the goal location of another
agent, giving rise to the need to communicate.

There are four actions that an agent can take: (1) turn clockwise by $\theta$
radians, (2) turn anti-clockwise by $\theta$ radians, (3) accelerate by $a$
units per second/second. The value $\theta$ is fixed at $\pi/8$ and $a$ at
1.0. Over each timestep, 0.2 seconds of simulated time elapse, i.e. the game
runs in `real-time' at 5 frames per second. The team has a maximum of 200
timesteps to complete the task, or the episode ends when all the goals have
been reached. There are two scenarios for this environment defined by the
presence or absence of a circular region called the `pit' in the centre of the
world where a large penalty is applied for every agent within the region.

Each agent's reward at each time step is computed from four components:

  1. 1.

$c_{pit}$ is the penalty for the agent being in the pit location, if the pit
scenario is selected.

  2. 2.

$\alpha\Delta d_{min}$, where $\Delta d_{min}$ is the change in closest
distance to the goal reached during the episode. $\alpha$ is a hyperparameter
set to 200. This term is zero if the distance to the goal is changing, but it
is also not given if the agent is in the pit. However, the `closest distance
to the goal' is still updated while in the pit, so the agent is penalised
directly and indirectly through the lost opportunity of being awarded the
bonus.

  3. 3.

$c_{time}$ is a penalty given at each time step to encourage completing the
task quickly. Set to a constant of 0.1.

  4. 4.

$r_{goal}$ is a bonus given for reaching the goal. It is set to 500.0 and only
awarded once at the timestep that the goal is reached.

After an agent has already reached its goal, it is always awarded zero reward
unless it is in the pit.

###  A.2 Training Hyperparameters

All reinforcement learning was done using RLlib and Pytorch. The
hyperparameters for MAPPO training in each environment can be found in Tables
1(a) and 1(b). Note the key differences being the temperature of the Gumbel-
Softmax communication channel, which was increased to improve learning, and
the size of the training batch that needed to dramatically increase. IL and
ECTL just use Pytorch for training and RLlib for evaluation. For IL both
components of the $\pi_{im}$ are feed-forward networks with hidden layer sizes
[256]. Likewise, for ECTL, both translation functions have hidden layer sizes
[256, 256]. The full hyperparameters for training with the different methods
are given in Table 2.

Table 2: Signalling/Listening training hyperparameters (for both IL and ECTL). Hyperparameter | Value
---|---
Optimiser | SGD with momentum
Learning rate | $0.001$
Momentum | 0.9
Minibatch Size | $1024$
Weight Decay | $1\times 10^{-5}$
Epochs | 1500

###  A.3 Evaluation Methodology

For evaluation on the CLAP-Replace tasks, we took each trained community and
used each permutation of teams to create joiner/target community pairs. We
trained joiner agents using IL and ECTL for each possible replaceable agent (2
agents in driving and 3 agents in gridworld), and then for each configuration
we conducted 3 trials and performed evaluations. Each configuration runs the
entire CLAP-Replace and training pipeline from scratch (i.e. independent data
collection and random seeds). Each trained joiner agent was then evaluated for
500 episodes in the zero-shot CLAP-Replace setting. For Figure 5(a), for each
sample along the $x$-axis (different $N_{collect}$ values), this entire
process was run. Thus there was 9 $N_{collect}$ samples $\times$ 2 community
permutations $\times$ 2 possible replacement agents $\times$ 3 trials, totally
432 training runs.

Figure 7: Training curves for one training run on the gridworld environment.
Figure 8: Training curves for one training run on the gridworld environment.
Figure 9: Training curves for one training run on the driving environment, in
the `pit' scenario. Figure 10: Training curves for one training run on the
driving environment, in the `pit' scenario. Figure 11: Training curves for one
training run on the driving environment, in the `no pit' scenario. Figure 12:
Training curves for one training run on the driving environment, in the `no
pit' scenario.