ifaamas [AAMAS ’24]Proc. of the 23rd International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2024)May 6 – 10, 2024 Auckland, New
ZealandN. Alechina, V. Dignum, M. Dastani, J.S. Sichman (eds.) 2024 2024
fp0488 Carnegie Mellon University Pittsburgh, Pennsylvania United States Equal
contribution. University of Washington Seattle, Washington United States [1]
Tsinghua University Beijing China Carnegie Mellon University Pittsburgh,
Pennsylvania United States

# MESA: Cooperative Meta-Exploration in Multi-Agent Learning through
Exploiting State-Action Space Structure

Zhicheng Zhang<EMAIL_ADDRESS>,  Yancheng Liang
<EMAIL_ADDRESS>,  Yi Wu<EMAIL_ADDRESS>and  Fei Fang
<EMAIL_ADDRESS>
###### Abstract.

Multi-agent reinforcement learning (MARL) algorithms often struggle to find
strategies close to Pareto optimal Nash Equilibrium, owing largely to the lack
of efficient exploration. The problem is exacerbated in sparse-reward
settings, caused by the larger variance exhibited in policy learning. This
paper introduces MESA, a novel meta-exploration method for cooperative multi-
agent learning. It learns to explore by first identifying the agents’ high-
rewarding joint state-action subspace from training tasks and then learning a
set of diverse exploration policies to “cover” the subspace. These trained
exploration policies can be integrated with any off-policy MARL algorithm for
test-time tasks. We first showcase MESA’s advantage in a multi-step matrix
game. Furthermore, experiments show that with learned exploration policies,
MESA achieves significantly better performance in sparse-reward tasks in
several multi-agent particle environments and multi-agent MuJoCo environments,
and exhibits the ability to generalize to more challenging tasks at test time.

###### Key words and phrases:

Multi-Agent Reinforcement Learning; Meta-Learning; Exploration Strategy

##  1\. Introduction

Reinforcement learning (RL) algorithms often adopt a trial-and-error learning
paradigm and optimize the policy based on the reward signals given by the
environment. The effectiveness of RL relies on efficient exploration,
especially in sparse reward settings, as it is critical to get sufficient
experiences with high rewards to guide the training.

The exploration challenge has been studied extensively and existing works can
be categorized mainly into two streams. One core idea with great success is to
incentivize the agent to visit the under-explored states more frequently by
adding an intrinsic reward based on a visitation measure Bellemare et al.
(2016); Pathak et al. (2017); Ostrovski et al. (2017); Tang et al. (2017) or
some other heuristics Hughes et al. (2018); Wang et al. (2019b).

However, in multi-agent settings, due to the exponential growth of the joint
state-action space, simply visiting more novel states can be increasingly
ineffective. Exploration policies need to better capture the low-dimensional
structure of the tasks and leverage the structural knowledge for higher
exploration efficiency.

Figure 1. Illustration of structured exploration and unstructured exploration
behavior in the $2$-player climb game. The rows and columns indicate the
players’ action space. While unstructured exploration aims to visit novel
states, structured exploration exploits structures in the joint state-action
space, helping agents coordinatedly and more efficiently explore the potential
high-reward subspace.

Illustration of structured exploration and unstructured exploration behavior
in the $2$-player climb game. The rows and columns indicate the players’
action space. While unstructured exploration aims to visit novel states,
structured exploration exploits structures in the joint state-action space,
helping agents coordinatedly and more efficiently explore the potential high-
reward subspace.

Another line of work specifically learns exploration strategies. However,
these works do not explicitly consider the underlying task structure. For
example, Mahajan et al. conditions the policy on a shared latent variable
Mahajan et al. (2019) learned via mutual information maximization. Liu et al.
adopts a goal-conditioned exploration strategy by setting state features as
goals Liu et al. (2021). Other works in the single-agent settings Colas et al.
(2017); Parisi et al. (2021); Schäfer et al. (2022) learn exploration policies
through a pre-defined intrinsic reward. All these works train the exploration
policy using task-agnostic exploration-specific rewards. In Section 4, we will
present a simple matrix game to show that popular exploration methods can have
difficulties finding the optimal solution due to the reward structure of the
game.

How can we enable the agents to more effectively explore by leveraging the
intrinsic structure of the environment? We adopt a meta-exploration framework
(i.e., learning to explore) for MARL: we first train multiple _structured
exploration policies_ from a set of training tasks (referred to as the meta-
training stage), and then use these exploration policies to facilitate agents’
learning in a test-time task, which is typically a new task sampled from the
task distribution (referred to as meta-testing stage). We develop a multi-
agent meta-exploration method, Cooperative Meta-Exploration in Multi-Agent
Learning through Exploiting State-Action Space Structure (MESA) for fully
cooperative settings. MESA leverages the task structures by explicitly
identifying the agents’ high-rewarding joint state-action subspace in the
training tasks. It then trains a set of diverse exploration policies to cover
this identified subspace. The exploration policies are trained with a reward
scheme induced by the distance to the high-rewarding subspace. The meta-
learned exploration policies can be combined with any off-policy MARL
algorithm during the meta-testing stage by randomly selecting learned
exploration policies to collect valuable experiences. Such structured
exploration can help the agents to learn good joint policies efficiently
(Figure 1). We empirically show the success of MESA on the matrix climb game
and its harder multi-stage variant. In addition, we evaluate MESA in two
continuous control tasks, i.e., the MPE environment Lowe et al. (2017) and the
multi-agent MuJoCo benchmark Peng et al. (2021). We demonstrate the superior
performance of MESA compared to existing multi-agent learning and exploration
algorithms. Furthermore, we show that MESA is capable of generalizing to
unseen test-time tasks that are more challenging than any of the training
tasks.

##  2\. Related Work

Exploration has been a long-standing challenge in RL with remarkable progress
achieved in the single-agent setting Bellemare et al. (2016); Pathak et al.
(2017); Ostrovski et al. (2017); Tang et al. (2017); Burda et al. (2018);
Riedmiller et al. (2018); Ecoffet et al. (2021). Most of these works maintain
pseudo-counts over states and construct intrinsic rewards to encourage the
agents to visit rarely visited states more frequently Bellemare et al. (2016);
Pathak et al. (2017); Ostrovski et al. (2017); Tang et al. (2017). These
count-based methods have been extended to the multi-agent setting by
incentivizing intra-agent interactions or social influence Jaques et al.
(2018); Hughes et al. (2018); Jaques et al. (2019); Wang et al. (2019b).
However, in the multi-agent setting, a simple count-based method can be less
effective due to the partial observability of each agent, an exponentially
large joint state-action space, and the existence of multiple non-Pareto-
optimal NE. Therefore, recent works focus on discovering the structures of
possible multi-agent behaviors. For example, Mahajan et al. (2019) adopts
variational inference to learning structured latent-space-policies; Gupta et
al. (2021) generates similar tasks with simpler reward functions to promote
cooperation; Liu et al. (2021) learns to select a subset of state dimensions
for efficient exploration. We follow a meta-learning framework and learn
structured exploration strategies by exploiting high-rewarding subspace in the
joint state-action space. Our method also leverages a count-based technique as
a subroutine during the meta-training phase to prevent over-exploitation and
mode collapse.

Meta reinforcement learning (meta-RL) is a popular RL paradigm that focuses on
training a policy that can quickly adapt on an unseen task at test time Duan
et al. (2016); Finn et al. (2017); Gupta et al. (2018); Xu et al. (2018); Lan
et al. (2019); Rakelly et al. (2019); Zintgraf et al. (2020); Zhang et al.
(2021). Such a paradigm has been extended to the setting of learning to
explore. The key idea is to meta-learn a separate exploration policy that can
be used in the testing task. Most closely related to our work is Parisi et al.
(2021), where an exploration policy is pretrained on a set of training tasks.
However, their method is designed for the single-agent setting and learns the
exploration policy by using a task-agnostic intrinsic reward to incentivize
visitation of interesting states , while we directly utilize the task reward
to learn the structure of the environments. Other existing works in meta-
exploration propose to learn a latent-space exploration policy that is
conditioned on a task variable, which can be accomplished by meta-policy
gradient Xu et al. (2018); Gupta et al. (2018); Lan et al. (2019), variational
inference Rakelly et al. (2019) or information maximization Zhang et al.
(2021) over the training tasks. Therefore, at test time, posterior inference
can be performed for the latent variable towards fast exploration strategy
adaption. Our approach follows a similar meta-exploration paradigm by learning
additional exploration policies. However, existing meta-exploration methods
focus on the single-agent setting while we consider much more challenging
multi-agent games with a distribution of similarly-structured tasks, for
example, the MPE environment Lowe et al. (2017) with a distribution of target
landmarks that the agents need to reach. In addition, we meta-learn a discrete
set of exploration policies through an iterative process, which results in a
much simpler meta-testing phase without the need for posterior sampling or
gradient updates on exploration policies. Besides, some other methods pretrain
exploration policies from an offline dataset Singh et al. (2020); Dorfman et
al. (2020); Pong et al. (2021), which is beyond the scope of this paper.

Finally, our approach largely differs from the setting of multi-task learning
Parisotto et al. (2016); Andrychowicz et al. (2017); Andreas et al. (2017);
Espeholt et al. (2018); Hessel et al. (2019), which are commonly evaluated in
environments with heterogeneous tasks or scenarios. Our exploration policies
are _not_ trained to achieve high returns in the training tasks. Instead, they
are trained to reach as many high-reward _state-action pairs_ as possible
collected in a diverse set of tasks. Therefore, the state-action pairs covered
by a single exploration policy are very likely to be distributed across
different training tasks.

##  3\. Preliminaries

Dec-POMDP. We consider fully-cooperative Markov games described by a
decentralized partially observable Markov decision process (Dec-POMDP), which
is defined by
$\left\langle\mathcal{S},\mathcal{A},P,R,\Omega,\mathcal{O},n,\gamma\right\rangle$.
$\mathcal{S}$ is the state space.
$\mathcal{A}\equiv\mathcal{A}_{1}\times...\times\mathcal{A}_{n}$ is the joint
action space. The dynamics is defined by the transition function
$P(s^{\prime}\mid s,\boldsymbol{a})$. Agents share a reward function
$R(s,\boldsymbol{a})$, and $\gamma\in(0,1)$ is the discount factor.
$\Omega\equiv\Omega_{1}\times..\times\Omega_{n}$ is the joint observation
space, where $\Omega_{i}$ is the observation space for agent $i$. At each
timestep, each agent $i$ only has access to its own observation
$o_{i}\in\Omega_{i}$ defined by the function
$\mathcal{O}:\mathcal{S}\times\mathcal{A}\mapsto\Omega$. The goal of agents in
Dec-POMDP is to maximize the common expected discounted return under the joint
policy $\boldsymbol{\pi}$:
$\mathcal{J}(\boldsymbol{\pi})=\mathbb{E}_{\boldsymbol{\pi}}\left[\sum_{t}\gamma^{t}R(s_{t},\boldsymbol{a}_{t})\right]$.

Learning to Explore. Meta-RL assumes a task distribution $p(\mathcal{T})$ over
tasks, and an agent aims to learn to quickly adapt to a test-time task
$\mathcal{T}_{\text{test}}$ drawn from $p(\mathcal{T})$ after training in a
batch of training tasks $\\{\mathcal{T}_{i}\mid\mathcal{T}_{i}\sim
p(\mathcal{T})\\}_{i=1}^{B}$. Inspired by the explicit exploration methods
Colas et al. (2017); Zhang et al. (2021), we adopt a meta-exploration
framework for MARL: we learn joint exploration policies $\boldsymbol{\pi}_{e}$
from training tasks $\\{\mathcal{T}_{i}\mid\mathcal{T}_{i}\sim
p(\mathcal{T})\\}_{i=1}^{B}$ and use $\boldsymbol{\pi}_{e}$ to collect
experiences for the training of the agents’ policy profile $\boldsymbol{\pi}$
in task $\mathcal{T}_{\text{test}}$, denoted as
$\boldsymbol{\pi}(\boldsymbol{\pi}_{e},\mathcal{T}_{\text{test}})$. Formally,
the objective of meta-exploration is

$\max_{\boldsymbol{\pi}_{e}}\mathbb{E}_{\mathcal{T}_{\text{test}}\sim
p(\mathcal{T})}\left[\mathbb{E}_{\boldsymbol{\pi}(\boldsymbol{\pi}_{e},\mathcal{T}_{\text{test}})}\left[\sum_{t}\gamma^{t}R_{i}(s_{t},\boldsymbol{a}_{t})\right]\right].$
(1)

Nash Equilibrium and Pareto Optimality. A joint policy $\boldsymbol{\pi}$ is
an NE if each agent’s policy $\pi_{i}$ is a best response to the other agents’
policies $\boldsymbol{\pi}_{-i}$. That is, for any agent $i$’s alternative
policy $\pi^{\prime}_{i}$, we have $Q_{i}(\boldsymbol{\pi})\geq
Q_{i}(\pi^{\prime}_{i},\boldsymbol{\pi}_{-i})$, where $Q_{i}$ is the value
function for agent $i$. A joint policy $\boldsymbol{\pi}$ is Pareto optimal if
there does not exist an alternative joint policy $\boldsymbol{\pi}^{\prime}$
such that $\forall i,\ Q_{i}(\boldsymbol{\pi}^{\prime})\geq
Q_{i}(\boldsymbol{\pi})$ and $\exists i,\
Q_{i}(\boldsymbol{\pi}^{\prime})>Q_{i}(\boldsymbol{\pi})$.

##  4\. A Motivating Example: Climb Game

Figure 2. MESA’s meta-learning framework. In the meta-training stage, MESA
learns exploration policies to cover the high-rewarding subspace. In the meta-
testing stage, MESA uses the learned exploration policies to assist the
learning in an unseen task. Each color corresponds to a different task, and
the colored points represent the high-rewarding joint state-action pairs
collected in that task.

MESA’s meta-learning framework. In the meta-training stage, MESA learns
exploration policies to cover the high-rewarding subspace. In the meta-testing
stage, MESA uses the learned exploration policies to assist the learning in an
unseen task. Each color corresponds to a different task, and the colored
points represent the high-rewarding joint state-action pairs collected in that
task.

We analyze a fully cooperative matrix game known as Climb Game. In Section
4.1, we show how popular exploration strategies, including unstructured
strategies like uniform exploration and task-specific strategies like
$\epsilon-$greedy, fail to efficiently explore the climb game. By contrast, we
show in Section 4.2 that a simple structured exploration strategy can
substantially improve the exploration efficiency.

A climb game $G_{f}(n,u,U)$ is a $n$-player game with action space
$\mathcal{A}_{i}=\\{0,\dots,U-1\\}$ for any player $i$. The reward of a joint
action $\boldsymbol{a}\in\mathcal{A}$ is determined by the number of players
performing a specific action $u$ (denoted as #$u$), which is

$\displaystyle R(\boldsymbol{a})=\begin{cases}1,&\text{if \\#}u=n,\\\
1-\delta\text{ }(0<\delta<1),&\text{if \\#}u=0,\\\
0,&\text{otherwise}.\end{cases}.$ (2)

###  4.1. Exploration Challenge

A climb game $G_{f}(n,u,U)$ has three groups of NE: the Pareto optimal NE
$(u,u,\dots,u)$, the sub-optimal NEs $\\{(a_{1},a_{2},\dots,a_{n})\mid\forall
i,\ a_{i}\neq u\\}$, and the zero-reward NEs $\\{(a_{1},a_{2},\dots,a_{n})\mid
1<\\#u<n\\}$. The sheer difference in the size of the three subsets of NEs
makes it particularly challenging for RL agents to learn the optimal policy
profile without sufficient exploration, as evidenced by the theoretical
analysis below and empirical evaluation in Section 6.

Consider a 2-agent climb game $G_{f}(2,0,U)$. A joint action $\boldsymbol{a}$
can be represented by a pair of one-hot vectors
$[\mathbf{e}_{i},\mathbf{e}_{j}]\in\\{0,1\\}^{2U}$. Let
$q(\mathbf{x},\mathbf{y};\theta)$ be a joint Q function parameterized by
$\theta$ that takes input $\mathbf{x},\mathbf{y}\in\\{0,1\\}^{U}$ and is
learned to approximate the reward of the game. We hope the joint Q function
has the same optimal policy profile.

######  Definition 4.1.

We call a joint $Q$ function $q(\mathbf{x},\mathbf{y};\theta)$ _equivalently
optimal_ when $q(\mathbf{e}_{0},\mathbf{e}_{0};\theta)=\max_{0\leq
i,j<U}q(\mathbf{e}_{i},\mathbf{e}_{j};\theta)$. When a joint $Q$ function is
equivalently optimal, one can use it to find the optimal policy.

Since neural networks are difficult to analyze in general Blum and Rivest
(1988), we parameterize the joint $Q$ function in a quadratic form:

$q(\mathbf{x},\mathbf{y};\mathbf{W},\mathbf{b},\mathbf{c},d)=\mathbf{x}^{\top}\mathbf{W}\mathbf{y}+\mathbf{b}^{\top}\mathbf{x}+\mathbf{c}^{\top}\mathbf{y}+d$
(3)

A Gaussian prior $p(\mathbf{W})=\mathcal{N}(\mathbf{W};0,\sigma^{2}_{w}I)$ is
introduced under the assumption that a non-linear $\mathbf{W}$ is harder and
slower to learn. Quadratic functions have been used in RL Gu et al. (2016);
Wang et al. (2019a) as a replacement for the commonly-used multi-layer
perceptron, and there are also theoretical results Du and Lee (2018) analyzing
neural networks with quadratic activation. For the climb game, it is easy to
verify that the quadratic coefficients make the joint $Q$ function
sufficiently expressive to perfectly fit the reward function by setting
$\mathbf{W}$ to be the reward matrix. Therefore, the learning process of $Q$
is mainly affected by how the exploration policy samples the data.

Consider an exploration policy $p_{e}^{(t)}$ that selects joint action
$\boldsymbol{a}=(i,j)$ at step $t$ with probability $p_{e}^{(t)}(i,j)$. The
efficiency of an exploration policy can be measured by the required number of
steps for learning an equivalently optimal $Q$ function using the maximum
likelihood estimator over the data sampled from $p_{e}^{(t)}$. The learning
objective includes both the prior $p(\mathbf{W})$ and the likelihood of
prediction error $p(E_{ij})$, where the prediction error
$E_{ij}=q(\mathbf{e}_{i},\mathbf{e}_{j};\cdot)-R_{ij}$. If the prediction
error is assumed to be depicted by a Gaussian distribution
$p(E_{ij})=\mathcal{N}(E_{ij};0,\sigma_{e}^{2})$ for every visited joint
action $(i,j)$, then the learning objective for the $Q$ function can be
formulated as:

$\displaystyle\mathcal{J}^{(T)}(\mathbf{W},\mathbf{b},\mathbf{c},d)$
$\displaystyle=$ $\displaystyle\mathbb{E}_{\\{(i^{(t)},j^{(t)})\sim
p_{e}^{(t)}\\}_{t=1}^{T}}\log\left(p(\textbf{W})\prod_{t^{\prime}=1}^{T}p(E_{i^{(t)}j^{(t)}})\right)$
$\displaystyle=$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}_{(i,j)\sim
p_{e}^{(t)}}\left[\log\mathcal{N}(q(\mathbf{e}_{i},\mathbf{e}_{j};\mathbf{W},\mathbf{b},\mathbf{c},d)-R_{ij};0,\sigma^{2}_{e})\right]$
$\displaystyle+$
$\displaystyle\log\mathcal{N}(\mathbf{W};0,\sigma^{2}_{w}I)+\text{Const.}$ (4)

We use $q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ to denote
the learned joint $Q$ function that maximizes $\mathcal{J}^{(T)}$ at step $T$.
$q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ is determined by
the exploration policy $p_{e}^{(t)}$ and the exploration steps $T$. Then we
have the following theorem for the uniform exploration strategy.

######  Theorem 4.2 (uniform exploration).

Assume $\delta\leq\frac{1}{6},U\geq 3$. Using a uniform exploration policy in
the climb game $G_{f}(2,0,U)$, it can be proved that
$q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ will become
equivalently optimal only after $T=\Omega(|\mathcal{A}|\delta^{-1})$ steps.
When $\delta=1$, $T=O(1)$ steps suffice to learn the equivalently optimal
joint Q function, suggesting the inefficiency of uniform exploration is due to
a large set of sub-optimal NEs.

The intuition behind Theorem 4.2 is that the hardness of exploration in climb
games largely comes from the sparsity of solutions: a set of sub-optimal NEs
exist but there is only a single Pareto optimal NE. Learning the joint $Q$
function can be influenced by the sub-optimal NEs. And if the exploration
attempts are not well coordinated, a lot of zero reward would be encountered,
making it hard to find the Pareto optimal NE. We also remark that uniform
exploration can be particularly inefficient since the term $|\mathcal{A}|$ can
be exponentially large in a multi-agent system. This indicates that more
efficient exploration can potentially be achieved by reducing the search space
and identifying a smaller “critical” subspace.

To formally prove Theorem 4.2, we define $f_{1},f_{2},f_{3}$ as the step-
averaged probability of taking the joint action in optimal NE, suboptimal NE
and zero-reward, respectively. We show that to make the joint $Q$ function
equivalently optimal, there is a necessary condition that $f_{1},f_{2},f_{3}$
should follow. When $T$ is not large enough, this condition cannot be
satisfied. Detailed proof is in Appendix A.2.

Next, we consider the case of another popular exploration paradigm,
$\epsilon$-greedy exploration.

######  Theorem 4.3 ($\epsilon$-greedy exploration).

Assume $\delta\leq\frac{1}{32},U\geq 4,U\geq\sigma_{w}\sigma_{e}^{-1}$. In the
climb game $G_{f}(2,0,U)$, under $\epsilon$-greedy exploration with fixed
$\epsilon\leq\frac{1}{2}$,
$q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ will become
equivalently optimal only after
$T=\Omega(|\mathcal{A}|\delta^{-1}\epsilon^{-1})$ steps. If $\epsilon(t)=1/t$,
it requires $T=\exp\left(\Omega\left(|\mathcal{A}|\delta^{-1}\right)\right)$
exploration steps to be equivalently optimal.

The proof is similar to that of Theorem 4.2 (detailed in Appendix A.3). By
comparing 4.2 and 4.3, $\epsilon$-greedy results in even poorer exploration
efficiency than uniform exploration. Note the $\epsilon$-greedy strategy is
training policy specific, i.e., the exploration behavior varies as the
training policy changes. Theorem 4.3 suggests that when the policy is sub-
optimal, the induced $\epsilon$-greedy exploration strategy can be even worse
than uniform exploration. Hence, it can be beneficial to adopt a separate
exploration independent from the training policy.

The above analysis shows that common exploration strategies like uniform
exploration or $\epsilon$-greedy exploration are inefficient for such a simple
game and the main reason is that it requires coordination between different
agents to reach high-rewarding states, but naive exploration strategies lack
such cooperation.

###  4.2. Structured Exploration

We will show that it is possible to design a better exploration strategy with
some prior knowledge of the climb game structure. Consider a specific
structured exploration strategy
$p_{e}^{(t)}(i,j)=U^{-1}\left[\mathds{1}_{i=j}\right]$, where both agents
always choose the same action. With such a strategy, we can quickly find the
optimal solution to the game. More formally, we have the following theorem.

######  Theorem 4.4 (structured exploration).

In the climb game $G_{f}(2,0,U)$, under structured exploration
$p_{e}^{(t)}(i,j)=U^{-1}\left[\mathds{1}_{i=j}\right]$,
$q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ is equivalently
optimal at step $T=O(1)$.

Theorem 4.4 shows the efficiency of exploration can be greatly improved if the
exploration strategy captures a proper structure of the problem, i.e., all
agents taking the same action. We further remark that by considering a set of
similar climb games $\mathcal{G}$, where
$\mathcal{G}=\\{G_{f}(2,u,U)\\}_{u=0}^{U-1}$, the structured exploration
strategy $p_{e}^{(t)}(i,j)=U^{-1}\left[\mathds{1}_{i=j}\right]$ can be
interpreted as a uniform distribution over the optimal policies of this game
set $\mathcal{G}$. This interesting fact suggests that we can first collect a
set of similarly structured games and then derive effective exploration
strategies from these similar games. Once a set of structured exploration
strategies are collected, we can further adopt them for fast learning in a
novel game with a similar problem structure. We take the inspiration here and
develop a general meta-exploration algorithm in the next section.

##  5\. Method

We detail our method Cooperative Meta-Exploration in Multi-Agent Learning
through Exploiting State-Action Space Structure (MESA) for cooperative multi-
agent learning. As shown in Figure 2, MESA consists of a meta-training stage
(Algo. 1) and a meta-testing stage (Algo. 2). In the meta-training stage, MESA
learns exploration policies by training in a batch of training tasks that
share intrinsic structures in the state-action space. In the meta-testing
stage, MESA utilizes the meta-learned exploration policies to assist learning
in an unseen task sampled from the distribution of the training tasks.

Algorithm 1 MESA: Meta-Training

Input: Meta-training tasks $\\{\mathcal{T}_{i}\\}_{i=1}^{B}\sim
p(\mathcal{T})$, off-policy MARL algorithm $f$, distance metric
$\|\cdot\|_{\mathcal{F}}$
Parameter: #policies $E$, threshold $R^{\star}$, horizon $h$
Output: Exploration policies $\\{\boldsymbol{\pi}_{e}^{i}\\}_{i=1}^{E}$

1: $\mathcal{M}_{*}\leftarrow\emptyset$, global pseudo-count
$\hat{N}\leftarrow 0$

2: for i = 1 to B do

3: Initialize policy $\boldsymbol{\pi}_{\theta}$

4: Train $\boldsymbol{\pi}_{\theta}$ with $f$ and collect dataset
$D_{i}=\\{(\boldsymbol{s}_{t},\boldsymbol{a}_{t},r_{t},\boldsymbol{s}_{t+1})\\}$

5: $\mathcal{M}_{*}\leftarrow\mathcal{M}_{*}\cup\\{\tau\mid R(\tau)\geq
R^{\star},\tau\in D_{i}\\}$

6: end for

7: for i = 1 to E do

8: Initialize exploration policy $\boldsymbol{\pi}_{e}^{i}$

9: while $\boldsymbol{\pi}_{e}^{i}$’s training not converged do

10: Initialize $N$ as $\hat{N},\mathcal{D}\leftarrow\emptyset$

11: for t = 0 to h-1 do

12: Execute $\boldsymbol{a}_{t}\sim\boldsymbol{\pi}_{e}^{i}(s_{t})$, and
observe $(s_{t},\boldsymbol{a_{t}}$ $,r_{t},s_{t+1})$

13: Calculate $\hat{r}_{t}$ based on Eq. 5 or 6

14: Store $(s_{t},\boldsymbol{a}_{t},\hat{r}_{t},s_{t+1})$ into $\mathcal{D}$

15: $N(\phi(s_{t},\boldsymbol{a}_{t}))\leftarrow
N(\phi(s_{t},\boldsymbol{a}_{t}))+1$

16: end for

17: Optimize policy $\boldsymbol{\pi}_{e}^{i}$ with algorithm $f$

18: end while

19: Update $\hat{N}$ using $\mathcal{D}$

20: end for

21: return $\\{\boldsymbol{\pi}_{e}^{i}\\}_{i=1}^{E}$

Algorithm 2 MESA: Meta-Testing

Input: Test task $\hat{\mathcal{T}}$, meta-trained exploration policies
$\\{\boldsymbol{\pi}_{e}^{i}\\}_{i=1}^{E}$, off-policy MARL algorithm $f$
Parameter: horizon $h$
Output: Policy $\boldsymbol{\pi}_{\theta}$ for task $\hat{\mathcal{T}}$

1: Initialize policy $\boldsymbol{\pi}_{\theta}$, $\mathcal{D}=\emptyset$,
annealing $\epsilon$

2: while not converged do

3: Determine $p_{e}$ under annealing probability schedule $\epsilon$

4: Choose policy to perform rollouts by
$\boldsymbol{\pi}_{d}=\begin{cases}\boldsymbol{\pi}_{e}\sim\mathcal{U}(\\{\boldsymbol{\pi}_{e}^{i}\\}_{i=1}^{E}),&\text{w.p.}\
p_{e}\\\ \boldsymbol{\pi}_{\theta},&\text{otherwise}.\end{cases}$

5: for t = 0 to h-1 do

6: Execute $\boldsymbol{a}_{t}\sim\boldsymbol{\pi}_{d}(s_{t})$.

7: Observe transition $(s_{t},\boldsymbol{a}_{t},r_{t},s_{t+1})$.

8:
$\mathcal{D}\leftarrow\mathcal{D}\cup(s_{t},\boldsymbol{a}_{t},r_{t},s_{t+1})$

9: end for

10: Optimize $\boldsymbol{\pi}_{\theta}$ with algorithm $f$ on replay buffer
$\mathcal{D}$

11: end while

12: return $\boldsymbol{\pi}_{\theta}$

###  5.1. Meta-Training

The meta-training stage contains two steps: 1) identify the high-rewarding
state-action subspace, and 2) train a set of exploration policies using the
subspace-induced rewards.

####  5.1.1. Identifying High-Rewarding Joint State-Action Subspace

For each training task $\mathcal{T}_{i}$, we collect experiences
$\mathcal{D}_{i}=\\{(s_{t},\boldsymbol{a}_{t},r_{t},s_{t+1})\\}$. If the
reward $r_{t}$ is higher than a threshold $R^{\star}$, we call this joint
state-action pair $(s_{t},\boldsymbol{a}_{t})$ valuable and store it into a
dataset $\mathcal{M}_{*}$. For goal-oriented tasks where
$r=\mathds{1}_{s=goal}$, the threshold can be set as $R^{\star}=1$. For other
tasks, the threshold can be set as a hyperparameter, for example, a certain
percentile of all collected rewards. A smaller $R^{\star}$ results in a larger
identified subspace but a less efficient exploration policy.

The data stored in $\mathcal{M}_{*}$ is highly diversified since it comes from
all the $B$ training tasks, which are expected to share an intrinsic
structure. We expect that with this intrinsic structure, the high-rewarding
joint state-action pairs fall into some low-dimensional subspace. In the
simplest case, they may form several dense clusters, or many of them lie in a
hyperplane. Even if the subspace is not easily interpretable to humans, it may
still be effectively “covered” by a set of exploration policies (to be found
in the subsequent step).

We also explicitly deal with the reward sparsity problem by assigning a
positive reward to a joint state-action pair $(s_{t},\boldsymbol{a}_{t})$ if
it has zero reward but leads to a valuable state-action pair
$(s_{t^{\prime}},\boldsymbol{a}_{t^{\prime}})$ later in the same trajectory.
We also put these relabeled pairs into the dataset $\mathcal{M}_{*}$. Let
$t^{\prime}=\arg\min_{t^{\prime}>t}[{r}_{t^{\prime}}>0]$, we therefore have
the following densified reward function

$\displaystyle\hat{r}_{t}=\begin{cases}\gamma^{t^{\prime}-t}\cdot{r}_{t^{\prime}},&{r}_{t}=0,\\\
{r}_{t},&{r}_{t}>0.\end{cases}$ (5)

####  5.1.2. Learning Exploration Policies

In this step, we aim to learn a diverse set of exploration policies to cover
the identified high-rewarding joint state-action subspace. We use a distance
metric $\|\cdot\|_{\mathcal{F}}$ (e.g., $l_{2}$ distance) to determine whether
two state-action pairs are close. Then if a visited joint state-action pair
$(s,\boldsymbol{a})$ is close enough to the identified subspace
$\mathcal{M}_{*}$, i.e.,
$\min_{d\in\mathcal{M}_{*}}\|(s,\boldsymbol{a}),d\|_{\mathcal{F}}<\epsilon$,
it would be assigned a derived positive reward $\hat{r}$. Increasing the value
of $B$ in the collection step would generally result in a more accurate
distance measurement. However, this comes at the cost of making the
minimization calculation more computationally expensive.

To encourage a broader coverage of the subspace and to avoid mode collapse,
the reward assignment scheme ensures that repeated visits to similar joint
state-action pairs within one trajectory would result in a decreasing reward
for each visit. Similar to Tang et al. (2017), we adopt a pseudo-count
function $N$ with a hash function $\phi(\boldsymbol{s},\boldsymbol{a})$ to
generalize between similar joint state-action pairs. We then apply a
decreasing function $f_{d}:\mathcal{N}\mapsto[0,1]$ on the trajectory-level
pseudo-count $N(\phi((s,\boldsymbol{a}))$. The resulted reward assignment
scheme is defined as follows:

$\tilde{r}_{t}=\hat{r}_{t}f_{d}(N(\phi((s_{t},\boldsymbol{a}_{t})))\left[\mathds{1}_{\min_{d\in\mathcal{\mathcal{M}_{*}}}\|(s_{t},\boldsymbol{a}_{t}),d\|_{\mathcal{F}}<\epsilon}\right]$
(6)

After one exploration policy is trained with this reward, we will train a new
policy to cover the part of the identified subspace that has not yet been
covered. This is achieved by having a global pseudo-count $\hat{N}$ which is
updated after training each exploration policy using its visitation counts and
is maintained throughout the training of all exploration policies. This
iterative process continues until the subspace is well-covered by the set of
trained exploration policies.

###  5.2. Meta-Testing

During meta-testing, MESA uses the meta-learned exploration policies
$\\{\boldsymbol{\pi}_{e}^{i}\\}_{i=1}^{E}$ to assist the training of any
generic off-policy MARL algorithm on a test-time task $\hat{\mathcal{T}}$.
Specifically, for each rollout episode, we choose with probability $\epsilon$
to execute one uniformly sampled exploration policy
$\boldsymbol{\pi}_{e}\sim\mathcal{U}(\\{\boldsymbol{\pi}_{e}^{i}\\}_{i=1}^{E})$.
For the best empirical performance, we also adopt an annealing schedule
$\epsilon:T\mapsto[0,1]$ so that the exploration policies provide more
rollouts at the initial stage of the training and are gradually turned off
later.

Here we further provide some analysis of deploying the meta-learned
exploration policy on unseen testing tasks.

######  Theorem 5.1 (Exploration during Meta-Testing).

Consider goal-oriented tasks with goal space
$\mathcal{G}\subseteq\mathcal{S}$. Assume the training and testing goals are
sampled from the distribution $p(x)$ on $\mathcal{G}$, and the dataset has $N$
i.i.d. goals sampled from a distribution $q(x)$ on $\mathcal{S}$. If the
exploration policy generalizes to explore $\epsilon$ nearby goals for every
training sample, we have that the testing goal is not explored with
probability at most

$P_{\text{fail}}\approx\int p(x)(1-\epsilon q(x))^{N}dx\leq
O\left(\frac{KL(p||q)+\mathcal{H}(p)}{\log(\epsilon N)}\right).$ (7)

Theorem 5.1 shows that the good performance of meta-learned exploration policy
relies on 1) a small difference between the training and testing distribution;
and 2) a structured, e.g., low-dimensional, high-rewarding subspace
$\mathcal{G}$ to reduce $\mathcal{H}(p)$. And when uniformly sampling the
training data, $KL(p||q)$ is bounded by $\log\Omega_{\mathcal{G}}$ in our
method. This term, however, can be up to $\log\Omega_{\mathcal{S}}$ with an
uncoordinated exploration on the joint state space $\mathcal{S}$, where
$\Omega_{\mathcal{S}}$ can be exponentially larger than
$\Omega_{\mathcal{G}}$.

###  5.3. Implementation Detail of MESA

We choose MADDPG, following the centralized training with decentralized
execution (CTDE) paradigm, as the off-policy MARL algorithm for MESA since it
can be applied to both discrete and continuous action space, as shown in its
original paper Lowe et al. (2017). We use a clustering mapping $f_{c}$ as the
hash function $\phi$ so that the dataset $\mathcal{M}_{*}$ is clustered into
$C$ clusters defined by the clustering function
$f_{c}:\mathcal{S}\times\mathcal{A}\mapsto[C]$. The cluster mapping is
implemented with the KMeans clustering algorithm Lloyd (1982). The number of
exploration policies to learn is viewed as a hyperparameter. See the Appendix
for detailed hyperparameter settings.

##  6\. Experiments

Our experimental evaluation aims to answer the following questions: (1) Are
the meta-learned exploration policies capable of achieving more efficient
exploration during meta-testing on newly sampled tasks in matrix climb game
variants (Section 4) and high-dimensional domains (Section 6.3 and 6.4)? (2)
Can these meta-learned exploration policies successfully generalize to unseen
test-time tasks from a more challenging (e.g., with more agents) test task
distribution which is different the training task distribution (Section 6.5)?

###  6.1. Evaluation Setup

Compared Methods. We compare to $3$ multi-agent reinforcement learning
algorithms: MADDPG Lowe et al. (2017), MAPPO Yu et al. (2021), and QMIX Rashid
et al. (2018), to measure the effectiveness of our exploration policies. We
also compare to $3$ multi-agent exploration algorithm: MAVEN Mahajan et al.
(2019), MAPPO with RND exploration Burda et al. (2018), and EMC Zheng et al.
(2021). To compare with baselines that adopt a similar meta-training stage, we
add two naive meta-learning baselines, including one with an unconditioned
shared policy, which is trained over all training tasks, and one with a goal-
conditioned policy, which takes the target landmarks as parts of the input. We
also adapt the single-agent meta-RL algorithm MAESN Gupta et al. (2018) to the
multi-agent setting. Finally, we adapt the single-agent C-BET Parisi et al.
(2021) to multi-agent settings based on MAPPO. The training and testing tasks
are as defined in Section 6.1. Please refer to the Appendix for more
visualization and experimental results.

Environments. We experiment on the Climb Game, Multi-agent Particle
Environment (MPE) Lowe et al. (2017), and multi-agent MuJoCo Peng et al.
(2021), on which generating a distribution of meta-training tasks
$p(\mathcal{T})$ is feasible.

Figure 3. Learning curve of the two climb game variants w.r.t number of
environment steps. The return is averaged over timesteps for the multi-stage
games. The dotted lines indicate the suboptimal return of $0.5$ (purple) and
the optimal return $1$ (blue) for each agent.

Learning curve of the two climb game variants w.r.t number of environment
steps. The return is averaged over timesteps for the multi-stage games. The
dotted lines indicate the suboptimal return of $0.5$ (purple) and the optimal
return $1$ (blue) for each agent.

###  6.2. Climb Game Variants

Figure 4. Learning curves of MESA and the compared baselines w.r.t the number
of environment interactions during the meta-testing stage in the MPE domain
and the multi-agent MuJoCo environment Swimmer. The two dotted lines indicate
the ideal optimal (purple) and sub-optimal (blue) return summed over
timesteps. A return above the blue line would typically indicate that the
agents are able to learn the optimal strategy.

Learning curves of MESA and the compared baselines w.r.t the number of
environment interactions during the meta-testing stage in the MPE domain and
the multi-agent MuJoCo environment Swimmer. The two dotted lines indicate the
ideal optimal (purple) and sub-optimal (blue) return summed over timesteps. A
return above the blue line would typically indicate that the agents are able
to learn the optimal strategy.

First, we consider task spaces consisting of variants of the aforementioned
climb games. We extend previous climb game to (1) one-step climb game
$G(n,k,u,U)$, which is a $n$-player game with $U$ actions for each player, and
the joint reward is $1$ if #$u=k$, $1-\delta$ if #$u=0$, and $0$ otherwise.
The task space $\mathcal{T}^{\text{one}}_{U}$ consists of all one-step climb
games that contain two players and $U$ actions; (2) multi-stage climb game,
which is an $S$-stage game where each stage is a one-stage climb game with the
same number of available actions. Each stage $t$ has its own configuration
$(k_{t},u_{t})$ of the one-stage climb game $G(2,k_{t},u_{t},U)$. Agents
observe the history of joint actions and the current stage $t$. The task space
$\mathcal{T}^{\text{multi}}_{S,U}$ consists of all multi-stage climb games
with $S$ stages and $U$ actions. In our experiments, we use
$\mathcal{T}^{\text{one}}_{10}$ and $\mathcal{T}^{\text{multi}}_{5,10}$ as the
task space for the one-step and multi-stage Climb Games. We choose uniformly
at random ten training tasks and three different test tasks from the task
space $\mathcal{T}$, and we keep $\delta=\frac{1}{2}$ as in the classic climb
games.

Results on Climb Game Variants. For the matrix games, we additionally compare
with MA-MAESN, which is our adaptation of the original single-agent meta-
learning algorithm MAESN Gupta et al. (2018) to the multi-agent scenario In
the single-step matrix game, MESA exhibits better performance, being able to
find the optimal reward in some harder tasks when $k=2$, while other baselines
are stuck at the sub-optimal reward for almost all tasks.

In the more challenging $10$-action multi-stage game where task space is
exponentially larger, MESA outperforms all compared algorithms by a large
margin. With the help of the exploration policies that have learned the high-
rewarding joint action pairs, MESA quickly learns the optimal joint action for
each stage and avoids being stuck at the sub-optimal.

Figure 5. Visualizations of a $2$-player $3$-landmark MPE climb game.

Visualizations of a $2$-player $3$-landmark MPE climb game with four types of
reward.

###  6.3. MPE Domain

We extend the matrix climb games to MPE Lowe et al. (2017), which has a
continuous high-dimensional state space. Agents must first learn to reach the
landmarks under sparse rewards and then learn to play the climb games
optimally.

In a MPE Climb Game $\bar{G}(n,k,u,U,\\{L_{j}\\}_{0}^{U-1})$ (Figure 5), there
are $U$ non-overlapping landmarks with positions $\\{L_{j}\\}_{j=0}^{U-1}$.
The reward is non-zero only when every agent is on some landmark. Agents will
be given a reward of $1$ if there are exactly $k$ agents located on the $u$-th
landmark (target landmark), and a suboptimal reward of $1-\delta$ will be
given when none of the agents are located on the target landmark. Otherwise,
the reward will be zero. As before, $u$ and $k$ are not present in the
observation and can only be inferred from the received reward. A task space
$\mathcal{T}^{\text{MPE}}_{n,U}$ consists of all MPE climb games with $n$
players and $U$ landmarks. We evaluate MESA on the $2$-agent tasks
($\mathcal{T}^{\text{MPE}}_{2,5}$ and $\mathcal{T}^{\text{MPE}}_{2,6}$) and
$3$-agent tasks ($\mathcal{T}^{\text{MPE}}_{3,5}$ and
$\mathcal{T}^{\text{MPE}}_{3,6}$) while fixing $k=2$. Each sampled training
and testing task has a different configuration of landmark positions.

Adaptation Performance in MPE. We show in Figure 4 the learning curve of our
approach MESA compared with the aforementioned baseline methods. MESA
outperforms the compared baselines by a large margin, being able to
coordinately reach the task landmark quickly, as evidenced by the near-optimal
reward. Even when combined with RND-based exploration, MAPPO easily sticks to
the sub-optimal equilibrium. Value-based methods like QMIX and MAVEN are
unable to learn the correct $Q$-function because the reward is quite sparse
before agents can consistently move themselves to a landmark. EMC sometimes
jumps out of the suboptimal equilibrium with curiosity-driven exploration, but
the performance is not robust. Furthermore, as the meta-learning baselines
only learn the sub-optimal behavior during meta-training, they fail to learn
the optimal equilibrium during test time and quickly converge to the
suboptimal equilibrium.

Visualization of Exploration Policies. To answer question (2), we visualize
the learned exploration policies in a $2$-agent $3$-landmark MPE task in
Figure 6. We can see that the learned exploration policy consecutively visited
the $3$ landmarks within $20$ timesteps in one trajectory.

Figure 6. Visualization of structured exploration behaviors discovered by the
meta-trained exploration policy in MESA.

Visualization of structured exploration behaviors discovered by the meta-
trained exploration policy in MESA.

###  6.4. Multi-agent MuJoCo Environments

We also extend the matrix climb games to multi-agent MuJoCo environments Peng
et al. (2021). We consider specifically the $2$-agent Swimmer environment
where each agent is a hinge on the swimmer’s body, and each agent’s action is
the amount of torque applied to hinge rotors. The extension considers the
angles between the two hinges and the body segments. Each task in the task
space is a target angle such that a reward of $1$ will be given only if the
two angles are both close to the target angles, a $0.5$ suboptimal reward is
given if none of two angles are close to the target, and a reward of $0$ if
only one of the two angles are close.

This multi-agent environment is extremely hard as agents are very likely to
converge to the suboptimal reward of $0.5$, which is confirmed by the results
that none of the baselines were able to find the optimal equilibrium in Figure
4. Therefore, MESA vastly outperforms all the compared baselines by learning a
final policy that frequently reaches the target angle.

###  6.5. Generalization Performance of MESA

In this section, our goal is to evaluate the generalization performance of the
meta-trained exploration policy in scenarios where the meta-training and meta-
testing task distributions are different. In particular, we focus on the
setting where the test-time tasks are _more challenging_ than the training-
time tasks and examine how an exploration policy learned from simpler tasks
can boost training performances on harder tasks.

The test task here is uniform on the $3$-agent high-difficulty MPE Climb
games. The task difficulty is defined by the average pairwise distances
between the landmark positions and the initial positions of the agents. We
consider two simpler training task distributions, including (1) a $2$-agent
setting with the same difficulty, and (2) a $3$-agent setting with a lower
difficulty. In both settings, the meta-training tasks are less challenging
than the test-time tasks. For evaluation, the meta-trained exploration policy
from each setting will be directly applied to assist the training on the more
challenging test-time tasks, _without any fine-tuning_.

We modified the neural network architecture by adopting an attention layer in
both actor and critic to ensure they are compatible with a varying number of
agents. The attention mechanism acts as an aggregation function between the
relative positions of the other agents and its own relative position to the
landmarks to handle the varying observation dimensions. Additionally, we
employed behavior cloning (BC) Pomerleau (1991) on the rollouts of the
exploration policies as a warm-up to accelerate learning of the final policy.

Figure 7. Generalization results of MESA on the hard $3$-agent MPE Climb game.
Left: Zero-shot generalizability of the meta-exploration policies, measured by
the number of visitations on high-reward transitions per episode on the test
tasks. The purple dotted line corresponds to the random exploration policy.
The plot shows the concatenated training curves for all exploration policies.
Right: Learning curves of MESA under different settings using the meta-
exploration policies trained on the two different training-task distributions.

Generalization results of MESA on the hard $3$-agent MPE Climb game. Left:
Zero-shot generalizability of the meta-exploration policies, measured by the
number of visitations on high-reward transitions per episode on the test
tasks. The purple dotted line corresponds to the random exploration policy.
The plot shows the concatenated training curves for all exploration policies.
Right: Learning curves of MESA under different settings using the meta-
exploration policies trained on the two different training-task distributions.

In Figure 7, we present the generalization results from our study. We evaluate
the zero-shot generalization ability of the meta-exploration policy by
measuring the average number of high-reward transitions hit in a test task
randomly sampled from the test task distribution. As shown on the left of
Figure 7, the meta-exploration policies are able to explore the test-time
tasks much more efficiently than a random exploration policy, even on test-
time tasks that are drawn from a harder task distribution. Notably, the
generalization ability increases with the number of exploration policies
($B$). Using the meta-exploration policies trained on the simpler tasks, MESA
is able to consistently reach the high-reward region in the unseen hard
$3$-agent tasks, as opposed to the vanilla MADDPG algorithm that only learns
the sub-optimal equilibrium. We also see that with an increasing number of
meta-exploration policies, the performance of MESA increases, but the
improvement becomes marginal, while the meta-training time increases linearly
with E.

##  7\. Conclusions

This paper introduces a meta-exploration method, MESA, for multi-agent
learning. The key idea is to learn a diverse set of exploration policies to
cover the high-rewarding state-action subspace and achieve efficient
exploration in an unseen task. MESA can work with any off-policy MARL
algorithm, and empirical results confirm the effectiveness of MESA in climb
games, MPE environments, and multi-agent MuJoCo environments and its
generalizability to more complex test-time tasks.

This research is supported in part by NSF IIS-2046640 (CAREER) and Sloan
Research Fellowship. We thank NVIDIA for providing computing resources.
Zhicheng Zhang is supported in part by SCS Dean’s Fellowship. The funders have
no role in study design, data collection and analysis, decision to publish, or
preparation of the manuscript.

## References

  * (1)
  * Andreas et al. (2017) Jacob Andreas, Dan Klein, and Sergey Levine. 2017.  Modular multitask reinforcement learning with policy sketches. In _ICML_. PMLR, 166–175.
  * Andrychowicz et al. (2017) Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. 2017.  Hindsight experience replay.  _arXiv preprint arXiv:1707.01495_ (2017).
  * Bellemare et al. (2016) Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. 2016.  Unifying count-based exploration and intrinsic motivation.  _NeurIPS_ 29 (2016), 1471–1479.
  * Blum and Rivest (1988) Avrim Blum and Ronald Rivest. 1988.  Training a 3-node neural network is NP-complete.  _NeurIPS_ 1 (1988).
  * Burda et al. (2018) Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. 2018.  Exploration by random network distillation. In _ICLR_.
  * Colas et al. (2017) Cédric Colas, Olivier Sigaud, and Pierre-Yves Oudeyer. 2017.  GEP-PG: Decoupling Exploration and Exploitation in Deep Reinforcement Learning Algorithms. In _ICML_.
  * Dorfman et al. (2020) Ron Dorfman, Idan Shenfeld, and Aviv Tamar. 2020.  Offline Meta Learning of Exploration.  _arXiv preprint arXiv:2008.02598_ (2020).
  * Du and Lee (2018) Simon Du and Jason Lee. 2018.  On the power of over-parametrization in neural networks with quadratic activation. In _ICML_. PMLR, 1329–1338.
  * Duan et al. (2016) Yan Duan, John Schulman, Xi Chen, Peter L Bartlett, Ilya Sutskever, and Pieter Abbeel. 2016.  Rl 2: Fast reinforcement learning via slow reinforcement learning.  _arXiv preprint arXiv:1611.02779_ (2016).
  * Ecoffet et al. (2021) Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. 2021.  First return, then explore.  _Nature_ 590, 7847 (2021), 580–586.
  * Espeholt et al. (2018) Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, et al. 2018\.  Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In _ICML_. PMLR, 1407–1416.
  * Finn et al. (2017) Chelsea Finn, Pieter Abbeel, and Sergey Levine. 2017.  Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks. In _Proceedings of the 34th ICML_ _(PMLR, Vol. 70)_ , Doina Precup and Yee Whye Teh (Eds.). PMLR, 1126–1135.  https://proceedings.mlr.press/v70/finn17a.html
  * Gu et al. (2016) Shixiang Gu, Timothy Lillicrap, Ilya Sutskever, and Sergey Levine. 2016.  Continuous deep q-learning with model-based acceleration. In _ICML_. PMLR, 2829–2838.
  * Gupta et al. (2018) Abhishek Gupta, Russell Mendonca, Yuxuan Liu, Pieter Abbeel, and Sergey Levine. 2018.  Meta-Reinforcement Learning of Structured Exploration Strategies.  _NIPS 2018_ (2018), 5302–5311.
  * Gupta et al. (2021) Tarun Gupta, Anuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. 2021.  Uneven: Universal value exploration for multi-agent reinforcement learning. In _ICML_. PMLR, 3930–3941.
  * Hessel et al. (2019) Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado van Hasselt. 2019.  Multi-task deep reinforcement learning with popart. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 3796–3803.
  * Hughes et al. (2018) Edward Hughes, Joel Z Leibo, Matthew Phillips, Karl Tuyls, Edgar Duenez-Guzman, Antonio Garcia Castaneda, Iain Dunning, Tina Zhu, Kevin McKee, Raphael Koster, et al. 2018\.  Inequity aversion improves cooperation in intertemporal social dilemmas.  _NIPS 2018_ 31 (2018).
  * Jaques et al. (2019) Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. 2019.  Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In _ICML_. PMLR, 3040–3049.
  * Jaques et al. (2018) Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro A Ortega, DJ Strouse, Joel Z Leibo, and Nando de Freitas. 2018.  Intrinsic social motivation via causal influence in multi-agent RL.  (2018).
  * Lan et al. (2019) Lin Lan, Zhenguo Li, Xiaohong Guan, and Pinghui Wang. 2019.  Meta reinforcement learning with task embedding and shared policy.  _arXiv preprint arXiv:1905.06527_ (2019).
  * Liu et al. (2021) Iou-Jen Liu, Unnat Jain, Raymond A Yeh, and Alexander Schwing. 2021.  Cooperative exploration for multi-agent deep reinforcement learning. In _ICML_. PMLR, 6826–6836.
  * Lloyd (1982) Stuart Lloyd. 1982.  Least squares quantization in PCM.  _IEEE transactions on information theory_ 28, 2 (1982), 129–137.
  * Lowe et al. (2017) Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. 2017.  Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. In _NIPS_.
  * Mahajan et al. (2019) Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. 2019.  MAVEN: Multi-Agent Variational Exploration. In _NeurIPS_ , Vol. 32. 7613–7624.
  * Ostrovski et al. (2017) Georg Ostrovski, Marc G Bellemare, Aäron Oord, and Rémi Munos. 2017.  Count-based exploration with neural density models. In _ICML_. PMLR, 2721–2730.
  * Parisi et al. (2021) Simone Parisi, Victoria Dean, Deepak Pathak, and Abhinav Gupta. 2021.  Interesting object, curious agent: Learning task-agnostic exploration.  _NeurIPS_ 34 (2021), 20516–20530.
  * Parisotto et al. (2016) Emilio Parisotto, Lei Jimmy Ba, and Ruslan Salakhutdinov. 2016.  Actor-Mimic: Deep Multitask and Transfer Reinforcement Learning. In _ICLR (Poster)_.
  * Pathak et al. (2017) Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. 2017.  Curiosity-driven exploration by self-supervised prediction. In _ICML_. PMLR, 2778–2787.
  * Peng et al. (2021) Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. 2021.  Facmac: Factored multi-agent centralised policy gradients.  _NeurIPS_ 34 (2021).
  * Pomerleau (1991) Dean A Pomerleau. 1991.  Efficient training of artificial neural networks for autonomous navigation.  _Neural computation_ 3, 1 (1991), 88–97.
  * Pong et al. (2021) Vitchyr H Pong, Ashvin Nair, Laura Smith, Catherine Huang, and Sergey Levine. 2021.  Offline Meta-Reinforcement Learning with Online Self-Supervision.  _arXiv preprint arXiv:2107.03974_ (2021).
  * Rakelly et al. (2019) Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. 2019.  Efficient off-policy meta-reinforcement learning via probabilistic context variables. In _ICML_. PMLR, 5331–5340.
  * Rashid et al. (2018) Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. 2018.  Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In _ICML_. PMLR, 4295–4304.
  * Riedmiller et al. (2018) Martin Riedmiller, Roland Hafner, Thomas Lampe, Michael Neunert, Jonas Degrave, Tom Wiele, Vlad Mnih, Nicolas Heess, and Jost Tobias Springenberg. 2018.  Learning by playing solving sparse reward tasks from scratch. In _ICML_. PMLR, 4344–4353.
  * Schäfer et al. (2022) Lukas Schäfer, Filippos Christianos, Josiah P Hanna, and Stefano V Albrecht. 2022.  Decoupled Reinforcement Learning to Stabilise Intrinsically-Motivated Exploration. In _Proceedings of the 21st AAMAS_. 1146–1154.
  * Singh et al. (2020) Avi Singh, Huihan Liu, Gaoyue Zhou, Albert Yu, Nicholas Rhinehart, and Sergey Levine. 2020.  Parrot: Data-Driven Behavioral Priors for Reinforcement Learning. In _ICLR_.
  * Tang et al. (2017) Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. 2017.  # exploration: A study of count-based exploration for deep reinforcement learning. In _31st NIPS_ , Vol. 30. 1–18.
  * Wang et al. (2019a) Pin Wang, Hanhan Li, and Ching-Yao Chan. 2019a.  Quadratic Q-network for learning continuous control for autonomous vehicles.  _arXiv preprint arXiv:1912.00074_ (2019).
  * Wang et al. (2019b) Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang. 2019b.  Influence-Based Multi-Agent Exploration. In _ICLR_.
  * Xu et al. (2018) Tianbing Xu, Qiang Liu, Liang Zhao, and Jian Peng. 2018.  Learning to explore with meta-policy gradient.  _arXiv preprint arXiv:1803.05044_ (2018).
  * Yu et al. (2021) Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. 2021.  The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games.  arXiv:2103.01955 [cs.LG]
  * Zhang et al. (2021) Jin Zhang, Jianhao Wang, Hao Hu, Tong Chen, Yingfeng Chen, Changjie Fan, and Chongjie Zhang. 2021.  Metacure: Meta reinforcement learning with empowerment-driven exploration. In _ICML_. PMLR, 12600–12610.
  * Zheng et al. (2021) Lulu Zheng, Jiarui Chen, Jianhao Wang, Jiamin He, Yujing Hu, Yingfeng Chen, Changjie Fan, Yang Gao, and Chongjie Zhang. 2021.  Episodic Multi-agent Reinforcement Learning with Curiosity-driven Exploration.  _NeurIPS_ 34 (2021).
  * Zintgraf et al. (2020) Luisa Zintgraf, Kyriacos Shiarlis, Maximilian Igl, Sebastian Schulze, Yarin Gal, Katja Hofmann, and Shimon Whiteson. 2020.  VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learning. In _ICLR_.

Appendix

##  Appendix A Proofs

###  A.1. Proof of Lemma on Equivalent Optimality

######  Lemma A.1.

In the 2-agent Climb Game with single-agent action space $|\mathcal{A}|=U$ and
reward matrix

$R=\begin{pmatrix}r&0&\cdots&0\\\ 0&r(1-\delta)&\cdots&r(1-\delta)\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&r(1-\delta)&\cdots&r(1-\delta)\end{pmatrix},$

for any exploration policy $p_{e}$ where $p_{e}^{(t)}(i,j)$ is the probability
of trying action $(i,j)$ at time step $t$, given the objective function

$\displaystyle\mathcal{J}^{(T)}(\mathbf{W},\mathbf{b},\mathbf{c},d)$
$\displaystyle=$ $\displaystyle\sum_{t=1}^{T}\mathbb{E}_{(i,j)\sim
p_{e}^{(t)}}\left[\log\mathcal{N}(q(\mathbf{e}_{i},\mathbf{e}_{j};\mathbf{W},\mathbf{b},\mathbf{c},d)-R_{ij};0,\sigma^{2}_{e})\right]$
$\displaystyle+$
$\displaystyle\log\mathcal{N}(W;0,\sigma^{2}_{W}I)+\text{Constant}$ (8)

maximized by parameters $\mathbf{W}^{*},\mathbf{b}^{*},\mathbf{c}^{*},d^{*}$,
the joint Q function
$q(\mathbf{e}_{i},\mathbf{e}_{j};\mathbf{W}^{*},\mathbf{b}^{*},\mathbf{c}^{*},d^{*})$
is equivalently optimal if the following criterion holds

$r\delta\geq\left(\frac{f_{2}}{f_{0}}-1\right)\frac{m^{2}}{f_{2}\lambda+m^{2}}\frac{r(2-\delta)}{1+\frac{2f_{2}(f_{1}\lambda+2m)m}{f_{1}(f_{2}\lambda+m^{2})}+\frac{f_{2}(f_{0}\lambda+1)m^{2}}{f_{0}(f_{2}\lambda+m^{2})}}.$
(9)

Here we use

$\displaystyle f_{0}=$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}p_{e}^{(t)}(0,0)$ $\displaystyle
f_{1}=$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{U-1}\left(p_{e}^{(t)}(0,i)+p_{e}^{(t)}(i,0)\right)$
$\displaystyle f_{2}=$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{U-1}\sum_{j=1}^{U-1}p_{e}^{(t)}(i,j)$
$\displaystyle m=$ $\displaystyle U-1$ $\displaystyle\lambda=$
$\displaystyle\frac{T\sigma_{w}^{2}}{\sigma_{e}^{2}}$

for a clearer demonstration of the criterion.

###### Proof.

From the symmetry of the parameters and the concavity of the objective
function, $\exists W_{0},W_{1},W_{2},B,C,D$ such that

$\displaystyle W_{0}=$ $\displaystyle\mathbf{W}^{*}_{00}$ $\displaystyle
W_{1}=$ $\displaystyle\mathbf{W}^{*}_{0i}=\mathbf{W}^{*}_{i0},$
$\displaystyle\forall i\neq 0$ $\displaystyle W_{2}=$
$\displaystyle\mathbf{W}^{*}_{ij},$ $\displaystyle\forall i,j\neq 0$
$\displaystyle B=$ $\displaystyle\mathbf{b}^{*}_{0}=\mathbf{c}^{*}_{0}$
$\displaystyle C=$ $\displaystyle\mathbf{b}^{*}_{i}=\mathbf{c}^{*}_{i},$
$\displaystyle\forall i\neq 0$ $\displaystyle D=$ $\displaystyle d$

Rewrite the objective function (A.1) we obtain

$\displaystyle\mathcal{J}=$
$\displaystyle-\frac{T}{2\sigma_{e}^{2}}\left(f_{0}(W_{0}+2B+D-r)^{2}\right.$
$\displaystyle+$ $\displaystyle f_{1}(W_{1}+B+C+D)^{2}$ $\displaystyle+$
$\displaystyle\left.f_{2}(W_{2}+2C+D-r(1-\delta))^{2}\right)$ $\displaystyle-$
$\displaystyle\frac{1}{2\sigma_{w}^{2}}\left(W_{0}^{2}+2mW_{1}^{2}+m^{2}W_{2}^{2}\right)$
(10)

Further, let

$\displaystyle K_{0}=$ $\displaystyle 2B+D-r$ $\displaystyle K_{1}=$
$\displaystyle B+C+D$ $\displaystyle K_{2}=$ $\displaystyle 2C+D-r(1-\delta)$

and immediately

$K_{0}+K_{2}=2K_{1}-r(2-\delta)$ (11)

Following equation (A.1),

$\displaystyle\left(2\frac{\partial}{\partial W_{0}}+\frac{\partial}{\partial
W_{1}}-\frac{\partial}{\partial B}\right)\mathcal{J}=0\Rightarrow$
$\displaystyle W_{0}=-mW_{1}$ $\displaystyle\left(2\frac{\partial}{\partial
W_{2}}+\frac{\partial}{\partial W_{1}}-\frac{\partial}{\partial
C}\right)\mathcal{J}=0\Rightarrow$ $\displaystyle W_{1}=-mW_{2}$
$\displaystyle\frac{\partial}{\partial W_{0}}\mathcal{J}=0\Rightarrow$
$\displaystyle W_{0}=-\frac{f_{0}\lambda}{f_{0}\lambda+1}K_{0}$
$\displaystyle\frac{\partial}{\partial W_{1}}\mathcal{J}=0\Rightarrow$
$\displaystyle W_{1}=-\frac{f_{1}\lambda}{f_{1}\lambda+2m}K_{1}$
$\displaystyle\frac{\partial}{\partial W_{2}}\mathcal{J}=0\Rightarrow$
$\displaystyle W_{2}=-\frac{f_{2}\lambda}{f_{2}\lambda+m^{2}}K_{2}$
$\displaystyle\frac{\partial}{\partial B}\mathcal{J}=0\Rightarrow$
$\displaystyle\frac{W_{0}+K_{0}}{W_{1}+K_{1}}=-\frac{f_{1}}{2f_{0}}$
$\displaystyle\frac{\partial}{\partial C}\mathcal{J}=0\Rightarrow$
$\displaystyle\frac{W_{1}+K_{1}}{W_{2}+K_{2}}=-\frac{2f_{2}}{f_{1}}$

and together with equation (11), we obtain

$\displaystyle
K_{2}=\frac{r(2-\delta)}{1+\frac{2f_{2}(f_{1}\lambda+2m)m}{f_{1}(f_{2}\lambda+m^{2})}+\frac{f_{2}(f_{0}\lambda+1)m^{2}}{f_{0}(f_{2}\lambda+m^{2})}}.$
(12)

Finally we deduce the criterion

$\displaystyle W_{0}+2B+D\geq W_{2}+2C+D$ $\displaystyle\Leftrightarrow$
$\displaystyle r\delta\geq\left(1-\frac{f_{2}}{f_{0}}\right)(W_{2}+K_{2})$
$\displaystyle\Leftrightarrow$ $\displaystyle
r\delta\geq\left(\frac{f_{2}}{f_{0}}-1\right)\frac{m^{2}}{f_{2}\lambda+m^{2}}\frac{r(2-\delta)}{1+\frac{2f_{2}(f_{1}\lambda+2m)m}{f_{1}(f_{2}\lambda+m^{2})}+\frac{f_{2}(f_{0}\lambda+1)m^{2}}{f_{0}(f_{2}\lambda+m^{2})}}.$

∎

###  A.2. Proof for Theorem 4.2 (uniform exploration)

Theorem 4.2. _Assume $\delta\leq\frac{1}{6},U\geq 3$. In the Climb Game
$G_{f}(2,0,U)$, given the quadratic joint Q function form
$q(\mathbf{x},\mathbf{y};\mathbf{W},\mathbf{b},\mathbf{c},d)$ and a Gaussian
prior $p(\mathbf{W})=\mathcal{N}(\mathbf{W};0,\sigma^{2}_{w}I)$, using a
uniform exploration policy,
$q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ will become
equivalently optimal only after $T=\Omega(|\mathcal{A}|\delta^{-1})$ steps.
When $\delta=1$, $T=O(1)$ steps suffice to learn the equivalently optimal
joint Q function, meaning the inefficiency of uniform exploration is due to a
large set of suboptimal NEs. _

###### Proof.

Under uniform exploration,

$f_{0}=\frac{1}{U^{2}},f_{1}=\frac{2m}{U^{2}},f_{2}=\frac{m^{2}}{U^{2}}.$

Criterion (9) can be reformulated to

$\delta\geq\frac{(m^{2}-1)(2-\delta)}{\left(1+\frac{\lambda}{U^{2}}\right)(m+1)^{2}}$
(13)

and thus with $\lambda=\frac{T\sigma_{w}^{2}}{\sigma_{e}^{2}},m\geq
2,\delta\leq\frac{1}{6}$,

$\displaystyle T\geq$
$\displaystyle\frac{U^{2}\sigma_{e}^{2}}{\sigma_{w}^{2}}\left(\frac{(m^{2}-1)(2-\delta)}{(m+1)^{2}}-1\right)$
$\displaystyle\geq$
$\displaystyle\frac{U^{2}\sigma_{e}^{2}}{\sigma_{w}^{2}}\left(\frac{3}{\delta}-\frac{6}{\delta}\right)$
$\displaystyle=$
$\displaystyle\frac{U^{2}\sigma_{e}^{2}}{6\sigma_{w}^{2}\delta}$

On the other hand, in non-penalty Climb Game where $\delta=1$, if at any time
step $\exists(i,j)\neq(0,0)$ where the joint Q function
$q_{\mathcal{J}^{(T)}}$ weighs action $(a_{i},a_{j})$ more than the action
$(a_{0},a_{0})$, just swap the parameters related to $(i,j)$ with thos related
to $(0,0)$ and the objective function $\mathcal{J}^{(T)}$ will be increased,
which makes a contradiction. Hence, $T=1$ suffices for the non-penalty Climb
Game.

∎

###  A.3. Proof for Theorem 4.3 ($\epsilon$-greedy exploration)

Theorem 4.3 _Assume
$\delta\leq\frac{1}{32},U\geq\max(4,\sigma_{w}\sigma_{e}^{-1})$. In the Climb
Game $G_{f}(2,0,U)$, given the quadratic joint Q function form
$q(\mathbf{x},\mathbf{y};\mathbf{W},\mathbf{b},\mathbf{c},d)$ and a Gaussian
prior $p(\mathbf{W})=\mathcal{N}(\mathbf{W};0,\sigma^{2}_{w}I)$, under
$\epsilon$-greedy exploration with fixed $\epsilon\leq\frac{1}{2}$,
$q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ will become
equivalently optimal only after
$T=\Omega(|\mathcal{A}|\delta^{-1}\epsilon^{-1})$ steps. If $\epsilon(t)=1/t$,
it requires $T=\exp\left(\Omega\left(|\mathcal{A}|\delta^{-1}\right)\right)$
exploration steps to be equivalently optimal. _

###### Proof.

Under the circumstances here, after the first step of uniform exploration, the
sub-optimal policy will be used for $\epsilon$-greedy exploration. Then for
both fixed $\epsilon$ or linearly decaying $\epsilon$, the following always
holds:

$\displaystyle\frac{f_{1}}{f_{0}}=$ $\displaystyle 2m$
$\displaystyle\frac{f_{2}}{f_{0}}\geq$ $\displaystyle\max(2,m^{2})$
$\displaystyle f_{2}\geq$
$\displaystyle\min(1-\epsilon,m^{2}U^{-2})\geq\frac{1}{2}.$

Then it can be derived from criterion 9 that

$\displaystyle r\delta\geq$
$\displaystyle\left(\frac{f_{2}}{f_{0}}-1\right)\frac{m^{2}}{f_{2}\lambda+m^{2}}\frac{r(2-\delta)}{1+\frac{2f_{2}(f_{1}\lambda+2m)m}{f_{1}(f_{2}\lambda+m^{2})}+\frac{f_{2}(f_{0}\lambda+1)m^{2}}{f_{0}(f_{2}\lambda+m^{2})}}$
$\displaystyle=$
$\displaystyle\left(\frac{f_{2}}{f_{0}}-1\right)\frac{m^{2}}{f_{2}\lambda+m^{2}}\frac{r(2-\delta)}{1+\frac{f_{2}(f_{0}\lambda+1)(m^{2}+2m)}{f_{0}(f_{2}\lambda+m^{2})}}$
$\displaystyle=$
$\displaystyle\left(\frac{f_{2}}{f_{0}}-1\right)\frac{m^{2}}{f_{2}\lambda+m^{2}}\frac{r(2-\delta)}{(m+1)^{2}}$
(14) $\displaystyle\geq$
$\displaystyle(m^{2}-1)\frac{m^{2}}{\lambda+m^{2}}\frac{r(2-\delta)}{(m+1)^{2}}$

Similar to inequality (13), this yields to

$\displaystyle\lambda\geq\frac{m^{2}}{6\delta}$ (15)

Following inequality (A.3), we further get

$\displaystyle r\delta\geq$
$\displaystyle\left(\frac{f_{2}}{f_{0}}-1\right)\frac{m^{2}}{f_{2}\lambda+m^{2}}\frac{r(2-\delta)}{(m+1)^{2}}$
$\displaystyle\geq$
$\displaystyle\frac{f_{2}}{2f_{0}}\frac{m^{2}}{\lambda+\lambda}\frac{r}{4m^{2}}$
$\displaystyle\geq$ $\displaystyle\frac{r}{16f_{0}\lambda},$

which is

$\lambda\geq\frac{\delta^{-1}}{16f_{0}}$ (16)

For fixed $\epsilon$,

$f_{0}\leq\frac{\epsilon}{U^{2}}+\frac{1}{TU^{2}}\leq\frac{\epsilon}{U^{2}}+\lambda^{-1},$

and further

$\displaystyle\lambda\geq\frac{\delta^{-1}}{16(\frac{\epsilon}{U^{2}}+\lambda^{-1})}$
$\displaystyle\Rightarrow$
$\displaystyle\lambda\geq\frac{U^{2}}{\epsilon}\left(\frac{\delta^{-1}}{16}-1\right)\geq\frac{U^{2}\delta^{-1}}{32\epsilon}$

which shows that

$T=\Theta(\lambda)=\Omega(U^{2}\delta^{-1}\epsilon^{-1}).$

When $\epsilon=\frac{1}{T}$,

$f_{0}\leq\frac{1}{U^{2}}\frac{\sum_{t=1}^{T}\frac{1}{t}}{T}\leq\frac{2\log(T)}{U^{2}T}$

and further

$\displaystyle\lambda\geq\frac{\delta^{-1}}{16\frac{2\log(T)}{U^{2}T}}$
$\displaystyle\Rightarrow$
$\displaystyle\log(T)\geq\frac{U^{2}\sigma_{e}^{2}}{32\sigma_{w}^{2}\delta}$

which shows that

$T=\exp(\Omega(U^{2}\delta^{-1})).$

∎

###  A.4. Proof for Theorem 4.4 (Structured exploration)

Theorem 4.4 _In the Climb Game $G_{f}(2,0,U)$, given the quadratic joint Q
function form $q(\mathbf{x},\mathbf{y};\mathbf{W},\mathbf{b},\mathbf{c},d)$
and a Gaussian prior
$p(\mathbf{W})=\mathcal{N}(\mathbf{W};0,\sigma^{2}_{w}I)$, under structured
exploration $p_{e}^{(t)}(i,j)=U^{-1}\left[\mathds{1}_{i=j}\right]$,
$q_{\mathcal{J}^{(T)}}(\mathbf{W},\mathbf{b},\mathbf{c},d)$ is equivalently
optimal at step $T=O(1)$. _

###### Proof.

It is easy to verify that
$\mathbf{W}=\mathbf{c}=0,\mathbf{b}=(1,0,....,0)^{\top},d=0$ is the learned
parameter that maximizes both the prior of $\mathbf{W}$ and the likelihood of
prediction error at any step $T$. This parameter configuration directly gives
the joint $Q$ function that is equivalently optimal.

∎

###  A.5. Proof for Theorem 5.1 (Exploration during Meta-Testing)

######  Definition A.2 ($\epsilon$ Generalization).

Suppose there are training and testing data from the same space $\mathcal{S}.$
Let $g(x,y)\in\\{0,1\\}$ denote whether a exploration policy trained on
training sample $x$ can learn to explore $y$ during testing time. And we
always assume $g(x,y)=g(y,x)$. Then we say a exploration policy generalizes to
explore $\epsilon$ nearby goals if for every training sample $x$, $\exists$ a
neighbourhood $|\Omega(x)|\geq\epsilon$ of $x$ s.t. $\forall y\in\Omega(x)$,
$g(x,y)=1$. Intuitively, that means the exploration policies learns to explore
$\epsilon$ nearby region of every training sample.

Theorem 5.1[Exploration during Meta-Testing] _Consider goal-oriented tasks
with goal space $\mathcal{G}\subseteq\mathcal{S}$. Assume the training and
testing goals are sampled from the distribution $p(x)$ on $\mathcal{G}$, the
dataset has $N$ i.i.d. goals sampled from a distribution $q(x)$ on
$\mathcal{S}$. If the exploration policy generalizes to explore $\epsilon$
nearby goals for every training sample, we have that the testing goal is not
explored with probability at most_

$P_{\text{fail}}\approx\int p(x)(1-\epsilon q(x))^{N}dx\leq
O\left(\frac{KL(p||q)+\mathcal{H}(p)}{\log(\epsilon N)}\right).$ (17)

_Here we make the assumption that $\epsilon$ is small and $g$ is Lipschitz
continuous. _

###### Proof.

For any testing goal $x$, every training sample $t\in\Omega(x)$ enables the
exploration policy to explore $y$ during testing time. As $\Omega(x)$ is a
neighborhood of $x$ and $g$ is Lipschitz continuous, we can select $\epsilon$
training samples $t$ from $\Omega(x)$ that is closest to $x$, and we think
those samples $t$ has a similar sampling density function, i.e., $g(t)\approx
g(x)$. Thus, with $N$ i.i.d samples, there is approximately $(1-\epsilon
q(x))^{N}$ probability that testing goals $x$ will not be explored during the
testing time. Then we have

$\displaystyle P_{\text{fail}}\approx$ $\displaystyle\int p(x)(1-\epsilon
q(x))^{N}dx$ $\displaystyle\leq$ $\displaystyle\int p(x)e^{-N\epsilon q(x)}dx$
$\displaystyle\leq$ $\displaystyle\int
p(x)\frac{\log\frac{1}{q(x)}+2q(x)+16}{\frac{1}{2}\log(\epsilon N)}dx$
$\displaystyle=$ $\displaystyle
O\left(\frac{KL(p||q)+\mathcal{H}(p)}{\log(\epsilon N)}\right)$

∎

You may refer to the following lemma which is used in the above proof.

######  Lemma A.3.

$\forall k>16,x>0$,

$e^{-kx}\leq\frac{\log\frac{1}{x}}{\frac{1}{2}\log k}+\frac{x}{\frac{1}{2}\log
k}+\frac{x}{k}$ (18)

###### Proof.

Let $x_{0}=\frac{2\log k}{k}$. We can prove inequality 18 by proving the
following three conditions.

$1.\leavevmode\nobreak\ \leavevmode\nobreak\ \forall x\geq
x_{0},\frac{x}{k}\geq e^{-kx}$ (19)

$2.\leavevmode\nobreak\ \leavevmode\nobreak\ \forall 0\leq x\leq
x_{0},\frac{\log\frac{1}{x}}{\frac{1}{2}\log k}\geq e^{-kx}$ (20)

$3.\leavevmode\nobreak\ \leavevmode\nobreak\ \forall x>0,x+\log\frac{1}{x}\geq
0.$ (21)

To prove (19), it suffices to show

$\frac{x_{0}}{k}=\frac{2\log k}{k^{2}}\geq\frac{1}{k^{2}}=e^{-kx_{0}},$

as $\frac{x}{k}$ is monotone increasing and $e^{-kx}$ is monotone decreasing.

Now we prove (20). Let

$f(x)=\frac{\log\frac{1}{x}}{\frac{1}{2}\log k}-e^{-kx}.$

Since

$xf^{\prime}(x)=kxe^{-kx}-\frac{2}{\log k}$

is increasing for $x\in(0,1/k)$ and decreasing for $x\in(1/k,+\infty)$,
$\exists 0<x_{1}<1/k<x_{2}$ s.t. $f^{\prime}(x)>0\Leftrightarrow x_{1}\leq
x\leq x_{2}$. Here $x_{1},x_{2}$ are two solutions of $kxe^{-kx}-2/\log k=0$.

Therefore, to prove (20), it suffices to show $f(x_{1})\geq 0$ and
$f(x_{0})\geq 0$, and the later one can be verified as

$\displaystyle f(x_{0})=$ $\displaystyle\frac{\log\frac{k}{2\log
k}}{\frac{1}{2}\log k}-.\frac{1}{k^{2}}$ $\displaystyle\geq$
$\displaystyle\frac{\log 2}{\frac{1}{2}\log k}-\frac{1}{k^{2}}$
$\displaystyle\geq$ $\displaystyle 0$

Since $x_{1}<1/k$, we have

$\frac{2}{\log k}=kx_{1}e^{-kx_{1}}>\frac{kx_{1}}{e}\Rightarrow
x_{1}<\frac{1}{2}.$

Thus,

$\frac{2}{\log
k}=kx_{1}e^{-kx_{1}}>kx_{1}(1-kx_{1})>\frac{kx_{1}}{2}\Rightarrow
x_{1}<\frac{4}{k\log k}$

and

$\displaystyle f(x_{1})=$
$\displaystyle\frac{\log\frac{1}{x_{1}}}{\frac{1}{2}\log k}-e^{-kx_{1}}$
$\displaystyle\geq$ $\displaystyle\frac{\log\frac{k\log k}{4}}{\frac{1}{2}\log
k}-1$ $\displaystyle=$ $\displaystyle\frac{\log k+\log\log k-\log
4}{\frac{1}{2}\log k}-1$ $\displaystyle\geq$ $\displaystyle 0.$

Finally, (21) is direct from the fact $e^{x}\geq x$. ∎

##  Appendix B Additional Experiment Detail

###  B.1. Environment Settings

####  B.1.1. Climb Game Variants

(i) One-step climb game. A one-time climb game $G(n,k,u,U)$ is a $n$-player
matrix game where every player has $U$ actions to choose from. The reward is
determined by the number of players who choose action $u$, which can be
defined as

$\displaystyle R(\boldsymbol{a})=\begin{cases}1,&\text{if \\#}u=k,\\\
1-\delta,&\text{if \\#}u=0,\\\ 0,&\text{otherwise}.\end{cases}$

where $\delta\in(0,1)$.

The task space $\mathcal{T}^{\text{one}}_{U}$ contains all $2$-player one-step
climb games with $U$ actions for each player, i.e.,
$\mathcal{T}^{\text{one}}_{U}=\\{G(2,k,u,U)\mid 1\leq k\leq n,0\leq u<U\\}$.

(ii) Multi-stage climb game. A multi-stage climb game
$\hat{G}(S,n,[(k_{t},u_{t})]_{t=1}^{S},U)$ is an $S$-stage game, where each
stage $t$ itself is a one-step climb game $G(n,k_{t},u_{t},U)$. At stage $t$,
agent $i$ is given the observation $\mathcal{O}_{i}^{t}=[t,h_{t-1}]$, where
$h_{t-1}$ is the history of the joint actions.

The task space $\mathcal{T}^{\text{multi}}_{S,U}$ consists of all $2$-player
multi-stage climb game with $S$ stages and $U$ actions, i.e.,
$\mathcal{T}^{\text{multi}}_{S,U}=\hat{G}(S,2,[(k_{t},u_{t})]_{t=1}^{S},U)\mid\forall
t\ 1\leq k_{t}\leq n,0\leq u_{t}<U\\}$. We choose
$\mathcal{T}^{\text{multi}}_{5,10}$ ($10$-Multi) for the experiments.

In all experiments $\delta$ is set to $\frac{1}{2}$. We use
$\mathcal{T}^{\text{one}}_{10}$ and $\mathcal{T}^{\text{multi}}_{5,10}$ in our
experiments.The task distribution $p(\mathcal{T})$ is uniform over the task
space. Ten training tasks are sampled from the task distribution, and three
testing tasks that are different from the training tasks are chosen to
evaluate the performance.

####  B.1.2. MPE Domain

In a MPE Climb Game $\bar{G}(n,k,u,U,L)$, there are $U$ non-overlapping
landmarks on the map with positions $\\{L_{j}\\}_{j=0}^{U-1}$. We assume a
distribution $L\sim\Psi^{U}$ from which the landmark positions $L$. The reward
is determined by the number of agents locating on the $u$-th landmark. More
formally, suppose $f_{j}(s)$ is the number of agents locating on the $j$-th
landmark, the reward can be defined as

$\displaystyle R(s,\boldsymbol{a})=\begin{cases}1,&\text{if }f_{u}(s)=k\text{
and }\sum_{j=0}^{U-1}f_{j}(s)=n,\\\ 1-\delta,&\text{if }f_{u}(s)=0\text{ and
}\sum_{j=0}^{U-1}f_{j}(s)=n,\\\ 0,&\text{otherwise}.\end{cases}$

The observation of agent $i$ contains the relative positions of all landmarks
and other agents. As before, $u$ and $k$ will not be given in the observation
and can only be inferred from the received reward. A task space
$\mathcal{T}^{\text{MPE}}_{n,U}=\\{\bar{G}(n,k,u,U,L)\mid k=n,0\leq
0<U,L\sim\Psi^{U}\\}$ consists of all MPE climb games with $n$ players and $U$
landmarks, and is fully cooperative by setting $k=n$.

We evaluate MESA on the $2$-agent tasks ($\mathcal{T}^{\text{MPE}}_{2,5}$ and
$\mathcal{T}^{\text{MPE}}_{2,6}$) and $3$-agent tasks
($\mathcal{T}^{\text{MPE}}_{3,5}$ and $\mathcal{T}^{\text{MPE}}_{3,6}$) while
fixing $k=2$. The task distribution $p(\mathcal{T})$ is defined by the
probability density function $p(\bar{G}(n,k,u,U,L))=U^{-1}\Psi^{U}(L)$.

We set $\delta=\frac{1}{2}$. The environments are different in landmark
positions, and the tasks are different in target landmarks.

####  B.1.3. Multi-agent MuJoCo Domain

In the multi-agent MuJoCo Swimmer environment, we similarly define a climb
game $G(\alpha)$ where there are $2$ agents and the angular states of the two
joints determine the current action of the two agents. Specifically, if state
$s$ corresponds to the two joints forming angles of $\alpha_{1}$ and
$\alpha_{2}$, then the reward can be defined as:

$\displaystyle R(s,\boldsymbol{a})=\begin{cases}1,&\text{if
}|\alpha_{1}-\alpha|<\epsilon,|\alpha_{2}-\alpha|<\epsilon\\\
1-\delta,&\text{if
}|\alpha_{1}-\alpha|>\epsilon,|\alpha_{2}-\alpha|>\epsilon\\\
0,&\text{otherwise},\end{cases}$

where $\epsilon$ is a very small angle. The task space consists of target
angles between $-30$ degrees and $30$ degrees, i.e.,
$\mathcal{T}=\\{\alpha\mid-30^{\circ}<\alpha<30^{\circ}\\}$. We also set
$\delta=\frac{1}{2}$.

###  B.2. Hyperparameter and Computation Settings

The hyperparameters are detailed in Table 1. All tasks are sampled uniformly
at random from the task space detailed in Section 6 and then divided into the
training and testing tasks. We use different tasks for the meta-training
stage, which includes the high-reward dataset collection and the training of
the exploration policies. We evaluate the meta-trained exploration policies on
novel meta-testing tasks over $3$ runs with different seeds, each consisting
of a different set of meta-testing tasks. Computation is done on a 32-core CPU
with 256 GB RAM and an NVIDIA GeForce RTX 3090.

Hyperparameter | Value
---|---
off-policy MARL Algorithm $f$ | MADDPG
Meta-training steps |  | 50k in One-step Climb Game
---
100k in Multi-stage Climb Game
3M in MPE
3M in MA-MuJoCo
| High-reward data collection steps
---
| 30K in Climb Game
---
500k in MPE
1M in MA-MuJoCo
Meta-training task size |  |  $10$ in Climb Game
---
$30$ in MPE and MA-MuJoCo Swimmer
Meta-testing steps |  | 50k in One-step Climb Game
---
100k in Multi-stage Climb Game
3M/6M in MPE
2.5M in MA-MuJoCo Swimmer
Meta-testing task size |  |  $5$ in Climb Game
---
$15,18$ in $5$-agent MPE and $6$-agent MPE
$6$ in MA-MuJoCo Swimmer
Random exploration |  | 3000 steps in Climb Game
---
50K steps in MPE and MA-MuJoCo
Network architecture |  | Recurrent Neural Network
---
(one GRU layer with 64 hidden units)
Threshold $R^{\star}$ | 1 (sparse-reward tasks)
Relabel $\gamma$ | 0.05
Decreasing function $f_{d}$ | $1/x^{5}$
Distance Metric $\|\cdot\|_{\mathcal{F}}$ | L2 norm
Number of Exploration Policies |  | 4 in Climb Game
---
2/4 in MPE
2 in MA-MuJoCo
Learning rate | 5e-3/1e-4 (Adam optimizer)
Batch size |  | 32 trajectories in Climb Game
---
300 trajectories in MPE
8 trajectories in MA-MuJoCo
Table 1. Hyperparameters used in MESA

###  B.3. Baseline Methods

For MAPPO Yu et al. (2021) and Random Network Distillation Burda et al.
(2018), we use the released codebase111https://github.com/marlbenchmark/on-
policy.

For QMIX Rashid et al. (2018) and MAVEN Mahajan et al. (2019), we use the
released codebase222https://github.com/AnujMahajanOxf/MAVEN. In MA-MuJoCo
environments, we discretize the action into $11$ even points for QMIX.

For MAESN Gupta et al. (2018), we modify the single-agent version to a multi-
agent version by treating agents as independently optimizing their own returns
without consideration of the other agents.

For EMC Peng et al. (2021), we use the released
codebase333https://github.com/kikojay/EMC.

For meta-training-based methods, we pretrain a policy (conditioned or
unconditioned) with the same configuration of MESA (number of tasks, number of
training steps) and then deploy it on the meta-testing task. The goal-
conditioned policy takes the information of the task goal (key action for
climb game, key landmark id for MPE Domain, key angles for MA-MuJoCo) as
additional observation. We adapt C-BET Parisi et al. (2021) to multi-agent
based on MAPPO Yu et al. (2021).

###  B.4. Results On All Environments

|  | One-step
---
Climb Game
| Multi-stage
---
Climb Game
| 2A5L MPE
---
| 2A6L MPE
---
| 3A5L MPE
---
| 3A6L MPE
---
| MA-MuJoCo
---
Swimmer
MESA | 0.83 $\pm$ 0.20 | 0.81 $\pm$ 0.06 | 61.32 $\pm$ 8.24 | 58.73 $\pm$ 10.16 | 51.83 $\pm$ 13.37 | 44.71 $\pm$ 15.92 | 599.32 $\pm$ 35.93
MADDPG | 0.74 $\pm$ 0.25 | 0.50 $\pm$ 0.00 | 21.09 $\pm$ 23.07 | 19.44 $\pm$ 18.41 | 5.45 $\pm$ 6.49 | 3.16 $\pm$ 5.73 | 499.33 $\pm$ 0.52
MAPPO | 0.50 $\pm$ 0.00 | 0.54 $\pm$ 0.05 | 24.42 $\pm$ 2.99 | 27.57 $\pm$ 4.86 | 10.12 $\pm$ 5.83 | 13.52 $\pm$ 2.91 | 496.88 $\pm$ 1.98
MAPPO-RND | 0.50 $\pm$ 0.00 | 0.53 $\pm$ 0.04 | 24.05 $\pm$ 2.45 | 27.10 $\pm$ 5.67 | 17.18 $\pm$ 3.52 | 7.30 $\pm$ 2.76 | 496.36 $\pm$ 1.76
QMIX | 0.50 $\pm$ 0.00 | 0.50 $\pm$ 0.00 | 0.21 $\pm$ 0.04 | 0.48 $\pm$ 0.12 | 0.06 $\pm$ 0.02 | 0.04 $\pm$ 0.03 | 499.97 $\pm$ 0.03
MAVEN | 0.50 $\pm$ 0.00 | 0.50 $\pm$ 0.00 | 0.06 $\pm$ 0.03 | 0.13 $\pm$ 0.10 | 0.06 $\pm$ 0.05 | 0.07 $\pm$ 0.00 | 495.41 $\pm$ 2.63
EMC | 0.50 $\pm$ 0.00 | 0.50 $\pm$ 0.00 | 50.49 $\pm$ 17.26 | 50.61 $\pm$ 17.41 | 36.63 $\pm$ 0.11 | 36.47 $\pm$ 0.28 | 499.66 $\pm$ 0.20
Pretrain | 0.55 $\pm$ 0.00 | 0.55 $\pm$ 0.00 | 23.26 $\pm$ 2.19 | 29.81 $\pm$ 4.97 | 17.91 $\pm$ 2.63 | 17.72 $\pm$ 5.28 | 496.49 $\pm$ 1.33
CBET | 0.55 $\pm$ 0.00 | 0.55 $\pm$ 0.00 | 23.69 $\pm$ 1.01 | 28.37 $\pm$ 3.59 | 19.85 $\pm$ 5.05 | 19.80 $\pm$ 4.36 | 497.54 $\pm$ 1.49
Goal | 0.55 $\pm$ 0.00 | 0.55 $\pm$ 0.00 | 31.61 $\pm$ 0.90 | 32.14 $\pm$ 0.10 | 30.60 $\pm$ 1.03 | 30.44 $\pm$ 0.60 | 498.13 $\pm$ 0.45
Table 2. Summary of final performance for all the algorithms evaluated on all
the environments. Numbers in bold indicate the best performing in a particular
environment. For simplicity, 2A5L MPE stands for $2$-agent MPE with 5
landmarks and the same for other MPE results.

Table 2 gives the final performance for each algorithm in all environments. We
observe that our proposed MESA outperforms all other baseline methods across
all environments.

##  Appendix C Visualization of Learned Exploration Policies

We visualize two exploration policies in the 2-agent 3-landmark MPE Climb Game
tasks. Both exploration policies are shown in Figure 8. In addition, the
learned policy visited the three landmarks within $20$ timesteps, less than a
third of the length of the trajectory, which showcases its ability to quickly
cover the collected promising subspace. Both policies successfully visited all
three landmarks consecutively and within only $1/3$ of the episode length.

Figure 8. Visualization of two learned exploration policies in 2-agent
3-landmark MPE tasks. The figure shows the critical steps in the trajectory
where agents coordinately reach high-rewarding states that were previously
collected.

##  Appendix D Ablation studies

Figure 9. Ablation study. Comparing our approach with 1) vanilla MADDPG
without using the high-rewarding state-action dataset $\mathcal{M}_{*}$ or the
trained exploration policies and 2) initializing the replay buffer with the
$\mathcal{M}_{*}$ but not using the exploration policies, we show that both
components contribute to overall performance.

To figure out the extent to which the high-rewarding state-action dataset
$\mathcal{M}_{*}$ and the trained exploration policies contribute to the
overall better performance, we perform an ablation study on the MPE domain.

We observe in Figure 9 that by initializing the buffer with $\mathcal{M}_{*}$,
the training process is accelerated (from $1$M steps to $2$M steps). However,
even though $\mathcal{M}_{*}$ contains the collected high-reward states,
directly learning the intrinsic structure and generalizing to unseen meta-
testing tasks is nontrivial. Hence, MADDPG with $\mathcal{M}_{*}$
initialization still fails to learn the optimal NE.

But when assisted with the trained exploration policies, the algorithm is able
to find the global optimum while also training faster than the vanilla MADDPG.
The greater variance of the ablated method also suggests that
$\mathcal{M}_{*}$ contains useful but subtle information for learning, and the
exploration policies help with extracting that information.