# Multi-agent Reinforcement Learning: A Comprehensive Survey

Dom Huh  University of California, Davis
{dhuh<EMAIL_ADDRESS>Prasant Mohapatra  University of California,
Davis
{dhuh<EMAIL_ADDRESS>University of South Florida

###### Abstract

The prevalence of multi-agent applications pervades various interconnected
systems in our everyday lives. Despite their ubiquity, the integration and
development of intelligent decision-making agents in a shared environment pose
challenges to their effective implementation. This survey delves into the
domain of multi-agent systems (MAS), placing a specific emphasis on unraveling
the intricacies of learning optimal control within the MAS framework, commonly
known as multi-agent reinforcement learning (MARL). The objective of this
survey is to provide comprehensive insights into various dimensions of MAS,
shedding light on myriad opportunities while highlighting the inherent
challenges that accompany multi-agent applications. We hope not only to
contribute to a deeper understanding of the MAS landscape but also to provide
valuable perspectives for both researchers and practitioners. By doing so, we
aim to facilitate informed exploration and foster development within the
dynamic realm of MAS, recognizing the need for adaptive strategies and
continuous evolution in addressing emerging complexities in MARL.

##  1 Introduction

Multi-agent reinforcement learning (MARL) have long been a pivotal domain in
artificial intelligence, offering solutions to complex tasks involving
multiple interacting entities. The significance of modeling multiple agents
that adapt and learn in coordination with one another is evident, as it
enables the realization of novel applications across diverse fields, where
collective decision-making among agents is paramount. The process of
developing decision-making and goal-oriented agents within MAS is centered
around facilitating the emergence of complex control and social behaviors.
Through proper modeling and learning, these agents will not only be capable of
understanding intricate social dynamics but also skilled at leveraging the
collective nature of their environment to achieve their individual goals.

By focusing on these behaviors and their underlying mechanisms, the goal of
MARL is to provide agents with the ability to navigate and excel in complex
social landscapes, ultimately leading to more effective and strategic
decision-making. This effort entails the integration of ideas from domains
like game theory and machine learning, all the while concurrently addressing
the distinctive challenges posed by a MAS [Stone and Veloso, 2000, Bowling,
2004, Shoham et al., 2007, Bernstein et al., 2013]. Moreover, future efforts
in this domain are poised to endow the desirable behavioral qualities that
characterize intelligent social agents through data-driven learning processes.
These learning processes embody models of bounded rationality [Shoham et al.,
2007], wherein agents progressively refine their behaviors in a myopic and
iterative manner over time and experience. Despite the many successes in this
domain, challenges persist, paving the way for ongoing research endeavors. The
purpose of this survey is to provide a comprehensive and extensive overview of
the current state of MARL, though we preface the survey is not to be
completely exhaustive.

The structure of this survey is as follows. In Section 3, we describe the
problem statement of learning optimal control within MAS, discussing
fundamental concepts and seminal ideas within fields such as game theory in
Section 3.3, deep learning in Section 3.4, and reinforcement learning in
Section 3.5. In Section 4, we first delve into the unique benefits and
foundational challenges of learning in a MAS, then explore the various
prospects of MARL, such as MARL-specific simulation in Section 4.3, training
paradigms in Section 4.6, communication in Section 4.9, the challenge of ad-
hoc team-play in Section 4.10, knowledge transfer in Section 4.11, and agent
modeling in Section 4.12. Lastly, we briefly discuss open challenges in the
field of MARL in Section 5.

##  2 Related Surveys

There exists a rich literature that comprises of articles surveying diverse
research topics in MARL, from general overviews [Stone and Veloso, 2000,
Shoham et al., 2003, Busoniu et al., 2008, Bloembergen et al., 2015, Gronauer
and Diepold, 2022] to specific research topics such as dealing with non-
stationarity [Hernandez-Leal et al., 2017], independent learners [Matignon et
al., 2012], multi-agent learning [Panait and Luke, 2005, Tuyls and Weiss,
2012], communication [Luong et al., 2019, Zhu et al., 2022], ad-hoc team-play
[Mirsky et al., 2022], agent modeling [Baarslag et al., 2016, Albrecht and
Stone, 2018], safety [Lasota et al., 2017] and knowledge transfer [Silva and
Costa, 2019]. However, many of these perspectives are constrained to game
theoretic, optimization, or machine learning viewpoints.

In contrast, our article aims to present a more modern and comprehensive
survey that aims to provide a holistic view of the challenges inherent in
learning control within a multi-agent environment. We explore these challenges
while weaving together various perspectives, derived from game theory and
machine learning into a new interconnected view, that aims to illuminate a
novel understanding of the essential requirements and the distinctive nature
of the MARL problem.

##  3 Background

In this section, we formalize the MAS problem statement and define the
learning goals and solution concepts set by the MAS optimization model. We
additionally explore related fields that contribute to the research of MARL.

###  3.1 Multi-agent Environment

A multi-agent system (MAS) consists of a population of decision-making agents
that operate within a shared environment, each pursuing their objectives.
These agents observe the state of the environment and may communicate with one
another. The communication among agents can be constrained by
decentralization.

Figure 1: A visualization of a multi-agent control system, inspired by
[Albrecht et al., 2024].

######  Definition 1 (Decentralization)

In a decentralized setting, each agent is an autonomous entity capable of
perceiving its environment, making decisions, and taking actions solely based
on its own local information.

There exists two forms of decentralization. Natural decentralization are the
limitations imposed by physical realities, like communication range, while
artificial decentralization involves specific requirements aimed to improve
tractability, such as communication bandwidth [Whiteson, 2020].

Each agent makes decisions that align with their objectives to reach their
defined goals. This causal association between stimuli, action, and objective
is what we refer to as the agent’s behavior [Matarić, 1994].

The environment reacts to the agent’s actions by updating the current setting
appropriately to the next state, and provides each agent with some feedback
signals. The response from the environment is referred to as the model. The
entire process forms a closed-loop interaction that continues until a terminal
condition is met.

The MAS setting described here is widely prevalent in real-world applications,
encompassing autonomous vehicles [Shalev-Shwartz et al., 2016, Zhou et al.,
2020], internet marketing [Jin et al., 2018], multi-robot control [Matarić,
1997], networking applications such as optimizing communication networks
[Luong et al., 2019] and traffic control [Calvo and Dusparic, 2018, Chu et
al., 2019], and multiplayer game playing [Samvelyan et al., 2019].

###  3.2 Stochastic Game

The framework of a stochastic game [Shapley, 1953, Bowling and Veloso, 2001]
provides a formal representation of the MAS setting introduced in Section 3.1
and serves as the mathematical basis for a wide range of dynamic multi-agent
applications [Busoniu et al., 2010].

Figure 2: Models of Games: The overview of different models of multi-agent
interactions is illustrated, from Markov Decision Processes (MDP) to
variations of stochastic games. The following figure was adapted and updated
from [Albrecht et al., 2024].

######  Definition 2 (Stochastic Game)

A stochastic game is a 6-tuple $(N,S,\bar{A},\bar{r},\mathcal{T},\gamma)$
where these elements are defined as:

  * •

$N$ is the set of $n$ agents.

  * •

$S$ is the set of (global) states.

  * •

$\bar{A}=\\{A_{0},A_{1},\dots A_{n}\\}$ is the set of action spaces.

  * •

$\bar{r}=\\{r_{0},r_{1},\dots r_{n}\\}$ is the set of reward functions.

  * •

$\mathcal{T}:S\times A\times S\mapsto[0,1]$ is the state transition operator.

  * •

$\gamma$ is the discount factor, where $\gamma\in[0,1]$.

The state defines the global setting and configuration of the environment.
Hence, the state of an environment is shared between the agents. To transition
from one state to another, each agent $i$ must select an action $a_{i}$ to
perform defined under the action space $A_{i}$. These agents utilize their
policy to either make decisions simultaneously or sequentially depending on
the nature of the task. An agent’s policy $\pi_{i}:S\mapsto A_{i}$ is the
functional representation of its behavior, expressed as a mapping from the
perceived state to action. Therefore, the joint policy $\pi:S\mapsto
A$111Joint spaces $X=\otimes_{X_{i}\in\bar{X}}X_{i}$ are denoted as the
Cartesian product over the set of individual agent’s domains (i.e.
$A=A_{0}\times A_{1}\dots\times A_{n}$ is the joint action space). is
considered the population’s behavior. A policy returns a probability
distribution over the action space conditioned on the state (i.e.
$\mathop{\sum}_{a\in A}\pi(a|s)=1$).

The state transition function $\mathcal{T}$ provides the probability of
reaching certain states from a given state-action pair. As each state holds
the Markov property (i.e. every state is fully contained to describe the
future), the state transition function is conditioned on only the prior state
and action.

$\mathcal{T}(s,a,s^{\prime})=P(s_{t+1}=s^{\prime}|s_{t}=s,a_{t}=a)$

##### Imperfect Information

In many real-world applications, it is intractable for agents to perceive the
(global) state of the environment. Rather, agents may only have access to
imperfect information, which are known as observations $o\in O$. Observations
are not necessarily Markovian and contain limited insights regarding the true
state of the environment. In fact, even joint observational histories
$h=\\{o_{0},o_{1},\dots o_{t}\\}$ can be insufficient to infer the state
$s_{t}$ of the environment. On the other hand, the contrapositive is true,
with the emission transition function defining the mapping from states to
corresponding observations that can be potentially induced.

$\mathcal{E}(o,s)=P(o|s)$

The notion of imperfect information underscores the limitations in information
agents may be restricted to in their decision-making process. This encompasses
the idea of partial observability, wherein agents possess access to only a
subset of the state, which could potentially be obscured further by noise.
Additionally, it encompasses the concept of incomplete information, where
agents face uncertainties concerning different aspects of the state. These
ideas help enforce the constraints of decentralization. This extension is
called partially-observable stochastic games (POSG).

##### Reward Function

The reward function returns immediate feedback to the agents, evaluating the
state and action of the agent with respects to their objective in the form of
a scalar value.

###### Definition 3

(Rationality) Rational agents take actions that will maximize the expected
cumulative reward they receive over time.

In a stochastic game, a reward function $r_{i}(\cdot)$ is defined for each
agent $i$. In other similar frameworks, such as the decentralized MDP (Dec-
MDP), a single reward function $r(\cdot)$ is defined for all agents.

##### Nature of Interaction

Given that the reward functions play a central role in shaping agents’
behavior, an important factor to consider when defining the reward function is
how the agents’ actions and decisions affect each other and the nature of
their interactions. In each setting, the interplay between each agents’
behaviors can lead to different dynamics and outcomes and may require varying
considerations.

  * •

Cooperative setting - All agents share the aligning goal.

  * •

Adversarial setting - Agents have dichotomous goals.

  * •

Mixed setting - Agents have varying goals.

In a cooperative setting, all agents share the aligning goal, and the reward
function is typically designed to promote collaboration and joint success. In
an adversarial setting, groups of agents may have dichotomous goals, meaning
agents that aim to maximize their own reward can potentially impede the
achievement of other agents’ goals. In a mixed setting, agents have varying
goals, and this introduces additional complexities as agents may have
aligning, conflicting or overlapping interests at various points in time.
Considering the nature of agents’ interactions and the specific setting is
crucial when designing the reward function, as it directly influences the
emergent behaviors and outcomes within the multi-agent system.

##### Networked Games

For certain applications, agents communicate with one another. These
interactions form a communication network $\mathcal{G}(s)$ associated to each
state $s$. We can explicitly append and define this element
$\mathcal{G}=(V,E)$ into the stochastic game framework, where vertices $V$
correspond to the agents and an edge $(i,j)\in E$ exists if agents $i$ and $j$
can communicate. We refer to this extended framework as a networked stochastic
games.

##### Return

A state-action trajectory $\tau=\\{s_{0},a_{0},s_{1},a_{1},\dots,s_{T}\\}$ is
sampled from the dynamics model distribution $p_{\pi}(\tau)$ following a joint
policy $\pi$, where
$p_{\pi}(\tau)=P(s_{0})\prod_{t=0}^{T}\pi(a_{t}|s_{t})\mathcal{T}(s_{t},a_{t},s_{t+1})$.
With this trajectory, we can compute an important quantity called the return,
which calculates the future utility of a given state. Formally, the return
$G_{(i,t)}$, sometimes called the gain, at each time step for an agent $i$ is
the cumulative future discounted reward.

$G_{(i,t)}(\tau)=\mathop{\sum}_{t^{\prime}=t}^{T}\gamma^{t^{\prime}}r_{i}(s_{t^{\prime}},a_{i,t^{\prime}})$

where $\gamma\in[0,1]$ is the discount factor, enforcing diminishing value for
more distant rewards.

##### Value Function

The value function $V_{\pi_{i}}(s_{t}|\pi)$ and the Q-value function
$Q_{\pi_{i}}(s_{t},a_{i,t}|\pi)$ are functions that map to the expected return
of a state $s_{t}$ and state-action pair $(s_{t},a_{i,t})$ for an agent $i$
given some joint policy $\pi$.

$V_{\pi_{i}}(s_{t}|\pi)=\mathbb{E}_{\tau\sim
p_{\pi}(\tau|s_{t})}[G_{(i,t)}(\tau)]$
$Q_{\pi_{i}}(s_{t},a_{i,t}|\pi)=\mathbb{E}_{\tau\sim
p_{\pi}(\tau|s_{t},a_{i,t})}[G_{(i,t)}(\tau)]$
$V_{\pi_{i}}(s_{t}|\pi)=\mathbb{E}_{a\sim\pi(a|s_{t})}[Q_{\pi_{i}}(s_{t},a_{i,t}|\pi)]$

The advantage function $A_{\pi_{i}}(s_{t},a_{i,t}|\pi)$ measures the benefit
of taking action $a_{i,t}$ in state $s_{t}$ for agent $i$ under the joint
policy $\pi$. It quantifies how much better or worse it is to choose action
$a_{i,t}$ compared to the average expected return of all actions in that
state. Hence, the advantage function is defined as the difference between the
Q-value function $Q_{\pi_{i}}(s_{t},a_{i,t}|\pi)$ and the state-value function
$V_{\pi_{i}}(s_{t}|\pi)$.

$A_{\pi_{i}}(s_{t},a_{i,t}|\pi)=Q_{\pi_{i}}(s_{t},a_{i,t}|\pi)-V_{\pi_{i}}(s_{t}|\pi)$

##### MAS Objective

The objective $J_{i}(\cdot)$ of agent $i$ is expressed as maximizing the
expected return, where trajectories $\tau$ are sampled from the dynamics model
distribution $p_{\pi}(\tau)$ following a joint policy $\pi$.

$J_{i}(\pi)=\mathbb{E}_{\tau\sim p_{\pi}(\tau)}[G_{(i,0)}(\tau)]$ (1)

where
$p_{\pi}(\tau)=P(s_{0})\prod_{t=0}^{T}\pi(a_{t}|s_{t})\mathcal{T}(s_{t},a_{t},s_{t+1})$.

In practice, this expectation is approximated using the Monte Carlo method.
The empirical estimate results in return estimates with high variance and
potential computation complexity.

We state the general form of the MAS optimization objective, which we describe
as maximizing the expected return for all agents.

$\textrm{maximize }J_{i}(\pi),\forall i\in N$ (2)

###  3.3 Game Theory

The field of game theory provides mathematical context that analyze and
conceptualize strategic interactions, or games, among multiple agents
[Osborne, 2009]. Using a game theoretic perspective, we examine the MAS
optimization objective to understand solution concepts relating to learning
goals and social principles used to identify the joint behaviors of a MAS that
are considered desirable or interesting [Myerson, 1985].

##### Utility Theory

We use the basis of the domain of decision and utility theory [Fishburn et
al., 1979, Shoham and Leyton-Brown, 2008], which studies how individuals make
choices under uncertainty by quantifying the preferences and subjective values
of the agents involved in the decision-making process. The utility function
$u(\cdot)$ reflects the individual’s subjective evaluation of the desirability
or satisfaction, assigning a numerical value to each outcome.

##### Equilibrium Computation

We begin by exploring how classical learning dynamics behave in a non-
stationary optimization landscape, often referred to as equilibrium
computation [Daskalakis, 2022]. This term is used to describe the process of
finding optimal or near-optimal solutions in evolving optimization landscapes
over time. The objective function or the search space undergoes fluctuations
or modifications due to factors like time-varying constraints, varying problem
parameters, or dynamic environments.

Within this non-stationary landscape, there are specific points of interest
known as equilibria. Equilibria represent stable or optimal solutions where
the system reaches a balance or steady state. These equilibria can be local or
global, indicating either a locally optimal solution or the best solution
across the entire landscape. Understanding the properties of these equilibria
is of great importance, particularly tractability in our case. Assuming the
equilibria’s existence, tractability refers to the ease at which equilibria
can be computed or found. In applying learning methods to these non-stationary
landscapes, tractability becomes a critical aspect since the changing nature
of the landscape can affect the search process. In much of our discussions, we
refer to solution concepts to states of equilibrium, which consist of
interesting and desirable properties, on the optimization landscape defined by
the joint utility.

##### Solution Concepts and Equilibrium

A general criterion for evaluating joint policies, or strategy profiles, of a
multi-agent system, is known as Pareto domination. A strategy profile
$\pi^{\prime}$ Pareto dominates another strategy profile $\pi$ if:

$\forall i\in N:u_{i}(\pi^{\prime})\geq u_{i}(\pi)$ $\exists i\in
N:u_{i}(\pi^{\prime})>u_{i}(\pi)$

With a Pareto-dominated strategy profile, no agents can be made better off
without making another agents worse off.

######  Definition 4 (Pareto Optimality)

A strategy profile $\pi^{*}$ is a Pareto efficient solution if it is not
Pareto dominated by any other strategy profiles.

This solution concept presents a notion of efficiency that focuses on
maximizing overall welfare without making anyone worse off. As it does not
consider individual rationality or collective stability explicitly, a Pareto
efficient solution may not necessarily be a good measure if the solution
require agents to act against their own self-interest or deviate from some
locally desirable strategies. Importantly, Pareto optimality does not address
the issue of fairness or equality, as some individuals may benefit more than
others in the pursuit of maximizing overall welfare [Shoham and Leyton-Brown,
2008].

The concept of best response provides an alternative perspective in analyzing
strategic interactions in multi-agent systems that aligns more towards
concepts of individual rationality and collective stability. Given a strategy
profile $\pi=\\{\pi_{0},\pi_{1},\dots,\pi_{i},\dots,\pi_{N}\\}$, a best
response strategy $\pi^{\prime}_{i}$ for agent $i$ is defined by:

$u_{i}(\llbracket\pi_{-i},\pi^{\prime}_{i}\rrbracket)\geq
u_{i}(\llbracket\pi_{-i},\pi_{i}\rrbracket),\forall\pi_{i}$

where $\pi_{-i}=\pi\setminus\pi_{i}$ denotes the strategy profile without
agent $i$ and $\llbracket\pi_{1},\pi_{2}\rrbracket=\pi_{1}\otimes\pi_{2}$ is
the strategy profile of $\pi_{1},\pi_{2}$.

The solution concept of an Nash equilibrium (NE) $\pi^{*}$ applies this notion
of best response to the collective, where for all agents $i$, $\pi^{*}_{i}$ is
a best response to $\pi^{*}_{-i}$.

$u(\llbracket\pi_{-i}^{*},\pi^{*}_{i}\rrbracket)\geq
u(\llbracket\pi_{-i}^{*},\pi_{i}\rrbracket),\forall\pi_{i}$

######  Definition 5 (Nash Equilibrium)

A Nash equilibrium (NE) defines a state where no individual agent can increase
its expected return by unilaterally deviating from their policy [Nash, 1951].
Hence, given that all other agent stick to their strategy, the agent’s
strategy is the best response.

Similar to Pareto efficient solutions, NE is not unique and determining the
differences between these sample equilibrium in terms of their social
behaviors is unclear. While NE remains a popular criterion for multi-agent
decision-making under uncertainty, directly optimizing for this equilibrium in
complex stochastic game settings poses significant challenges due to its
intractability. Moreover, achieving desired joint behaviors in a stochastic
game setting is not guaranteed through this approach [Shoham et al., 2003,
Matignon et al., 2012]. Nonetheless, NE do represent stable points akin to
saddle points within the optimization landscape.

Due to the intractability of computing a strict NE, $\epsilon$-Nash
equilibrium relaxes the requirements by allowing agent to deviate if it
improves its expected returns by more than some $\epsilon$.

$u(\llbracket\pi_{-i}^{*},\pi^{*}_{i}\rrbracket)\geq
u(\llbracket\pi_{-i}^{*},\pi_{i}\rrbracket)-\epsilon,\forall\pi_{i}$

A generalization of NE is the correlated equilibrium (CE), which adds the
notion of correlating strategies among agents in a game to allow for the use
of signals to coordinate the agents’ actions [Aumann, 1974]. Hence, CE
introduces a correlating distribution over the strategies of all agents. If
such correlating signals do not necessarily affect the joint strategies,
causing no agents to deviate irregardless of the information provided by the
signals, then we call the following optimization state the coarse correlated
equilibrium (CCE). NE can be considered a special case of CE, where the
correlating distribution of the agents’ strategies is a product over
independent distributions.

The concept of perfect equilibrium [Bielefeld, 1988] refines the idea of NE by
imposing additional requirements of consistency and mutual optimality. It
describes an optimization state where agents’ strategies are mutually
consistent and takes into account the possibility of off-equilibrium actions,
requiring agents to choose strategies that are robust against such deviations.
We now explore additional refinements to these solution concepts useful under
the context of stochastic games.

##### Equilibrium Complexity

Given all games always have at least one equilibrium solution [Nash, 1951],
the complexity of computing an equilibrium is most aptly discussed under the
pretense of a total search problem (i.e. PPAD), rather than as a decision
problems (i.e. P/NP). Although, computing an equilibrium which satisfies
additional properties is an NP-hard decision problem [Gilboa and Zemel, 1989,
Conitzer and Sandholm, 2008, Nisan et al., 2007, Albrecht et al., 2024].

###### Definition 6

(PPAD) Polynomial parity argument for directed graphs (PPAD) consists problems
that can be reduced to the following (End-Of-The-Line) problem:

Given a directed graph with vertices have at most one predecessor and/or one
successor, and a source vertex $s$, where $s$ has no predecessor, find a
vertex $t$ with no predecessor or no successor, such that $s\neq t$. Let there
be a polynomial-time function that returns the predecessor and successor of
all vertices in this graph.

where PPAD-completeness is shown by reducing the End-Of-The-Line problem to
it. To support the hardness of PPAD problems, [Daskalakis et al., 2009]
proposes the following question: How can one hope to devise an efficient
algorithm that telescopes exponentially long paths in every implicitly given
graph?

Computing the Nash equilibrium is proven to be a PPAD-complete [Daskalakis et
al., 2009, Chen et al., 2007], further affirming its intractability.

##### Learning Dynamics

While these solution concepts of equilibria provides context for stability and
optimality, it does not to give insights into the process of reaching such
states. The concept of learning dynamics bridges this disconnect by detailing
the procedure in reaching equilibrium. While many such models exist, we will
explore two central approaches: best-response dynamics and no-regret dynamics.
With best-response dynamics, the objective is to directly optimize and
converge to a NE, or one of its refinements. Popular examples include:

  * •

Fictitious play [Robinson, 1951] optimizes for the best response policy for
each agent, assuming a fixed stationary joint strategy, by explicitly modeling
the other agent’s strategies. Extensions to including uncertainty within these
models of other agents, known as rational learning [Jordan, 1991, Kalai and
Lehrer, 1993], can be applied to optimize value of information [Dearden et
al., 1999, Albrecht et al., 2024], or how actions will influence future
behaviors.

  * •

Minimax Q-learning [Littman, 1994], Nash Q-Learning [Hu and Wellman, 2003],
Correlated Q-learning [Greenwald and Hall, 2003], Friend-or-Foe Q-learning
[Littman, 2001b] apply value iteration [Shapley, 1953] within a joint-action
space.

  * •

Infinitesimal gradient ascent (IGA) [Singh et al., 2000] utilizes gradient
learning to optimize agent’s policy with respects to their utility. Similar
methods and its extensions to improve convergence include using variable step
sizes [Bowling and Veloso, 2002, Bowling, 2004], use of multiplicative update
rule [Arora et al., 2012], proximal point optimization [Mokhtari et al.,
2019], extra-gradient [Korpelevich, 1976], and optimistic gradients [Rakhlin
and Sridharan, 2013, Daskalakis and Panageas, 2018, Wei et al., 2021].

In no-regret dynamics, the aim is instead to minimize regret, which measures
how much an agent would have gained if they had chosen a different strategy,
to find equilibrium points [Hart and Mas-Colell, 2000]. Concretely, such
measure can be quantified by the average cost between the utility of the best
possible strategy profile and the actual utility of the chosen strategy
profile. The tractability of computing and verifying best-response can be
compromised with games with high complexity, thereby no-regret dynamics, or
regret-matching, is an alternative in such settings [Zinkevich et al., 2007,
Tammelin, 2014]. In fact, IGA and its extensions also achieves no-regret
[Zinkevich, 2003], under certain conditions.

##### Active Equilibrium

The equilibrium states provided in the game theoretic solution concept do not
account for the non-stationarity aspect induced by a learning dynamics. Hence,
non-stationary [Daskalakis et al., 2022] and active equilibrium [Kim et al.,
2022] provide a further generalization of NE and CE that accounts for these
changes in strategy profiles.

###  3.4 Deep Learning

We can represent elements of a stochastic game, such as the policy, value
function, or model, using neural networks to optimize the joint behavior by
utilizing deep learning algorithms [Goodfellow et al., 2016].

We define a set of parameters $\theta$ that transforms information using
layers of linear and non-linear operations. We optimize these parameters with
respects to a defined cost function $J(\theta)$ using methods of statistical
learning and numerical optimization, such as stochastic gradient ascent.

$\theta=\theta+\nabla_{\theta}J(\theta)$

A key attribute to a deep learning approach is its ability to develop a
scalable end-to-end solution. We avoid the need to handcraft features and
instead allow the optimization to learn curated latent representation tailored
towards the task at hand in a data-driven manner. The central constraints in
such methods reside with the need for large-scale data collection and high
computational cost required for training.

###  3.5 Reinforcement Learning

The domain of reinforcement learning (RL) focuses on developing learning
methods that optimize control policies guided by reward [Sutton and Barto,
2018], where the mathematical framework commonly considered is the MDP. RL
provides a strong foundation for optimizing MAS control using a stochastic
game formulation. We briefly describe four central approaches [Levine et al.,
2020] used in RL that serves as the foundations of learning controls.

Figure 3: Policy Iteration: The process of policy iteration consists of an
iterative cycle of policy evaluation (shown as $\xrightarrow{\text{E}}$) and
policy improvement (shown as $\xrightarrow{\text{I}}$). Policy evaluation
computes value function for current policy whereas policy improvement updates
current policy with respect to evaluated value function. The following figure
was taken and modified from [Sutton and Barto, 2018].

##### Value Function Approximation

The value-based approach estimates the value function of the optimal policy,
often without defining an explicit policy and instead, extracting this
implicit policy from the value function, $\pi(a|s)\propto Q(s,a)$. Typically,
these Q-learning [Watkins, 1989, Watkins and Dayan, 1992] methods utilize
approximate dynamic programming using the Bellman (expectation) equations
[Bellman, 1957], a set of recursive definitions of the value functions, and
often leveraging the theorem of policy iteration [Sutton and Barto, 2018] (see
Figure 3).

$\displaystyle Q_{\pi}(s_{t},a_{t})$ $\displaystyle=\mathbb{E}_{\tau\sim
p_{\pi}(\tau|s_{t},a_{t})}[G_{t}(\tau)]$
$\displaystyle=r(s_{t},a_{t})+\mathbb{E}_{s_{t+1}\sim\mathcal{T}(s_{t},a_{t},s_{t+1}),a_{t+1}\sim\pi(a|s_{t+1})}[Q_{\pi}(s_{t+1},a_{t+1})]$
(3)

To briefly cover the theoretical foundation for the convergence of such
methods, we define the Bellman backup operator $\mathcal{B}_{\pi}$ on our
value function estimate $Q$ such that $Q=\mathcal{B}_{\pi}Q$ is equivalent to
Equation 3.5. By iteratively applying the Bellman backup operator
$\mathcal{B}_{\pi}$, as it can be shown that $\mathcal{B}_{\pi}$ is a
contraction mapping and by the Banach fixed-point theorem, $Q$ is guaranteed
to converge to a unique fixed point that corresponds to the true Q-function
$Q_{\pi}$ for the policy $\pi$ [Sutton and Barto, 2018].

By employing an optimal (implicit) policy denoted as
$\pi^{*}(a|s)=\delta(\mathop{\textstyle{\textrm{argmax}}}_{a\in A}Q(s,a))$,
the need for policy evaluation can be circumvented, which scales poorly with
the state-action space. This approach, known as value iteration, leverages the
Bellman optimality equation in the form of the Bellman backup
$\mathcal{B}_{\pi}$ to minimize the Bellman residual error.

$Q_{\pi^{*}}(s_{t},u_{t})=r(s_{t},u_{t})+\mathbb{E}_{s_{t+1}\sim\mathcal{T}(s_{t},u_{t},s_{t+1})}[\max_{a\in
A}Q_{\pi^{*}}(s_{t+1},a)]$

Value function approximation methods have come with several improvements over
the past decade, including:

  * •

Extension to deep neural networks representation for continuous state space
and usage of experience replay to stabilize off-policy learning [Mnih et al.,
2013].

  * •

Reformulation of Bellman update to increase action gap [Bellemare et al.,
2015].

  * •

Distributional value function representation [Bellemare et al., 2017, Dabney
et al., 2018b, a, Yang et al., 2019] for richer expressiveness.

  * •

Mitigate overoptimism/maximization bias with double learning [Van Hasselt et
al., 2016], clipped double Q-learning, and target policy smoothing [Fujimoto
et al., 2018b].

  * •

Utilization of dueling architecture [Wang et al., 2016b] to better model
Q-functions.

  * •

Improvements to experience replay to prioritize important transitions [Schaul
et al., 2015], perform better with sparse rewards [Andrychowicz et al., 2017],
and work with recurrent networks [Hausknecht and Stone, 2015, Kapturowski et
al., 2018].

  * •

Improved exploration through randomized modeling [Fortunato et al., 2017],
intrinsic rewards [Badia et al., 2020b, a], maximum entropy framework
[Haarnoja et al., 2017].

  * •

Handle continuous action spaces by assuming a deterministic policy [Lillicrap
et al., 2015], parameterizing the Q-function as a well-defined convex function
[Gu et al., 2016], or utilizing sampling methods [Kalashnikov et al., 2018] in
order to compute the Bellman update.

  * •

Learn on datasets of offline experiences while managing distributional
mismatch and continuing improvements beyond behaviors seen in dataset [Levine
et al., 2020] by regularizing overestimation [Kumar et al., 2020], utilizing
probabilistic regression [Kostrikov et al., 2021, Ma et al., 2021], and an
model estimate [Yu et al., 2022b].

  * •

Integration of improvements through the years [Hessel et al., 2017,
Kapturowski et al., 2022]

##### Policy Gradient

The policy-based approach aims to directly optimize the objective in Equation
2, to search for an explicitly defined optimal policy $\pi$. The popular idea
is to perform gradient ascent along the objective using the policy gradient,
pioneered by the REINFORCE (REward Increment $=$ Nonnegative Factor $\times$
Offset Reinforcement $\times$ Characteristic Eligibility) algorithm [Williams,
1988, 1992].

$\displaystyle\nabla_{\theta_{\pi}}J(\pi)$
$\displaystyle=\nabla_{\theta_{\pi}}\mathbb{E}_{\tau\sim
p_{\pi}(\tau)}[G_{0}(\tau)-b(\tau)]$ $\displaystyle=\mathbb{E}_{\tau\sim
p_{\pi}(\tau)}[\sum_{t=0}^{T}(G_{t}(\tau)-b(\tau))\nabla_{\theta^{\pi}}\log(\pi(a_{t}|s_{t}))]$
(4)

where $\theta_{\pi}$ represents the parameters of the policy $\pi$ and
$b(\cdot)$ is the reinforcement baseline function used to help stabilize the
approximated current reinforcement $G_{t}(\tau)$222We highlight that the
return $G_{t}(\tau)$ here removed the notation of which agent it is referring
to, as we are only considering one agent in this scenario.. As often this
approximation is performed through Monte Carlo sampling, it can often lead to
high variance despite providing an unbiased estimate of the expected return.
Hence, as noted by [Williams, 1992, Schulman et al., 2018], the choice of
$b(\cdot)$ can improve convergence and qualitative behavior.

Key improvements to the policy gradient approaches consist of:

  * •

Off-policy learning with policy gradient methods with importance sampling
corrections [Jie and Abbeel, 2010, Degris et al., 2012]

  * •

Mitigate dominating gradients on the parameter-level by reparameterizing loss
under a probabilistic manifold using Fisher information matrix [Kakade, 2001]
or Kronecker-factored approximated curvature [Wu et al., 2017].

  * •

Utilize surrogate objective that guarantees monotonic improvements,
conditioned on a trust-region optimization [Kakade and Langford, 2002,
Schulman et al., 2017a, b].

##### Actor-Critic Methods

Actor-critic algorithms provide an integration of policy-based and value-based
methods [Sutton et al., 1999]. Instead of estimating the value function of an
implicit policy, we model the value function for an explicitly defined policy,
hence minimizing Bellman residual using Equation 3.5 while also learning from
a policy gradient. With access to a value estimate, temporal difference (TD)
learning or $n$-step learning can be utilized instead of Monte Carlo sampling
to approximate the offset reinforcement. While these methods do introduce
bias, the variance is considerately lowered as updates are no longer depend on
the entire trajectories but only on a subset of the trajectory [Sutton and
Barto, 2018]. Additionally, the value function can also improve the quality of
the policy gradient by stabilizing return estimate with a new baseline
[Schulman et al., 2018].

Key improvements to the actor-critic methods include:

  * •

Generalized baseline functions [Schulman et al., 2018] and action-dependent
control variate [Gu et al., 2017, Liu et al., 2018, Tucker et al., 2018] for
stabilizing the variance of policy gradient.

  * •

Distributed training of actor-critic methods [Mnih et al., 2016, Espeholt et
al., 2018]

  * •

Utilizing a shared latent space between actor and critic [Cobbe et al., 2020,
Huh, 2021]

  * •

Extending efforts from policy-based and value-based methods to actor-critic
framework, such as experience replay [Wang et al., 2016a] and soft Q-learning
[Haarnoja et al., 2018, 2019].

##### Model-based Approaches

With a model-based approach, we maintain an explicit estimates of the
transition dynamics $\mathcal{T}$ and/or reward probabilities and uses this
model for planning without an explicit policy or for policy improvement
[Sutton, 1990]. In contrast, we refer to methods without such estimates as a
model-free approach. A model-based approach can be more challenging, as
accurately representing the transition dynamics and reward function especially
over long time horizons is non-trivial and difficult.

Key improvements in model-based approaches include:

  * •

Integrate model learning with deep learning methods [Ha and Schmidhuber, 2018,
Weber et al., 2018, Hafner et al., 2020, 2022, 2023].

  * •

Mitigate distributional mismatch using online data collection [Ross et al.,
2011], uncertainty estimation [Deisenroth and Rasmussen, 2011, Feinberg et
al., 2018] via Bayesian neural network [Blundell et al., 2015], bootstrap
ensembling [Chua et al., 2018, Kurutach et al., 2018, Clavera et al., 2018,
Luo et al., 2021, Buckman et al., 2018], or dropout [Gal et al., 2017].

  * •

Learning on imperfect information [Watter et al., 2015, Zhang et al., 2019]

An alternative approach to alleviate the cost of learning a complex
environment model while still being adaptive to distal reward changes is using
a successor representation [Dayan, 1993], which disentangles the state
transitions from reward estimation by maintaining a state occupancy function
$M(\cdot)$ for a given policy $\pi$.

$M_{\pi}(s,s^{\prime})=\mathbb{E}_{\tau\sim
p_{\pi}(\tau|s_{0}=s)}[\sum_{t=0}^{T}\gamma^{t}\mathbbm{1}(s_{t}=s^{\prime})]$

where $\mathbbm{1}$ is the characteristic function. The state occupancy
function captures the notion of environmental affordance, caching statistics
relating to which future states are possible. Similar to the Bellman
equations, we can derive a recursive definition for the state occupancy
function.

$M_{\pi}(s,s^{\prime})=\mathbbm{1}(s_{t}=s^{\prime})+\gamma\mathbb{E}_{s_{t+1}\sim
p_{\pi}(\tau|s_{t}=s)}[M(s_{t+1},s^{\prime})]$

Using the successor representation, we express the value function as the
product between the state occupancy function and the reward function.

$V(s)=\sum_{s^{\prime}\in S}M_{\pi}(s,s^{\prime})r(s^{\prime})$

This factorization provides a compact and structured representation of the
model for efficient and adaptive learning in complex environments [Kulkarni et
al., 2016].

Notable continuations on this topic include:

  * •

Grounded formulation to learn successor representation with deep learning
methods [Blier et al., 2021, Touati and Ollivier, 2021]

  * •

Utilization of passive data to learn latent and useful features [Ghosh et al.,
2023]

##  4 Learning in a Multi-agent Environment

The transition from single-agent RL to learning a strategy profile for a
multi-agent stochastic game setting is accompanied by numerous promising
opportunities, but also presents significant challenges that require major
considerations [Resnick, 2005]. In contrast to single-agent control systems,
where one agent interacts with its environment, a multi-agent setting involve
multiple entities interacting with each other and their shared environment.
Facilitating social, stable and adaptive behaviors within a multi-agent
control learning process is key, and thereby comes with several intricacies
that converge to necessitate non-trivial solutions.

###  4.1 Benefits of MARL

The focus of MARL is to directly address the optimization problem containing
multiple decision-making agents that operate in a shared environment. Hence,
these algorithms are designed to excel in such MAS scenarios. In other words,
given that these agents face the distinctive intricacies that arise within
multi-agent dynamics during training, the agent’s behaviors are optimized
within such unique scenarios, holding the potential to yield a wide range of
valuable behaviors, from fostering adaptive social strategies, facilitating
the emergence of implicit coalitions, enabling intelligent interactions, and
improving robustness to dynamic changes within the population [Busoniu et al.,
2008].

The usage of MARL also enables the realization of applications that could not
be accurately modeled in single agent RL alone [Matarić, 1994], particularly
in scenarios that involve multiple adaptive agents that can influence the
environment or other agents [Lanctot et al., 2017]. The context of training
under MAS features additionally introduces the chance to capitalize on the
unique prospects of the multi-agent nature, which can enhance the efficiency
and depth of training through various means.

###  4.2 Challenges of MARL

The task of MARL is not only riddled with the already challenging objective of
optimizing control but is further compounded by the involvement of multiple
agents. Throughout this paper, we investigate four central challenges ---
computational complexity, non-stationarity, coordination, and performance
evaluation--- that often coupled to various learning pathologies.

######  Definition 7 (Learning Pathology)

Learning pathology refers to undesirable or sub-optimal behaviors that can
emerge from learning dynamics, potentially hindering the learning process. As
listed in [Palmer, 2020], these include: stochasticity, deception, the moving-
target problem, miscoordination, relative overgeneralization, and the alter-
exploration problem.

Much of the problematic intricacies of MARL stem from a mixture of these
challenges, given that they tend to be deeply interconnected.

####  4.2.1 Computational Complexity

Aforementioned, optimizing for an equilibrium solution is theoretically
demonstrated as intractable. Furthermore, the cost of modeling multiple agents
can easily scale intractably. For instances, since joint state-action space
scales exponentially with respects to the number of agents [Qu et al., 2021],
the complexity of the optimization problem and the computational cost required
can render the optimization impractical to learn any useful joint behaviors.
Other key factors, such as the pathologies of stochasticity and deception,
play a major role in contributing to this complexity.

##### Stochasticity

In practical MAS applications, stochastic rewards or transitions can arise due
to various factors such as noise or unobservable elements in the state space.
When a game is inherently stochastic, the intricacies of identifying the
sources responsible for the fluctuations in observed rewards can lead to
learning instabilities. This, in turn, demands that agents accumulate more
experience to discern and adapt to these sources of uncertainty [Palmer,
2020].

##### Deception

The pathology of deception involves a game that contain certain states have a
high local reward but low return. For many traditional MAS algorithm derived
from maximum-based learners [Kapetanakis and Kudenko, 2003, Matignon et al.,
2012], over-estimation remains a key challenge that leads to early convergence
to sub-optimal equilibrium.

Therefore, it becomes even more crucial to design our optimization model
carefully, such that the modelled components are not susceptible to fail to
converge or to find good approximate equilibrium states during learning. With
these considerations, we need to balance the trade-offs between solution
complexity, computational efficiency, and learning performance to effectively
devise a tractable MARL solution.

####  4.2.2 Non-stationarity

Informally, a stationary process can be classified by its underlying
distribution’s invariance under time shifts. In a multi-agent setting, the
decisions each agents impact the dynamics of the environment. Consequently,
from the perspective of a single agent, the other agents’ behaviors are
inherent components of the dynamics. Therefore, whenever these external agents
adapt and alter their behaviors, the underlying model distribution in the
perspective of the agent also changes, rendering it to seem non-stationarity
[Hernandez-Leal et al., 2017]. Importantly, this non-stationarity arises not
from a stochastic process that can be easily modeled, such as white-noise
Gaussian, but rather from the structured learning process of the external
agents [Daskalakis, 2022].

Non-stationarity is a critical deviation from the fundamental assumption made
by conventional fully-observable single-agent RL algorithms, which operate
within stationary environments [Choi et al., 1999]. The absence of the
stationary property destabilizes the optimization and contributes to the
pathology of the moving-target problem, i.e. what needs to be learned by an
agent depends on and changes with what has been learned by the respective
other agents [Tuyls and Weiss, 2012]. Hence, the learning landscape the agents
are optimizing over is in flux at each update step. This setting can make
learning infeasible for agents to properly converge to a stable behavior
[Papoudakis et al., 2019]. Therefore, it is essential to consider extensions
of methods that can effectively account for this non-stationarity to develop
stable algorithms for MARL.

####  4.2.3 Coordination

One of the unique aspects of developing a multi-agent solution is the ability
for the agents to work together to achieve their goal. As each agent makes
decisions based on its own local observations in a shared environment, they
can heavily benefit from coordinating their actions in order to achieve a
joint strategy that maximizes the collective return and avoid unintended
interference, i.e. mitigate diminishing returns [Cai et al., 2007].

However, within a decentralized and heterogeneous MAS, achieving successful
coordination can be challenging since the agents have limited information
about the environment and the behaviors of other agents. Addressing the
problem of coordination has been a significant research challenge in MARL that
holds substantial promise in allowing agents to engage in expressive
communication to effectively implement a collaborative joint strategy to
handle complex tasks. Notably, the challenge of coordination is directly
associated with the pathologies of miscoordination and relative
overgeneralization.

##### Miscoordination

The pathology of miscoordination, otherwise known as the Pareto-selection
problem, can be observed when two or more incompatible Pareto-optimal
equilibria are present. As a consequence of the equilibria being incompatible,
agents can choose an action from an alternative equilibria (assuming improper
coordination), harming performance. For instances, given the bi-matrix game in
Table 1, there exists two incompatible equilibria, $(a,a),(b,b)$, where both
strategy profiles $(a,b)$ and $(b,a)$ come from either equilibria.

######  Definition 8 (Incompatiable Equilibria)

Two equilibria $\pi$ and $\pi^{{}^{\prime}}$ are incompatible if and only if,

$\exists_{i}\pi_{i}\neq\pi^{{}^{\prime}}_{i},J_{i}([\pi_{i},\pi^{{}^{\prime}}_{-i}])<J_{i}(\pi^{{}^{\prime}})$

where $[\pi_{i},\pi^{{}^{\prime}}_{-i}]$ signifies a strategy profile using
agent $i$ action from $\pi$ and the other agent’s action from
$\pi^{{}^{\prime}}$.

| $a$ | $b$ | $c$
---|---|---|---
$a$ | $1$ | $-2$ | $0$
$b$ | $-2$ | $1$ | $0$
$c$ | $0$ | $0$ | $0.5$
Table 1: Payoff Matrix of a Climbing Game: Motivated by the climbing game
proposed in [Kapetanakis and Kudenko, 2003], this game consists of two agents,
each with three possible actions $(a,b,c)$.

##### Relative Overgeneralization

Relative overgeneralization derives as a form of action shadowing. This
pathology occurs in games where, as a result of a shadowed equilibrium, the
agents converge upon a sub-optimal Nash Equilibrium that is Pareto-dominated
by at least one other Nash Equilibrium. Hence, agents can be drawn to sub-
optimal but wide peaks in the return space, due to a greater likelihood of
achieving collaboration.

######  Definition 9 (Action Shadowing)

Action shadowing is a phenomenon wherein one individual action seems more
favorable than another, despite the potential greater return of the second
action [Fulda and Ventura, 2007]. Concretely, a sub-optimal policy may result
in a higher average payoff when paired with arbitrary actions chosen by other
agents, leading to utility values of optimal actions being underestimated.

######  Definition 10 (Shadowed Equilibrium)

An equilibrium $\pi$ is shadowed by another one $\pi^{{}^{\prime}}$ if there
exists an agent which receives a low return by unilaterally deviating from
this equilibrium and if this return is lower than the minimal return when
deviating from the other equilibrium [Palmer, 2020].

$\exists_{i}\exists_{\bar{\pi}}J([\bar{\pi}_{i},\pi_{-i}])<\min_{j}J([\bar{\pi}_{j},\pi^{{}^{\prime}}_{-j}])$

For instances, in the bi-matrix game presented in Table 1, while $(a,a),(b,b)$
are both Pareto-optimal equilibrium, a miscoordination penalty is associated
with both of them. No such penalty exists with action $c$. Hence, both
equilibrium are shadowed by $(c,c)$, as the expected gain if one agent
deviates unilaterally from either equilibrium is inferior to the lowest
expected gain if one agent deviates unilaterally from $(c,c)$.

Figure 4: Visualization of a two-player game’s reward space taken from [Wei
and Luke, 2016].

The pathology of relative overgeneralization is easily seen in Figure 4. The
$x$ and $y$ axis represent the continuous actions for agents $i$ and $j$
respectively. The $z$ axis represents the reward for each joint-action. The
reward space is structured where action $i_{M}$ can lead to the optimal
reward, however, due to miscoordination being less severely punished for
actions approaching $i_{N}$, the agents are drawn towards the sub-optimal Nash
equilibrium.

##### The Alter-Exploration Problem

The exploration-exploitation trade-off requires RL algorithms to strike a
balance between the exploitation of the agent’s current knowledge and the
exploration of new actions to improve that knowledge [Sutton and Barto, 2018].
The balance between exploration and exploitation remains a crucial factor for
the efficiency of many modern RL algorithms. Nevertheless, in light of the
inherent delicacy involved in optimizing and coordinating multi-agent systems
under the influence of shadowed equilibria and miscoordination penalties, such
exploration can introduce instabilities within the learning dynamics [Matignon
et al., 2012]. For instances, other agents may adapt to these stochastic
actions too abruptly.

####  4.2.4 Performance Evaluation

Assessing the performance of a MAS is a multifaceted challenge. Firstly, the
optimality of one agent’s policy, that can often be measured with its return,
can be intricately linked to the policies of other agents, rendering its
assessment unclear to properly interpret. This is compounded by the problem of
establishing unbiased and useful metrics that quantifies inherently
qualitative social behaviors, such as measuring the quality of communication
and coordination [Havrylov and Titov, 2017, Jaques et al., 2019, Bogin et al.,
2019, Lowe et al., 2019].

Alternatively, a focus on more egalitarian criterions, such as social welfare
and fairness, can be made, where effort is directed to enforce some notion of
altruism through preference ordering throughout the population such as
concentrating on the agents that are most struggling [Zhang and Shah, 2014].
Hence, it is also important to understand credit assignment, or being able to
discern the individual impact of each agent in terms of the coalition’s
utility, especially where there exists only a global reward structure (i.e.
decentralized MDP). A classic example is the Shapley value, which quantify and
capture the notion of marginal contribution by averaging over all possible
combinations of the marginalized population’s achieved utility [Shapley,
1952]. More recently, a popular approach in deep MARL is utilizing an
advantage function, which compares the current Q-values to the counterfactual
[Foerster et al., 2017a, Li et al., 2022], or to utilize value function
decomposition [Sunehag et al., 2017], as to marginalize the contribution of
each agent.

On a theoretical plane, determining which solution concepts would lead to
optimal behaviors and strategies, as studied in game theory literature,
remains unclear [Bergerson, 2021]. Even so, as many studied solution concepts
prove prohibitively costly to explicitly measure and optimize with complex and
dynamic tasks, the research for definable metrics that captures the nuances of
diverse MAS settings persists as an ongoing and open challenge.

###  4.3 Simulating MARL Tasks

A critical constraint in learning algorithms for control is its training
efficiency due to its sample complexity [Daskalakis et al., 2022]. Often, in
order to acquire valuable behaviors, it requires significant computational
resources. This constraint arises from various factors, mostly notably sample
inefficiency and brittle optimization landscape [Gu et al., 2017, van Hasselt
et al., 2018, Tucker et al., 2018, Henderson et al., 2019].

Sample efficiency is broken down into two factors: the number of interactions
required by each agent and the cost associated with each interaction [Huh and
Mohapatra, 2024]. It is important to emphasize the pivotal role that
simulators play in this equation. Not only can simulators help reduce the
resource requirements for sample collection, but in fact, they can also
enhance the learning process by yielding higher-quality samples through
greater accessibility, stability, accuracy and precision of the retrieved
data.

In recent years, the processing capabilities of massively parallelizable
processors, such as graphic processing units (GPUs) and tensor processing
units (TPUs), have advanced significantly. This progress has opened up
exciting possibilities for leveraging this technology to simulate highly
complex tasks effectively, minimizing the cost of simulating large number of
trajectories. These processors are specifically designed to handle parallel
computations efficiently by executing tasks simultaneously on a large scale,
enabling simulations to run orders-of-magnitude faster compared to
conventional CPU-based implementations. There have been notable efforts to
develop task-specific [Dalton et al., 2019] and general physics-based
simulators, such as IsaacSims [Makoviychuk et al., 2021] and Brax [Freeman et
al., 2021] that leverage GPUs. Many of these simulators primarily concentrate
on addressing single-agent problems, with some addressing their extension to
MAS [Chen et al., 2022, Gu et al., 2023, Huh and Mohapatra, 2024, Rutherford
et al., 2023]. In turn, there exists promising potential to further optimize
and extend the usage of vectorized processing to MAS scenarios [Lan et al.,
2021].

Name |  Description
---|---
Multi-agent Particle Environment (MPE) [Lowe et al., 2020] |  Various social tasks focused on communication within a particle world setting.
StarCraft Multi-Agent Challenge (SMAC)[Samvelyan et al., 2019, Ellis et al., 2022, Phan et al., 2023] |  Cooperative StarCraft decentralised micromanagement scenarios.
PettingZoo [Terry et al., 2021] |  A collection of different MARL tasks and libraries.
MA-Gym [Koul, 2019] |  Multi-agent tasks in a grid-world setting.
MAgent [Zheng et al., 2017] |  A collection of many-agent tasks.
Level-based Foraging (LBF) and Robot Warehouse (RWARE) [Christianos et al., 2020] |  Customizable grid-world foraging task and simulation warehouse with robots moving and delivering product in gridworld
Google Research Football [Kurach et al., 2020] |  Simulated soccer game using physics-based 3D simulator.
Overcooked [Carroll et al., 2020] |  Human-AI coordination on multiplayer video-game task.
Vectorized Multi-Agent Simulator (VMAS) [Bettini et al., 2022] |  Various MARL tasks using a vectorized Pytorch-based 2D physics engine
IsaacTeams [Huh and Mohapatra, 2024] |  Various physics-based MARL tasks using GPU-accelerated IsaacSim platform.
JaxMARL [Rutherford et al., 2023] |  Various physics-based MAS tasks using GPU-accelerated Brax platform.
Table 2: List of open-source environments

##### Open Source Environments

There exists a wide range of libraries that are used as common benchmarks for
MARL research. While the following list is not exhaustive, Table 2 provides
descriptions of some of the more widely recognized environments.

###  4.4 Social Context

In a shared environment, it is crucial for agents to develop strategies that
are mutually consistent with each other. This is because the outcomes of any
individual agent’s actions within the environment are affected not only by
their own decisions but also by the actions taken by other agents, where
agents must align their individual rationality with one another in order to
achieve a rational joint behavior.

Thereby, it is essential to consider the social conventions, role assignment,
and communication predisposed in the shared environment. Social conventions
establishes a social preferences over agents, thereby aiding with resolution
on conflicting action selections. Role assignments restrict and define the
actions available for each agent. Communication encapsulates the method in
which negotiations between agents is permitted, enabling agents to make more
"globally" informed decisions. The properties and conditions of these elements
is largely considered task-specific, however, any MARL solutions must take
into account the unique characteristics and demands of each situation.

####  4.4.1 Agent Awareness

Agents can exhibit different degrees of awareness of other agents, which can
be classified into three categories: independent, tracking, and agent-aware
[Busoniu et al., 2008]. The selection of an awareness level involves unique
considerations, advantages, and challenges, contingent upon the specific
nature of the interaction and the task. At each level, a trade-off between
stability and adaptability becomes evident.

######  Definition 11 (Stability and Adaptability)

Stability focuses on achieving convergence to a stationary policy $\pi$, while
adaptability aims to maintain or improve performance in the face of changes in
other agents’ behaviors.

######  Definition 12 (Stationary Policy)

A policy $\pi^{i}$ is stationary, for any state $s^{i}$ and time-steps $t$ and
$t^{\prime}$, where $t\neq t^{\prime}$,

$|\pi^{i}_{t}(a|s^{i}_{t})-\pi^{i}_{t^{\prime}}(a|s^{i}_{t^{\prime}})|\leq\epsilon,\forall
a\in A$

While stability and adaptability are not necessarily dichotomous objectives,
the balance between the two helps illustrate the extent at which coordination
is emphasized. Effectively addressing this coordination problem requires
agents to skillfully navigate these intricacies and strike the right balance
between focusing on stability and adaptability.

##### Independent

Independent agents can be thought as disregarding the notion of coordination
entirely. Moreover, their focus lies solely on converging to stable behaviors
rather than adapting to the actions of other agents in their environment. In
cooperative settings, such methods are referred to as "coordination-free" and
are commonly employed in situations where coordination is not necessary,
demonstrating empirical success under restricted problem settings [Littman,
2001a, Lauer and Riedmiller, 2000]. In adversarial and mixed settings,
opponent-independent and agent-independent methods, respectively, have exhibit
similar trends [Hernandez-Leal et al., 2017]. However, these independent
methods can often result in sub-optimal outcomes or even failure to achieve
desired goals as coordination becomes crucial in many scenarios to anticipate
and respond strategically to the actions of other agents. Hence, when
situations are more dynamic and sensitive to the behaviors of others,
adaptability and proper coordination becomes essential.

##### Tracking

Tracking agents prioritize adaptability over stability, placing a greater
emphasis on coordination rather than learning a stable individual behavior.
This approach allows agents to continuously adjust their strategies based on
the observed behavior of other agents, and therefore provides a more
responsive and coordinated approach in dynamic environments. Empirically,
agent-tracking methods rely on opponent-modeling to guide the agents’ action
selection process. This involves developing internal models of other agents’
behaviors and using fictitious play techniques [Robinson, 1951, Weinberg and
Rosenschein, 2004]. Given the dynamic nature of opponent behavior and the
evolving strategies of other agents, the system’s stability may be
compromised. The constant adaptation and heavy reliance on coordination can
lead to non-stationary behaviors, as the agents respond not only to changes in
the environment but also the changing strategies of other agents.

##### Agent-Aware

Agent-aware agents strive to achieve a balance between stability and
adaptability by being conscious of their environment and attempting to
coordinate while preserving elements of their individuality. Previous studies
have explored approaches such as "Adapt When Everyone is Stationary, Otherwise
Move to Equilibrium" (AWESOME) [Conitzer and Sandholm, 2003] or "Win or Learn
Fast" (WoLF) [Bowling, 2004] to determine when to adapt and re-coordinate or
maintain their local strategy, largely by adjusting the learning rate, or to
incorporate the other agent’s anticipated learning to one another [Foerster et
al., 2018]. These concepts primarily address handling the non-stationarity of
the optimization problem, but this heightened awareness also establishes a
well-rounded foundation for fostering social behaviors that lead to stable and
successful coordination.

###  4.5 Coordination Graphs

For several multi-agent domains, the outcome of an agent’s action often
depends only on a subset of other agents in the domain. Coordination graphs
[Nair et al., 2005, Guestrin et al., 2001] are graphs defined in the MAS that
compactly represents these interactions between subsets of agents.
Specifically, coordination graphs factorized the value function into a set of
payoff functions and utility function. Each payoff function is associated to a
subset of agents and can be interpreted as (hyper)-edges in a graph where the
nodes are agents [Amato and Oliehoek, 2014], whereas the utility functions
reflect individual agent’s utility.

With this factorization, maximum-a-posteriori estimation techniques, such as
variable elimination [Guestrin et al., 2001] and max-plus [Vlassis et al.,
2004], can be used to compute the joint action. More recent extensions
leverage deep neural networks to model different components of the factorized
value function [Böhmer et al., 2020] or the coordination graph itself [Li et
al., 2021].

##### Scope of Coordination

The scope of agent coordination can be categorized into global, neighbourhood,
or agent level [Zhang et al., 2021b]. Global-level coordination approaches
involve a form of virtual centralization, permitting collaboration to occur
with shared observations and actions among all agents [Sunehag et al., 2017].
On the other hand, neighbourhood-level coordination methods involve agents
sharing observations and actions only within a predefined local neighbourhood
[Subramanian et al., 2022]. While both global-level and neighbourhood-level
approaches aim to address overall coordination issues among agents, they often
overlook the coordination needs of individual agents, which vary based on
their distinct roles. Therefore, the heterogeneity in role assignment can make
it challenging to merge them into a single virtual agent.

Agent-level coordination frameworks recognize and preserve the unique roles
and behaviors of individual agents by enabling coordination on an agent-to-
agent level [Zhang et al., 2021b]. However, designing efficient and effective
methods for expressive agent-level coordination that is scalable remains an
open challenge.

###  4.6 MAS Training Schemes

In MARL research, there exists a spectrum of agent representations in training
and execution in order to combat the scalability and complexity issues of
learning joint strategies. This spectrum includes three main categories:
centralized training and centralized execution (CTCE), decentralized training
and decentralized execution (DTDE), and centralized training and decentralized
execution (CTDE) [Lowe et al., 2020]. The idea of centralization couples
components of agents’ behaviors to provide a more complete state information
to work with. Importantly, leveraging some level of centralization poses as a
good solution for handling non-stationarity, as each agents now will have some
access to global information to stabilize the changes in other agents’
behaviors.

####  4.6.1 CTCE

A fully centralized approach involves mapping a collection of local
observations from each agent to distributions over individual action spaces.
In other words, we essentially reduced the MAS control problem into a single-
agent RL optimization over the concatenated observations and combinatorial
joint action space. In training, this paradigm proves beneficial in terms of
expressiveness and completeness, as centralized states are provided, enabling
access to all available information [Gupta et al., 2017b]. Often times, CTCE
approaches are used as strong performance baselines for non-CTCE methods [Yu
et al., 2022a].

However, during execution, the assumptions of decentralization may be
compromised. This is because during execution, decentralized agents can only
make decisions based on their local observations and may not have access to
the global information it was trained on. Therefore, nontrivial and unnatural
adjustments from a centralized executor to decentralized policies must be
made, such as masking the other agent’s information to prevent information
leakage. CTCE approaches also fail to address the exponential scaling caused
by the joint state-action space of MAS, sometime regarded as the curse of
dimensionality problem [Gronauer and Diepold, 2022]. A key issue noted by
prior efforts is the lazy agent problem [Sunehag et al., 2017], when certain
agents learns a good policy but some agents have less incentive to continue to
explore and learn themselves, as their actions may negatively affect the
already high-performing agents. For example, as discussed in [Sunehag et al.,
2017], consider the scenario of training a soccer team with the number of
goals as the team’s reward signal. If certain players are more proficient
scorer than the other, it becomes evident that when the less skilled player
takes a shot, the resulting outcome is less favorable on average.
Consequently, the weaker player learns to avoid taking shots [Hausknecht,
2016].

####  4.6.2 DTDE

A fully decentralized approach segregates the learning and testing process of
individual agents. This distributed approach maps individual observations to
local action spaces. Hence, each agent relies solely on its local observations
to determine its actions without any centralized controller, thereby having no
access to global information at any point of training of execution. This does
not necessarily mean the agents cannot perceive nor is aware of other agent’s
existence (i.e. independent learners (IL) vs. joint action learner (JAL) as
defined in [Claus and Boutilier, 1998]), but it does mean that they must
adhere to all decentralization constraints in all aspects of training and
execution.

In prior efforts [Claus and Boutilier, 1998, Tan, 1997, Lauer and Riedmiller,
2000, Tampuu et al., 2015], independent learning with standard RL algorithms
does demonstrate the ability to converge to an equilibrium in deterministic
settings. In fact, in certain settings and under fine-tuned optimization
schemes, such as in [Jaderberg et al., 2019], DTDE approaches are capable of
learning very complex multi-agent tasks proficiently. Other learning
paradigms, such as in federated learning [McMahan et al., 2023, Bouacida and
Mohapatra, 2021], also utilize decentralized learning for various
applications.

The key challenge in the DTDE training scheme, as notably emphasized, is non-
stationarity. This challenge is exacerbated by the absence of centralization,
leading to the loss of crucial mutual information among agents, which, in
turn, can give rise to various learning pathologies [Palmer, 2020]. To
mitigate these pathologies, a widely adopted strategy involves inducing
optimism [Matignon et al., 2007, Palmer et al., 2018, Lyu and Amato, 2020],
through hysteric learning or leniency. These approach restricts the reduction
of value estimations, thereby alleviating the impact of other agents’
exploration strategies and promoting exploration beyond equilibria that can
easily trap agents without the added optimism.

##### Hysteric Learning and Leniency

While DTDE has demonstrated success in deterministic settings, independent
learning has struggled to replicate such achievements in stochastic settings.
A significant stumbling block has been the tendency to overestimate the value
function, a consequence of the inherent stochasticity, resulting in sub-
optimal solutions, as stated in [Matignon et al., 2007]. To address this
issue, hysteric Q-learning [Matignon et al., 2007] was introduced to provide
an optimistic update function that assigns greater weight to positive
experiences, particularly beneficial in cooperative multi-agent scenarios.
This is achieved through the use of two learning rates, denoted as $\alpha$
and $\beta$. The larger learning rate, $\alpha$, is applied when updating
Q-values following improvements, while $\beta$ is utilized otherwise.

Alternatively, another method to adjust the degree of optimism during the
learning process is leniency [Palmer et al., 2018]. Leniency effectively
allows for the forgiveness or disregard of suboptimal actions taken by
teammates that result in low rewards during initial exploration, taking in
form of lenient Q-value updates and lenient-based exploration. Over time, this
optimism exhibited by lenient agents is gradually reduced as they encounter
and revisit state-action pairs. Consequently, agents become less lenient in
situations frequently encountered, while retaining their optimistic outlook in
unexplored territories. This shift towards average-based reward learning from
maximum-based, which helps lenient agents steer clear of suboptimal joint
policies, especially in environments where rewards are subject to stochastic
fluctuations. Empirically, leniency shows higher learning stability compared
to hysteretic learning, primarily due to a temperature-enabled leniency at
different stages of estimation maturity. The leniency decay allows for a more
faithful representation of domain dynamics during later stages of training,
where it is probable that teammate policies become stable and near-optimal,
assuming the rate of decay is appropriate and value maturity is synchronized
across all states.

Like CTCE, DTDE demonstrates an significant issue of scalability, as a
distributed solution requires each agent to not only be represented
individually, but also requires their own set of samples for learning. As
agents are not granted any access to the global state, which can be pivotal
not only for sample efficiency but good performance [Gupta et al., 2017b].

####  4.6.3 CTDE

CTDE provides a middle-ground by centralizing certain variables during
training that still enable decentralized execution of agents [Kraemer and
Banerjee, 2016]. This approach strikes a balance between the advantages of
centralization and while maintaining the constraints set by natural and
artificial decentralization during execution. CTDE is commonly practiced
either by using centralized value function and value function factorization.

##### Centralized Critic

In actor-critic methods, the value function serves the purpose of stabilizing
the policy gradient during training, rather than being directly utilized
during execution [Gu et al., 2017]. As a result, centralizing the value
function in a CTDE framework does not violate any decentralization
constraints, while still benefiting from access to more comprehensive state
information during the training process. Hence, agents with centralized value
function can still take advantage of a broader range of state information,
leading to enhanced learning, efficient updates and coordination between the
actor and the critic, thereby facilitating improved policy convergence
[Foerster et al., 2017a, Lowe et al., 2020]. With this paradigm, single-agent
RL algorithms can naturally be extended, similar to DTDE, however, using a
shared critic model (i.e. MAPG [Samvelyan et al., 2019], MADDPG [Lowe et al.,
2020] and MAPPO [Yu et al., 2022a]).

##### Value Function Factorization

Value function factorization decomposes a centralized value function into
local policies for each agent. A simple implementation of this is known as
value decomposition network (VDN) [Sunehag et al., 2017], where the sum of the
learned local value functions can be treated as the global value. Typically,
this approach is more applicable in settings with a global reward structure,
hence in Dec-MDP applications. In many extensions of VDN, the standard
constraints of Individual-Global-Max (IGM) [Rashid et al., 2018] and
Individual-Global-Optimal (IGO) [Zhang et al., 2021a] serve as theoretical
basis for guaranteeing and maintaining consistency between the global and
local value estimates. However, these constraints have shown to restrict the
expressiveness of the value function representations [Mahajan et al., 2020],
leading to sub-optimal value approximations and poor explorations.

Like CTCE, this approach is prone to scalability issues. As the number of
agents grows, the centralized value function may need to handle a larger or
more intricate state space. This can lead to significant computational costs
and difficulties in defining the concise state space. Another critical
challenge is the centralized-decentralized mismatch. Since the value function
is shared among agents, sub-optimal policies from one agent can have a
detrimental impact on the policy learning of other agents, causing
catastrophic miscoordination [Wang et al., 2020]. Largely, this increased
variance in learning a shared critic remains a long-standing challenge.

####  4.6.4 Parameter Sharing

A commonly used approach to implement centralization is through parameter
sharing, where different agents share representation modes [Gupta et al.,
2017a]. This allows each agent to update the same set of parameters,
potentially leading to a more efficient and richer learning process. In a
sense, all of the agents are able to aggregate their experience and learn much
much faster in a more memory-efficient manner. However, it is important to
note that this can introduce instability, especially when dealing with highly
diverse agents, as it essentially transforms the problem into a difficult
multi-task optimization problem. Parameter sharing among such agents,
especially if they are heterogeneous, becomes a nontrivial task.

###  4.7 Off-policy Learning

To improve the sample efficiency of RL training, agents can learn using off-
policy data, meaning they are able to use experiences that come from different
policies in some manner [Sutton and Barto, 2018, Silver et al., 2014].
Typically, these approaches rely on storing these samples in an experience
replay buffer. However, proper implementation of experience replay in a multi-
agent setting is non-trivial due to the adaptive nature of agent policies over
time (i.e. non-stationary dynamics), rendering past experiences obsolete.
Previous efforts [Foerster et al., 2017b] account for this discrepancies
through two methods. The first approach utilizes importance sampling to
correct the policy updates, however there remains questions of the
tractability of computing the importance weightings and its large and
unbounded variance. Extensions to alleviate these issues, including
truncation, does reduce variance, however, introduces additional bias.
Fingerprinting, on the other hand, appends contextual information regarding
the current stage of learning of the agents in the environment to the samples
that are stored in the experience replay buffer, as to disambiguate the age of
the sample. Both approaches prove to stabilize experience replay sufficiently.

Aside the depreciation of samples, other issues, such as concurrency of
experience sampling [Omidshafiei et al., 2017] and detecting miscoordination
within samples to reduce the learning rate when encountering exploratory
teammates [Palmer et al., 2019, Lyu and Amato, 2020], assist to target
learning pathologies such as relative over-generalization. Traditional
experience replay mechanisms, such as priority replay [Schaul et al., 2016],
has been experimented with MAS. However, a naive application may deteriorate
the convergence and performance due to the noisy reward and the continuous
behavior changes of coexisting agents, causing a priority bias. Hence, a
lenient reward function is modeled [Zheng et al., 2018] to correct the
priority bias.

###  4.8 Exploration

The long-standing challenge of exploration in RL studies the task of
effectively exploring unknown environments to collect valuable experiences
that benefits the agents’ learning the most. This task can be especially
demanding in intricate environments characterized by sparse and delayed reward
signals, noisy transitions, long horizons, and non-stationary dynamics [Hao et
al., 2023]. Traditionally, simple exploration methods, such as
$\epsilon$-greedy [Sutton and Barto, 2018] or noise perturbation [Fujimoto et
al., 2018a], can be employed for random action-selection, however, such naive
methods can lead to unintentional and indiscriminate exploration which can be
inefficient in complex learning tasks with exploration challenges. Exploration
can be driven by two different approaches: uncertainty-oriented exploration
and intrinsic motivation-oriented exploration.

##### Uncertainty-oriented Exploration

Despite a lack of knowledge regarding the optimal actions, agents can
incorporate their own uncertainty into the decision-making process when
selecting actions. A common heuristic to employ is the principle of ’’Optimism
in the Face of Uncertainty", where agents are incentivized to explore state-
action pairs with high epistemic uncertainty.

######  Definition 13 (Epistemic and aleatoric uncertainty)

Epistemic uncertainty represents the errors that arise from insufficient and
inaccurate knowledge about the environment whereas aleatoric uncertainty
represents the inherent randomness of the environment.

Typically, this approach requires some modeling of these uncertainties. A
common approach is to parameterize the solution as a distribution [Zhu et al.,
2020, Sun et al., 2021, Zhao et al., 2022] to be able to properly express the
stochasticity of the environment and leveraging an classic exploration
technique utilizing these estimates.

##### Intrinsic Motivation-oriented Exploration

An alternative approach is to incorporate the meta-task of exploration by
designing intrinsic rewards for agents. These rewards can be to minimize
prediction errors regards the environment [Zheng et al., 2021], motivated by
novelty of states [Mahajan et al., 2020, Iqbal and Sha, 2021, Liu et al.,
2021], social influence [Jaques et al., 2019], or driven by information gain
[Houthooft et al., 2017]. For instances, in [Du et al., 2019], the individual
intrinsic reward are learned and used to update an agent’s policy with the
objective of maximizing the team reward.

##### Multi-agent Exploration

In a multi-agent setting, we face the challenge of not only the complexity,
but also mis-coordination (i.e. alter-exploration problem). This issue
requires some level of coordinated exploration [Hao et al., 2023], as
exploratory actions of one agent can affect the learning of others [Palmer et
al., 2018] and in certain multi-agent tasks, efficient exploration requires a
degree of global planning as opposed to pure local exploration [Brafman and
Tennenholtz, 2003].

###  4.9 Communication

Communication enables agents to behave as a collective, rather than a
collection of independent individuals. Hence, agent can utilize not only its
local observation but also information received from the other agents to
formulate its strategy. In many multi-agent tasks, communications proves vital
to coordinate the behavior of multiple agents to achieve optimal performance
[Foerster et al., 2016], especially under settings with imperfect information
and partial observability [Zaïem and Bennequin, 2019].

The establishment of an efficient communication mechanism presents several key
challenges. It necessitates consideration not only of what information to
communicate [Sukhbaatar et al., 2016, Foerster et al., 2016], but also how,
when [Singh et al., 2018], and with whom [Jiang and Lu, 2018] to communicate.
This research topic has been heavily studied in the MARL domain, as it holds
huge potential in bringing a more cohesive behaviors in MAS [Zhu et al.,
2022].

####  4.9.1 Communication Infrastructure

In a networked stochastic game, a communication graph is introduced to define
which agents each agent can communicate with. The restriction placed on its
edges’ existence are bounded by the constraints of decentralization, and
require solutions that address issues that include limited range [Huh and
Mohapatra, 2023], limited bandwidth [Foerster et al., 2016], noisy
communication channels [Freed et al., 2020], and contentions with shared
communication mediums [Kim et al., 2019], such as a proxy.

##### Proxy

While decentralization prohibits centralized executors, a centralized
communication medium is not prohibited. The proxy serves as a coordinator and
message transformer for specific purposes. It can gather local observations
and hidden states from agents in the environment, subsequently broadcasting a
common message to each of them [Kong et al., 2017]. Alternatively, it can
connect nearby agents who opt to participate in a communication group,
facilitating the sharing of coordinated messages with each group member [Jiang
and Lu, 2018].

##### Networked communication

In contrast, the networked communication protocol consists of decentralized
policies that operate based on local observations and messages received from
network neighbors [Zhang et al., 2018, Chu et al., 2020]. Specifically, a
graph neural network [Kipf and Welling, 2017] is frequently employed for
graph-like communication protocol [Singh et al., 2018, Sukhbaatar et al.,
2016, Liu et al., 2019].

##### Graph Neural Networks

Facilitating rich communication among agents requires a scalable framework
that can naturally process information within the coordination graph in an
expressive manner. Graph neural networks (GNNs) are a fundamental tool for
handling non-Euclidean data, especially when dealing with information
naturally occurring in graph structures. GNNs, akin to other neural network
architectures, are designed to learn to map input data to latent
representations that can be used in subsequent tasks. GNNs generate these
latent embeddings by iteratively performing the following operations: message
computation, propagation, and aggregation. Together, these three operations
can be collectively described as a graph convolution [Kipf and Welling, 2017],
which enable GNNs to scalably extract meaningful information from the graph
structure and expressively model complex relationships between nodes. Graph
convolutions can be performed iteratively, increasing the receptive field and
allowing GNNs to capture more global information as the number of message
passing rounds increase, i.e. increase the number of GNN layers.

There have been several advancements with GNN algorithms, specifically to
increase expressiveness, complexity, scale, and compensate for the over-
smoothing problem [Xu et al., 2018], especially in dense graphs with vertices
that have many shared neighbors, resulting in redundant node embeddings.
Current MARL research leverage advancements in GNNs, such as graph convolution
network (GCN) [Kipf and Welling, 2017], graph attention network (GAT) [Brody
et al., 2022], and graph isomorphism network (GIN) [Xu et al., 2019] and the
use of skip connections [Xu et al., 2021]. However, much of these GNN
architectural designs are geared towards other applications such as
representation learning purposed for supervised classification. There has been
efforts to bridge these tools into the domain of control such that mechanisms
are tailored to the intricacies of MAS, although this remains an open problem
in MARL.

##### Implicit Communication

Implicit forms of communication can be developed, such as stigmergy [Stone and
Veloso, 2000]. Active stigmergy occurs when an agent alters the environment to
affect the sensory input of another agent, whereas passive stigmergy involves
altering the environment so that the effects of another agent’s actions change
[Holland, 1996].

####  4.9.2 Learning to Communicate

The process of learning communication makes use of implicit or explicit
feedback, such as rewards, which may be optimized in conjunction with the
learning of control policies. While the optimization of the communication
mechanism and control can be separate [Foerster et al., 2016, Gupta et al.,
2022], common practice is to seamlessly integrate the two learning dynamics,
often with differentiable modeling and backpropagation [Foerster et al., 2016,
Sukhbaatar et al., 2016, Freed et al., 2020].

Communication mechanisms can be optimized to facilitate and guide the
coordination of agents. For instance, the edges within the communication graph
can be dynamically weighted based on the correlation between two agents, as
determined through sample reward trajectories [Zhang et al., 2021b], or they
can be learned through the utilization of attention mechanisms [Jiang and Lu,
2018, Li et al., 2021]. An alternative approach involves applying stronger
regularization based on various communication conditions to enhance the
likelihood of inducing the desired coordinating behaviors. Drawing inspiration
from pre-training concepts in single-agent Reinforcement Learning (RL),
techniques like contrastive learning can be employed to encourage latent
representations of spatially [Srinivas et al., 2020] or temporally [Jaderberg
et al., 2016, Stooke et al., 2021] similar inputs to become more similar while
ensuring that more distinct inputs become more dissimilar. This method aims to
establish effective coordination among agents, characterized by effectiveness,
stability and consistency over time [Jiang et al., 2020]. To achieve this,
regularization can be applied to promote temporal relationships between
communication links, thereby ensuring the reliability and persistence of
communication.

###  4.10 Ad-Hoc Team-Play

The concept of ad-hoc teamwork [Stone et al., 2010] challenges the learned
behaviors of agents to work with unknown partners who are capable of
contributing to the task. The keys assumptions that hold is that agents have
no prior coordination before the ad-hoc interactions, and agents have no
direct control over other agents [Mirsky et al., 2022]. If we assume no ad-hoc
interactions and without any behavioral adaptation, this is often known as
zero-shot coordination (ZSC) [Hu et al., 2021b].

The crucial aspect of this challenge is to avoid arbitrary conventions that
are often arise in standard RL/MARL training [Carroll et al., 2020] and to
properly handle the intricacies of MAS. Specifically, dealing with
heterogeneous agents, open environments (i.e. variation in number of agents in
environment), imperfect information, reliable and robust communication
mechanism, adaptive agents, and the nature of interactions [Mirsky et al.,
2022] remain unclear to handle while achieving good cross-play [Nekoei et al.,
2023].

To address ad-hoc team-play, an option is for agents learn to identity the
behaviors of the other agents [Chen et al., 2020] such that it can properly
adjust its strategy to its current environment. Similarly, agents can instead
learn models of the other agents for fast and efficient teamwork in the
absence of explicit prior coordination [Barrett et al., 2017, Santos et al.,
2021]. However, these approach is sample inefficient, as agents would need to
learn these additional capability effectively. Another option is to remove
grounded beliefs of the agents by utilizing off-belief learning [Hu et al.,
2021a].

###  4.11 Knowledge Transfer

The sharing of learned behaviors among agents can improve the efficiency of
enriching the collective knowledge of populations [Silva and Costa, 2019], a
phenomenon that has been extensively studied within the framework of diffusion
of innovation. Knowledge transfer manifests through two central approaches:
intra-agent transfer, where knowledge is transferred and reused from different
domains, and inter-agent transfer, where agents share knowledge within the
same task and setting. While both forms of knowledge transfer play crucial
roles in facilitating efficient learning and adaptation among multi-agent
systems, our focus will be on inter-agent transfer.

We define new set of role assignment amongst the populations, where there can
exist advisor/advisee, teacher/student, and mentor/observer.

  * •

In the advisor/advisee relationship, the advisor receives requests from the
advisee and observes their state, offering valuable information without
presuming anything about the internal representation of agents.

  * •

The interaction between a teacher and student is similar to that of an
advisor/advisee, but in this case, certain assumptions are made, allowing for
more informed designs for any information exchange.

  * •

As for the mentor/observer relationship, the observer aims to emulate the
behavior of the mentor, thereby learning from the mentor’s expertise and
experience.

####  4.11.1 Inter-agent Transfer

For inter-agent transfer, we explore two forms of its implementation: action
advising and reward shaping. Each of these approaches offers unique ways for
agents to leverage the knowledge of their peers and improve their performance
in the collective endeavor.

The fundamental concept of action advising revolves around the notion of an
experienced agent assisting a less experienced agent by providing
recommendations on the next best actions to take. This approach enables
effective learning, as agents can readily execute the suggested actions
without significant computational burden, commonly taking form of
advisor/advisee or teacher/student frameworks [Omidshafiei et al., 2018]. In
many cases, one agent can offer action suggestions to another, even when the
internal representation of the other agents remain unknown. Empirically, this
can take form through methods of imitation learning or model distillation.

With reward shaping, a teacher or advisor can influence the reward signals
received by the student, or advisee, to enhance exploration and guide their
learning [Gupta et al., 2017a]. This proves particularly valuable in scenarios
where rewards are sparse, as it allows for a learnable method to devise a
reward function, and in settings where behaviors are recurring.

###  4.12 Agent Modeling

An important ability for agents to have is to reason about the behaviors of
other agents by constructing models that make predictions about the modeled
agents. The process of creating models of other agents is often referred to as
agent modeling, or more traditionally known as opponent modeling. It consists
of understanding and predicting the other agents’ behaviors, goals, and
beliefs. An autonomous agent can employ such a model in various ways, with the
most significant being its use in guiding decision-making processes [Albrecht
and Stone, 2018]. A key concept within this area of research is the theory of
mind, where agents recursively reason about the states of other agents
[Premack and Woodruff, 1978], sometimes termed recursive reasoning
[Gmytrasiewicz and Durfee, 2000]. Often, nested reasoning methods approximated
the belief nesting down to a fixed recursion depth, traditionally by use of
game tree search [Carmel and Markovitch, 1996].

To account for the internal beliefs and the uncertainties of other agents in
the environment, the interactive POMDP [Gmytrasiewicz and Doshi, 2005] adds
the model spaces to the environment state, such that an agent has beliefs
about the environment state and the models of other agents.

Other solutions often include modeling various components of the other agent’s
policies as their future actions [Hong et al., 2018], nature of interactions,
roles, goals [Raileanu et al., 2018]. An important consideration is the trust
and robustness of utilizing these models, as agent may make incorrect or
inaccurate predictions. In fact, a interesting application is an adversarial
attempt to trick agents through actions to promote misleading synergies.

##  5 Concluding Remarks

While the challenges within MARL have been extensively studied and assessed,
the existing methodologies for acquiring multi-agent behaviors fall short of
fully harnessing the myriad opportunities within a MAS. Despite substantial
progress, particularly in unique areas of learning in a MAS, such as agent
modeling, knowledge transfer, ad-hoc team-play, credit assignment, and the
fundamental challenges of MARL listed in Section 4.2, there exists untapped
potential that demands further exploration and refinement.

The intricacies of MARL extend beyond individual agent behavior to encompass
the dynamic interactions unfolding within complex environments. Other
properties of certain applications, such as open environments, human-robot
interactions, heterogeneous agents, merit additional considerations, as for
instances, how to handle the unbounded and evolving nature of open
environments, safety and proper coordination with human-robot interactions,
and manage the diverse capabilities, behaviors, and learning speeds within
heterogeneous populations.

To conclude our discussion of MARL, our exploration of MARL discussed both the
progress made and the avenues yet to be fully explored. The multifaceted
nature of multi-agent interactions within dynamic environments demands ongoing
research and refinement of methodologies to unlock the full potential of MARL
in harnessing the complexities inherent in a MAS.

## References

  * Albrecht and Stone [2018] S. V. Albrecht and P. Stone.  Autonomous agents modelling other agents: A comprehensive survey and open problems.  _Artificial Intelligence_ , 258:66--95, may 2018.  doi: 10.1016/j.artint.2018.01.002.  URL https://doi.org/10.1016%2Fj.artint.2018.01.002.
  * Albrecht et al. [2024] S. V. Albrecht, F. Christianos, and L. Schäfer.  Multi-agent reinforcement learning: Foundations and modern approaches.  2024\.  URL https://www.marl-article.com.
  * Amato and Oliehoek [2014] C. Amato and F. A. Oliehoek.  Scalable planning and learning for multiagent pomdps: Extended version, 2014.
  * Andrychowicz et al. [2017] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, P. Abbeel, and W. Zaremba.  Hindsight experience replay.  _arXiv preprint arXiv:1707.01495_ , 2017.
  * Arora et al. [2012] S. Arora, E. Hazan, and S. Kale.  The multiplicative weights update method: a meta-algorithm and applications.  _Theory of Computing_ , 8(6):121--164, 2012.  doi: 10.4086/toc.2012.v008a006.  URL https://theoryofcomputing.org/articles/v008a006.
  * Aumann [1974] R. J. Aumann.  Subjectivity and correlation in randomized strategies.  _Journal of Mathematical Economics_ , 1(1):67--96, 1974.  ISSN 0304-4068.  doi: https://doi.org/10.1016/0304-4068(74)90037-8.  URL https://www.sciencedirect.com/science/article/pii/0304406874900378.
  * Baarslag et al. [2016] T. Baarslag, M. Hendrikx, K. Hindriks, and C. Jonker.  Learning about the opponent in automated bilateral negotiation: a comprehensive survey of opponent modeling techniques.  _Autonomous Agents and Multi-Agent Systems_ , 30, 09 2016.  doi: 10.1007/s10458-015-9309-1.
  * Badia et al. [2020a] A. P. Badia, B. Piot, S. Kapturowski, P. Sprechmann, A. Vitvitskyi, D. Guo, and C. Blundell.  Agent57: Outperforming the atari human benchmark, 2020a.
  * Badia et al. [2020b] A. P. Badia, P. Sprechmann, A. Vitvitskyi, D. Guo, B. Piot, S. Kapturowski, O. Tieleman, M. Arjovsky, A. Pritzel, A. Bolt, and C. Blundell.  Never give up: Learning directed exploration strategies, 2020b.
  * Barrett et al. [2017] S. Barrett, A. Rosenfeld, S. Kraus, and P. Stone.  Making friends on the fly: Cooperating with new teammates.  _Artificial Intelligence_ , 242:132--171, 2017.  ISSN 0004-3702.  doi: https://doi.org/10.1016/j.artint.2016.10.005.  URL https://www.sciencedirect.com/science/article/pii/S0004370216301266.
  * Bellemare et al. [2015] M. G. Bellemare, G. Ostrovski, A. Guez, P. S. Thomas, and R. Munos.  Increasing the action gap: New operators for reinforcement learning, 2015.
  * Bellemare et al. [2017] M. G. Bellemare, W. Dabney, and R. Munos.  A distributional perspective on reinforcement learning.  70:449--458, 06--11 Aug 2017.  URL https://proceedings.mlr.press/v70/bellemare17a.html.
  * Bellman [1957] R. Bellman.  Dynamic programming princeton university press princeton.  _New Jersey Google Scholar_ , pages 24--73, 1957.
  * Bergerson [2021] S. Bergerson.  Multi-agent inverse reinforcement learning: Suboptimal demonstrations and alternative solution concepts, 2021.
  * Bernstein et al. [2013] D. S. Bernstein, S. Zilberstein, and N. Immerman.  The complexity of decentralized control of markov decision processes.  _CoRR_ , abs/1301.3836, 2013.  URL http://arxiv.org/abs/1301.3836.
  * Bettini et al. [2022] M. Bettini, R. Kortvelesy, J. Blumenkamp, and A. Prorok.  Vmas: A vectorized multi-agent simulator for collective robot learning.  _The 16th International Symposium on Distributed Autonomous Robotic Systems_ , 2022.
  * Bielefeld [1988] R. S. Bielefeld.  Reexamination of the perfectness concept for equilibrium points in extensive games, 1988.  URL https://doi.org/10.1007/978-94-015-7774-8_1.
  * Blier et al. [2021] L. Blier, C. Tallec, and Y. Ollivier.  Learning successor states and goal-dependent values: A mathematical viewpoint, 2021.
  * Bloembergen et al. [2015] D. Bloembergen, K. Tuyls, D. Hennes, and M. Kaisers.  Evolutionary dynamics of multi-agent learning: A survey.  _Journal of Artificial Intelligence Research_ , 53:659--697, 08 2015.  doi: 10.1613/jair.4818.
  * Blundell et al. [2015] C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra.  Weight uncertainty in neural networks, 2015.
  * Bogin et al. [2019] B. Bogin, M. Geva, and J. Berant.  Emergence of communication in an interactive world with consistent speakers, 2019.
  * Bouacida and Mohapatra [2021] N. Bouacida and P. Mohapatra.  Vulnerabilities in federated learning.  _IEEE Access_ , 9:63229--63249, 2021.  doi: 10.1109/ACCESS.2021.3075203.  URL https://doi.org/10.1109/ACCESS.2021.3075203.
  * Bowling [2004] M. Bowling.  Convergence and no-regret in multiagent learning.  _Advances in neural information processing systems_ , 17, 2004.
  * Bowling and Veloso [2001] M. Bowling and M. Veloso.  An analysis of stochastic game theory for multiagent reinforcement learning.  08 2001.
  * Bowling and Veloso [2002] M. Bowling and M. Veloso.  Multiagent learning using a variable learning rate.  _Artificial Intelligence_ , 136(2):215--250, 2002.  ISSN 0004-3702.  doi: https://doi.org/10.1016/S0004-3702(02)00121-2.  URL https://www.sciencedirect.com/science/article/pii/S0004370202001212.
  * Brafman and Tennenholtz [2003] R. I. Brafman and M. Tennenholtz.  Learning to coordinate efficiently: A model-based approach.  _Journal of Artificial Intelligence Research_ , 19:11--23, jul 2003.  doi: 10.1613/jair.1154.  URL https://doi.org/10.1613%2Fjair.1154.
  * Brody et al. [2022] S. Brody, U. Alon, and E. Yahav.  How attentive are graph attention networks?, 2022.
  * Buckman et al. [2018] J. Buckman, D. Hafner, G. Tucker, E. Brevdo, and H. Lee.  Sample-efficient reinforcement learning with stochastic ensemble value expansion.  _CoRR_ , abs/1807.01675, 2018.  URL http://arxiv.org/abs/1807.01675.
  * Busoniu et al. [2008] L. Busoniu, R. Babuska, and B. De Schutter.  A comprehensive survey of multiagent reinforcement learning.  _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , 38(2):156--172, 2008.  doi: 10.1109/TSMCC.2007.913919.
  * Busoniu et al. [2010] L. Busoniu, R. Babuvska, and B. D. Schutter.  Multi-agent reinforcement learning: An overview.  2010\.  URL https://api.semanticscholar.org/CorpusID:17136625.
  * Böhmer et al. [2020] W. Böhmer, V. Kurin, and S. Whiteson.  Deep coordination graphs, 2020.
  * Cai et al. [2007] C. Cai, C. Yang, Q. Zhu, and Y. Liang.  Collision avoidance in multi-robot systems.  pages 2795--2800, 2007.  doi: 10.1109/ICMA.2007.4304002.
  * Calvo and Dusparic [2018] J. A. Calvo and I. Dusparic.  Heterogeneous multi-agent deep reinforcement learning for traffic lights control.  2018\.  URL https://api.semanticscholar.org/CorpusID:57661298.
  * Carmel and Markovitch [1996] D. Carmel and S. Markovitch.  Incorporating opponent models into adversary search.  pages 120--125, 01 1996.
  * Carroll et al. [2020] M. Carroll, R. Shah, M. K. Ho, T. L. Griffiths, S. A. Seshia, P. Abbeel, and A. Dragan.  On the utility of learning about humans for human-ai coordination, 2020.
  * Chen et al. [2020] S. Chen, E. Andrejczuk, Z. Cao, and J. Zhang.  Aateam: Achieving the ad hoc teamwork by employing the attention mechanism.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(05):7095--7102, Apr. 2020.  doi: 10.1609/aaai.v34i05.6196.  URL https://ojs.aaai.org/index.php/AAAI/article/view/6196.
  * Chen et al. [2007] X. Chen, X. Deng, and S.-H. Teng.  Settling the complexity of computing two-player nash equilibria, 2007.
  * Chen et al. [2022] Y. Chen, Y. Yang, T. Wu, S. Wang, X. Feng, J. Jiang, Z. Lu, S. M. McAleer, H. Dong, and S.-C. Zhu.  Towards human-level bimanual dexterous manipulation with reinforcement learning.  2022\.  URL https://openreview.net/forum?id=D29JbExncTP.
  * Choi et al. [1999] S. Choi, D.-Y. Yeung, and N. Zhang.  An environment model for nonstationary reinforcement learning.  12, 1999.  URL https://proceedings.neurips.cc/paper_files/paper/1999/file/e8d92f99edd25e2cef48eca48320a1a5-Paper.pdf.
  * Christianos et al. [2020] F. Christianos, L. Schäfer, and S. V. Albrecht.  Shared experience actor-critic for multi-agent reinforcement learning.  2020\.
  * Chu et al. [2019] T. Chu, J. Wang, L. Codecà, and Z. Li.  Multi-agent deep reinforcement learning for large-scale traffic signal control, 2019.
  * Chu et al. [2020] T. Chu, S. Chinchali, and S. Katti.  Multi-agent reinforcement learning for networked system control, 2020.
  * Chua et al. [2018] K. Chua, R. Calandra, R. McAllister, and S. Levine.  Deep reinforcement learning in a handful of trials using probabilistic dynamics models, 2018.
  * Claus and Boutilier [1998] C. Claus and C. Boutilier.  The dynamics of reinforcement learning in cooperative multiagent systems.  page 746–752, 1998.
  * Clavera et al. [2018] I. Clavera, J. Rothfuss, J. Schulman, Y. Fujita, T. Asfour, and P. Abbeel.  Model-based reinforcement learning via meta-policy optimization, 2018.
  * Cobbe et al. [2020] K. Cobbe, J. Hilton, O. Klimov, and J. Schulman.  Phasic policy gradient, 2020.
  * Conitzer and Sandholm [2003] V. Conitzer and T. Sandholm.  Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents, 2003.
  * Conitzer and Sandholm [2008] V. Conitzer and T. Sandholm.  New complexity results about nash equilibria.  _Games and Economic Behavior_ , 63(2):621--641, 2008.  ISSN 0899-8256.  doi: https://doi.org/10.1016/j.geb.2008.02.015.  URL https://www.sciencedirect.com/science/article/pii/S0899825608000936.  Second World Congress of the Game Theory Society.
  * Dabney et al. [2018a] W. Dabney, G. Ostrovski, D. Silver, and R. Munos.  Implicit quantile networks for distributional reinforcement learning.  pages 1096--1105, 2018a.
  * Dabney et al. [2018b] W. Dabney, M. Rowland, M. G. Bellemare, and R. Munos.  Distributional reinforcement learning with quantile regression.  2018b.
  * Dalton et al. [2019] S. Dalton, I. Frosio, and M. Garland.  Gpu-accelerated atari emulation for reinforcement learning.  _CoRR_ , abs/1907.08467, 2019.  URL http://arxiv.org/abs/1907.08467.
  * Daskalakis [2022] C. Daskalakis.  Equilibrium computation and machine learning, 2022.
  * Daskalakis and Panageas [2018] C. Daskalakis and I. Panageas.  The limit points of (optimistic) gradient descent in min-max optimization, 2018.
  * Daskalakis et al. [2009] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou.  The complexity of computing a nash equilibrium.  _SIAM Journal on Computing_ , 39(1):195--259, 2009.  doi: 10.1137/070699652.  URL https://doi.org/10.1137/070699652.
  * Daskalakis et al. [2022] C. Daskalakis, N. Golowich, and K. Zhang.  The complexity of markov equilibrium in stochastic games, 2022.
  * Dayan [1993] P. Dayan.  Improving generalization for temporal difference learning: The successor representation.  _Neural Computation_ , 5(4):613--624, 1993.  doi: 10.1162/neco.1993.5.4.613.
  * Dearden et al. [1999] R. Dearden, N. Friedman, and D. Andre.  Model based bayesian exploration.  page 150–159, 1999.
  * Degris et al. [2012] T. Degris, M. White, and R. S. Sutton.  Off-policy actor-critic.  _arXiv preprint arXiv:1205.4839_ , 2012.
  * Deisenroth and Rasmussen [2011] M. Deisenroth and C. E. Rasmussen.  Pilco: A model-based and data-efficient approach to policy search.  pages 465--472, 2011.
  * Du et al. [2019] Y. Du, L. Han, M. Fang, T. Dai, J. Liu, and D. Tao.  Liir: Learning individual intrinsic reward in multi-agent reinforcement learning.  2019\.
  * Ellis et al. [2022] B. Ellis, S. Moalla, M. Samvelyan, M. Sun, A. Mahajan, J. N. Foerster, and S. Whiteson.  Smacv2: An improved benchmark for cooperative multi-agent reinforcement learning, 2022.  URL https://arxiv.org/abs/2212.07489.
  * Espeholt et al. [2018] L. Espeholt, H. Soyer, R. Munos, K. Simonyan, V. Mnih, T. Ward, Y. Doron, V. Firoiu, T. Harley, I. Dunning, S. Legg, and K. Kavukcuoglu.  Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures, 2018.
  * Feinberg et al. [2018] V. Feinberg, A. Wan, I. Stoica, M. I. Jordan, J. E. Gonzalez, and S. Levine.  Model-based value estimation for efficient model-free reinforcement learning, 2018.
  * Fishburn et al. [1979] P. C. Fishburn, P. C. Fishburn, et al.  Utility theory for decision making.  1979\.
  * Foerster et al. [2017a] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson.  Counterfactual multi-agent policy gradients, 2017a.
  * Foerster et al. [2017b] J. Foerster, N. Nardelli, G. Farquhar, T. Afouras, P. H. S. Torr, P. Kohli, and S. Whiteson.  Stabilising experience replay for deep multi-agent reinforcement learning.  70:1146--1155, 06--11 Aug 2017b.  URL https://proceedings.mlr.press/v70/foerster17b.html.
  * Foerster et al. [2016] J. N. Foerster, Y. M. Assael, N. de Freitas, and S. Whiteson.  Learning to communicate with deep multi-agent reinforcement learning, 2016.
  * Foerster et al. [2018] J. N. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, and I. Mordatch.  Learning with opponent-learning awareness, 2018.
  * Fortunato et al. [2017] M. Fortunato, M. G. Azar, B. Piot, J. Menick, I. Osband, A. Graves, V. Mnih, R. Munos, D. Hassabis, O. Pietquin, et al.  Noisy networks for exploration.  _arXiv preprint arXiv:1706.10295_ , 2017.
  * Freed et al. [2020] B. Freed, G. Sartoretti, J. Hu, and H. Choset.  Communication learning via backpropagation in discrete channels with unknown noise.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(05):7160--7168, Apr. 2020.  doi: 10.1609/aaai.v34i05.6205.  URL https://ojs.aaai.org/index.php/AAAI/article/view/6205.
  * Freeman et al. [2021] C. D. Freeman, E. Frey, A. Raichuk, S. Girgin, I. Mordatch, and O. Bachem.  Brax -- a differentiable physics engine for large scale rigid body simulation, 2021.
  * Fujimoto et al. [2018a] S. Fujimoto, H. van Hoof, and D. Meger.  Addressing function approximation error in actor-critic methods, 2018a.
  * Fujimoto et al. [2018b] S. Fujimoto, H. van Hoof, and D. Meger.  Addressing function approximation error in actor-critic methods, 2018b.
  * Fulda and Ventura [2007] N. Fulda and D. Ventura.  Predicting and preventing coordination problems in cooperative q-learning systems.  page 780–785, 2007.
  * Gal et al. [2017] Y. Gal, J. Hron, and A. Kendall.  Concrete dropout, 2017.
  * Ghosh et al. [2023] D. Ghosh, C. Bhateja, and S. Levine.  Reinforcement learning from passive data via latent intentions, 2023.
  * Gilboa and Zemel [1989] I. Gilboa and E. Zemel.  Nash and correlated equilibria: Some complexity considerations.  _Games and Economic Behavior_ , 1(1):80--93, 1989.  ISSN 0899-8256.  doi: https://doi.org/10.1016/0899-8256(89)90006-7.  URL https://www.sciencedirect.com/science/article/pii/0899825689900067.
  * Gmytrasiewicz and Durfee [2000] P. Gmytrasiewicz and E. Durfee.  Rational coordination in multi-agent environments.  _Autonomous Agents and Multi-Agent Systems_ , 3, 08 2000.  doi: 10.1023/A:1010028119149.
  * Gmytrasiewicz and Doshi [2005] P. J. Gmytrasiewicz and P. Doshi.  A framework for sequential planning in multi-agent settings.  _Journal of Artificial Intelligence Research_ , 24:49--79, jul 2005.  doi: 10.1613/jair.1579.  URL https://doi.org/10.1613%2Fjair.1579.
  * Goodfellow et al. [2016] I. Goodfellow, Y. Bengio, and A. Courville.  Deep learning.  2016\.  http://www.deeplearningarticle.org.
  * Greenwald and Hall [2003] A. Greenwald and K. Hall.  Correlated-q learning.  page 242–249, 2003.
  * Gronauer and Diepold [2022] S. Gronauer and K. Diepold.  Multi-agent deep reinforcement learning: A survey.  _Artif. Intell. Rev._ , 55(2):895–943, feb 2022.  ISSN 0269-2821.  doi: 10.1007/s10462-021-09996-w.  URL https://doi.org/10.1007/s10462-021-09996-w.
  * Gu et al. [2016] S. Gu, T. Lillicrap, I. Sutskever, and S. Levine.  Continuous deep q-learning with model-based acceleration.  pages 2829--2838, 2016.
  * Gu et al. [2017] S. Gu, T. Lillicrap, Z. Ghahramani, R. E. Turner, and S. Levine.  Q-prop: Sample-efficient policy gradient with an off-policy critic, 2017.
  * Gu et al. [2023] S. Gu, J. G. Kuba, Y. Chen, Y. Du, L. Yang, A. Knoll, and Y. Yang.  Safe multi-agent reinforcement learning for multi-robot control.  _Artificial Intelligence_ , page 103905, 2023.
  * Guestrin et al. [2001] C. Guestrin, D. Koller, and R. Parr.  Multiagent planning with factored mdps.  14, 2001.  URL https://proceedings.neurips.cc/paper_files/paper/2001/file/7af6266cc52234b5aa339b16695f7fc4-Paper.pdf.
  * Gupta et al. [2017a] A. Gupta, C. Devin, Y. Liu, P. Abbeel, and S. Levine.  Learning invariant feature spaces to transfer skills with reinforcement learning, 2017a.
  * Gupta et al. [2017b] J. K. Gupta, M. Egorov, and M. J. Kochenderfer.  Cooperative multi-agent control using deep reinforcement learning.  2017b.
  * Gupta et al. [2022] N. Gupta, G. Srinivasaraghavan, S. K. Mohalik, N. Kumar, and M. E. Taylor.  Hammer: Multi-level coordination of reinforcement learning agents via learned messaging, 2022.
  * Ha and Schmidhuber [2018] D. Ha and J. Schmidhuber.  Recurrent world models facilitate policy evolution.  pages 2451--2463. Curran Associates, Inc., 2018.  URL https://papers.nips.cc/paper/7512-recurrent-world-models-facilitate-policy-evolution.  https://worldmodels.github.io.
  * Haarnoja et al. [2017] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine.  Reinforcement learning with deep energy-based policies.  pages 1352--1361, 2017.
  * Haarnoja et al. [2018] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine.  Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor, 2018.
  * Haarnoja et al. [2019] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel, and S. Levine.  Soft actor-critic algorithms and applications, 2019.
  * Hafner et al. [2020] D. Hafner, T. Lillicrap, J. Ba, and M. Norouzi.  Dream to control: Learning behaviors by latent imagination, 2020.
  * Hafner et al. [2022] D. Hafner, T. Lillicrap, M. Norouzi, and J. Ba.  Mastering atari with discrete world models, 2022.
  * Hafner et al. [2023] D. Hafner, J. Pasukonis, J. Ba, and T. Lillicrap.  Mastering diverse domains through world models, 2023.
  * Hao et al. [2023] J. Hao, T. Yang, H. Tang, C. Bai, J. Liu, Z. Meng, P. Liu, and Z. Wang.  Exploration in deep reinforcement learning: From single-agent to multiagent domain.  _IEEE Transactions on Neural Networks and Learning Systems_ , pages 1--21, 2023.  doi: 10.1109/tnnls.2023.3236361.  URL https://doi.org/10.1109%2Ftnnls.2023.3236361.
  * Hart and Mas-Colell [2000] S. Hart and A. Mas-Colell.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5):1127--1150, 2000.
  * Hausknecht and Stone [2015] M. Hausknecht and P. Stone.  Deep recurrent q-learning for partially observable mdps.  2015\.
  * Hausknecht [2016] M. J. Hausknecht.  _Cooperation and communication in multiagent deep reinforcement learning_.  PhD thesis, The University of Texas at Austin, 2016.
  * Havrylov and Titov [2017] S. Havrylov and I. Titov.  Emergence of language with multi-agent games: Learning to communicate with sequences of symbols, 2017.
  * Henderson et al. [2019] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger.  Deep reinforcement learning that matters, 2019.
  * Hernandez-Leal et al. [2017] P. Hernandez-Leal, M. Kaisers, T. Baarslag, and E. M. de Cote.  A survey of learning in multiagent environments: Dealing with non-stationarity.  _CoRR_ , abs/1707.09183, 2017.  URL http://arxiv.org/abs/1707.09183.
  * Hessel et al. [2017] M. Hessel, J. Modayil, H. van Hasselt, T. Schaul, G. Ostrovski, W. Dabney, D. Horgan, B. Piot, M. Azar, and D. Silver.  Rainbow: Combining improvements in deep reinforcement learning, 2017.
  * Holland [1996] O. Holland.  Multiagent systems: Lessons from social insects and collective robotics.  01 1996.
  * Hong et al. [2018] Z.-W. Hong, S.-Y. Su, T.-Y. Shann, Y.-H. Chang, and C.-Y. Lee.  A deep policy inference q-network for multi-agent systems, 2018.
  * Houthooft et al. [2017] R. Houthooft, X. Chen, Y. Duan, J. Schulman, F. D. Turck, and P. Abbeel.  Vime: Variational information maximizing exploration, 2017.
  * Hu et al. [2021a] H. Hu, A. Lerer, B. Cui, D. Wu, L. Pineda, N. Brown, and J. Foerster.  Off-belief learning, 2021a.
  * Hu et al. [2021b] H. Hu, A. Lerer, A. Peysakhovich, and J. Foerster.  "other-play" for zero-shot coordination, 2021b.
  * Hu and Wellman [2003] J. Hu and M. P. Wellman.  Nash q-learning for general-sum stochastic games.  _J. Mach. Learn. Res._ , 4(null):1039–1069, dec 2003.  ISSN 1532-4435.
  * Huh [2021] D. Huh.  Mix and mask actor-critic methods.  _ArXiv_ , abs/2106.13037, 2021.  URL https://api.semanticscholar.org/CorpusID:235691945.
  * Huh and Mohapatra [2023] D. Huh and P. Mohapatra.  Decentralized multi-agent filtering, 2023.
  * Huh and Mohapatra [2024] D. Huh and P. Mohapatra.  Isaacteams: Extending gpu-based physics simulator for multi-agent learning.  1 2024.
  * Iqbal and Sha [2021] S. Iqbal and F. Sha.  Coordinated exploration via intrinsic rewards for multi-agent reinforcement learning, 2021.
  * Jaderberg et al. [2016] M. Jaderberg, V. Mnih, W. M. Czarnecki, T. Schaul, J. Z. Leibo, D. Silver, and K. Kavukcuoglu.  Reinforcement learning with unsupervised auxiliary tasks, 2016.
  * Jaderberg et al. [2019] M. Jaderberg, W. M. Czarnecki, I. Dunning, L. Marris, G. Lever, A. G. Castañ eda, C. Beattie, N. C. Rabinowitz, A. S. Morcos, A. Ruderman, N. Sonnerat, T. Green, L. Deason, J. Z. Leibo, D. Silver, D. Hassabis, K. Kavukcuoglu, and T. Graepel.  Human-level performance in 3d multiplayer games with population-based reinforcement learning.  _Science_ , 364(6443):859--865, may 2019.  doi: 10.1126/science.aau6249.  URL https://doi.org/10.1126%2Fscience.aau6249.
  * Jaques et al. [2019] N. Jaques, A. Lazaridou, E. Hughes, C. Gulcehre, P. A. Ortega, D. Strouse, J. Z. Leibo, and N. de Freitas.  Social influence as intrinsic motivation for multi-agent deep reinforcement learning, 2019.
  * Jiang and Lu [2018] J. Jiang and Z. Lu.  Learning attentional communication for multi-agent cooperation, 2018.
  * Jiang et al. [2020] J. Jiang, C. Dun, T. Huang, and Z. Lu.  Graph convolutional reinforcement learning, 2020.
  * Jie and Abbeel [2010] T. Jie and P. Abbeel.  On a connection between importance sampling and the likelihood ratio policy gradient.  23, 2010.  URL https://proceedings.neurips.cc/paper/2010/file/35cf8659cfcb13224cbd47863a34fc58-Paper.pdf.
  * Jin et al. [2018] J. Jin, C. Song, H. Li, K. Gai, J. Wang, and W. Zhang.  Real-time bidding with multi-agent reinforcement learning in display advertising.  oct 2018.  doi: 10.1145/3269206.3272021.  URL https://doi.org/10.1145%2F3269206.3272021.
  * Jordan [1991] J. Jordan.  Bayesian learning in normal form games.  _Games and Economic Behavior_ , 3(1):60--81, 1991.  ISSN 0899-8256.  doi: https://doi.org/10.1016/0899-8256(91)90005-Y.  URL https://www.sciencedirect.com/science/article/pii/089982569190005Y.
  * Kakade [2001] S. M. Kakade.  A natural policy gradient.  _Advances in neural information processing systems_ , 14, 2001.
  * Kakade and Langford [2002] S. M. Kakade and J. Langford.  Approximately optimal approximate reinforcement learning.  2002\.  URL https://api.semanticscholar.org/CorpusID:31442909.
  * Kalai and Lehrer [1993] E. Kalai and E. Lehrer.  Rational learning leads to nash equilibrium.  _Econometrica: Journal of the Econometric Society_ , pages 1019--1045, 1993.
  * Kalashnikov et al. [2018] D. Kalashnikov, A. Irpan, P. Pastor, J. Ibarz, A. Herzog, E. Jang, D. Quillen, E. Holly, M. Kalakrishnan, V. Vanhoucke, et al.  Qt-opt: Scalable deep reinforcement learning for vision-based robotic manipulation.  _arXiv preprint arXiv:1806.10293_ , 2018.
  * Kapetanakis and Kudenko [2003] S. Kapetanakis and D. Kudenko.  Improving on the reinforcement learning of coordination in cooperative multi-agent systems.  04 2003.
  * Kapturowski et al. [2018] S. Kapturowski, G. Ostrovski, J. Quan, R. Munos, and W. Dabney.  Recurrent experience replay in distributed reinforcement learning.  2018\.
  * Kapturowski et al. [2022] S. Kapturowski, V. Campos, R. Jiang, N. Rakićević, H. van Hasselt, C. Blundell, and A. P. Badia.  Human-level atari 200x faster, 2022.
  * Kim et al. [2019] D. Kim, S. Moon, D. Hostallero, W. J. Kang, T. Lee, K. Son, and Y. Yi.  Learning to schedule communication in multi-agent reinforcement learning, 2019.
  * Kim et al. [2022] D.-K. Kim, M. Riemer, M. Liu, J. N. Foerster, M. Everett, C. Sun, G. Tesauro, and J. P. How.  Influencing long-term behavior in multiagent reinforcement learning, 2022.
  * Kipf and Welling [2017] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks, 2017.
  * Kong et al. [2017] X. Kong, B. Xin, F. Liu, and Y. Wang.  Revisiting the master-slave architecture in multi-agent deep reinforcement learning, 2017.
  * Korpelevich [1976] G. M. Korpelevich.  The extragradient method for finding saddle points and other problems.  1976\.  URL https://api.semanticscholar.org/CorpusID:118602977.
  * Kostrikov et al. [2021] I. Kostrikov, A. Nair, and S. Levine.  Offline reinforcement learning with implicit q-learning, 2021.
  * Koul [2019] A. Koul.  ma-gym: Collection of multi-agent environments based on openai gym.  https://github.com/koulanurag/ma-gym, 2019.
  * Kraemer and Banerjee [2016] L. Kraemer and B. Banerjee.  Multi-agent reinforcement learning as a rehearsal for decentralized planning.  _Neurocomputing_ , 190:82--94, 2016.  ISSN 0925-2312.  doi: https://doi.org/10.1016/j.neucom.2016.01.031.  URL https://www.sciencedirect.com/science/article/pii/S0925231216000783.
  * Kulkarni et al. [2016] T. D. Kulkarni, A. Saeedi, S. Gautam, and S. J. Gershman.  Deep successor reinforcement learning, 2016.
  * Kumar et al. [2020] A. Kumar, A. Zhou, G. Tucker, and S. Levine.  Conservative q-learning for offline reinforcement learning, 2020.
  * Kurach et al. [2020] K. Kurach, A. Raichuk, P. Stańczyk, M. Zając, O. Bachem, L. Espeholt, C. Riquelme, D. Vincent, M. Michalski, O. Bousquet, and S. Gelly.  Google research football: A novel reinforcement learning environment, 2020.
  * Kurutach et al. [2018] T. Kurutach, I. Clavera, Y. Duan, A. Tamar, and P. Abbeel.  Model-ensemble trust-region policy optimization, 2018.
  * Lan et al. [2021] T. Lan, S. Srinivasa, H. Wang, and S. Zheng.  Warpdrive: Extremely fast end-to-end deep multi-agent reinforcement learning on a gpu, 2021.
  * Lanctot et al. [2017] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Perolat, D. Silver, and T. Graepel.  A unified game-theoretic approach to multiagent reinforcement learning, 2017.
  * Lasota et al. [2017] P. A. Lasota, T. Fong, and J. A. Shah.  A survey of methods for safe human-robot interaction.  _Found. Trends Robotics_ , 5:261--349, 2017.  URL https://api.semanticscholar.org/CorpusID:207179253.
  * Lauer and Riedmiller [2000] M. Lauer and M. A. Riedmiller.  An algorithm for distributed reinforcement learning in cooperative multi-agent systems.  page 535–542, 2000.
  * Levine et al. [2020] S. Levine, A. Kumar, G. Tucker, and J. Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _CoRR_ , abs/2005.01643, 2020.  URL https://arxiv.org/abs/2005.01643.
  * Li et al. [2021] S. Li, J. K. Gupta, P. Morales, R. Allen, and M. J. Kochenderfer.  Deep implicit coordination graphs for multi-agent reinforcement learning, 2021.
  * Li et al. [2022] Y. Li, G. Xie, and Z. Lu.  Difference advantage estimation for multi-agent policy gradients.  162:13066--13085, 17--23 Jul 2022.  URL https://proceedings.mlr.press/v162/li22w.html.
  * Lillicrap et al. [2015] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Littman [1994] M. L. Littman.  Markov games as a framework for multi-agent reinforcement learning.  page 157–163, 1994.
  * Littman [2001a] M. L. Littman.  Value-function reinforcement learning in markov games.  _Cognitive Systems Research_ , 2(1):55--66, 2001a.  ISSN 1389-0417.  doi: https://doi.org/10.1016/S1389-0417(01)00015-8.  URL https://www.sciencedirect.com/science/article/pii/S1389041701000158.
  * Littman [2001b] M. L. Littman.  Friend-or-foe q-learning in general-sum games.  page 322–328, 2001b.
  * Liu et al. [2018] H. Liu, Y. Feng, Y. Mao, D. Zhou, J. Peng, and Q. Liu.  Action-depedent control variates for policy optimization via stein’s identity, 2018.
  * Liu et al. [2021] I.-J. Liu, U. Jain, R. A. Yeh, and A. G. Schwing.  Cooperative exploration for multi-agent deep reinforcement learning, 2021.
  * Liu et al. [2019] Y. Liu, W. Wang, Y. Hu, J. Hao, X. Chen, and Y. Gao.  Multi-agent game abstraction via graph attention neural network, 2019.
  * Lowe et al. [2019] R. Lowe, J. Foerster, Y.-L. Boureau, J. Pineau, and Y. Dauphin.  On the pitfalls of measuring emergent communication, 2019.
  * Lowe et al. [2020] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch.  Multi-agent actor-critic for mixed cooperative-competitive environments, 2020.
  * Luo et al. [2021] Y. Luo, H. Xu, Y. Li, Y. Tian, T. Darrell, and T. Ma.  Algorithmic framework for model-based deep reinforcement learning with theoretical guarantees, 2021.
  * Luong et al. [2019] N. C. Luong, D. T. Hoang, S. Gong, D. Niyato, P. Wang, Y.-C. Liang, and D. I. Kim.  Applications of deep reinforcement learning in communications and networking: A survey.  _IEEE Communications Surveys and Tutorials_ , 21(4):3133--3174, 2019.  doi: 10.1109/COMST.2019.2916583.
  * Lyu and Amato [2020] X. Lyu and C. Amato.  Likelihood quantile networks for coordinating multi-agent reinforcement learning, 2020.
  * Ma et al. [2021] Y. Ma, D. Jayaraman, and O. Bastani.  Conservative offline distributional reinforcement learning.  34:19235--19247, 2021.  URL https://proceedings.neurips.cc/paper_files/paper/2021/file/a05d886123a54de3ca4b0985b718fb9b-Paper.pdf.
  * Mahajan et al. [2020] A. Mahajan, T. Rashid, M. Samvelyan, and S. Whiteson.  Maven: Multi-agent variational exploration, 2020.
  * Makoviychuk et al. [2021] V. Makoviychuk, L. Wawrzyniak, Y. Guo, M. Lu, K. Storey, M. Macklin, D. Hoeller, N. Rudin, A. Allshire, A. Handa, and G. State.  Isaac gym: High performance gpu-based physics simulation for robot learning, 2021.
  * Matarić [1994] M. J. Matarić.  Learning to behave socially.  1994\.
  * Matarić [1997] M. J. Matarić.  Reinforcement learning in the multi-robot domain.  _Autonomous Robots_ , 4:73--83, 1997.  URL https://api.semanticscholar.org/CorpusID:14610547.
  * Matignon et al. [2007] L. Matignon, G. J. Laurent, and N. Le Fort-Piat.  Hysteretic q-learning : an algorithm for decentralized reinforcement learning in cooperative multi-agent teams.  pages 64--69, 2007.  doi: 10.1109/IROS.2007.4399095.
  * Matignon et al. [2012] L. Matignon, G. J. Laurent, and N. Le Fort-Piat.  Independent reinforcement learners in cooperative markov games: a survey regarding coordination problems.  _The Knowledge Engineering Review_ , 27(1):1–31, 2012.  doi: 10.1017/S0269888912000057.
  * McMahan et al. [2023] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.  Communication-efficient learning of deep networks from decentralized data, 2023.
  * Mirsky et al. [2022] R. Mirsky, I. Carlucho, A. Rahman, E. Fosong, W. Macke, M. Sridharan, P. Stone, and S. V. Albrecht.  A survey of ad hoc teamwork research, 2022.
  * Mnih et al. [2013] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.