ifaamas [AAMAS ’22]Proc. of the 21st International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2022)May 9–13, 2022 Auckland, New
ZealandP. Faliszewski, V. Mascardi, C. Pelachaud, M.E. Taylor (eds.) 2022 2022
385 INESC-ID and Instituto Superior Técnico Lisbon Portugal Instituto Superior
Técnico Lisbon Portugal INESC-ID and Instituto Superior Técnico Lisbon
Portugal INESC-ID and Instituto Superior Técnico Lisbon Portugal

# Assisting Unknown Teammates in Unknown Tasks:
Ad Hoc Teamwork under Partial Observability

João G. Ribeiro<EMAIL_ADDRESS>,  Cassandro Martinho
<EMAIL_ADDRESS>,  Alberto Sardinha
<EMAIL_ADDRESS>and  Francisco S. Melo  fmelo@inesc-
id.pt

###### Abstract.

In this paper, we present a novel Bayesian online prediction algorithm for the
problem setting of ad hoc teamwork under partial observability (ATPO), which
enables on-the-fly collaboration with unknown teammates performing an unknown
task without needing a pre-coordination protocol. Unlike previous works that
assume a fully observable state of the environment, ATPO accommodates partial
observability, using the agent’s observations to identify which task is being
performed by the teammates. Our approach assumes neither that the teammate’s
actions are visible nor an environment reward signal. We evaluate ATPO in
three domains—two modified versions of the Pursuit domain with partial
observability and the overcooked domain of Carroll et al. (2019). Our results
show that ATPO is effective and robust in identifying the teammate’s task from
a large library of possible tasks, efficient at solving it in near-optimal
time, and scalable in adapting to increasingly larger problem sizes.

###### Key words and phrases:

Ad Hoc Teamwork, Partially Observable Markov Decision Processes, Multi-Agent
Systems

##  1\. Introduction

The problem of ad hoc teamwork was first proposed by Stone et al. (2010b), and
considers an autonomous agent (the “ad hoc agent”) deployed into an existing
group of “teammates”, with whom it must engage in teamwork while having no
pre-established communication or coordination protocols. Previous works on ad
hoc teamwork rely on strong assumptions regarding the interaction between the
“ad hoc agent” and the “teammates”. For example, Barrett et al. (2017); Hu et
al. (1998); Bu et al. (2008) consider that a reward signal is available to the
agents to learn from, casting the problem of ad hoc teamwork as a
specialization of multiagent RL. Other works do not consider an RL setting,
instead, assuming that the team is performing one among a set of possible
tasks, and use the observed teammate behavior to infer the target task (Melo
and Sardinha, 2016; Fern et al., 2007). Closest to our work, Ribeiro et al.
(2021) recently proposed an approach to ad hoc teamwork where the actions of
the teammates are not assumed observable; however, the underlying state of the
environment is.

Full state observability is a strong assumption within the ad hoc teamwork
setting, as it significantly restricts the applicability of such an approach
to very narrow settings. Either all tasks share the state space and dynamics
(and thus differ only in their goal) or —if the dynamics are different—such
differences greatly facilitate identifying the underlying task.

In this paper, we address ad hoc teamwork with partial observability. In this
setting, the “ad hoc agent” can only access a limited view of the environment
state and must (i) infer what the underlying target task may be; (ii) infer
how the teammates are playing it; (iii) plan how to coordinate with the
“teammates”. Moreover, the agent cannot observe the actions of the teammates
nor communicate with them.

The setting of ad hoc teamwork with partial observability significantly
broadens the applicability of ad hoc teamwork in real-world scenarios. It
allows for a much richer set of possible tasks, with widely different dynamics
and states that need only to share the perceptual space of the ad hoc agent.
It is, therefore, suited to address tasks involving ad hoc robotic agents,
accommodating the natural perceptual limitations of robotic platforms (Genter
et al., 2017).

To address partial observability, we build a model that encapsulates the
“perceptual dynamics” associated with each task and use the history of
observations of the agent to estimate which of the set of possible tasks best
matches such perceptual dynamics. Our results in several benchmark multiagent
problems from the literature illustrate that our approach, ATPO (Ad hoc
Teamwork with Partial Observability), can correctly infer the underlying task
and coordinate with the teammates.

In summary, our contributions are threefold:

  * •

We contribute the formalization of ad hoc teamwork under partial
observability;

  * •

We propose ATPO, a novel approach for ad hoc teamwork with partial
observability that infers the underlying target task from the agent’s history
of observations;

  * •

We illustrate the applicability of our approach in two partially observable
variants of pursuit and in Overcooked, a recent benchmark for multiagent
systems (Carroll et al., 2019).

###  1.1. Related Work

Since the seminal work of Stone et al. (2010b), ad hoc teamwork has been under
great attention by the multi-agent systems community. However, in a setting
where the main challenges consist on assisting unknown teammates in performing
unknown tasks, early works assumed the ad hoc agent knew the target task and
the teammates’ behavior (Stone and Kraus, 2010; Stone et al., 2010a; Agmon and
Stone, 2012; Genter et al., 2013; Chakraborty and Stone, 2013) (reducing the
problem to one of planning).

It wasn’t until later on that Melo and Sardinha (2016) formalized ad hoc
teamwork by breaking it down into three sub-problems (task identification,
teammate identification and planning) and allowing authors to specify in their
work which they were tackling. Following Melo and Sardinha (2016), Barrett et
al. (2017) introduced the PLASTIC framework (Barrett et al., 2017; Barrett and
Stone, 2015), where the authors learn predictive models of the teammates by
observing their actions and policies for the tasks via trial-and-error
(assuming the environment provides a reward signal). Both assumptions (visible
teammate actions and available reward signals), however, limit their approach
from being deployed in real-world scenarios.

Ribeiro et al. (2021) later on tackle these limitation by assuming instead
that neither the actions nor the reward signals are available, and instead
that the ad hoc agent access to a set of possible tasks and teammates. The
authors showcase how by only having access to the state of the environment,
the ad hoc agent is able to infer the most likely task/teammate combination.
Once more, the assumption that the environment is fully observable will seldom
be met in practice since ad hoc agents in the real world will often be plagued
by issues of partial observability.

Three similar (yet different) lines of work, parallel to ad hoc teamwork, are
the framework of assistance (Fern et al., 2007), the problem of zero-shot
coordination (Hu et al., 2020) and the IPOMDP framework (Gmytrasiewicz and
Doshi, 2005). The framework of assistance (Fern et al., 2007) models a
scenario where an agent must help a teammate in solving a given sequential
task under uncertainty. The goal, however, is for an agent to assist unknown
teammates in performing known tasks. Even though the authors do not refer to
the problem as ad hoc teamwork, one could argue that the identification of
unknown teammates with known tasks falls under the scope of ad hoc teamwork.
In their work, however, Fern et al. (2007) also consider that the teammate’s
actions to be accessible to the assistant. The problem of zero-shot
coordination (Hu et al., 2020), unlike in ad hoc teamwork, studies how
independently trained agents may interact with one another on first-attempt
(Lupu et al., 2021; Treutlein et al., 2021; Bullard et al., 2021) (therefore
falling out of the scope of ad hoc teamwork). Finally, the IPOMDP framework
(Gmytrasiewicz and Doshi, 2005), considers how an agent can augment the state
space of a POMDP taking into account all possible, unknown, teammates. Not
only does this approach grow exponentially with the number of possible
teammates, but, similar to the framework of assistance, it also assumes that
all teammates perform the same task (modeled by a single reward function). In
their work, however, (Gmytrasiewicz and Doshi, 2005), the authors do not
assume that the teammates’ actions are visible to the agent, therefore sharing
a common assumption with our work. Unlike Gmytrasiewicz and Doshi (2005), we
expand upon Melo and Sardinha (2016) and Ribeiro et al. (2021), introducing an
approach capable of explicitly identifying the teammate behavior and the
tasks’ goal by describing the set of possible tasks as a partially observable
Markov decision problem and using a Bayesian approach to map the history of
observations of the ad hoc agent into a belief over the set of possible tasks
and possible teammates (growing linearly with the number of possible teammates
and tasks instead of exponentially like IPOMDPs).

##  2\. Background

In this work, we address ad hoc teamwork under partial observability using a
decision-theoretic framework. This section introduces some key concepts and
sets up the nomenclature regarding Markov decision problems and related
models.

###  2.1. Markov decision problems

A Markov decision problem (Puterman, 2005), or MDP, is denoted as a tuple
$(\mathcal{X},\mathcal{A},\left\\{\mathbf{P}_{a},a\in\mathcal{A}\right\\},r,\gamma)$,
where $\mathcal{X}$ is the state space, $\mathcal{A}$ is the action space,
$\mathbf{P}_{a}$ is a transition probability matrix, where
$\mathbf{P}_{a}(x^{\prime}\mid x)$ is probability of moving from state $x$ to
$x^{\prime}$ given action $a\in\mathcal{A}$, $r$ is the expected reward
function, and $\gamma\in[0,1]$ is a discount factor.

A policy $\pi$ maps states to distributions over actions. We write $\pi(a\mid
x)$ to denote the probability of selecting action $a$ in state $x$ according
to policy $\pi$. Solving an MDP consists of determining a policy $\pi$ to
maximize the value

$v^{\pi}(x)\triangleq\mathbb{E}_{A_{t}\sim\pi(X_{t})}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\mid
X_{0}=x\right],$ (1)

for any initial state $x\in\mathcal{X}$. In the above expression, $X_{t}$,
$A_{t}$ and $R_{t}$ denote the (random) state, action and reward at time step
$t$. The function $v^{\pi}:\mathcal{X}\to\mathds{R}$ is called a value
function, and a policy $\pi^{*}$ is optimal if, given any policy $\pi$,
$v^{\pi^{*}}(x)\geq v^{\pi}(x)$, for all $x\in\mathcal{X}$. The value function
associated with an optimal policy is denoted as $v^{*}$ and can be computed
using, for example, dynamic programming. An optimal policy, $\pi^{*}$, is such
that $\pi^{*}(a\mid x)>0$ only if $a\in\operatorname{\rm
argmax}q^{*}(x,\cdot)$, where

$q^{*}(x,a)=r(x,a)+\gamma\sum_{x^{\prime}\in\mathcal{X}}\mathbf{P}_{a}(x^{\prime}\mid
x)v^{*}(x^{\prime}).$

###  2.2. Multiagent Markov decision problems

A multiagent MDP (MMDP) is an extension of MDPs to multiagent settings and can
be described as a tuple

$\mathcal{M}=(N,\mathcal{X},\left\\{\mathcal{A}^{n},n=1,\ldots,N\right\\},\left\\{\mathbf{P}_{{\boldsymbol{a}}},{\boldsymbol{a}}\in\mathcal{A}\right\\},r,\gamma),$

where $N$ is the number of agents, $\mathcal{X}$ is the state space,
$\mathcal{A}^{n}$ is the individual action space for agent $n$,
$\mathbf{P}_{{\boldsymbol{a}}}$ is the transition probability matrix
associated with joint action ${\boldsymbol{a}}$, $r$ is the expected reward
function, and $\gamma$ is the discount. We write $\mathcal{A}$ to denote the
set of all joint actions, corresponding to the Cartesian product of all
individual action spaces $\mathcal{A}^{n}$, i.e.,
$\mathcal{A}=\mathcal{A}^{1}\times\mathcal{A}^{2}\times\ldots\times\mathcal{A}^{N}$.
We also denote an element of $\mathcal{A}^{n}$ as $a^{n}$ and an element of
$\mathcal{A}$ as a tuple ${\boldsymbol{a}}=(a^{1},\ldots,a^{N})$, with
$a^{n}\in\mathcal{A}^{n}$. We write ${\boldsymbol{a}}^{-n}$ to denote a
reduced joint action, i.e., a tuple
${\boldsymbol{a}}^{-n}=(a^{1},\ldots,a^{n-1},a^{n+1},\ldots,a^{N})$, and thus
$\mathcal{A}^{-n}$ is the set of all reduced joint actions. We adopt, for
policies, a similar notation. Specifically, we write $\pi^{n}$ to denote an
individual policy for agent $n$, ${\boldsymbol{\pi}}=(\pi^{1},\ldots,\pi^{N})$
to denote a joint policy, and ${\boldsymbol{\pi}}^{-n}$ to denote a reduced
joint policy.

The common goal of the agents in an MMDP is to select a joint policy,
${\boldsymbol{\pi}}^{*}$, such that $v^{{\boldsymbol{\pi}}^{*}}(x)\geq
v^{{\boldsymbol{\pi}}}(x)$, where, as before,

$v^{{\boldsymbol{\pi}}}(x)=\mathbb{E}_{{\boldsymbol{A}}_{t}\sim{\boldsymbol{\pi}}(X_{t})}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\mid
X_{0}=x\right].$ (2)

In other words, an MMDP is just an MDP in which the action selection process
is distributed across $N$ agents, and can be solved by computing
${\boldsymbol{\pi}}^{*}$ from $v^{*}$ as standard MDPs.

###  2.3. Partially observable MDPs

A partially observable MDP, or POMDP, is an extension of MDPs to partially
observable settings. A POMDP can be described as a tuple
$(\mathcal{X},\mathcal{A},\mathcal{Z},\left\\{\mathbf{P}_{a},a\in\mathcal{A}\right\\},\left\\{\mathbf{O}_{a},a\in\mathcal{A}\right\\},r,\gamma)$,
where $\mathcal{X}$, $\mathcal{A}$,
$\left\\{\mathbf{P}_{a},a\in\mathcal{A}\right\\}$, $r$, and $\gamma$, are the
same as in MDPs, $\mathcal{Z}$ is the observation space, and $\mathbf{O}_{a}$
is the observation probability matrix, where

$\mathbf{O}_{a}(z\mid x)=\mathbb{P}\left[Z_{t+1}=z\mid
X_{t+1}=x,A_{t}=a\right].$

The belief at time step $t$ is a distribution ${\boldsymbol{b}}_{t}$ such that

$b_{t}(x)\triangleq\mathbb{P}\left[X_{t}=x\mid
X_{0}\sim{\boldsymbol{b}}_{0},A_{0}=a_{0},Z_{1}=z_{1},\ldots,Z_{t}=z_{t}\right],$

where ${\boldsymbol{b}}_{0}$ is the initial state distribution. Given the
action $a_{t}$ and the observation $z_{t+1}$, we can update the belief $b_{t}$
to incorporate the new information yielding

$\begin{split}b_{t+1}(x^{\prime})&=\mathrm{Bel}(b_{t},a_{t},z_{t+1})\\\
&\triangleq\frac{1}{\rho_{t+1}}\sum_{x\in\mathcal{X}}b_{t}(x)\mathbf{P}(x^{\prime}\mid
x,a_{t})\mathbf{O}(z_{t+1}\mid x^{\prime},a_{t}),\end{split}$ (3)

where $\rho_{t+1}$ is a normalization factor. Every finite POMDP admits an
equivalent belief-MDP with $b_{t}$ being the state of this new MDP at time
step $t$. A policy in a POMDP can thus be seen as mapping $\pi$ from beliefs
to distributions over actions, and we define

$v^{\pi}(b)\triangleq\mathbb{E}_{A_{t}\sim\pi(b_{t})}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\mid
b_{0}=b\right].$ (4)

As in MDPs, the value function associated with an optimal policy is denoted as
$v^{*}$ and can be computed using, for example, point-based approaches (Pineau
et al., 2006). From $v^{*}$, the optimal $Q$-function can now be computed as

$q^{*}(b,a)=\sum_{x\in\mathcal{X}}b(x)\Bigg{[}r(x,a)\\\ \
+\gamma\sum_{z\in\mathcal{Z}}\sum_{y\in\mathcal{X}}\mathbf{P}(y\mid
x,a)\mathbf{O}(z\mid y,a)v^{*}(\mathrm{Bel}(b,a,z))\Bigg{]},$

yielding as optimal any policy $\pi^{*}$ such that $\pi^{*}(a\mid b)>0$ only
if $a\in\operatorname{\rm argmax}_{a\in\mathcal{A}}q^{*}(b,a)$.

##  3\. Ad Hoc Teamwork under Partial Observability

In this section, we introduce our key contributions to ad hoc teamwork under
partial observability.

###  3.1. Problem formulation

We consider a team of $N$ agents engaged in a cooperative task (henceforth
referred as “target task”), described as an MMDP
$m=(N,\mathcal{X},\left\\{\mathcal{A}_{n}\right\\},\left\\{\mathbf{P}_{a}\right\\},r,\gamma)$.
One of the agents (the focus of our work) does not know the task beforehand
but must, nevertheless, engage in ad hoc teamwork with the remaining agents to
complete the unknown task. We refer to such agent as the “ad hoc agent” and
denote it as $\alpha$, and refer to the remaining $N-1$ agents collectively as
the “teammates”. Formally, we treat the teammates as a “meta-agent” and denote
it as $-\alpha$.

We assume that the teammates all know the target task. The ad hoc agent,
however, does not. Instead, it knows only that the target task is one among
$K$ possible tasks, where each task can be represented as an MMDP

$m_{k}=(2,\mathcal{X}_{k},\left\\{\mathcal{A}^{\alpha},\mathcal{A}_{k}^{-\alpha}\right\\},\left\\{\mathbf{P}_{k,{\boldsymbol{a}}},{\boldsymbol{a}}\in\mathcal{A}\right\\},r_{k},\gamma_{k}).$
(5)

Note that we require the action space of the ad hoc agent,
$\mathcal{A}^{\alpha}$, to be the same in all tasks. Other than that, we
impose no restrictions on the state space, dynamics, or reward describing
these tasks (in particular, they may all be different).

Let $\pi^{-\alpha}_{k}$ denote a teammates optimal policy for task
$k,k=1,\ldots,K$. Then, for task $k$, we have

$\mathbf{P}_{k}(y\mid x,a^{\alpha})\triangleq\mathbb{P}[X_{t+1}=y\mid
X_{t}=x,A^{\alpha}=a^{\alpha},\\\
A^{-\alpha}\sim\pi^{-\alpha}_{k}(x),M=m_{k}],$ (6)

for $x,y\in\mathcal{X}_{k}$, where we write $M=m_{k}$ to denote the fact that
the transitions in (6) concerns task $k$.

Let us now suppose that, at each moment, the ad hoc agent cannot observe the
underlying state of the environment. Instead, at each time step $t$, the agent
can only access an observation $Z_{t}$. We assume that the observations
$Z_{t}$ take values in a (task-independent) set $\mathcal{Z}$ and depend both
on the underlying state of the environment and the previous action of the
agent (not the teammates). Specifically, for each task $k=1,\ldots,K$, we
assume that there is a family of task-dependent observation probability
matrices,
$\mathbf{O}_{k,a^{\alpha}},k=1,\ldots,K,a^{\alpha}\in\mathcal{A}^{\alpha}$,
with

$\mathbf{O}_{k}(z\mid x,a^{\alpha})=\mathbb{P}\left[Z_{t}=z\mid
X_{t}=x,A^{\alpha}_{t-1}=a^{\alpha},M=m_{k}\right].$ (7)

The elements $[\mathbf{O}_{k,a}]_{xz}$ are only defined for
$x\in\mathcal{X}_{k}$. Thus, from the ad hoc agent’s perspective, each task
$k$ defines a POMDP $\hat{m}_{k}$ corresponding to the tuple

$(\mathcal{X}_{k},\mathcal{A}^{\alpha},\mathcal{Z},\left\\{\mathbf{P}_{k,a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\},\left\\{\mathbf{O}_{k,a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\},r_{k},\gamma_{k}).$

We denote the solution to $\hat{m}_{k}$ as $\hat{\pi}_{k}$.

###  3.2. Algorithm

We adopt a Bayesian framework and treat the target task as a random variable,
$M$, taking values in the set of possible MMDP task descriptions,
$\mathcal{M}=\left\\{m_{1},\ldots,m_{K}\right\\}$. For $m_{k}\in\mathcal{M}$,
let $p_{0}(m_{k})$ denote the ad hoc agent’s prior over $\mathcal{M}$.
Additionally, let $H_{t}$ denote the random variable corresponding to the
history of the agent up to time step $t$, defined as

$H_{t}=\left\\{a^{\alpha}_{0},z_{1},a^{\alpha}_{1},z_{2},\ldots,a^{\alpha}_{t-1},z_{t}\right\\}.$
(8)

Then, given a history $h_{t}$, we define

$p_{t}(m_{k})\triangleq\mathbb{P}\left[M=m_{k}\mid H_{t}=h_{t}\right],\qquad
m_{k}\in\mathcal{M}.$ (9)

The distribution $p_{t}$ corresponds to the agent’s belief about the target
task at time step $t$. The action for the ad hoc agent at time step $t$ can be
computed within our Bayesian setting as

$\pi_{t}(a^{\alpha}\mid
h_{t})\triangleq\mathbb{P}\left[A^{\alpha}_{t}=a^{\alpha}\mid
H_{t}=h_{t}\right]=\sum_{k=1}^{K}\hat{\pi}_{k}(a^{\alpha}\mid
b_{k,t})p_{t}(m_{k}),$

where

$b_{k,t}(x)\triangleq\mathbb{P}\left[X_{t}=x\mid H_{t}=h_{t},M=m_{k}\right],$
(10)

for $x\in\mathcal{X}_{k}$. Upon selecting an action $a^{\alpha}_{t}$ and
making a new observation $z_{t+1}$, we can update $p_{t}$ by noting that

$\displaystyle p_{t+1}(m_{k})$ $\displaystyle=\mathbb{P}\left[M=m_{k}\mid
H_{t+1}=\left\\{h_{t},a^{\alpha}_{t},z_{t+1}\right\\}\right]$
$\displaystyle=\frac{1}{\rho}\mathbb{P}\left[A^{\alpha}_{t}=a^{\alpha}_{t},Z_{t+1}=z_{t+1}\mid
M=m_{k},H_{t}=h_{t}\right]$ $\displaystyle\hskip
85.35826pt\cdot\mathbb{P}\left[M=m_{k}\mid H_{t}=h_{t}\right]$
$\displaystyle=\frac{1}{\rho}\mathbb{P}\left[A^{\alpha}_{t}=a^{\alpha}_{t},Z_{t+1}=z_{t+1}\mid
M=m_{k},H_{t}=h_{t}\right]p_{t}(m_{k}),$

where $\rho$ is some normalization constant. Moreover,

$\displaystyle\mathbb{P}\left[A^{\alpha}_{t}=a^{\alpha}_{t},Z_{t+1}=z_{t+1}\mid
M=m_{k},H_{t}=h_{t}\right]$ $\displaystyle=\mathbb{P}\left[Z_{t+1}=z_{t+1}\mid
A^{\alpha}_{t}=a^{\alpha}_{t},H_{t}=h_{t},M=m_{k}\right]$ $\displaystyle\hskip
85.35826pt\cdot\mathbb{P}\left[A^{\alpha}_{t}=a^{\alpha}_{t}\mid
H_{t}=h_{t},M=m_{k}\right]$
$\displaystyle=\sum_{y\in\mathcal{X}_{k}}\mathbf{O}_{k}(z_{t+1}\mid
y,a^{\alpha}_{t})$ $\displaystyle\quad\cdot\mathbb{P}\left[X_{t+1}=y\mid
A^{\alpha}_{t}=a^{\alpha}_{t},H_{t}=h_{t},M=m_{k}\right]\pi_{t}(a^{\alpha}\mid
h_{t}),$

where the last equality follows from the fact that the agent’s action
selection given the history does not depend on the task $M$. Therefore,

$\displaystyle\mathbb{P}\left[A^{\alpha}_{t}=a^{\alpha}_{t},Z_{t+1}=z_{t+1}\mid
M=m_{k},H_{t}=h_{t}\right]$
$\displaystyle=\sum_{x,y\in\mathcal{X}_{k}}\mathbf{O}_{k}(z_{t+1}\mid
y,a^{\alpha}_{t})\mathbf{P}_{k}(y\mid
x,a^{\alpha}_{t})b_{k,t}(x)\pi_{t}(a^{\alpha}\mid h_{t}).$

Putting everything together, we get

$p_{t+1}(m_{k})=\frac{1}{\rho}\sum_{x,y\in\mathcal{X}_{k}}\mathbf{O}_{k}(z_{t+1}\mid
y,a^{\alpha}_{t})\\\ \cdot\mathbf{P}_{k}(y\mid
x,a^{\alpha}_{t})b_{k,t}(x)\pi_{t}(a^{\alpha}\mid h_{t})p_{t}(m_{k}),$ (11)

with

$\rho=\sum_{k=1}^{K}\sum_{x,y\in\mathcal{X}_{k}}\mathbf{O}_{k}(z_{t+1}\mid
y,a^{\alpha}_{t})\\\ \cdot\mathbf{P}_{k}(y\mid
x,a^{\alpha}_{t})b_{k,t}(x)\pi_{t}(a^{\alpha}\mid h_{t})p_{t}(m_{k}).$

Note that the update (11) requires the ad hoc agent to keep track of the
beliefs $b_{k,t}$ for the different POMDPs $\hat{m}_{k}$. In other words, at
each time step $t$, upon executing its individual action $a^{\alpha}_{t}$ and
observing $z_{t+1}$, the agent updates each belief $b_{k,t}$ using (3),
yielding

$b_{k,t+1}(y)=\frac{1}{\rho}\sum_{x\in\mathcal{X}_{k}}b_{t,k}(x)\mathbf{P}_{k}(y\mid
x,a^{\alpha}_{t})\mathbf{O}_{k}(z_{t+1}\mid y,a^{\alpha}_{t}),$ (12)

where $\rho$ is the corresponding normalization constant. Since some of the
computations in the update (11) are common to the update (12), some
computational savings can be achieved by caching the intermediate values.

Finally, at each time step $t$, we define the loss for selecting an action
$a^{\alpha}\in\mathcal{A}^{\alpha}$ when the target task is $m_{k}$ to be

$\ell_{t}(a^{\alpha}\mid
m_{k})=v^{\hat{\pi}_{k}}(b_{k,t})-q^{\hat{\pi}_{k}}(b_{k,t},a^{\alpha}),$ (13)

where $\hat{\pi}_{k}$ is the solution to the POMDP $\hat{m}_{k}$.

It is important to note that both $v^{\hat{\pi}_{k}}(b_{k,t})$ and
$q^{\hat{\pi}_{k}}(b_{k,t},a^{\alpha})$ can be computed from
$\hat{v}^{\hat{\pi}_{k}}$ at runtime, while the latter can be computed offline
when solving the POMDP $\hat{m}_{k}$. Note also that $\ell_{t}(a^{\alpha}\mid
m_{k})\geq 0$ for all $a^{\alpha}$, and $\ell_{t}(a^{\alpha}\mid m_{k})=0$
only if $\hat{\pi}_{k}(a^{\alpha}\mid b_{k,t})>0$.

###  3.3. Loss bounds for ATPO

We conclude this section by providing a bound on the loss incurred by our
approach. The bound can be derived from a standard compression lemma from
Banerjee (2006), by comparing the performance of an agent using an arbitrary
constant distribution over tasks. Let $p$ denote a distribution over
$\mathcal{M}$, and define

$\displaystyle L_{t}(p)$
$\displaystyle=\sum_{k=1}^{K}p(m_{k})\ell_{t}(\hat{\pi}_{k}\mid m^{*}),$

where $m^{*}$ is the (unknown) target task, and

$\ell_{t}(\hat{\pi}_{k}\mid
m^{*})=\sum_{a^{\alpha}\in\mathcal{A}^{\alpha}}\hat{\pi}_{k}(a^{\alpha}\mid
b_{k,t})\ell_{t}(a^{\alpha}\mid m^{*}).$

We have the following result.

###### Proposition

Let $q$ denote an arbitrary stationary distribution over the tasks in
$\mathcal{M}$, and $\left\\{p_{t}\right\\}$ the sequence of beliefs over tasks
generated by ATPO. Then,

$\sum_{t=0}^{T-1}L_{t}(p_{t})\leq\sum_{t=0}^{T-1}L_{t}(q)+\sqrt{\frac{2}{T}}\sum_{t=0}^{T-1}\mathrm{KL}(q\parallel
p_{t})+\sqrt{\frac{T}{2}}\cdot\frac{R_{\max}^{2}}{(1-\gamma)^{2}}.$ (14)

Due to space limitations, we include the proof in Appendix A.
Unsurprisingly—and aside from the term
$\sqrt{\frac{T}{2}}\cdot\frac{R_{\max}^{2}}{(1-\gamma)^{2}}$, which is
independent of $q$ and grows sublinearly with $T$—the bound in (14) states
that the difference between the performance of ATPO and that obtained using a
constant distribution (for example, the distribution concentrated on $m^{*}$)
is similar to those reported by Banerjee (2006) for Bayesian online prediction
with bounded loss, noting that

$\sum_{t=0}^{T-1}\mathrm{KL}(q\parallel
p_{t})=\mathrm{KL}({\boldsymbol{q}}\parallel{\boldsymbol{p}}_{0:T-1}),$ (15)

where we write ${\boldsymbol{q}}$ and ${\boldsymbol{p}}_{0:T-1}$ refer to
distributions over sequences in $\mathcal{M}^{T}$.

(a) The Night-time Pursuit domain. Two predators must simultaneously capture
two sleeping preys.

(b) Pursuit under partial observability. Two predators must surround a moving
prey. One of the predators has limited perception.

(c) The Overcooked domain (Carroll et al., 2019).

Figure 1. The three domains used in the experiments.

##  4\. Evaluation

In order to evaluate ATPO, we ran several experiments to respond to the
following questions:

  1. (1)

How does ATPO compare with the optimal teammate in terms of task performance?

  2. (2)

How does ATPO scale with: (i) the size of the underlying problem? (ii) the
number of tasks in $\mathcal{M}$?

  3. (3)

How well is ATPO able to deal with the uncertainty in both transitions and
observations?

To answer these questions, we assess the performance of ATPO in three
different environments, namely the Night-time Pursuit, the Pursuit under
partial observability, and the Overcooked domain. Given the easy
parameterization of the Night-time Pursuit, we used it to answer all the
questions above. Furthermore, we used the other environments to complement the
Night-time Pursuit in addressing Question (1).

###  4.1. Test environments

In our experiments, we consider three distinct environments.

  * •

The Night-time Pursuit domain. In this environment, two predators must capture
two sleeping preys (see Fig. 1(a)). The preys do not change their position,
and the predators must coordinate regarding which predator captures each prey.
The ad hoc agent can only observe the neighboring cells. The position of the
preys is not encoded in the state. Rather, the different tasks in
$\mathcal{M}$ correspond to different configurations of the sleeping preys.
Given its easy parameterization, we use this domain to evaluate the dependence
of the performance of the different methods with different environment
configurations.

  * •

Pursuit under partial observability. This environment is a modification of the
standard Pursuit domains to include only two predators and one moving prey
(see Fig. 1(b). The perception of the ad hoc agent deteriorates with the
distance to its position: cells further away are observed with higher
uncertainty than the cells closer to the agent. The different tasks in
$\mathcal{M}$ correspond to different capturing behaviors of the teammate.

  * •

The Overcooked domain. This domain is depicted in Fig. 1(c). In this
environment, two cooks must coordinate to fetch the necessary ingredients to
produce a soup. The scenario was proposed by (Carroll et al., 2019) as a
benchmark to evaluate cooperation. However, it does not feature partial
observability. The different tasks correspond to different roles that the
teammate can assume.

We provide detailed descriptions of the different scenarios in Appendix B.

###  4.2. Baselines

We compare ATPO with different baseline agents in each domain, deploying each
baseline agent to act as the ad hoc agent. We consider the following
baselines:

  * •

Value Iteration: The Value Iteration agent knows the target task and can
perfectly observe the current state of the environment. It follows the optimal
policy for the associated MMDP, computed using value iteration. The
performance of this agent can be considered as an upper bound to ATPO.

  * •

Perseus: The Perseus agent knows the target task, but suffers from partial
observability. It follows the optimal policy for the target POMDP computed
using Perseus (Spaan and Vlassis, 2005b). The performance of this agent can
also be considered as an upper bound to ATPO.

  * •

Bayes Online Prediction for Ad hoc teamwork (BOPA): The BOPA agent corresponds
to the ad hoc algorithm of Ribeiro et al. (2021). To handle partial
observability, we adopt the most-likely state heuristic, where the state with
the highest belief in each task is considered the current state. This baseline
cannot be used in scenarios where different tasks have different state spaces.

  * •

Assistant: The Assistant agent corresponds to the algorithm of Fern et al.
(2007) for assistive tasks. It can be seen as an ad hoc algorithm where the
agent can observe the actions of the teammate.

  * •

Random Policy: This agent selects actions randomly. The performance of this
agent can be considered as a lower bound to ATPO and the other agents.

###  4.3. Metrics

To answer the questions outlined at the beginning of this section, we consider
four different metrics. First, Effectiveness, measuring whether ATPO can
identify the correct task. Second, Efficiency, measuring whether an agent can
solve the task in near-optimal time. Third, Robustness, assessing the
performance of the agent as a function of the noise in the environment,
$\varepsilon$.111A higher noise increases the uncertainty in both state
transitions and observations. Finally, scalability, measuring the dependence
of the agent’s performance on the problem size and the number of tasks in
$\mathcal{M}$.

(a) Average steps to solve a task for each agent.

(b) Task likelihood averaged over all trials. The likelihood of the correct
task is marked in green, while those of other tasks are marked in red.

Figure 2. Performance in the baseline configuration for the Night-time Pursuit
domain.

(a) Task performance as a function of $\left\lvert\mathcal{X}\right\rvert$.

(b) Task performance as a function of $\varepsilon$.

(c) Task performance as a function of $\left\lvert\mathcal{M}\right\rvert$.

Figure 3. Results on the Night-time Pursuit domain, as we vary
$|\mathcal{X}|$, $\varepsilon$ and $|\mathcal{M}|$ around their baseline
values.

In all experiments, the reported values consist of averages and $95\%$
confidence intervals over $32$ independent trials, where a single trial
consists of running on a given task over a finite horizon. We consider a task
from the Pursuit domains complete whenever the interaction reaches a horizon
of 50 timesteps and a task from the Overcooked domain complete whenever the
interaction reaches a horizon of 75 timesteps.

##  5\. Results

We now discuss the results of our experiments. Due to its simplicity and ease
of interpretation, we use the Night-time pursuit domain for a more extensive
evaluation of the different approaches. We then complete our evaluation by
reporting the comparative performance of ATPO in the other two domains.

###  5.1. Night-time Pursuit Domain

In this scenario, our baseline environment configuration is such that
$|\mathcal{X}|=625$, $\varepsilon=0.30$ and $|\mathcal{M}|=4$. For each of the
possible tasks in $\mathcal{M}$, we run 32 independent trials. Figure 2(a)
plots, by agent, the number of steps it takes each agent to solve the target
task and ATPO’s belief over tasks, averaged over the 128 trials and with a
$95\%$ confidence intervals.

As expected, Value Iteration achieved the best results. Conversely, the random
policy achieved the worst results. Our approach, ATPO, stands between Perseus
and BOPA agents because Perseus has more information (i.e., it knows the
target task) and BOPA discards important history information by considering
only the most likely state. We also observe that ATPO can pinpoint the target
task quite efficiently.

We then compare the performance of the different ad hoc agents as we vary each
of the three environment parameters around the baseline configuration. We vary
$\left\lvert\mathcal{X}\right\rvert$ between $81$ states (in a $3\times 3$
world) and $1,296$ states (in a $6\times 6$ world), $\varepsilon$ between
$0.0$ and $0.5$, and $\left\lvert\mathcal{M}\right\rvert$ between 1 and 10. We
run 32 independent trials for each configuration, where the task library and
target task are randomly selected from a pool of 32 possible tasks. The
results are depicted in Fig. 3.

The results also correspond to what we expected. In terms of task performance
(Fig. 3(a)), all methods scale gracefully as the problem size increases. In
particular, the relative performance of all methods remains mostly the same,
with some methods (such as BOPA) showing larger degradation than the other
methods due to the higher state uncertainty expected as the state space
increases. Similar observations can be made regarding the dependence on
$\varepsilon$ (Fig. 3(b)). Once again, BOPA presents larger degradation
because—as the noise increases—it is less capable of tracking the underlying
state. In both cases, the performance of ATPO is slightly worse than the two
more informed agents (Perseus and Value Iteration) and better than the other
baselines (BOPA and random agents).

Finally, when analyzing the dependence on
$\left\lvert\mathcal{M}\right\rvert$, we compare only BOPA and ATPO, since
these are the only two algorithms that consider the existence of multiple
tasks. As observed in Fig. 3(c), the performance of both algorithms shows some
slight decay as $\left\lvert\mathcal{M}\right\rvert$ increases, since it will
take more observations for the ad hoc agent to identify the target task.

To conclude our analysis of the Night-time Pursuit domain, we measured the
online and offline computation effort required by the different methods. The
results are depicted in Fig. 4.

(a) Total setup time for the different agents for a single task (offline).
Results correspond to a single instantiation of each agent.

(b) Average decision time per timestep for each agent. Results correspond to
150 samples and are reported with a confidence of $95\%$.

Figure 4. Computation time as a function of the problem size for the Night-
time Pursuit domain.

As seen in Fig. 4(a), the setup times (corresponding to offline computation)
are significantly different between the approaches relying on MDP formulations
(value iteration and BOPA) and those relying on POMDP formulations (ATPO and
Perseus). Value iteration and BOPA show a linear increase in computation time
as the size of the task grows. ATPO and Perseus, on the other hand, show a
super-linear growth as a function of $\left\lvert\mathcal{X}\right\rvert$.
Consequently, for the larger domains, the computation time of the POMDP-based
methods is several orders of magnitude larger than that of MDP-based methods.
Note also that the computation times reported are for a single task, meaning
that the actual computation times for BOPA and ATPO should be multiplied by
$\left\lvert\mathcal{M}\right\rvert$. These results are unsurprising, as
POMDPs are known to be significantly harder to solve than their fully
observable counterparts (Spaan and Vlassis, 2005a).

Conversely, Fig. 4(b) depicts the decision time (corresponding to online
computation). We can now observe that the increase in computation time grows
much more gracefully. As expected, the two methods that identify the target
task (BOPA and ATPO) exhibit larger decision times than those that know the
target task (Perseus and value iteration).

###  5.2. Pursuit Domain under Partial Observability

We now use the Pursuit domain under partial observability to complement the
Night-time Pursuit in addressing Question (1) in Section 4. We consider a
fixed configuration, where $|\mathcal{X}|=552$, corresponding to a $5\times 5$
world, $\epsilon(d)=1-0.15d$, and $|\mathcal{T}|=3$. The different tasks
correspond to different teammate behaviors, for which we consider the
following teammates:

  * •

Greedy teammate: Always moves in the direction of the prey, regardless of any
obstacles along the way.

  * •

Teammate-aware teammate: Computes the shortest path to the prey using A*
search, taking into account the position of the ad hoc agent.

  * •

Probabilistic-destinations teammate: Tries to surround the prey, taking into
account the position of the ad hoc agent.

For each of the three possible teammate types, we ran 32 independent trials
(adding to a total of 96 trials). The results are depicted in Fig. 5.

(a) Average steps to solve a task for each agent on the Pursuit domain under
partial observability. Results correspond to 96 total trials and are reported
with a confidence of $95\%$.

(b) Average entropy per timestep from ATPO model priors $p(m_{k})$ (lower
scale). Results correspond to 96 total trials and are reported with a
confidence of $95\%$.

Figure 5. Performance in Pursuit under partial observability.

The results are similar to those observed in Night-time Pursuit. Value
Iteration is again the best performing agent, and the random policy the worst
performing one. Another noteworthy aspect is that there is almost no
difference between Perseus and ATPO, indicating the near-optimal performance
of the latter. We can also observe, in Fig. 5(b), that the uncertainty
regarding the target task slowly decreases, again showing that ATPO can
effectively identify the target task (in this case, the type of teammate).

###  5.3. Overcooked Domain

(a) Average number of soups cooked in a 75 timestep horizon. Results
correspond to 192 total trials and are reported with a confidence of $95\%$.

(b) Average entropy per timestep from ATPO’s and The Assistant’s model priors
$p(m_{k})$ (lower scale). Results correspond to 192 total trials and are
reported with a confidence of $95\%$.

Figure 6. Performance in Overcooked.

Finally, we consider the third test scenario—the Overcooked domain. This
scenario has been proposed as a benchmark to evaluate cooperation. Therefore,
it is an interesting domain in the context of ad hoc teamwork. Unlike the
previous scenarios, however, Overcooked does not have partial observability.
In our experiments, we evaluate the performance of ATPO when the ad hoc agent
can be either a helper (against four possible types of cook teammate) or a
cook (against two possible types of helper teammate). The possible teammates
with a cook’s role are Greedy, Dummy, and Upper and Downer. Furthermore,
teammates with a helper role are Greedy and Dummy. Greedy agents try to
complete the task as quickly as possible, not waiting for the ad hoc agent.
Dummy agents only act as a response to the actions of the ad hoc agent. Upper
and Downer agents perform the cook role but without moving—remaining only in
the upper or lower cell, respectively. For each of the 6 possible tasks, we
ran 32 independent trials, adding up to 192 total independent trials. Results
are shown in Fig. 6.

By looking at the number of soups cooked (Fig. 6(a)), we can observe that the
random policy is only able to finish a small number of soups—mostly by chance.
The other three methods perform similarly, as there is no statistical
significance between the observed differences. ATPO thus performs optimally—a
performance that is indistinguishable from that of value iteration. It is also
similar to that of the Assistant algorithm.

We can also observe in Fig. 6(b) the entropy of the belief $p_{t}$ at each
time step $t$, both for ATPO and the Assistant. Both agents can identify the
target task, on average, in less than 10 timesteps. We can also see no
statistically significant difference between both agents, even though the
Assistant was able to achieve a slightly lower entropy overall when compared
to ATPO. This result is not unexpected, given that the Assistant can fully
observe the teammate’s actions. Nevertheless, our results show that both
agents are effective in identifying the target task with great certainty, but
also that our approach, ATPO, can do so without being able to observe the
teammate’s actions.

##  6\. Conclusion

This paper presents and evaluates the Ad Hoc Teamwork under Partial
Observability (ATPO) algorithm, a novel approach for the ad hoc teamwork
problem. In this setting, an agent has to learn to cooperate with teammates in
solving an unknown task, without observing the current state of the
environment, the teammates’ actions, and the environment’s reward signals.

Unlike previous approaches that assume relevant information is always readily
accessible to the agent (e.g., environment’s reward signals, teammate’s
actions, and state observations), ATPO does not rely on the assumption that
the multi-agent system is fully observable, relying only on partial
observations. Our results in three domains — the Night Time Pursuit domain,
the Pursuit domain under partial observability, and the Overcooked domain —
show that our approach effectively identifies which task is being performed
from a pool of possible tasks. The results also show that it is: (i) efficient
at solving the correct task in near-optimal times, as if it knew the task
beforehand; (ii) scalable, by being able to adapt to faulty sensors,
actuators, and larger problem sizes; (iii) robust, by being able to adapt to
an increasingly larger number of possible tasks.

## References

  * (1)
  * Agmon and Stone (2012) N. Agmon and P. Stone. 2012.  Leading ad hoc agents in joint action settings with multiple teammates. In _Proc. 11th Int. Conf. Autonomous Agents and Multiagent Systems_. 341–348.
  * Banerjee (2006) A. Banerjee. 2006\.  On Bayesian bounds. In _Proc. 23rd Int. Conf. Machine Learning_. 81–88.
  * Barrett et al. (2017) S. Barrett, A. Rosenfeld, S. Kraus, and P. Stone. 2017\.  Making friends on the fly: Cooperating with new teammates.  _Artificial Intelligence_ 242 (2017), 132–171.
  * Barrett and Stone (2015) S. Barrett and P. Stone. 2015.  Cooperating with unknown teammates in complex domains: A robot soccer case study of ad hoc teamwork.  _Proc. 29th AAAI Conf. Artificial Intelligence_ (2015), 2010–2016.
  * Bu et al. (2008) Lucian Bu, Robert Babu, Bart De Schutter, et al. 2008\.  A comprehensive survey of multiagent reinforcement learning.  _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ 38, 2 (2008), 156–172.
  * Bullard et al. (2021) Kalesha Bullard, Douwe Kiela, Joelle Pineau, and Jakob Foerster. 2021.  Quasi-Equivalence Discovery for Zero-Shot Emergent Communication.  _arXiv preprint arXiv:2103.08067_ (2021).
  * Carroll et al. (2019) M. Carroll, R. Shah, M. Ho, T. Griffiths, S. Seshia, P. Abbeel, and A. Dragan. 2019.  On the utility of learning about humans for human-AI coordination. In _Adv. Neural Information Processing Systems 32_.
  * Chakraborty and Stone (2013) D. Chakraborty and P. Stone. 2013.  Cooperating with a Markovian ad hoc teammate. In _Proc. 12th Int. Conf. Autonomous Agents and Multiagent Systems_.
  * Fern et al. (2007) Alan Fern, Sriraam Natarajan, Kshitij Judah, and Prasad Tadepalli. 2007.  A Decision-Theoretic Model of Assistance.. In _IJCAI_. 1879–1884.
  * Genter et al. (2013) K. Genter, N. Agmon, and P. Stone. 2013.  Ad hoc teamwork for leading a flock. In _Proc. 12th Int. Conf. Autonomous Agents and Multiagent Systems_. 531–538.
  * Genter et al. (2017) K. Genter, T. Laue, and P. Stone. 2017.  Three years of the RoboCup standard platform league drop-in player competition.  _J. Autonomous Agents and Multi-Agent Systems_ 31, 4 (2017), 790–820.
  * Gmytrasiewicz and Doshi (2005) Piotr J Gmytrasiewicz and Prashant Doshi. 2005.  A framework for sequential planning in multi-agent settings.  _Journal of Artificial Intelligence Research_ 24 (2005), 49–79.
  * Hu et al. (2020) Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. 2020\.  “Other-Play” for Zero-Shot Coordination. In _International Conference on Machine Learning_. PMLR, 4399–4410.
  * Hu et al. (1998) Junling Hu, Michael P Wellman, et al. 1998\.  Multiagent reinforcement learning: theoretical framework and an algorithm.. In _ICML_ , Vol. 98. Citeseer, 242–250.
  * Lupu et al. (2021) Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. 2021\.  Trajectory diversity for zero-shot coordination. In _International Conference on Machine Learning_. PMLR, 7204–7213.
  * Melo and Sardinha (2016) F. Melo and A. Sardinha. 2016.  Ad hoc teamwork by learning teammates’ task.  _Autonomous Agents and Multi-Agent Systems_ 30, 2 (2016), 175–219.
  * Pineau et al. (2006) J. Pineau, G. Gordon, and S. Thrun. 2006.  Anytime point-based approximations for large POMDPs.  _J. Artificial Intelligence Res._ 27 (2006), 335–380.
  * Puterman (2005) M. Puterman. 2005\.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_.  Wiley-Interscience.
  * Ribeiro et al. (2021) João G Ribeiro, Miguel Faria, Alberto Sardinha, and Francisco S Melo. 2021.  Helping People on the Fly: Ad Hoc Teamwork for Human-Robot Teams. In _EPIA Conference on Artificial Intelligence_. Springer, 635–647.
  * Spaan and Vlassis (2005a) M. Spaan and N. Vlassis. 2005a.  Perseus: Randomized point-based value iteration for POMDPs.  _J. Artificial Intelligence Res._ 24 (2005), 195–220.
  * Spaan and Vlassis (2005b) Matthijs TJ Spaan and Nikos Vlassis. 2005b.  Perseus: Randomized point-based value iteration for POMDPs.  _Journal of artificial intelligence research_ 24 (2005), 195–220.
  * Stone et al. (2010b) P. Stone, G. Kaminka, S. Kraus, and J. Rosenschein. 2010b.  Ad hoc autonomous agent teams: Collaboration without pre-coordination. In _Proc. 24th AAAI Conf. Artificial Intelligence_. 1504–1509.
  * Stone et al. (2010a) P. Stone, G. Kaminka, and J. Rosenschein. 2010a.  Leading a best-response teammate in an ad hoc team.  In _Agent-Mediated Electronic Commerce. Designing Trading Strategies and Mechanisms for Electronic Markets_. Lecture Notes in Business Information Processing, Vol. 59. Springer Berlin Heidelberg, 132–146.
  * Stone and Kraus (2010) P. Stone and S. Kraus. 2010.  To teach or not to teach?: Decision-making under uncertainty in ad hoc teams. In _Proc. 9th Int. Conf. Autonomous Agents and Multiagent Systems_. 117–124.
  * Treutlein et al. (2021) Johannes Treutlein, Michael Dennis, Caspar Oesterheld, and Jakob Foerster. 2021.  A New Formalism, Method and Open Issues for Zero-Shot Coordination.  _arXiv preprint arXiv:2106.06613_ (2021).

##  Appendix A Proof of Proposition 3.3

We can derive the bound for the loss in (14) incurred by our agent, when
compared against an agent considering a constant distribution $q$ over tasks.
We use the following compression lemma from Banerjee (2006).

###### Lemma

Given a set of hypothesis $\mathcal{H}=\left\\{1,\ldots,H\right\\}$, for any
measurable function $\phi:\mathcal{H}\to\mathds{R}$ and any distributions $p$
and $q$ on $\mathcal{H}$,

$\mathbb{E}_{h\sim q}\left[\phi(h)\right]-\log\mathbb{E}_{h\sim
p}\left[\exp(\phi(h))\right]\leq\mathrm{KL}(q\parallel p).$ (16)

We want to bound the loss incurred by our agent after $T$ time steps. Before
introducing our result, we require some auxiliary notation. Let $m^{*}$ denote
the (unknown) target task at time step $t$. The expected loss of our agent at
time step $t$ is given by

$\displaystyle L_{t}(\pi_{t})$
$\displaystyle=\mathbb{E}\left[\ell_{t}(A^{\alpha}\mid m^{*})\right]$
$\displaystyle=\sum_{a^{\alpha}\in\mathcal{A}^{\alpha}}\pi_{t}(a^{\alpha})\ell_{t}(a^{\alpha}\mid
m^{*})$
$\displaystyle=\sum_{k=1}^{K}p_{t}(m_{k})\sum_{a^{\alpha}\in\mathcal{A}^{\alpha}}\hat{\pi}_{k}(a^{\alpha}\mid
b_{k,t})\ell_{t}(a^{\alpha}\mid m^{*})$
$\displaystyle=\sum_{k=1}^{K}p_{t}(m_{k})\ell_{t}(\hat{\pi}_{k}\mid m^{*}),$

where, for compactness, we wrote

$\ell_{t}(\hat{\pi}_{k}\mid
m^{*})=\sum_{a^{\alpha}\in\mathcal{A}^{\alpha}}\hat{\pi}_{k}(a^{\alpha}\mid
b_{k,t})\ell_{t}(a^{\alpha}\mid m^{*}).$ (17)

Let $q$ denote an arbitrary distribution over $\mathcal{M}$, and define

$L_{t}(q)=\sum_{k=1}^{K}q(m_{k})\ell_{t}(\hat{\pi}_{k}\mid m^{*}).$ (18)

Then, setting $\phi(m_{k})=-\eta\ell_{t}(\hat{\pi}_{k_{t}}\mid m^{*})$, for
some $\eta>0$, and using Lemma A, we have that

$\mathbb{E}_{m\sim q}\left[\phi(m)\right]-\log\mathbb{E}_{m\sim
p_{t}}\left[\exp(\phi(m))\right]\leq\mathrm{KL}(q\parallel p_{t})$ (19)

which is equivalent to

$-\log\mathbb{E}_{m\sim p_{t}}\left[\exp(\phi(m))\right]\leq\eta
L_{t}(q)+\mathrm{KL}(q\parallel p_{t}).$ (20)

Noting that $-2\eta\frac{R_{\max}}{1-\gamma}\leq\phi(m)\leq 0$ and using
Hoeffding’s Lemma,222Hoeffding’s lemma states that, given a real-valued random
variable $X$, where $a\leq X\leq b$ almost surely,
$\mathbb{E}\left[e^{\lambda
X}\right]\leq\exp\left(\lambda\mathbb{E}\left[X\right]+\frac{\lambda^{2}(b-a)^{2}}{8}\right),$
(21) for any $\lambda\in\mathds{R}$.  we have that

$-\log\mathbb{E}_{m\sim p_{t}}\left[\exp(\phi(m))\right]\geq\eta
L_{t}(p_{t})-\frac{\eta^{2}R_{\max}^{2}}{2(1-\gamma)^{2}}.$ (22)

Combining (20) and (22), yields

$L_{t}(p_{t})\leq L_{t}(q)+\frac{1}{\eta}\mathrm{KL}(q\parallel
p_{t})+\frac{\eta R_{\max}^{2}}{2(1-\gamma)^{2}}$ (23)

which, summing for all $t$, yields

$\sum_{t=0}^{T-1}L_{t}(p_{t})\leq\sum_{t=0}^{T-1}L_{t}(q)+\frac{1}{\eta}\sum_{t=0}^{T-1}\mathrm{KL}(q\parallel
p_{t})+\frac{T\eta R_{\max}^{2}}{2(1-\gamma)^{2}}.$ (24)

Since $\eta$ can be selected arbitrarily, setting $\eta=\sqrt{\frac{T}{2}}$ we
finally get

$\sum_{t=0}^{T-1}L_{t}(p_{t})\leq\sum_{t=0}^{T-1}L_{t}(q)+\sqrt{\frac{2}{T}}\sum_{t=0}^{T-1}\mathrm{KL}(q\parallel
p_{t})+\sqrt{\frac{T}{2}}\cdot\frac{R_{\max}^{2}}{(1-\gamma)^{2}}\square$ (25)

##  Appendix B Environment description

We now provide detailed descriptions of our three test scenarios.

###  B.1. Night-time pursuit

Our first evaluation testbed—the Night-time Pursuit domain—represents a
modified version of the Pursuit
domain,333https://www.cs.cmu.edu/afs/cs/usr/pstone/public/papers/97MAS-
survey/node8.html in which we introduce partial observability. Unlike the
traditional Pursuit domain, where $N$ predator agents much capture a moving
prey, in the Night-time Pursuit domain, $N$ predator agents must each capture
its own sleeping, static prey. In the Night Time Pursuit domain, the preys
positions are fixed and not encoded in the state, only in the reward.
Different possible configurations for the preys thus correspond to the
different tasks in $\mathcal{M}$.

In this scenario, the ad hoc agent can move up, down, left and right, or stay
in its current cell. Each moving action succeeds with probability
$1-\varepsilon$, for some $\varepsilon\geq 0$, except if there is a wall in
the corresponding direction, in which case the position of the agent remains
unchanged. When an action fails, the position of the agent remains unchanged.

The ad hoc agent can only observe the neighboring cells. For example, in Fig.
1(a), the ad hoc agent (in the top left corner) can only observe, at each time
step, the elements (teammate, preys) in the white cells. It cannot observe its
current position. Observations are also not flawless: whenever an element
(teammate, prey) is in a neighboring cell, there is a probability
$\varepsilon$ that the agent will fail to observe it.

We model each task $k$ in the Night-time Pursuit domain as a POMDP
$(\mathcal{X},\mathcal{A}^{\alpha},\mathcal{Z},\left\\{\mathbf{P}_{a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\},\left\\{\mathbf{O}_{a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\},r_{k},\gamma)$.
A state $x\in\mathcal{X}$ contains information regarding the positions of both
agents, and is therefore represented as a tuple $x=(c_{1},r_{1},c_{2},r_{2})$,
where $(c_{n},r_{n})$ represents the cell (column and row) where agent $n$ is
located.

Each observation $z\in\mathcal{Z}$ are also represented by a tuple
$z=(\hat{u},\hat{d},\hat{l},\hat{r})$, where each entry represents what is
observed, respectively, above, below, to the left, and to the right of the
agent. For each entry there are three possible values: Nothing, Teammate,
Prey. The action space $\mathcal{A}^{\alpha}$ contains five possible actions,
Up, Down, Left, Right and Stay. The transition probabilities
$\left\\{\mathbf{P}_{a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\}$
map a state $x$ and action $a^{\alpha}$ to every possible next state
$x^{\prime}$, taking into account the probability $\epsilon$ of the agent
failing to move (considering that the teammate actions always succeed and move
the teammate towards its closest prey). Similarly, the observation
probabilities
$\left\\{\mathbf{O}_{a}^{\alpha},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\}$
map a state $x$ and previous action $a^{\alpha}$ to every an observation $z$,
taking into account the probability $\epsilon$ of the agent failing to observe
any given element. The reward function $r_{k}$ assigns the reward of $-1$ for
all time steps except those where the preys have been captured, in which case
it assigns a reward of $100$ for the one the preys are captured in and $0$
afterwards (in other words, since where dealing with an horizon of 50 steps,
we do not reset the environment whenever the preys have been captured).
Finally, we consider a discount factor $\gamma=0.95$.

###  B.2. Pursuit under partial observability

Our second evaluation scenario—the Pursuit domain under partial
observability—is a modification of the original Pursuit domain where we add
partial state observability. In it, $N$ agents ($N=2$ in our experiments) must
capture a single moving prey by surrounding it in a coordinated way. In this
scenario, the different tasks correspond to different behaviors of the
teammate.

In this scenario, the ad hoc agent is able to observe the elements located in
a larger neighborhood, but the probability of it failing to observe an element
increases with the distance. Specifically, the agent fails to observe an
existing element (teammate, prey) located at a distance $d$ with probability
$\varepsilon(d)=1-0.15d$.

We model each possible task $m_{k}\in\mathcal{M}$ as a POMDP

$(\mathcal{X},\mathcal{A}^{\alpha},\mathcal{Z},\left\\{\mathbf{P}_{k,a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\},\left\\{\mathbf{O}_{a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\},r,\gamma).$

Each state $x\in\mathcal{X}$ contain information regarding the relative
distances to the teammate and prey and is therefore represented by a tuple
$x=(d{{}^{a_{1}}}_{x},d{{}^{a_{1}}}_{y},d{{}^{p}}_{x},d{{}^{p}}_{y})$, where
$d{{}^{a_{1}}}_{x},d{{}^{a_{1}}}_{y}$ represents the relative distance (in
units) to the teammate and $d{{}^{p}}_{x},d{{}^{p}}_{y}$ represents the
relative distance (in units) to the prey. Each observation $z\in\mathcal{Z}$
is also represented as a tuple
$z=(\hat{d}{{}^{a_{1}}}_{x},\hat{d}{{}^{a_{1}}}_{y},\hat{d}{{}^{p}}_{x},\hat{d}{{}^{p}}_{y})$,
where the distance to an entity $e$ (prey or teammate),
$(\hat{d}{{}^{e}}_{x},\hat{d}{{}^{e}}_{y})$, represents an observation of the
respective true relative distance $(d{{}^{e}}_{x},d{{}^{e}}_{y})$. According
to the probability $\varepsilon(d)=1-0.15d$, when a successful entity
observation is made (i.e., roll $>=\varepsilon(d)$),
$(\hat{d}{{}^{e}}_{x},\hat{d}{{}^{e}}_{y})=(d{{}^{e}}_{x},d{{}^{e}}_{y})$.
Otherwise, when an unsuccessful observation is made, (i.e., roll
$<\varepsilon(d)$), the tuple $(\hat{d}{{}^{e}}_{x},\hat{d}{{}^{e}}_{y})$ is
instead filled with the distance to one of the four neighbouring cells to the
entity (randomly picked). The action space $\mathcal{A}^{\alpha}$ contains
four possible actions, Up, Down, Left, Right. For each teammate type $k$, the
transition probabilities
$\left\\{\mathbf{P}_{k,a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\}$
map a state $x$ and action $a$ to every possible next state $x^{\prime}$,
taking into account the probability of the teammate executing each possible
action on $x$ given their policy for task $k$. Similarly, the observation
probabilities
$\left\\{\mathbf{O}_{a}^{\alpha},a^{\alpha}\in\mathcal{A}\right\\}$ map a
state $x$ and previous action $a^{\alpha}$ to every possible observation $z$,
taking into account the probability $\epsilon(d)$ of the agent failing to
observe the position of the other agents. The reward function $r_{k}$ assigns
the reward of $-1$ for all time steps except those where the prey has been
cornered, in which case it assigns a reward of $100$ for the one the prey was
cornered in and $0$ afterwards (in other words, since where dealing with an
horizon of 50 steps, we do not reset the environment whenever the prey have
been cornered). Finally, we consider a discount factor $\gamma=0.95$.

###  B.3. Overcooked

Finally, for our third and last evaluation scenario, we resort to the
Overcooked domain (Carroll et al., 2019). The Overcooked domain requires two
agents, a helper and a cook, to cooperate in order to cook as many soups as
possible in a given timeframe. In this case, tasks represent different
teammates which the ad hoc agent must (i) identify; and (ii) adapt to, in
order to cook as many soups as possible. Our ad hoc agent may play one of two
possible roles: the helper, which has the goal of providing the cook with
onions and plates, placing them on a kitchen counter; and the cook, which has
the goal of cooking a soup using three onions and serving it in a plate (which
is then dispatched through a window). The layout used in our experiments is
depicted in Fig. 1(c).

We can model each task $k$ in the Overcooked domain as an MDP
$(\mathcal{X},\mathcal{A}^{\alpha},\\{\mathbf{P}_{k,a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\\},r,\gamma)$,
since the state is fully observable in this domain. Each different task has
distinct transition probabilities. Each state $x\in\mathcal{X}$ is represented
as a tuple $x=(p_{a},p_{c},h_{a},h_{c},tb,bb,s)$, where, respectively,
$(p_{a},p_{c})$ represents the cell (top or bottom) and $(h_{a},h_{c})$
represents the objects (nothing, onion, plate or soup) in hand of the helper
and the cook. $(tb,bb)$ represents the objects on the top kitchen counter
balcony and bottom kitchen counter balcony (respectively). Finally, $s$
represents the contents of the soup pan (empty, one onion, two onions, cooked
soup). The action space $\mathcal{A}$ contains four possible actions, Up,
Down, Noop and Act. The transition probabilities
$\left\\{\mathbf{P}_{k,a^{\alpha}},a^{\alpha}\in\mathcal{A}^{\alpha}\right\\}$
map a state $x$ and action $a^{\alpha}$ to every possible next state
$x^{\prime}$, taking into account the probability of the teammate executing
each action on $x$. The reward function $r$ assigns the reward of $15$ to
states $x$ where the cook delivers a cooked soup through the kitchen window,
and $-1$ otherwise. We consider a discount factor $\gamma=0.95$.