August2023 Ph.D. Niko A. Grupen

# Responsible Emergent Multi-Agent Behavior

Niko A. Grupen

(2023)

###### Abstract

Responsible AI has risen to the forefront of the AI research community. As
neural network-based learning algorithms continue to permeate real-world
applications, the field of Responsible AI has played a large role in ensuring
that such systems maintain a high-level of human-compatibility. Despite this
progress, the state of the art in Responsible AI has ignored one crucial
point: human problems are multi-agent problems. Predominant approaches largely
consider the performance of a single AI system in isolation, but human
problems are, by their very nature, multi-agent. From driving in traffic to
negotiating economic policy, human problem-solving involves interaction and
the interplay of the actions and motives of multiple individuals.

This dissertation develops the study of responsible emergent multi-agent
behavior, illustrating how researchers and practitioners can better understand
and shape multi-agent learning with respect to three pillars of Responsible
AI: interpretability, fairness, and robustness. First, I investigate multi-
agent interpretability, presenting novel techniques for understanding emergent
multi-agent behavior at multiple levels of granularity. With respect to low-
level interpretability, I examine the extent to which implicit communication
emerges as an aid to coordination in multi-agent populations. I introduce a
novel curriculum-driven method for learning high-performing policies in
difficult, sparse reward environments and show through a measure of position-
based social influence that multi-agent teams that learn sophisticated
coordination strategies exchange significantly more information through
implicit signals than lesser-coordinated agents. Then, at a high-level, I
study concept-based interpretability in the context of multi-agent learning. I
propose a novel method for learning intrinsically interpretable, concept-based
policies and show that it enables novel behavioral analysis tools via concept
intervention that can reliably detect emergent coordination, coordination
failures (lazy agents), the emergence of strategy and role assignment, and
other dependencies between agent behavior. In the second part of the thesis, I
study fairness through the lens of cooperative multi-agent learning. There I
show that, despite being necessary for learning sophisticated coordination,
mutual reward alone does not incentivize fair multi-agent behavior. I
introduce novel group-based measures of fairness for multi-agent learning and
develop two novel algorithms that achieve provably fair outcomes via
equivariant policy learning. The third part of this thesis addresses
robustness. I present a systematic analysis of search-based multi-agent
learning systems such as AlphaZero and identify concrete failure modes that
are present in its policy and value networks, but are disguised by search. I
use these empirical findings to derive a novel extension of AlphaZero that
combines uncertainty-informed value estimation and improved exploration to
align AlphaZero’s policy and value predictions; thereby improving its
robustness.

Altogether, this body of work develops a framework within which researchers
and practitioners can begin to understand and shape multi-agent learning
systems; representing an initial step towards connecting Responsible AI and
multi-agent learning.

Niko A. Grupen is a Ph.D. candidate in the Department of Computer Science at
Cornell University, advised by Bart Selman and Daniel Lee. Niko’s research
centers on bridging advances in multi-agent learning, and reinforcement
learning more broadly, with Responsible AI. His work has appeared in top
conferences in AI and multi-agent systems such as NeurIPS, AAAI, ICML, AAMAS,
and ICRA; and he has spent time at top research labs including Google Brain
and Google’s People + AI Research organization. Niko is also an avid writer
and has contributed to the public discourse on AI and society through articles
in popular venues such as Future by Andreessen Horowitz and a chapter in the
2020 book Future of Text by Frode Hegland (with contributions by Vint Cerf and
Alan Kay, amongst others). Prior to his Ph.D., Niko was a machine learning
engineer at Apple, working on emergent technologies. Niko received his B. Sc.
of Computer Science summa cum laude from Villanova University, with minors in
Mathematics and Economics. He was elected to Phi Beta Kappa and was the
recipient of the Gregor Mendel medallion for excellence in Computer Science
(awarded to one student annually).

To my parents, Rod & Mary, and my brother, Yianni.

###### Acknowledgements.

I am extremely fortunate to have been surrounded by mentors, professors,
friends, and family who have generously shared their wisdom, expertise, and
support with me along this journey. Their passion for knowledge and their
willingness to invest time and effort in my growth have made this thesis
possible. I am forever thankful to my advisor Bart Selman for his wisdom and
guidance over these many years, for his patience and tact in shaping my messy
ideas into the work it has become today, and for our many Gimme chats. It has
been an honor to learn from my co-advisor Daniel Lee, whose careful attention
and feedback has sharpened my wit and taught me how to pursue ambitious, open-
ended ideas in a principled manner. I am grateful to David Field for his
kindness and encouragement, for cultivating my interest in psychology and
cognitive science, and for the many stimulating conversations at his weekly
round-table. I am honored to have had the opportunity to work with the three
of you as a committee—I will carry your many lessons with me. I am extremely
grateful to Shayegan Omidshafiei, Natasha Jaques, and Been Kim for their
mentorship and support during (and since) my time at Brain/PAIR; and for
believing in Concept Bottleneck Policies when it was just a bullet point under
"Possible Research Ideas:" on a literature review. I would also like to thank
my other collaborators and colleagues from Brain, PAIR, and DeepMind for many
thoughtful discussions: Yannick Assogba, Lucas Dixon, Joel Leibo, Edgar Duéñez
Guzmán, Asma Ghandeharioun, Adam Pearce, Ryan Mullins, Peter Hase, Srivatsan
Krishnan, and Blair Bilodeau. I would like to thank my brilliant friends and
colleagues at the Stanford Digital Economy lab—Stephan Zheng, Seth Benzell,
Victor Ye, Michael Curry, James Chapman—who graciously let me participate as
they navigated the frontier of multi-agent RL + macroeconomics. Thanks also to
Aviv Tamar and Carmel Rabinowitz for your joint love of intuitive physics and
robot learning, and for our collaborations in those areas. Thanks also goes to
Benjamin Laufer for our collaboration on collective obfuscation and to Michael
Hanlon and Alexis Hao for our work together on AlphaZero. To many lab-mates
and friends at Cornell and Cornell Tech—namely, Travers Rhodes, Chanwoo Chun,
Ge Gao, Ilan Mandel, David Goedicke, Rei Lee, Frank Bu, Matt Franchi, Maria
Teresa Parreira, Natalie Friedman, Mark Colley, Alexandra Bremers, Elif
Çelikörs, Alena Hutchinson, Christoforos Mavrogiannis, Wil Thomason, Claire
Liang, Andy Ricci, and Valts Blukis—thank you for making this such an
incredible experience. And special thanks goes to George Karagiannis and
Florian Suri-Pyaer—two funny guys. I am indebted to Gabriel Pereyra and
Winston Weinberg for taking a chance on me. I look forward to the journey
ahead, and to learning from the the brilliant minds of Daniel Hunter, Julio
Pereyra, Spencer Poff, BK, Beth Lebens, Karl de la Roche, Lisa Patel, John
LaBarre, and Gordon Moodie. To my close and long-term friends—especially
Connor and Alexandra, Tyler and Alison, Curtis, Danny, Ryan and Liz, Sean, and
Kirsten—thank you for always being there, supporting me, and mostly for
bearing with me. Most of all, I am grateful for the love and support of my
parents, Roderic Grupen and Mary Andrianopoulos. Thank you for instilling in
me a love for science, an insatiable curiosity, and for always being a sound
board to my craziest ideas. To my brother, Yianni, thank you for constantly
challenging me to be my best, and teaching me to be determined in what I do. I
would like to thank my grandparents, William and Doris Grupen, for supporting
the pursuit of education and knowledge, and for always inviting me over for a
coffee table chat. And to my grandparents, John and Eugenia Andrianopoulos,
who gave up their lives in Greece, immigrated through Ellis Island, and worked
in a pie factory so that future generations of their family could have an
opportunity at a better life—there is no way that I can thank you enough.

###  Chapter 1 Introduction

####  1.1 Move 37, Emergence, and Multi-Agent Problems

For thirty-six moves, there was nothing unusual about Lee Sedol’s second match
against DeepMind’s AlphaGo. Sedol and AlphaGo had each spent their first
eighteen stones establishing positions in the upper and lower corners of the
board, as is standard in high-level Go play. With its 19th stone, however,
AlphaGo opted to play a stone in a largely unoccupied middle section on the
right-hand side of the board, rather than continuing to fortify its hold on
the corners. To capture just how unprecedented this move was, Sedol—then the
world’s highest-ranked Go player—was so flummoxed that he actually left the
room to collect himself and, upon returning, studied the board for a full 15
minutes before playing another stone. What is more, though many viewers took
AlphaGo’s move to be a mistake at first, Move 37 initiated a highly complex
and influential sequence of moves that ultimately led to AlphaGo’s victory in
the match; and was heralded afterwards as "beautiful" by fellow Go champion
Fan Hui [135].

Understanding how a distinctly non-human move like Move 37 could occur
requires an understanding of how AlphaGo learns in the first place. AlphaGo is
a self-play reinforcement learning (RL) algorithm—starting from scratch, it
plays against itself, improving its strategy slowly over time as guided
exclusively by a straightforward objective: win the game. This simple
strategy, repeated across millions of games, enables AlphaGo to grow from
novice to super-human level expert. Moreover, aside from setting up the
algorithm and defining the rules of the game, self-play involves zero human
input. This means that a system trained via self-play is not constrained to
make the same decisions that a human would make—every decision is an emergent
behavior picked up during its training. In the case of Go, self-play allowed
AlphaGo to explore move sequences that were effective within the context of
winning the game, yet highly non-traditional from the perspective of an
extensive history of human gameplay.

AlphaGo’s success is representative of a larger paradigm shift sweeping across
AI research—one defined by simple yet highly scalable algorithms that are used
to train an appropriately large neural network over vast quantities of data
with little to no human intervention—and there are few domains where
algorithms leveraging these ingredients have yet to achieve super-human levels
of performance. For example, successor algorithms to AlphaGo have generalized
self-play learning to other complex games such as Chess and Shogi [184], and
even to general planning problems [174]. Elsewhere, these same principles have
led to diffusion-based model architectures, which have redefined the fields of
image [162, 170, 168] and video generation [188, 83, 82]; and transformer-
based architectures that have subsumed the majority of natural language
processing tasks [18, 20], many programming-related tasks [117], and even
previously infeasible tasks such as protein structure prediction [97] and
mathematical problem solving [119].

Despite the success of this design pattern that promotes scale-at-all-costs
and minimal human input, it is important to recognize that AI systems do not
exist in a vacuum. In their current form, AI systems are primarily used with
or alongside human counterparts. Even in scenarios where AI automation removes
humans from the problem-solving loop, the impact of AI systems materially
changes the human experience and the intent is to do so positively.

Recently, the fields of Responsible AI and AI Safety have grown to fill the
role of mediator for AI progress. As AI continues to permeate real-world use
cases and be deployed in human-facing applications, it is the role of these
communities to ensure that it is done safely and with human-compatibility as
an utmost priority. Thus far, they have been successful in this goal. For
example, issues of bias and fairness have risen to the forefront of supervised
learning research [136, 7], leading to formal measures that quantify the
presence of unfair or biased outcomes and novel algorithms that improve model
performance with respect to those measures [50, 102, 74, 54, 222, 96, 98].
Discussions of human-centered AI have also percolated more broadly [169] to
include studies of how learning objectives can be better aligned with human
preferences [72, 228], or avoid causing societal harm by way of under-
specification or uncertainty in learning processes [3, 79]. Most recently,
these ideas have been channeled towards generative models by studying the
extent to which generative outputs can be steered towards human-aligned
outcomes by fine-tuning from human feedback [32, 229, 147] or constraining
outputs to adhere to human-specified principles [4].

However, the aforementioned research vectors within Responsible AI have
focused primarily on supervised, self-supervised/generative, or single-agent
contexts, ignoring one crucial point: human problems are multi-agent problems.
Predominant approaches largely consider the performance of a single AI system
in isolation, but human problem-solving is, by its very nature, multi-agent.
From driving in traffic [204] to negotiating economic policy [226], human
problem-solving involves interaction and the interplay of the actions and
motives of multiple individuals.

Multi-agent learning has a deep-rooted history and it is one that has also
been rejuvenated by deep learning. In reinforcement learning settings
specifically, the incorporation of neural network-based policy and value
functions has led to novel algorithms and network architectures that stabilize
and scale multi-agent learning [126, 57, 218, 205, 153, 221, 77, 208, 12, 129,
164]; and has further enabled the exploration of solution spaces for complex
social interactions involving diverse incentive structures [44, 45, 92, 95,
115, 114, 5] and ab initio strategies for learning inter-agent communication
that simulate the development of language-like communication protocols [56,
112, 111, 40, 26, 36, 166, 25, 140, 193, 75, 51, 127].

However, the majority of multi-agent learning research is targeted at
maximizing traditional measures of performance (e.g. reward, Elo rating,
competition against human experts, etc). To realize the full potential of AI
systems, the research community will need to bridge multi-agent learning with
Responsible AI. This thesis introduces responsible emergent multi-agent
behavior as a new class of techniques developed at the intersection of these
two points; with the goal of reliably understanding and shaping emergent
behavior as a first-step towards unlocking the full potential of AI systems.
Focusing on responsible emergent multi-agent behavior will help multi-agent
learning in reaching technical parity with other learning disciplines,
developing fundamentally new algorithms and techniques for understanding and
shaping emergent multi-agent behavior, and formalizing measures of performance
that meet the unique demands of multi-agent problems.

####  1.2 Towards Responsible Emergent Multi-Agent Behavior

The goal of this thesis is to initiate the study of responsible emergent
multi-agent behavior, illustrating how researchers and practitioners can
better understand and shape emergent multi-agent behavior with respect to
three pillars of Responsible AI: interpretability, fairness, and robustness.
Each of these sub-disciplines and the motivation behind the contributions of
this thesis are outlined below.

#####  1.2.1 Interpretability

Part I of this thesis focuses on interpreting emergent multi-agent behavior.
Unlike supervised learning, where there have been significant efforts to
understand a model’s decisions, multi-agent interpretability remains under-
investigated. This is in part due to the increased complexity of the multi-
agent setting. For one, interpreting the decisions of multiple agents over
time is combinatorially more complex than understanding individual, static
decisions. Moreover, due to non-stationary learning dynamics, the scope and
variability of emergent behavior is vast—the behavior of each individual
agent, as well as the joint behavior of the multi-agent system, can vary
drastically with environmental conditions, or even random seeds (even more so
than in single-agent RL). Finally, behavioral changes are difficult to
identify through traditional measures of performance (e.g. reward, Elo,
evaluations against human experts, etc) alone; and so the trailing pace of
multi-agent interpretability relative other learning settings is also a
reflection of the limited availability of interpretability tools. Overall, the
nature of interactions between agents remains difficult to gauge in MARL.

This thesis posits that a rich set of interpretability techniques are needed,
specific to multi-agent learning and that match the expressivity and level of
insight outlined by these in other disciplines (e.g. supervised learning).
Such tools should enable us to answer high-level strategic questions, such as:

  * •

In cooperative environments, do agents learn to coordinate, opt for less
structured independent action, or some combination both?

  * •

In mixed-motive environments, do agents act selfishly, in a manner that
improves social welfare, or both?

  * •

In competitive environments, when during the training process do strategic
behaviors such as role assignment emerge, if at all?

as well as low-level behavioral questions, such as:

  * •

To what extent do agents exchange information implicitly through their
respective action spaces?

  * •

Can we measure the influence of one agent’s behavioral cues on its teammates?

#####  1.2.2 Fairness

Next, this thesis examines the implications of emergent behavior with respect
to algorithmic fairness. Increasingly, multi-agent algorithms are being
employed alongside human counterparts [34], as a proxy for human engagement
[150], or to solve problems that may materially impact a human’s socio-
economic well-being (e.g. tax policy, social planning [226]). However, as we
have seen, simple reward maximization yields a wide range of multi-agent
behavior. The emergence of sub-optimal behavior in these human-centered
applications is problematic, as it may impact human outcomes.

The goal of algorithmic fairness is to ensure that outcomes or decisions
derived from machine learning systems do not come to rely on sensitive
information, or disproportionately favor particular individuals or groups
based on that information (in terms of accuracy or output quality). As in the
interpretability domain, however, algorithmic fairness has not received the
depth of formal treatment in MARL settings as it has in supervised
learning111There is a large body of literature studying fairness in the game-
theoretic contexts, but our focus here is on formalizing multi-agent fairness
more generally (irrespective of reward structure) and, in particular,
highlighting the role of sensitive attributes and their interactions with
multi-agent outcomes; and there are a number of key differences in the problem
setup across these domains. In supervised learning, decisions (i.e.
predictions or classifications) are made statically for one individual at a
time [7, 136, 50, 74], whereas in multi-agent settings, decisions (i.e.
actions) influence multiple individuals (or agents) simultaneously and occur
repeatedly over many time-steps. Reward as a measure of outcomes further
complicates the picture—agent incentives may be aligned (cooperative),
conflicting (competitive), or mixed between local vs. global interests (social
dilemmas).

Existing fairness frameworks do not yet fully capture these multi-agent
nuances. This part of the thesis takes first steps towards addressing fairness
in multi-agent learning settings by asking:

  * •

How do we formalize fairness in multi-agent settings? For example, what do
sensitive variables mean for an agent within a multi-agent team? Can we
reconcile reward as an outcome variable?

  * •

In cooperative environments, is shared reward enough to incentivize fair
behavior to emerge, or does unfair behavior emerge naturally?

  * •

Can we shape multi-agent behavior during training to achieve fairer outcomes?
If so, to what extent does a trade-off between fairness and utility/efficiency
exist, and what properties of the MARL problem contribute to that trade-off?

#####  1.2.3 Robustness

Finally, we turn our attention to issues of robustness in search-based multi-
agent learning systems, such as AlphaZero [184]. By combining tree search with
neural network-based value estimation and action selection, AlphaZero and its
variants (e.g. AlphaGo [186]) have achieved impressive feats, including
reaching super-human levels of play in Go [186], Chess, and Shogi [185].
However, the combinatorial complexity of these games222Chess has up to
${\sim}10^{44}$ possible board states, Shogi ${\sim}10^{71}$, and Go
${\sim}10^{170}$ and the complexity of the AlphaZero algorithm itself makes
interpretation and analysis of its performance challenging. For this reason,
despite the clear evidence that AlphaZero’s best case performance surpasses
human game players, researchers have a limited understanding of what exactly
AlphaZero has learned about the games it plays and why it makes the decisions
that it does.

This is especially problematic in situations where AlphaZero’s decision-making
is sub-optimal. For example, recent work has shown that many board states
elicit surprising yet ineffective actions from AlphaGo [108]; and that
simple333Simple enough that each of the adversarial attacks was easily
countered by amateur-level Go players opponent strategies [209] create the
equivalent of adversarial examples [67] for AlphaZero’s policy network.
Subsequent work in concept-based interpretability has gone a long way towards
understanding where in AlphaZero’s large network certain strategic concepts
are encoded [132], yet the issue of robustness still remains.

The goal of this work is not only to examine how AlphaZero fails, but also to
uncover why AlphaZero fails; and use that understanding as motivation for
algorithmic improvements to AlphaZero’s generalization and robustness. In
particular, the following questions are relevant to this study of robustness:

  * •

Why does AlphaZero’s performance degrade so severely in the presence of simple
adversarial examples?

  * •

Can the robustness of AlphaZero’s policy and value networks be improved
algorithmically?

####  1.3 Contributions

The primary contribution of this thesis is to initiate the study of
responsible emergent multi-agent behavior, bridging Responsible AI and multi-
agent learning to better understand and shape emergent phenomena in multi-
agent systems. In doing so, I introduce several novel methods and improvements
to multi-agent learning algorithms, propose novel ways of measuring and
analyzing emergent phenomena, and investigate their benefits across a range of
multi-agent problem domains.

With respect to the core research areas outlined in the previous section, my
contributions can be enumerated as follows:

###### Interpretability

In the pursuit of interpretability, I introduce methods to better understand
emergent multi-agent behavior at both a low-level, by examining agent action
selection and behavioral cues, and at a high-level, by deriving concept-based
explanations that are more amenable to human understanding.

First, at the low-level, I examine the extent to which implicit communication
aides coordination in multi-agent populations. To accurately model the
conditions under which coordination and communication emerges naturally, I
prioritize decentralized multi-agent learning and introduce novel algorithms
that enable multi-agent teams to learn to coordinate from scratch in difficult
sparse-reward environments (where decentralized learning typically fails).
Specifically, I introduce Curriculum-Driven Deep Deterministic Policy
Gradients (CD-DDPG) as a policy learning method that combines environment
shaping and behavioral curricula. I then compare the highly-coordinated
strategies learned by CD-DDPG agents to those of lesser-skilled agents; and
introduce a method of position-based social influence to measure the exchange
of implicit information between agents. Results of this study show that agents
trained with CD-DDPG exchange almost three times more information on average,
compared to other less-coordinated strategies This shows that agents trained
with our method learn to rely heavily on the exchange of implicit signals as a
means to coordinating in a sophisticated manner (and outperforming other
strategies).

In sum, my contributions in this area are as follows:

  1. 1.

I highlight the importance of studying implicit signals as a form of emergent
communication.

  2. 2.

I introduce a curriculum-driven learning strategy, Curriculum-Driven DDPG,
that enables cooperative agents to solve difficult coordination tasks with
sparse reward.

  3. 3.

I show that, using this strategy, agents learn strong coordination strategies
that significantly outperforming sophisticated analytical and learned methods.

  4. 4.

I examine the use of implicit signals in emergent multi-agent coordination
through position-based social influence and find that agents trained with my
strategy exchange up three times more information per time-step on average
than competing methods.

Next, with the goal of understanding emergent multi-agent behaviors at a
higher-level, I examine the intersection of multi-agent learning and concept-
based interpretability. I introduce an intrinsically-interpretable, concept-
based policy architecture for multi-agent learning—the Concept Bottleneck
Policy (CBP)—that makes multi-agent decision-making immediately transparent by
distilling each agent’s decisions into a set of human-understandable concepts.
The CBP architecture forces an agent to make decisions by first predicting an
intermediate set of human-understandable concepts, then using those concepts
to select actions. In turn, agents reveal the environmental and inter-agent
factors influencing each of their actions.

This method unlocks a novel class of techniques for understanding emergent
multi-agent behavior. By conditioning each agent’s actions on its own concepts
from construction, CBPs support behavioral analysis via concept intervention.
Specifically, it is possible to perform interventions over an individual
agent’s CBP, examine its impact on performance (with respect to rewards,
actions, environment features, etc), and derive insights into key aspects of
the emergent behavior of the larger multi-agent system. I perform this
analysis over multi-agent teams in a range of domains, including cooperative
environments—where intervention can be used to identify coordination from
independent action, expose inter-agent factors that drive coordination, and
even diagnose common failure modes such as lazy agents—and mixed-motive social
dilemmas—where intervention unlocks our ability to examine inter-agent social
dynamics (e.g., exploitation, public resource sharing). Finally, I show that
CBPs perform comparably to non-concept based policies, thus achieving
interpretability without sacrificing performance

In sum, my contributions in this area are as follows:

  1. 1.

I introduce Concept Bottleneck Policies as an interpretable, concept-based
architecture for multi-agent reinforcement learning.

  2. 2.

I introduce a suite of novel techniques for multi-agent behavioral
understanding that leverage concept intervention and graph learning.

  3. 3.

I show that CBPs can match the performance of non-concept-based network
architectures.

###### Fairness

In the pursuit of fairness, I examine algorithmic fairness in the context of
multi-agent learning and develop the connective tissue needed to understand
fairness in cooperative multi-agent settings. I begin with a study of emergent
behavior amongst cooperative multi-agent teams that are trained under mutual
reward. Initial experiments suggest that mutual reward, though crucial for
learning coordination, is not enough to incentivize fair emergent
coordination. Specifically, I find that naive, unconstrained maximization of
mutual reward yields a symmetry-breaking form of role assignment that in turn
creates unfair individual outcomes for cooperative teammates.

I introduce a novel measure of fairness for multi-agent learning settings—team
fairness—that is able to capture this phenomenon quantitatively. Team fairness
is a group-based fairness measure, inspired by demographic parity [50, 54],
that requires the distribution of a team’s reward to be equitable across
sensitive groups. Next, to incorporate team fairness into policy learning, I
introduce a novel multi-agent learning strategy—Fairness through Equivariance
(Fair-E). Fair-E enforces team fairness during policy optimization by
transforming the team’s joint policy into an equivariant map and achieves
provably fair reward distributions under assumptions of agent homogeneity.

Despite achieving fair outcomes, Fair-E represents a binary switch—one can
either choose fairness (at the expense of utility) or utility (at the expense
of fairness). In many cases, however, it is advantageous to modulate between
fairness and utility. To this end, I also introduce a soft-constraint version
of Fair-E that incentivizes equivariance through regularization: Fairness
through Equivariance Regularization (Fair-ER. With Fair-ER, it is possible to
tune fairness constraints over multi-agent policies by adjusting the weight of
equivariance regularization. Empirically, Fair-ER reaches higher levels of
utility than Fair-E while achieving fairer outcomes than non-equivariant
policy learning.

Finally, as in both prediction-based settings [38, 225] and in traditional
multi-agent variants of fairness [145, 113], it is important to understand the
“cost" of fairness. I present novel findings regarding the fairness-utility
trade-off for cooperative multi-agent settings, showing that the magnitude of
the trade-off depends on the skill level of the multi-agent team. When agent
skill is high (making the task easier to solve), fairness comes with no trade-
off in utility, but as skill decreases (making the task more difficult), gains
in team fairness are increasingly offset by decreases in team utility.

In sum, my contributions in this area are as follows:

  1. 1.

I show that mutual reward is critical to multi-agent coordination.
Experimentally, agents trained with mutual reward learn to coordinate
effectively, whereas agents trained with individual reward do not. Despite
this, the agents learn coordination strategies that are unfair with respect to
individual agent outcomes.

  2. 2.

I introduce team fairness as a group-based fairness measure for multi-agent
teams that requires equitable reward distributions across sensitive groups.

  3. 3.

I introduce Fairness through Equivariance (Fair-E), a novel multi-agent
strategy leveraging equivariant policy learning. Fair-E achieves provably fair
outcomes for individual members of a cooperative team.

  4. 4.

I introduce Fairness through Equivariance Regularization (Fair-ER) as a soft-
constraint version of Fair-E. Fair-ER reaches higher levels of utility than
Fair-E while achieving fairer outcomes than non-equivariant learning.

  5. 5.

I present novel findings regarding the fairness-utility trade-off for
cooperative settings, showing that the magnitude of the trade-off depends on
agent skill—when agent skill is high, fairness comes for free; whereas with
lower skill levels, fairness is increasingly expensive.

###### Robustness

Finally, in the pursuit of robustness, I examine emergent phenomena within
search-based multi-agent learning algorithms like AlphaZero. As mentioned
previously, recent studies have shown that, in addition to positive emergent
phenomena like Move 37, there are may negative phenomena hidden within
AlphaZero’s vast neural network backbone. For example, studies leveraging
adversarial game-play have shown that AlphaZero is surprisingly susceptible to
minor perturbations in opponent behavior [108] and can be exploited to lose
games that could be easily won by amateur human players.

To better understand AlphaZero’s hidden failure modes, I conduct a thorough
analysis of AlphaZero’s gameplay in solved board games. This examination
reveals multiple phenomena that underlie AlphaZero’s documented failure modes.
First, despite learning to play a game optimally within its search process,
AlphaZero’s policy network and value function are far from optimal themselves.
This reveals an interesting tension between learning and search: search is
necessary to fight the combinatorial exploration problem of complex games, but
also offers neural networks a crutch that leads to inadequate generalization.
Next, I identify a novel emergent phenomenon, policy-value misalignment, in
which AlphaZero’s policy and value predictions contradict each other. This
misalignment is a direct consequence of AlphaZero’s objective, which includes
separate terms for policy and value error, but no constraint on their
consistency. I introduce an information-theoretic definition of policy-value
misalignment and use it to quantify AlphaZero’s misalignment. Lastly, I find
evidence of inconsistency within AlphaZero’s value function with respect to
symmetries in the environment. As a result, AlphaZero’s value predictions
generalize poorly to infrequently-visited and unseen states. Crucially, these
phenomena are masked by search and exist even when AlphaZero plays optimally
within its search process. This work therefore demonstrates that, though
search allows AlphaZero to achieve unprecedented scale and performance, it
also hides deficiencies in its learned components.

To address these issues, I propose two modifications to AlphaZero aimed
directly at policy-value alignment and value function consistency. First, I
introduce Value-Informed Selection (VIS): a modified action-selection rule in
which action probabilities are computed using a one-step lookahead with
AlphaZero’s value network. VIS then alternates stochastically between this
value action selection rule and AlphaZero’s standard policy (which is derived
from search probabilities). During training, this forces alignment between
AlphaZero’s policy and value predictions. Next, I introduce Value-Informed
Symmetric Augmentation (VISA): a data augmentation technique that takes into
account uncertainty in AlphaZero’s value network. Unlike data augmentation
techniques that naively add states to a network’s replay buffer, VISA
considers symmetric transformations of a given state and stores only the
transformed state whose value differs most from the network’s value estimate
for the original, un-transformed state.

VISA and VIS can improve both policy-value alignment and value robustness in
AlphaZero simultaneously. I refer to this joint method as VISA-VIS. In
experiments across a variety of symmetric, two-player zero-sum games, VISA-VIS
reduces policy-value misalignment by up to 76%, reduces value generalization
error by up to 50%, and reduces average value prediction error by up to 55%;
as compared to AlphaZero.

In sum, my contributions in this area are as follows:

  1. 1.

I systematically study AlphaZero and identify multiple emergent phenomena that
are masked by search.

  2. 2.

I define an information-theoretic measure of policy-value misalignment.

  3. 3.

I propose Value-Informed Selection (VIS): a modified action-selection rule for
AlphaZero that forces alignment between policy and value predictions.

  4. 4.

I propose Value-Informed Symmetric Augmentation (VISA): a data augmentation
technique that leverages symmetry and value function uncertainty to learn a
more consistent value network.

  5. 5.

I introduce a new method, VISA-VIS, that combines VIS and VISA into a single
algorithm. Experimentally, I show that VISA-VIS improves the quality of
AlphaZero’s policy and value networks, and significantly reduces policy-value
misalignment.

####  1.4 Overall Structure

This dissertation is organized in three parts, each addressing one of the
outstanding challenges outlined in the preceding section. The core
contributions are preceded by a review of background material. Chapter 2
reviews material in each of the key areas presented throughout the thesis.
There exists a setup of the reinforcement learning (RL) problem and discussion
of the RL and multi-agent RL algorithms that provide a foundation for this
work. Then, a short introduction to notation and definitions for related areas
of machine learning is provided—namely, interpretability and fairness—that
will be incorporated into the MARL framework. Finally, background on the
multi-agent environments used in our experiments is provided.

Part I initiates a study of interpretability in the context of emergent multi-
agent behavior. Chapter 3, addresses low-level interpretability through
emergent implicit communication in multi-agent RL. Specifically, this work
highlights the importance of recognizing communication as a spectrum—from
fine-grained behavioral cues that are exchanged implicitly to rich,
compositional protocols that are exchanged explicitly—and show that agents
learn to rely upon implicit signals from their teammates when solving
difficult coordination tasks. In turn, the volume of implicit information
exchange is indicative of the strength of their coordination. Chapter 4,
targets high-level, concept-based explanations of emergent multi-agent
behavior and introduces an intrinsically interpretable policy architecture for
MARL agents that conditions each agent’s policy on a set of human-
understandable concepts. By conditioning on understandable concepts, this
method enables post-hoc behavioral analysis via concept intervention. Concept
intervention is then shown to reliably detect emergent coordination, expose
sub-optimal behavior (e.g., lazy agents), identify complex inter-agent social
dynamics, and strategic behavior as they emerge throughout training.

Part II connects algorithmic fairness to cooperative multi-agent settings.
There we provide formal definitions of fairness for multi-agent teams,
introducing a group-based fairness measure that requires equitable reward
distributions across sensitive groups. Then, we introduce a novel actor-critic
algorithm for learning provably fair multi-agent policies and conduct an
empirical analysis of fairness in cooperative games. Finally, we revisit the
canonical fairness-utility trade-off for multi-agent learning and show that,
in cooperative settings, the magnitude of this trade-off is largely dependent
on the relative skills of each agent in the team.

Part III addresses robustness in large-scale multi-agent systems. In
particular, conduct a thorough analysis of AlphaZero’s failure modes is
conducted, using board games with enumerable state spaces to gain a holistic
picture of AlphaZero’s behavior. Two issues are found at the root of
AlphaZero’s brittleness. First, AlphaZero’s policy and value functions are
misaligned in many states—i.e. AlphaZero’s policy network selects a winning
action, yet its value network estimates that AlphaZero is losing (or vice
versa). This is possible because AlphaZero employs a joint objective (weighted
sum) that includes separate terms promoting action and value accuracy, but
does not enforce that they are consistent. Further inconsistency within
AlphaZero’s value function itself, which causes it to generalize poorly to
infrequently visited or unseen states. Using these empirical findings as
motivation, we derive a novel extension of AlphaZero that combines
uncertainty-informed value estimation and improved exploration. Together, this
algorithm aligns AlphaZero’s policy and value predictions. Experimentally, our
algorithm greatly improves AlphaZero’s robustness.

###  Chapter 2 Background

####  2.1 Reinforcement Learning

Reinforcement Learning (RL) refers to a class of sequential decision-making
problems in which an agent resides in an environment and interacts with the
environment by performing actions over the course of some time horizon. The
environment responds to agent actions by transitioning from its current state
to a new state—as governed by a (possibly unknown) transition function—and
providing a reward that quantifies the strength or weakness of the agent’s
action. The goal of the agent is to maximize the cumulative reward it obtains
over time.

#####  2.1.1 Problem Setup

Under full-observability, RL problems are formalized with a Markov Decision
Process (MDP). An MDP $\mathcal{M}$ is a tuple $\mathcal{M}=\\{S,A,T,R\\}$
consisting of a state-space $\mathcal{S}$, action-space $A$, transition
function $T$, and reward function $R$, respectively. The state-space $S$
defines the set of all environmental states that an agent may encounter. The
action-space $A$ defines the set of possible actions an agent can take. Both
states and actions may be discrete or continuous. The transition function $T$
defines the probability $p(s^{\prime}\mid s,a)$ of transitioning from a state
$s\in S$ to a new state $s^{\prime}\in S$ after taking an action $a\in A$.
Finally, the reward function $R$ defines the single-step reward $r(s,a)$ that
an agent receives for taking the action $a$ in state $s$.

An agent’s decision-making is dictated by a policy, which is a function $\pi$
mapping states to actions. Policies can be either deterministic, where
$\pi(s)=a$ (deterministic policies may also be denoted $\mu$), or stochastic,
wherein $\pi$ defines a conditional probability distribution $\pi(a\mid
s)=P(A=a\mid S=s)$. Using these ingredients, the agent-environment interaction
more formally as follows: for each time-step $t$, the agent observes a state
$s_{t}$, selects an action $a_{t}\sim\pi(a\mid s_{t})$, transitions to a new
state $s_{t+1}$ with probability $p(s_{t+1}\mid s_{t},a_{t})$, and receives a
reward $r_{t}=r(s_{t},a_{t})$. For a time horizon of $T$ steps, this produces
a $T$-step trajectory:

$\tau=\\{s_{1},a_{1},...,s_{T},a_{T}\\}$ (2.1)

with probability:

$\displaystyle p(\tau)$ $\displaystyle=p(s_{1},a_{1},...,s_{T},a_{T})$ (2.2)
$\displaystyle=p_{\emptyset}(s_{1})\prod_{t=1}^{T}\pi_{\theta}(a_{t}\mid
s_{t})p(s_{t+1}\mid s_{t},a_{t})$ (2.3)

where the initial state $s_{1}$ is drawn from a special start-state
distribution $p_{\emptyset}$.

###### Value Functions

Recall that the goal of an RL agent is to maximize the cumulative reward it
obtains over time. It is therefore important for an agent to compute or
estimate the reward that it can expect to receive in the future. This quantity
is known as the return (denoted $G$) and it can be computed for any time-step
$t$, as the total sum of discounted rewards going forward:

$G_{t}=r_{t}+\gamma
r_{t+1}+\gamma^{2}r_{t+2}+\cdots=\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}$ (2.4)

where $\gamma\in[0,1]$ is a discount factor for future rewards.

From $G_{t}$, we define two functions that quantify the value of a state (or
state-action pair) with respect to expected reward. The state-value function
$V^{\pi}(s)$ for a state $s_{t}$ defines the expected return of an agent,
starting from $s_{t}$ and following a specific policy $\pi$ thereafter:

$V^{\pi}(s_{t})=\mathbb{E}[G_{t}\mid S_{t}=s_{t}]$ (2.5)

and the action-value function (or Q-function) $Q^{\pi}(s_{t},a_{t})$ defines
the expected return of an agent, after taking the action $a_{t}$ from $s_{t}$,
and following the policy $\pi$ thereafter:

$Q^{\pi}(s_{t},a_{t})=\mathbb{E}[G_{t}\mid S_{t}=s_{t},A_{t}=a_{t}]$ (2.6)

Since $V^{\pi}$ and $Q^{\pi}$ are defined with respect to a specific policy
$\pi$ (hence the superscript), $\pi$ can recover $V^{\pi}$ from $Q^{\pi}$ as
follows:

$V^{\pi}(s)=\sum_{a\in A}Q^{\pi}(s,a)\pi(a\mid s)$ (2.7)

Another useful quantity is the difference between $Q^{\pi}(s,a)$ and
$V^{\pi}(s)$:

$A^{\pi}(s,a)=Q^{\pi}(s,a)-V^{\pi}(s)$ (2.8)

which is known as the advantage function. Intuitively, $A^{\pi}(s,a)$ tells us
how strong of an action $a$ is relative all actions available from $s$.

Importantly, using Equation 2.4, both the state and state-action value
functions can be decomposed into a sum of the immediate reward for the current
time-step and the discounted future values. For $V^{\pi}(s_{t})$, this is done
as follows:

$\displaystyle V^{\pi}(s_{t})$ $\displaystyle=\mathbb{E}[G_{t}\mid
S_{t}=s_{t}]$ (2.9) $\displaystyle=\mathbb{E}[r_{t}+\gamma
r_{t+1}+\gamma^{2}r_{t+2}+\cdots\mid S_{t}=s_{t}]$ (2.10)
$\displaystyle=\mathbb{E}[r_{t}+\gamma(r_{t+1}+\gamma r_{t+2}+\cdots)\mid
S_{t}=s_{t}]$ (2.11) $\displaystyle=\mathbb{E}[r_{t}+\gamma G_{t+1}\mid
S_{t}=s_{t}]$ (2.12) $\displaystyle=\mathbb{E}[r_{t}+\gamma
V^{\pi}(S_{t+1})\mid S_{t}=s_{t}]$ (2.13)

and similarly for $Q^{\pi}(s_{t},a_{t})$ we have:

$\displaystyle Q^{\pi}(s_{t},a_{t})$ $\displaystyle=\mathbb{E}[G_{t}\mid
S_{t}=s_{t},A_{t}=a_{t}]$ (2.14) $\displaystyle=\mathbb{E}[r_{t}+\gamma
V^{\pi}(S_{t+1})\mid S_{t}=s_{t},A_{t}=a_{t}]$ (2.15)
$\displaystyle=\mathbb{E}[r_{t}+\gamma\mathbb{E}_{a\sim\pi}Q^{\pi}(S_{t+1},a_{t})\mid
S_{t}=s_{t},A_{t}=a_{t}]$ (2.16)

Equation 2.13 and Equation 2.16 are referred to as the Bellman equations.

The recursive nature of the Bellman equations are key to solving the RL
problem, as it means that it is possible to either (i) compute $V^{\pi}$ and
$Q^{\pi}$ directly (if a model of the environment is available) or (ii)
estimate them from experience (if such a model is not available). In both
cases, once the value function is known (or learned), a policy can be derived
by acting greedily with respect to the value function (i.e. taking the
highest-value action from every state).

#####  2.1.2 Value-based Learning

In complex environments, it is often the case that a model—i.e. the transition
probabilities $T$ and rewards $R$ specified by the environment—is unavailable.
In such cases, $V^{\pi}$ and/or $Q^{\pi}$ must be computed in a model-free
manner, by collecting an agent’s interactions with the environment
(exploration) and learning from that experience. Value-based learning refers
to a class of algorithms that learn a value function from experience. Here we
review a few model-free methods that our key to our work.

###### Temporal-Difference Learning

Temporal-difference (TD) learning is the canonical algorithm for model-free,
value-based learning. TD learning is derived from the following key insight:
for a given value $V(s_{t})$, it is possible to create a slightly better
estimate of $s_{t}$’s true value using a one-step look-ahead. That look-ahead
is computed as the discounted sum of the immediate reward $r_{t+1}$ received
when exiting $s_{t}$ and the value $V(s_{t+1})$ of the subsequent state
$s_{t+1}$ as follows:

$r_{t+1}+\gamma V(s_{t+1})$ (2.17)

where $\gamma$ is a discount factor (as in Equation 2.4). This look-ahead is
known as the TD target. Importantly, the TD target can be computed via
bootstrapping. Namely, the value estimate $V(s_{t})$ can be computed using an
existing estimate of $V(s_{t+1})$, rather than computing $V(s_{t+1})$
recursively down to some terminal state. Updating the TD target with existing
estimates means that TD learning can operate over partial episodes of
experience (as opposed to requiring entire trajectories).

Together, these insights motivate the following value function update rule:

$V(s_{t})\leftarrow V(s_{t})+\alpha(r_{t+1}+\gamma V(s_{t+1})-V(s_{t}))$
(2.18)

where $\alpha$ is akin to a learning rate hyperparameter dictating how rapidly
existing estimates are updated. The difference between the TD target
$r_{t+1}+\gamma V(s_{t+1})$ and current value estimate $V(s_{t})$ is known as
the TD error. Similarly for the action-value function, we have:

$Q(s_{t},a_{t})\leftarrow Q(s_{t},a_{t})+\alpha(r_{t+1}+\gamma
Q(s_{t-1},a_{t-1})-Q(s_{t},a_{t}))$ (2.19)

This simple update rule is the basis for nearly every value-based RL
algorithm.

###### Q-Learning

Q-learning [211] is an off-policy algorithm for finding an optimal policy via
TD learning. Q-learning first learns the optimal action-value function
$Q^{*}(s,a)$ using the update rule outlined in Equation 2.19, then recovers
the optimal policy as $\pi^{*}(a|s)=\operatorname*{arg\,max}_{a}Q^{*}(s,a)$.
More concretely, starting from an initial $Q$ (random or all zeros),
Q-learning iteratively performs the following steps until convergence:

  1. 1.

At time-step $t=0$, initialize a trajectory starting from a state $s_{0}$.

  2. 2.

Select an action $a_{t}=\operatorname*{arg\,max}_{a\in A}Q(s_{t},a)$.

  3. 3.

After applying $a_{t}$, collect the reward $r_{t+1}$ and next state $s_{t+1}$
returned by the environment.

  4. 4.

Update $Q$ using Equation 2.19.

  5. 5.

Increment $t$ and repeat steps 2-4 until the trajectory ends.

An exploration strategy such as $\epsilon$-greedy action selection is commonly
used in place of greedy action selection in step (2) to ensure a diverse set
of actions are used during training.

###### Deep Q-Learning

Though Q-learning is effective for simple environments, computing $Q^{*}(s,a)$
becomes computationally infeasible as the size of the environment’s state and
action spaces increases (and is impossible for continuous states and actions).
The Deep Q-Network (DQN) [137, 138] was introduced to circumvent these issues
by using neural networks to approximate $Q$. Specifically, DQN defines a
neural network function $Q_{\omega}$ with parameters $\omega$ and optimizes it
with the following TD error-inspired loss:

$\mathcal{L}(\theta)=\mathop{\mathbb{E}}_{s,a,r,s^{\prime}}\big{[}(Q_{\omega}(s_{t},a_{t})-y_{t})^{2}\big{]}$
(2.20)

where:

$y_{t}=r(s_{t},a_{t})+Q_{\omega}(s_{t+1},\pi(s_{t+1}))$

Tuples of experience ($s_{t}$, $a_{t}$, $r_{t}$, $s_{t+1}$) are collected
throughout training by a separate exploration policy, stored in a replay
buffer $\mathcal{D}=\\{(s_{t},a_{t},r_{t},s_{t+1})\\}_{i=1}^{N}$, and sampled
uniformly at random when computing Equation 2.20. In practice, the use of a
replay buffer is vital to the performance of DQN, as it improves data
efficiency and reduces correlations between sequential data points.

Also important to the stability of DQN training (and most value-based learning
methods) is the use of a target network. A target network is copy
$Q^{\prime}_{\omega}(s,a)$ of the original Q-network $Q_{\omega}(s,a)$ that is
in a separate process such that the copied parameters $\omega^{\prime}$ trail
those of the original network:

$\omega^{\prime}\leftarrow\tau\omega+(1-\tau)\omega^{\prime}$

where $\tau<<1$. The target values provided by $Q^{\prime}_{\omega}(s,a)$ are
constrained to change slowly, which prevents $Q_{\omega}$ from computing
Q-values as it is updating. This in turn improves the stability.

#####  2.1.3 Policy Gradient Methods

Policy gradient methods are a class of policy-based RL solutions [196]. Unlike
value-based methods, which derive and improve a policy implicitly through an
approximate value function, policy gradient methods assume the policy itself
is a function $\pi_{\phi}$ with parameters $\phi$ and seek to optimize this
policy directly. Policy-based methods have an advantage over value-based
methods in continuous action spaces, as they avoid computing a max over
actions; though they pay for this convenience with efficiency, suffering from
higher variance and, in turn, slower convergence. Below is an introduction top
policy gradients and a review of prior methods that are key to this work.

###### The Gradient of a Policy

Let $r(\tau)$ represent the cumulative reward the agent receives over a
trajectory $\tau=\\{s_{1},a_{1},...,s_{T},a_{T}\\}$:

$r(\tau)=\sum_{t=1}^{T}r(s_{t},a_{t})$

We can use this to write the RL objective (reward maximization) as:

$J(\phi)=\mathop{\mathbb{E}}_{\tau\sim
p_{\phi}(\tau)}\bigg{[}\sum_{t}r(\tau)\bigg{]}=\int\pi_{\phi}(\tau)r(\tau)d\tau$
(2.21)

To improve $\pi_{\phi}$, the gradient of Equation 2.21 is computed with
respect to parameters $\phi$:

$\nabla_{\phi}J(\phi)=\int\nabla_{\phi}\pi_{\phi}(\tau)r(\tau)d\tau$ (2.22)

and ascend accordingly:

$\phi\leftarrow\phi+\alpha\nabla_{\phi}J(\phi)$ (2.23)

Though gradient ascent is simple in principle, computing
$\nabla_{\phi}J(\phi)$ is difficult in practice, as $\pi_{\phi}(\tau)$ can
contain a product of many terms (depending on trajectory length). Moreover,
$\pi_{\phi}(\tau)$ includes terms that may not be known a priori, such as the
transition distribution $p(s_{t+1}|s_{t},a_{t})$. We must therefore construct
an objective that does not depend on these terms explicitly. Fortunately, the
policy gradient theorem allows us to do just that.

###### Policy Gradient Theorem

For any policy $\pi_{\phi}(\tau)$ and any objective $J(\phi)$, we can write
the policy gradient as:

$\displaystyle\nabla_{\phi}J(\phi)$
$\displaystyle=\mathop{\mathbb{E}}_{\tau\sim\pi_{\phi}(\tau)}\bigg{[}\bigg{(}\sum_{t}\nabla_{\phi}\textrm{log}\pi_{\phi}(a_{t}|s_{t})\bigg{)}\bigg{(}\sum_{t}r(s_{t},a_{t})\bigg{)}\bigg{]}$
(2.24)
$\displaystyle\approx\frac{1}{N}\sum_{i=1}^{N}\bigg{(}\sum_{t=1}^{T}\nabla_{\phi}\textrm{log}\pi_{\phi}(a_{i,t}|s_{i,t})\bigg{)}\bigg{(}\sum_{t=1}^{T}r(s_{i,t},a_{i,t})\bigg{)}$
(2.25)

This theorem alone enables the construction of a theoretically sound policy
gradient method. In fact, the REINFORCE algorithm [214, 213] does just
that—the method generates samples trajectories from the current policy
$\pi_{\phi}(a_{t}|s_{t})$, computes the gradient using Equation 2.24, and
updates the parameters $\phi$ of the policy according to Equation 2.23.

Note: The summation over reward in Equation 2.24 starts at time-step $t=1$,
even when the summation over policy $\pi_{\phi}$ is at a time-step $t>1$. In
reality, the policy at time $t^{\prime}$ cannot effect the reward at time $t$
when $t<t^{\prime}$. To account for this, the policy gradient
$\nabla_{\phi}J(\phi)$ is often rewritten as:

$\displaystyle\nabla_{\phi}J(\phi)$
$\displaystyle\approx\frac{1}{N}\sum_{i=1}^{N}\bigg{(}\sum_{t=1}^{T}\nabla_{\phi}\textrm{log}\pi_{\phi}(a_{i,t}|s_{i,t})\bigg{)}\bigg{(}\sum_{t^{\prime}=t}^{T}r(s_{i,t^{\prime}},a_{i,t^{\prime}})\bigg{)}$
(2.26)
$\displaystyle\approx\frac{1}{N}\sum_{i=1}^{N}\bigg{(}\sum_{t=1}^{T}\nabla_{\phi}\textrm{log}\pi_{\phi}(a_{i,t}|s_{i,t})\bigg{)}Q_{i,t}^{\pi_{\phi}}(s_{i,t},a_{i,t})$
(2.27)

where the summation of “reward-to-go", conditioned on actions, is equivalent
to the action-value function in Equation 2.6.

###### Baselines

Though simple, one drawback of REINFORCE is that it results in a high-variance
gradient estimator, which leads to inefficient learning in practice. Due to
randomness, the return of each trajectory may vary drastically episode-to-
episode. By estimating the gradient with finite samples, it is possible to
receive a different gradient estimate for every set of samples. This reduces
the smoothness of the gradient path, in turn increasing the amount of time
needed to converge. The problem of variance is inherent to all policy gradient
methods and there exist many extensions of this basic idea that specifically
target the amount of variance in the learning process.

The most prominent variance reduction technique is to subtract some quantity
from cumulative reward. For a single trajectory $\tau$, we have:

$\nabla_{\phi}J(\phi)\approx\frac{1}{N}\sum_{i=1}^{N}\nabla_{\phi}\textrm{log}\pi_{\phi}(\tau)[r(\tau)-b]$
(2.28)

The quantity $b$ is known as a baseline and allows us to change the amount of
variance present in the system while keeping the same gradient in expectation.
The baseline can be chosen strategically to maximize variance reduction while
maintaining the direction of the gradient. For example, a popular choice is
$b(s_{t})=V^{\pi_{\phi}}(s_{t})$, which results in the modified objective:

$\displaystyle\nabla_{\phi}J(\phi)$
$\displaystyle\approx\frac{1}{N}\sum_{i=1}^{N}\bigg{(}\sum_{t=1}^{T}\nabla_{\phi}\textrm{log}\pi_{\phi}(a_{i,t}|s_{i,t})\bigg{)}\bigg{(}Q_{i,t}^{\pi_{\phi}}(s_{i,t},a_{i,t})-V_{i,t}^{\pi_{\phi}}(s_{i,t})\bigg{)}$
(2.29)
$\displaystyle\approx\frac{1}{N}\sum_{i=1}^{N}\bigg{(}\sum_{t=1}^{T}\nabla_{\phi}\textrm{log}\pi_{\phi}(a_{i,t}|s_{i,t})\bigg{)}A_{i,t}^{\pi_{\phi}}(s_{i,t},a_{i,t})$
(2.30)

where the difference $Q^{\pi_{\phi}}(s_{t},a_{t})-V^{\pi_{\phi}}(s_{t})$ is
equivalent to the advantage function $A^{\pi_{\phi}}(s_{t},a_{t})$ from
Equation 2.8.

###### Proximal Policy Optimization

Proximal Policy Optimization (PPO) [177] is an on-policy, policy gradient
learning method that streamlines recent advances in trust-region based policy
optimization [175]. PPO iteratively updates the parameters $\phi$ of an
agent’s policy $\pi_{\phi}$ with the respect to the following clipped
surrogate objective:

$L_{\textrm{CLIP}}(\phi)=\underset{a,s\sim\pi_{\phi_{\textrm{old}}}}{\mathbb{E}}\bigg{[}\min\bigg{(}\frac{\pi_{\phi}(a|s)}{\pi_{\phi_{\textrm{old}}}}\hat{A}^{\pi_{\textrm{old}}},\textrm{clip}\bigg{(}\frac{\pi_{\phi}(a|s)}{\pi_{\phi_{\textrm{old}}}}\hat{A}^{\pi_{\textrm{old}}},1-\epsilon,1+\epsilon\bigg{)}\hat{A}^{\pi_{\textrm{old}}}\bigg{)}\bigg{]}$

where $\epsilon$ regulates the step size of policy updates (from
$\phi_{\textrm{old}}$ to $\phi$) and $\hat{A}^{\pi_{\textrm{old}}}$ is an
estimate of the agent’s advantage function (via generalized advantage
estimation [176]). In practice, PPO benefits from two additional objectives:

  1. 1.

An error term on value estimation, which we take to be the mean-squared error,
$(V_{\omega}(s)-V^{\textrm{targ}}_{\omega^{\prime}}(s))^{2}$, between value
estimates from the agent’s value function $V_{\omega}$ (with parameters
$\omega$) and a target value function $V^{\textrm{targ}}_{\omega^{\prime}}$.
Typically, parameter sharing between the policy and value functions is allowed
(i.e. $\phi=\omega$).

  2. 2.

An entropy bonus $H(\pi_{\phi}(\cdot|s))$ over the agent’s policy that
encourages exploration.

Altogether this yields the following three-pronged PPO objective:

$L_{\textrm{PPO}}(\phi,\omega)=L_{\textrm{CLIP}}(\phi)-\alpha_{1}(V_{\omega}-V^{\textrm{targ}}_{\omega^{\prime}})^{2}+\alpha_{2}H(\pi_{\phi}(\cdot|s))$
(2.31)

where $\alpha_{1}$ and $\alpha_{2}$ are coefficients weighing the relative
importance of the value error term and entropy bonus term, respectively.
Recently, PPO has shown strong performance in cooperative multi-agent settings
[43, 221].

#####  2.1.4 Actor-Critic Algorithms

Both Equation 2.27 and Equation 2.30 offer powerful ways to estimate the
gradient while also reducing variance. In reality, however, we often do not
have access to the true $Q^{\pi}(s,a)$ or $V^{\pi}(s)$ and must approximate
them as well. Actor-critic methods, combining the benefits of value-based and
policy-based RL methods, provide a mechanism to do so. In actor-critic
methods, an actor function controls the policy $\pi_{\phi}$, taking actions in
the environment. A critic function performs policy evaluation, fitting an
approximate value function (either $Q_{\omega}(s,a)$ or $V_{\omega}(s)$) and
using it to evaluate the actor’s actions. The actor then updates $\phi$ in the
direction suggested by the critic. This back-and-forth procedure yields an
approximate policy gradient—adjust $\pi_{\phi}$ in the direction that will get
more reward, according to the critic.

###### Deep Deterministic Policy Gradients

Deep Deterministic Policy Gradients (DDPG) is an off-policy actor-critic
algorithm for policy gradient learning in continuous action spaces [120]. DDPG
learns an optimal deterministic policy $\mu_{\phi}$ with respect to the RL
objective:

$J(\phi)=\mathbb{E}_{s}[Q_{\omega}(s,a)\mid_{s=s_{t},a=\mu_{\phi}(s_{t})}]$
(2.32)

by performing gradient ascent over the following gradient:

$\nabla_{\phi}J(\phi)=\mathbb{E}_{s}[\nabla_{a}Q_{\omega}(s,a)\mid_{s=s_{t},a=\mu(s_{t})}\nabla_{\phi}\mu(s)\mid_{s=s_{t}}]$
(2.33)

where $\phi$ and $\omega$ are parameters associated with $\mu$ and $Q$,
respectively. Equation 2.33 is a consequence of the deterministic policy
gradient theorem [182]. For critic updates, DDPG minimizes the loss function:

$L(\omega)=\underset{s,a,r,s^{\prime}}{\mathbb{E}}\big{[}\big{(}Q_{\omega}(s,a)-(r(s,a)+\gamma
Q_{\omega}(s^{\prime},\mu_{\phi}(s^{\prime})))\big{)}^{2}\big{]}$ (2.34)

where ($s,a,r,s^{\prime}$) are transition tuples sampled from a replay buffer
and $\gamma{\in}[0,1]$ is a scalar discount factor. In this work, agents learn
in a decentralized manner, each performing DDPG updates individually.

#####  2.1.5 Multi-Agent Settings

In this section, we review a few notational and algorithmic considerations for
RL in multi-agent settings.

###### Markov Games

A Markov game is a multi-agent extension of the Markov decision process (MDP)
formalism [122]. For $n$ agents, it is represented by a state space $S$, joint
action space $\bm{A}=\\{A_{1},...,A_{n}\\}$, joint observation space
$\bm{O}=\\{O_{1},...,O_{n}\\}$, transition function
$T:S\times\bm{A}\rightarrow S$, and joint reward function $\bm{r}$. Following
multi-objective RL [230], we define a vectorial reward
$\bm{r}:S\times\bm{A}\rightarrow\mathbb{R}^{n}$ with each component $r_{i}$
representing agent $i$’s contribution to $\bm{r}$. Each agent $i$ is
initialized with a policy $\pi_{i}:O_{i}\rightarrow A$ (or deterministic
policy $\mu_{i}$) from which it selects actions and an action-value function
$Q_{i}:S\times A_{i}\rightarrow\mathbb{R}$ with which it judges the value of
state-action pairs. Following action selection, the environment transitions
from its current state $s_{t}$ to a new state $s_{t+1}$, as governed by $T$,
and produces a reward vector $\bm{r}_{t}$ indicating the strength or weakness
of the group’s decision-making. In the episodic case, this process continues
for a finite time horizon $T$, producing a trajectory
$\tau=(s_{1},\bm{a_{1}},...,s_{T-1},\bm{a_{T-1}},s_{T})$ with probability:

$P(\tau)=P_{\emptyset}(s_{1})\prod_{t=1}^{T}P(s_{t+1}\mid
s_{t},a_{t})\pi(a_{t}\mid s_{t})$ (2.35)

where $P_{\emptyset}$ is a special distribution specifying the likelihood of
each “start" state.

###### Decentralized vs. Centralized Learning

As discussed in Section 2.1.3, policy gradient methods are inherently
susceptible to high variance gradient updates. This variance problem is
exacerbated in multi-agent settings, as the environment (and thus the learning
problem) becomes increasingly non-stationary for each agent. For example,
consider an agent $i$ that, at some time $t$, selects an action $a_{i,t}$ from
some state $s_{t}$. In single-agent RL, the reward $r_{i,t}$ received by agent
$i$ is primarily a function of the quality of agent $i$’s decision-making from
$s_{t}$. In multi-agent settings, however, this is not always the case. In
separate trajectories, agent $i$ could select the same action $a_{i,t}$ from
$s_{t}$ and receive different rewards because one or many agents in the
environment changed their action selection. Since each agent runs its own
learning process and updates its policy quickly, this scenario can occur
frequently throughout training, to the detriment of learning stability.

To solve this problem, recent work has popularized centralized training,
decentralized execution (CTDE) training paradigms in which each agent receives
some information about the parameter updates of the other agents in the
environment during training [126, 57]. Here we present one such
technique—Multi-Agent DDPG (MADDPG) [126]—as a representative example.

###### Multi-Agent Deep Deterministic Policy Gradients

MADDPG a multi-agent extension of the DDPG algorithm from Section 2.1.4. Given
$N$ agents with policies
$\bm{\pi_{\phi}}=\\{\pi_{\phi_{1}},...,\pi_{\phi_{N}}\\}$ parameterized by
$\bm{\phi}=\\{\phi_{1},...,\phi_{N}\\}$, we can write a multi-agent variant of
the policy gradient as:

$\nabla_{\phi_{i}}J(\phi_{i})=\mathop{\mathbb{E}}_{\begin{subarray}{c}s_{t+1}\sim
p(s_{t+1}|s_{t},a_{t})\\\
a_{i}\sim\pi_{\phi_{i}}\end{subarray}}\bigg{[}\nabla_{\phi_{i}}\textrm{log}\pi_{\phi_{i}}(a_{i}|o_{i})Q^{\pi_{i}}(\bm{x},a_{1},...,a_{N})\bigg{]}$

where $Q^{\pi_{i}}$ is a centralized action-value function that receives state
information $\bm{x}$ and the actions of each agent as input. The state
information $\bm{x}=(o_{1},...,o_{N})$ consists of the observations of each
agent plus, in some cases, additional state from the environment. As in DDPG,
we can write the multi-agent objective in terms of deterministic policies
$\bm{\mu_{\phi}}=\\{\mu_{\phi_{1}},...,\mu_{\phi_{N}}\\}$:

$\nabla_{\phi_{i}}J(\phi_{i})=\mathop{\mathbb{E}}_{\begin{subarray}{c}s_{t+1}\sim
p(s_{t+1}|s_{t},a_{t})\\\
a_{i}\sim\mathcal{D}\end{subarray}}\bigg{[}\nabla_{\phi_{i}}\textrm{log}\mu_{\phi_{i}}(a_{i}|o_{i})\nabla_{a_{i}}Q^{\mu_{i}}(\bm{x},\mu_{\phi_{1}}(o_{1}),...,\mu_{\phi_{N}}(o_{N}))\bigg{]}$

and make use of a replay buffer
$\mathcal{D}=(\bm{x},\bm{x^{\prime}},a_{1},...,a_{N},r_{1},...,r_{N})$ and
target networks for both the actor ($\mu_{\phi_{i}}^{\prime}$) and the critic
($Q_{\omega}^{\mu_{i}^{\prime}}$). The critic is trained via Q-learning with
the objective:

$\mathcal{L}(\phi_{i})=\mathop{\mathbb{E}}_{\bm{x},a,r,\bm{x}^{\prime}}\big{[}(Q_{\omega}^{\mu_{i}}(\bm{x},\mu_{\phi_{1}}(o_{1}),...,\mu_{\phi_{N}}(o_{N}))-y)^{2}\big{]}$
(2.36)

where:

$y=r_{i}+(Q_{\omega}^{\mu_{i}^{\prime}}(\bm{x}^{\prime},\mu_{\phi_{1}}^{\prime}(o_{1}),...,\mu_{\phi_{N}}^{\prime}(o_{N})))$
(2.37)

In this work, however, we prioritize decentralized learning because it more
accurately that type of learning problem that agents will face when learning
alongside human counterparts.

#####  2.1.6 AlphaZero

AlphaZero is a hybrid algorithm that combines self-play RL and Monte-Carlo
Tree Search (MCTS). AlphaZero’s search and learning processes are reviewed
below, as both are crucial to understanding our method.

###### Setup

AlphaZero maintains a search tree in which each node is a state $s$ and each
edge $(s,a)$ represents taking an action $a$ from $s$. Each edge is described
by a tuple of statistics $\\{N(s,a),W(s,a),Q(s,a),P(s,a)\\}$, holding the
edge’s visit count, total action value, mean action value, and selection
probability, respectively. AlphaZero uses a two-headed neural network
$f_{\theta}$ with parameters $\theta$ to compute policy probabilities $\bm{p}$
and a value estimate $v$ for a state $s$ as follows:

$(\bm{p},v)=f_{\theta}(s)$ (2.38)

MCTS uses $f_{\theta}$ to evaluate states during the search process.

###### Search

In each state $s$, AlphaZero executes $n$ simulations of MCTS tree search. In
each simulation, MCTS traverses the game tree by selecting edges that
maximizes the upper confidence bound $Q(s,a)+U(s,a)$, where:

$U(s,a)=cP(s,a)\frac{\sqrt{\sum_{b}N(s,b)}}{1+N(s,a)}$ (2.39)

encourages the exploration of lesser-visited states (within the search tree);
and $c$ is a coefficient determining the level of exploration. When a leaf
node $s_{L}$ is encountered, it is expanded, evaluated by AlphaZero’s network
to produce $(\bm{p}_{L},v_{L})\sim f_{\theta}(s_{L})$, and initialized as
follows:

$N(s,a)=0,W(s,a)=0,Q(s,a)=0,P(s,a)=p_{L,a}$ (2.40)

Then, in a backward pass up the search tree, the statistics of each traversed
edge are updated as follows: $N(s,a)=N(s,a)+1$, $W(s,a)=W(s,a)+v_{L}$,
$Q(s,a)=W(s,a)/N(s,a)$.

###### Action Selection

After MCTS, AlphaZero constructs a policy $\bm{\pi}$, where the probability
$\pi(a\mid s)$ of selecting action $a$ from state $s$ is computed directly
from visitation counts:

$\pi(a\mid s)=\frac{N(s,a)^{1/\tau}}{\sum_{b}N(s,b)^{1/\tau}}$ (2.41)

and $\tau$ is a temperature parameter that controls exploration. During both
training and test-time rollouts, AlphaZero samples actions $a\sim\bm{\pi}$
according to this policy.

###### Learning

Starting from an initial state $s_{0}$ (e.g. an empty board), AlphaZero
proceeds with self-play, using the aforementioned search process to select
actions until a terminal state $s_{T}$ is reached. A score $z$ is produced for
$s_{T}$ according to the rules of the game and tuples $(s_{t},a_{t},z)$ are
stored in a replay buffer $D$ for each time-step $t\in[0,T]$ in the
trajectory. AlphaZero’s neural network is updated to minimize the loss
function:

$l=(z-v)^{2}-\bm{\pi}^{T}\log\bm{p}+\lambda||\theta||^{2}$ (2.42)

where $(\bm{p},v)\sim f_{\theta}(s)$ as in Equation 2.38, $\bm{\pi}$ follows
from Equation 2.41, and $\lambda$ is a coefficient weighting
$L2$-regularization. Intuitively, Equation 2.42 encourages the network to (i)
minimize the error between predicted values $v$ and game outcomes $z$; and
(ii) maximize similarity between predicted policy probabilities $\bm{p}$ and
search probabilities $\bm{\pi}$.

####  2.2 Interpretability

Neural networks, and any algorithms that leverage them, are inherently black-
box decision-makers. The field of interpretable machine learning seeks to
unlock this black-box such that neural networks have the "the ability to
explain [their decisions] or to present [them] in understandable terms to a
human" [49]. In general, interpretability techniques can be classified into
one of two categories: (i) intrinsic interpretability, which describes
algorithms and models that are architected to have an interpretable decision-
making structure prior to training (e.g. decision trees); and (ii)post-hoc
interpretability, where interpretation methods (e.g. linear probing) are
applied to a pre-trained, often uninterpretable, model. The descriptions below
prioritize concept-based interpretability—a subset of interpretability methods
that aim to express network decisions and explanations in terms of a set of
manually-curated, human-understandable concepts—as it is a primary motivation
for the interpretability methods developed in this work.

#####  2.2.1 Intrinsic Interpretability

Consider a standard supervised learning setting, such as regression, where the
goal is to learn a function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ that maps
inputs $x\in\mathbb{R}^{d}$ to scalar outputs $y\in\mathbb{R}$, using a
dataset $\\{(x^{(j)},y^{(j)})\\}_{j=1}^{n}$ of input-output examples as
supervision. The goal of intrinsic interpretability is to ensure that $f$
itself is interpretable—i.e. when an output $\hat{y}=f(x)$ is produced, the
factors driving the prediction $\hat{y}$ are explicitly exposed by $f$ (e.g.
feature importance, decision tree elements).

In most cases, this means that representing $f_{\theta}$ as a neural network
(here with parameters $\theta$) is not feasible, because neural network
activations do not provide this level of decision transparency. However,
recent work has shown that it is possible to construct customized network
architectures that enable intrinsic interpretability while still leveraging
the expressivity of neural network function approximation [105]. One such
method is a focal point here, as it is key to the motivation of the
interpretability methods developed in this work, though many other intrinsic
interpretability methods have been proposed in the literature [224, 49, 63].

###### Concept Bottleneck Models

Most relevant to our work is the Concept Bottleneck Model architecture
introduced by Koh et al. [105]. Concept bottleneck models refer to a class of
intrinsically-interpretable neural network architectures for supervised
learning. The CBM network makes predictions by first estimating a set of
human-understandable concepts, then producing an output based on those concept
estimates—i.e. the network is “bottlenecked" by concepts. Formally, given a
dataset $\\{(x^{(j)},y^{(j)},c^{(j)})\\}_{j=1}^{n}$ consisting of inputs
$x\in\mathbb{R}^{d}$, outputs $y\in\mathbb{R}$, and human-understandable
concepts $c\in\mathbb{R}^{k}$ (where $k$ is the number of unique concepts), a
concept bottleneck model learns two
mappings—$f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ from input-space to
concept-space, and $g:\mathbb{R}^{k}\rightarrow\mathbb{R}$ from concept-space
to output-space. The model can then make predictions $\hat{y}=f(g(x))$ as a
composition of those mappings.

Koh et al. [105] demonstrate the increased interpretability achieved by
concept bottlenecks in the context of an arthritis classification task in
which arthritis severity is predicted from MRI images of knee joints. Unlike
standard networks that learn an uninterpretable mapping from MRI images to
arthritis severity labels, the concept bottleneck’s output is conditioned on
an intermediate set of human-understandable concepts. Since these concepts
correspond to real-world features—e.g., the presence of bone spurs in the
arthritis task—they can be used by human observers to understand model
failures or misclassifications. Moreover, because the model’s predictions are
conditioning on these concepts, we can manually change the model’s output
(without retraining or fine-tuning) by intervening on its concept estimates.

#####  2.2.2 Post-hoc Interpretability

Despite the explicit decision-making transparency enabled by intrinsically
interpretable models, there is often a trade-off in asymptotic performance
that comes with the architectural choices needed to support that
interpretability. For example, concept bottleneck models require a
sufficiently rich set of concepts [220] to perform well, which can be
difficult to obtain manually in complex settings. For this reason, post-hoc
interpretability methods seek to generate or otherwise extract explanations
from a pre-trained model.

###### Linear Probing

We review the predominant post-hoc interpretability method, linear probing, as
a representative example. As above, we focus on a concept-based variant of the
problem domain [100]. Let $f_{\theta}$ be a neural network with parameters
$\theta$ that has been trained via supervised learning (as outlined in Section
2.2.1). Given an input $\bm{x}$, and assuming that $f_{\theta}$ is composed of
$L$ layers, we can rewrite the network’s prediction
$\hat{y}=f_{\theta}(\bm{x})$ as:

$\hat{y}=f^{L}_{\theta}\circ...\circ f^{2}_{\theta}\circ
f^{1}_{\theta}(\bm{x})=f^{1:L}_{\theta}(\bm{x})$

where $f^{l}_{\theta}$ is an intermediate layer $f_{\theta}$ accessed via an
index $l\in\\{1,...,L\\}$. During a forward pass through the network, it is
also possible to extract the activation $\bm{z}^{l}$ from layer $l$ by passing
the output of the previous layer $\bm{z}^{l-1}$ through $f^{l}_{\theta}$:

$\bm{z}^{l}=f^{l}_{\theta}(\bm{z}^{l-1})$

where $\bm{z}^{0}=\bm{x}$ and $\bm{z}^{L}=\hat{y}$. Now, given a human-
understandable concept $c$, the goal of linear probing is to train a separate
model $g^{l}$ over the activation $\bm{z}^{l}$ from some layer $l$ to
approximate $c$. Importantly, $g^{l}$ is defined as a sparse linear regression
function:

$g^{l}(\bm{z}^{l})=\bm{w}^{T}\bm{z}^{l}+\bm{b}^{l}$

weighted by $\bm{w}$ (and with biases $\bm{b}$). Concept-based
interpretability can then be measured as a function of the accuracy of the
linear predictor. Intuitively, if $g^{l}(\bm{z}^{l})$ accurately predicts $c$
on a held-out test set of examples, we can say that layer $l$ has learned to
encode and therefore carries information about the concept $c$.

The recent work of McGrath et al. [132] underscores the power of linear
probing as a post-hoc interpretability tool. Specifically, they conduct an
interpretability analysis over AlphaZero’s policy network using probing
techniques and show that it is possible to identify both when (and where) in
it has learned to encode strategic concepts that are pertinent to strong
performance in board games. In the board game setting, a single concept
$c:\mathbb{R}\rightarrow R$ is a mapping of the current game state $c(\bm{x})$
to a scalar value—e.g. in chess, $c$ could be defined in terms of piece
location ($c(\bm{x})=1$ if white has both bishops, $c(\bm{x})=0$ otherwise) or
some higher-level evaluation (material imbalance).

####  2.3 Fairness

As machine learning algorithms proliferate real-world applications (e.g.
lending [74, 123], hiring [85]), making decisions on behalf of real people and
operating over the private and often personal information of individuals, it
is of the utmost importance that the researchers and practioners behind the
development and commercialization of these algorithms ensure that they do not
disproportionately harm already disadvantaged groups or reinforce societal
biases. This has driven significant research interest into definitions and
quantifications of fairness, and algorithmic improvements that enable machine
learning systems to uphold these fairness definitions.

#####  2.3.1 Prediction-based Fairness

The majority of fairness work to date has examined fairness in the context of
supervised learning; also known as prediction-based fairness. Prediction-based
fairness considers a population of $n$ individuals (indexed $i=1,...,n$), each
described by variables $v_{i}$ (i.e. features or attributes), which are
separated into sensitive variables $z_{i}$ and other variables $x_{i}$.
Variables $v_{i}$ are used to predict (typically binary) outcomes $y_{i}\in Y$
by estimating the conditional probability $P[Y=1\mid V=v_{i}]$ through a
scoring function $\psi:\mathcal{V}\rightarrow\\{0,1\\}$. Outcomes in turn
yield decisions by applying a decision rule $\delta(v_{i})=f(\psi(v_{i}))$.
For example, in a lending scenario, a classifier may use $v_{i}$ to predict
whether an individual $i$ will default on ($y_{i}=0$) or repay ($y_{i}=1$)
his/her loan, which informs the decision to deny ($d_{i}=0$) or approve
($d_{i}=1$) the individual’s loan application [136].

This notation supports a wide range of fairness criteria111We point to
Mitchell et al. [136] for a comprehensive overview of individual and group
fairness definitions that are not used in this work.. For one, it enables the
comparison of outcome or decision fairness at the level of individuals. Such
individual fairness measures [50] posit that two individuals with similar
features should receive similar decision outputs from a classifier—i.e.
similarity in feature-space implies similarity in decision-space—and many
task-specific measures of similarity have been proposed in the literature [7,
31].

It is also possible to quantify fairness across cohorts of individuals with a
particular assignment of sensitive variables. These are known as group
fairness measures. Group-based fairness examines how well outcome ($Y$) and
decision ($D$) consistency is preserved across sensitive groups ($Z$) [54,
222]. We highlight the group-based measure of demographic parity, which
requires that $D\perp Z$ or, equivalently, that $P[D=1\mid Z=z]=P[D=1\mid
Z=z^{\prime}]$ for all $z,z^{\prime}$ where $z\neq z^{\prime}$. Group-based
fairness definitions are of particular relevance to this work and will be
examined in multi-agent settings in Section 5.1.

#####  2.3.2 Multi-Agent Fairness

In multi-agent settings, fairness has traditionally been examined through a
socio-economic lens, where outcomes are defined in terms of utility, and
fairness is defined in terms of social welfare (the distribution of utility).
For example, in the seminal work of Zheng et al. [226], socio-economic agents
are participants in a gather-and-build game where utility is derived from raw
resources collected in the environment (and goods built from those resources)
and fairness is measured wealth equality that is attained through taxation and
transfer (as dictated by a governing body, such as a tax authority). Many
social welfare functions have been proposed to measure the equality outcomes,
such as the well-known Gini index [65, 48], and can be incorporated directly
into the objectives of learning agents [230, 181].

These definitions are well-suited to multi-agent problems in which measuring
outcome equality is straightforward, such as resource allocation [52, 223]; or
in game-theoretic settings such as social dilemmas—where an agent’s local
incentives conflict with some global notion of utility that is defined for all
agents (e.g. tragedy of the commons) [115, 114, 42].

However, drawing an analogy to studies of fairness in supervised learning
settings, measuring fairness through outcomes alone may not be a complete
picture, as there may exist influential, though less visible, factors (i.w.
sensitive variables) upon which the fairness of outcomes or decisions relies.
We posit that the influence of sensitive variables—and even how they should be
defined in the first place—is far more nuanced in multi-agent settings than
what has been captured in the literature thus far. One of the primary goals of
this work is to highlight and address these considerations.

####  2.4 Environments

Multi-agent learning environments come in many forms and with a variety of
incentive structures. In cooperative settings, agents’ incentives are
aligned—in terms of reward (or other utility-based objectives) what is good
for one agent is good for all agents in the multi-agent system and this
alignment provides a rich ground for studying coordination dynamics among
agents. Competitive multi-agent environments are characterized by conflicting
incentives, where an increase in one agent’s reward corresponds to a decrease
in another’s, and these settings are particularly interesting for studying
strategic behavior and competition among agents. Mixed-motive social dilemmas
present a more complex scenario where agents’ incentives are partially aligned
and partially in conflict, often leading to sub-optimal outcomes if agents act
purely out of self-interest without considering the collective good. These
environments are suitable for studying learned social dynamics, such as:
exploitation, public resource sharing, and the emergence of free-rider
problems. In this work, we investigate each type of environment with the goal
of understanding and shaping emergent behavior in each.

#####  2.4.1 Cooperative Environments

Here we describe the cooperative multi-agent environments used in this work.

###### Pursuit-Evasion

Pursuit-evasion is a classic setting for studying multi-agent coordination
[88]. Though often played on a graph [151], work on continuous-space pursuit-
evasion has enabled real-world applications such as unmanned aerial vehicles
[202] and mobile robots [33]. Further work has shown that optimal control
strategies can be derived from value functions [91] or even learned from
scratch in MARL setting [126]. A relevant class of pursuit-evasion games
define the evader to be of equal or greater speed than the pursuers. This
setting highlights the need for coordinated motion (e.g. encircling) [201] and
communication [210] by the pursuers and is subject to theoretical performance
bounds under these conditions [161]. We use this setting to study the
emergence of implicit communication as a low-level form of behavioral
understanding; and as a means for identifying issues of fairness that emerge
amongst cooperative agents.

Formally, the pursuit-evasion game is played between $n$ pursuers
$\\{p_{1},...,p_{n}\\}$ and a single evader $e$. The goal of the pursuers is
to catch the evader as quickly as possible and, conversely, the goal of the
evader is to remain uncaught. Each agent $i$ is described by its current
position and heading $q_{i}$ and is subject to planar motion $\dot{q}_{i}$:

$\displaystyle q_{i}=\begin{bmatrix}x_{i}\\\ y_{i}\\\ \theta_{i}\end{bmatrix}$
$\displaystyle\dot{q}_{i}=\begin{bmatrix}\dot{x}_{i}\\\ \dot{y}_{i}\\\
\dot{\theta}_{i}\end{bmatrix}=\begin{bmatrix}\lvert\vec{v}_{i}\rvert\,\textrm{cos}(\theta_{i})\\\
\lvert\vec{v}_{i}\rvert\,\textrm{sin}(\theta_{i})\\\
\textrm{atan2}(\dot{y}_{i},\dot{x}_{i})\end{bmatrix}$

where $\vec{v}_{i}$ is the agent $i$’s velocity. The environment state $s_{t}$
is described by the position and heading of all agents
$s_{t}=\\{q_{p_{1}},...,q_{p_{n}},q_{e}\\}$. Upon observing $s_{t}$, each
agent selects its next heading $\theta_{i}$ as an action. The chosen heading
is pursued at the maximum allowed speed for each agent
($\lvert\vec{v}_{p}\rvert$ for the pursuers, $\lvert\vec{v}_{e}\rvert$ for the
evader); with orientation changes being instantaneous. To encourage teamwork,
we set $\lvert\vec{v}_{p}\rvert\leq\lvert\vec{v}_{e}\rvert$ in our work.

This work utilizes the pursuit-evasion environment in Section 2.4.1, which is
a toroidal extension of the planar pursuit-evasion game proposed by Lowe et
al. [126].

A planar pursuit-evasion game with periodic boundary conditions interpreted as
a toroidal pursuit-evasion environment.

In general, unbounded planar pursuit-evasion can be described by two cases:

  * •

Case 1: $\lvert\vec{v}_{p}\rvert>\lvert\vec{v}_{e}\rvert$. The game is solved
by a straight-line chase towards the evader and is not interesting from the
perspective of coordination.

  * •

Case 2: $\lvert\vec{v}_{p}\rvert\leq\lvert\vec{v}_{e}\rvert$. The evader has a
significant advantage. Pursuers have at most one opportunity to capture the
evader and are usually only successful under strict initialization conditions
[161].

Lowe et al. [126] addressed this by penalizing agents for leaving the
immediate area defined by the camera with negative reward. The evader defined
by Equation 3.3, however, will run away indefinitely in the
$\lvert\vec{v}_{p}\rvert\leq\lvert\vec{v}_{e}\rvert$ case. To provoke
consistent interaction between agents, we extend the planar environment with
periodic boundary conditions. One can think of this as playing the pursuit-
evasion game on a torus (see Section 2.4.1).

Toroidal pursuit-evasion does not require strict initialization conditions or
special rewards. Pursuers can be initialized randomly and allowed to construct
ad-hoc formations. Second, pursuit is no longer a one-and-done proposition.
This reflects the notion that, in nature, predators often do not give up after
a single attempt at a prey—they regroup and pursue it again.

###### Collaborative Cooking

Collaborative Cooking Environments.

Collaborative Cooking is a cooperative multi-agent environment from DeepMind’s
Melting Pot suite of environments [115]. Based on the game Overcooked [61] and
subsequent work that has developed Overcooked-like environments for studying
multi-agent coordination [24, 216], Melting Pot’s Collaborative Cooking is a
game in which a group of agents inhabit a kitchen-like environment and must
collaborate to find ingredients, complete recipes, and deliver finished dishes
as quickly as possible. Solving the cooking task requires sophisticated
coordination, involving both task partitioning—splitting a recipe into
parts—and role assignment—distributing sub-tasks among agents. For these
reasons, Collaborative Cooking is investigated in a number of prior works
[216, 24, 192] and is emerging as a strong benchmark for multi-agent learning.
A visualization of the Collaborative Cooking environments that we use in our
experiments is shown in Section 2.4.1.

More formally, the Collaborative Cooking game for $N$ agents is defined as
follows:

  * •

_States_ : Each environment is a grid world. Grid cells can be filled by an
agent or an environment-specific object.

  * •

_Observations_ : Agents receive partial multi-modal observations consisting of
their own position and orientation in the grid, as well as a partial RGB
rendering of a $5\textrm{-cell}\times 5\textrm{-cell}$ window centered at the
agent.

  * •

_Actions_ : Agents can execute one of 8 actions: no-op, move
$\\{\texttt{up},\texttt{down},\texttt{left},\texttt{right}\\}$, turn
$\\{\texttt{left},\texttt{right}\\}$, and interact.

  * •

_Recipe_ : (i) Bring a tomato to a cooking pot (3 times), (ii) Wait for soup
to cook in the pot (20 time-steps), (iii) Bring a dish to the cooking pot,
(iv) Pour soup from the pot into the dish, (v) Deliver soup to the delivery
location. In practice, solving this task from scratch in its entirety is
extremely difficult, as each of the aforementioned steps requires agents to
execute a series of movement and interaction actions in sequence.

  * •

_States_ : Grid cells can be filled by an agent or any of the following items:
Floor, Counter, Cooking Pot, Dish, Tomato.

  * •

_Reward_ : By default, agents share a positive reward for completing the
entire recipe outlined above. In practice, however, solving the cooking task
with this sparse reward alone is infeasible (completing each of the recipe
steps through random exploration is prohibitively challenging) and successful
approaches in prior works either pair learning agents with helpful bot agents
or introduce “densified" pseudorewards to augment the agents’ learning signal
[114]. We implement the latter, giving agents a small positive reward for
completing steps (i) and (iii) of the recipe. More concretely, we define the
following three-part reward:

$r_{t}=\begin{cases}20,&\textrm{if soup cooked and delivered}.\\\
1,&\textrm{if tomato placed in cooking pot.}\\\ 1,&\textrm{if soup poured into
dish.}\\\ 0,&\textrm{otherwise.}\end{cases}$

  * •

_Concepts_ : We assume that each environment supports the following concepts
(and concept types): (i) agent position (scalar); (ii) agent orientation
(scalar); (iii) whether or not an agent has a tomato, dish or soup (binary);
(iv) cooking pot position (scalar) (v) the progress of the cooking pot
(scalar); (vi) the number of tomatoes in the cooking pot (categorical); and
(vii) the position of each tomato and dish (scalar).

#####  2.4.2 Social Dilemmas

Here we describe the mixed-motive multi-agent environments used in this work.

###### Clean Up

Clean Up Environment.

The Clean Up game, also from Melting Pot [115], is shown in Section 2.4.2.
Clean Up is a classic social dilemma in which agents are forced to balance
selfish behaviors with public goods. Each agent is rewarded proportionally to
the number of apples it harvests. However, the rate at which apples respawn
after they are eaten is directly related to the amount of pollution that
exists in the river. Over time, pollution builds up in the river if it remains
uncleaned until eventually, apples are prevented from growing altogether.
Agents must learn to periodically clean the river to ensure that apples
continuously grown, even though they are not directly incentivized to do so by
default. Therefore, it is possible for agents to develop both emergent "free-
loading" behaviors—harvesting apples without cleaning the river—and emergent
public service behaviors—cleaning the river while trying to harvest as many of
the remaining apples after cleaning. This makes Clean Up a fitting environment
with which to study the extent to which inter-agent social dynamics can be
revealed.

The state space, observation space, and action space for this environment are
the same as outlined in the Collaborative Cooking environments in Section
2.4.1, except for the following environment-specific details:

  * •

_States_ : Grid cells can be filled by an agent or any of the following items:
Floor, Wall, Apple, Clean River, Polluted River.

  * •

_Reward_ : Agents receive an individual positive reward for collecting apples.
By default, agents are not rewarded for cleaning the river. We found that this
greatly increased the amount of training time required for agents to learn to
clean the river (because they have no incentive to do so). Because we are
motivated by understanding social behaviors once they have emerged, we
augmented each agent’s reward with a small positive reward for cleaning the
river. Specifically, we define the following reward for the cleaning task:

$r_{t}=\begin{cases}1,&\textrm{for eating an apple}.\\\ 0.01,&\textrm{for
cleaning pollution.}\\\ 0,&\textrm{otherwise.}\end{cases}$

#####  2.4.3 Competitive Environments

Here we describe the competitive multi-agent environments used in this work.

###### Capture the Flag

Capture the Flag Environment.

The Capture the Flag game is shown in Section 2.4.3. Capture the Flag is a
well-known competitive environment in the multi-agent literature [90]. The
game is played as follows: two multi-agent teams (red, blue) head-to-head in
an arena-style environment. The red team is spawned at the top of the
environment, and the blue team is spawned at the bottom. Both team have at
their “home base" a flag of their team’s color. The goal of each team is to
capture the opposing team’s flag as many times as possible within the game’s
time horizon; while also preventing the opposing team from capturing the
team’s home flag. The primary defense mechanism for an agent is a “zap" action
that reduces an opponent agent’s health if it is in the zap radius, and forces
the agent to drop the flag (if it is holding one). In addition to zapping
other agents, agents can choose a “paint" action that colors the floor tiles
with the painting agent’s home color. Agents of the opposite color cannot move
over painted tiles until they paint it their own color, so the painting
mechanism can be used strategically to slow down the movement of opponents
through certain corridors. There is also a set of purple tiles in the
environment (one in the center, many surrounding the arena) that serves as an
indicator of whether or not a flag has been taken from its home base. This
tile serves as an observation for each agent, informing that agent of the
current state of both team’s flags (purple = no flags taken, blue = blue flag
taken, red = red flag taken, gray = both flags taken).

Sophisticated Capture the Flag agents can learn a number of complex
strategies, such as attacking an opponent’s flag, battling opponent agents for
territory, and base camping to protect the home flag. Agents are forced to
learn these competitive behaviors from scratch and refine those behaviors
during training. From the perspective of our work, therefore, Capture the Flag
is a strong case study of the emergence of strategic behaviors over time.

The state space, observation space, and action space are the same as outlined
in the Collaborative Cooking environments in Section 2.4.1. Some environment-
specific details are outlined below:

  * •

_States_ : Grid cells can be filled by an agent or any of the following items:
Wall, Red Flag, Blue Flag, Red Paint, Blue Paint, Flag Indicator Tile.

  * •

_Reward_ : Agents receive a shared team reward for capturing the opposing
team’s flag (by running it back to base). Agents are also rewarded
individually for picking up a flag from the opposing team’s base, returning a
previously stolen flag to base, and zapping an opponent flag carrier. Agents
are therefore most strongly motivated to act offensively, but must learn to
balance attacks with defensive strategy. In sum, we define the following
reward for the task:

$r_{t}=\begin{cases}1,&\textrm{for capturing the opponent's flag.}.\\\
0.01,&\textrm{for picking up the opponent's flag.}\\\ 0.01,&\textrm{for
returning a flag to base.}\\\ 0.01,&\textrm{for zapping an opponent flag
carrier.}\\\ 0,&\textrm{otherwise.}\end{cases}$

###### Board Games

Board games studied in this thesis.

Historically, board games have proven to be a fertile ground for testing and
advancing artificial intelligence (AI) systems. The deterministic rules and
clear win-loss conditions of these games offer a structured environment where
AI can learn, experiment, and improve over time. The first notable success
came when IBM’s DeepBlue defeated the reigning world chess champion, Garry
Kasparov, in 1997 [23]. This was a landmark achievement, demonstrating the
potential of AI in complex decision-making tasks. Decades later, Google’s
AlphaGo mastered the ancient Chinese board game of Go, a game with a
complexity far exceeding that of chess [186]. These victories underscored the
power of AI and its capabilities in strategic thinking and decision-making.

Moreover, board games are fundamentally multi-agent environments—multiple
players interact and make decisions that affect the game’s outcome. This makes
them an excellent testbed for studying multi-agent systems, which are critical
in understanding how AI can function in environments where multiple, possibly
competing, agents coexist. In this work, three primary board games are studied
experimentally (see Section 2.4.3): tic-tac-toe, a variant of tic-tac-toe on a
4x4 grid, and Connect Four.

Tic-tac-toe is a two-player game played on a 3x3 grid. Players take turns
placing their mark (either an ’X’ or an ’O’) in an empty square. The objective
is to place three of one’s own marks in a horizontal, vertical, or diagonal
row before the opponent can do the same. The game ends when either player
achieves this goal or when all squares are filled, resulting in a draw. The
4x4 variant follows the same rules on a larger board.

Connect Four is a two-player game played on a 6x7 grid. Players take turns
dropping a colored disc into one of the vertical columns, with the objective
of forming a horizontal, vertical, or diagonal line of four of one’s own
discs. The game ends when either player achieves this goal or when all
positions are filled, which results in a draw.

These games, with their simple rules but deep strategic possibilities, are an
excellent platform for studying and understanding the dynamics of AI in multi-
agent environments.

##  Part I Interpreting Emergent Multi-Agent Behavior

In this first part of the thesis, we focus on interpreting emergent multi-
agent behavior. Drawing inspiration from the supervised learning literature,
we will seek to answer both high-level strategic questions, such as:

  * •

In cooperative environments, do agents learn to coordinate or opt for less
structured independent action?

  * •

In mixed-motive environments, do agents act selfishly or in a manner that
improves social welfare?

and low-level behavioral questions, such as:

  * •

To what extent do agents exchange information implicitly through their
respective action spaces?

  * •

Can we measure the influence of one agent’s behavioral cues on its teammates?

In Chapter 3, we address the low-level through a study of emergent implicit
communication. We highlight the importance of recognizing communication as a
spectrum and show that multi-agent teams, not unlike humans or animals, learn
to rely upon implicit signals from their teammates when coordinating.

In Chapter 4, we target high-level, concept-based explanations of emergent
multi-agent behavior. We introduce an intrinsically interpretable policy
architecture for MARL agents and show experimentally that it can reliably
detect emergent coordination, expose sub-optimal behaviors (e.g., lazy
agents), identify complex inter-agent social dynamics, and strategic behaviors
as they emerge throughout training.

###  Chapter 3 Emergent Implicit Signaling

####  3.1 Introduction

Communication is a critical scaffolding for coordination. It enables humans
and animals alike to coordinate on complex tasks, synchronize plans, allocate
team resources, and share missing state. Understanding the process through
which communication emerges has long been a goal of philosophy, linguistics,
cognitive science, and AI. Recently, advances in multi-agent reinforcement
learning (MARL) have propelled computational studies of emergent communication
that examine the representations and social conditions necessary for
communication to emerge in situated multi-agent populations [111]. Existing
approaches, targeting language-like communication, have shown that it is
possible for agents to learn protocols that exhibit language-like properties
such as compositionality [26, 166] and Zipf’s Law [25] when given additional
learning biases [51].

Left: Animal communication spans a complete spectrum from explicit to implicit
communication. Right: A pursuit-evasion game with two pursuers $p_{1}$ and
$p_{2}$ and an evader $e$ (with positions $q_{1,t}$, $q_{2,t}$, and $q_{e,t}$
at time $t$). The emergent communication literature has typically considered
only language-like communication (top), where agents share information over
specialized sender-receiver architectures—e.g. $p_{1}$ receives the extended
observation $o_{1,t}=[q_{1,t}\ q_{2,t}\ q_{e,t}\ m_{2,t-1}]^{T}$ and selects
actions using the extra information $m_{2,t-1}$ that $p_{2}$ chose to share at
the previous time-step (and vice versa for $p_{2}$). With implicit signals
(bottom), $p_{1}$ selects a movement action $a_{1,t}$ based only on the
observation $o_{1,t}=[q_{1,t}\ q_{2,t}\ q_{e,t}]^{T}$. The only information
$p_{1}$ gets from $p_{2}$ is generated by $p_{2}$’s physical position (and
vice versa for $p_{2}$). We posit that implicit signals are an important step
towards learning richer communication.

Though emergent communication is fundamentally an ab initio approach compared
to top-down language learning [200], most recent methods have targeted
protocols with complex structure and representational capacity, like that of
human language [111, 127]. Such techniques equip agents with specialized
sender-receiver architectures and allow them to exchange bits of information
(or continuous signals) through these channels. One notable exception is the
work of Jaques et al. [92], which considers how influential agents can pass
information to other agents through their actions in the environment. We build
on these ideas, recognizing the full spectrum of communication that exists in
nature and proposing the study of lower-level forms of communication that do
not require specialized architectures as a first step towards more
sophisticated communication (see Section 3.1).

Multi-agent cooperation in nature yields a wide range of communication
protocols that vary in structure and complexity. In animal communication [16],
for example, reef-dwelling fish use body shakes [198, 19] and octopuses punch
collaborators [171]—forms of non-verbal communication—whereas chimps [15],
macaques [130], and gentoo penguins [30] each maintain a diverse vocal
repertoire. Importantly, animals also exchange information through non-
explicit channels. In the Serengeti, for example, lions use the posture of
fellow pride members to stalk prey covertly [172]. Moreover, wolves [154] and
dolphins [160], both frequent vocal communicators, communicate implicitly
during foraging—adjusting their group formation based on the position and
orientation of other pack members [81]. Breazeal et al. [17] define such forms
of communication, called implicit communication, as "conveying information
that is inherent in behavior but which is not deliberately communicated".
Studies have shown that implicit cues are used frequently by humans as well.
Human teams rely on gaze, facial expressions, and non-symbolic movement during
cooperative tasks [53] including collaborative design [217], crowdsourcing
[227], and multiplayer games (e.g. Hanabi [118, 6]).

The role of implicit communication in teamwork has been studied extensively in
the human-computer [118, 173] and human-robot interaction [27, 17, 103, 21]
communities, and even in multi-agent systems [148, 64]; but is less well-
understood in the context of emergent agent-agent interactions [41]. This is
due in large part to the anthropomorphized nature of standard definitions of
implicit communication. Note that the key difference between explicit
communication (a deliberate information exchange) and implicit communication
(a non-deliberate exchange) in the definition above is intent [17, 64].
Understanding implicit communication in the context of artificial agents
requires (i) ascribing human-like mental states to artificial agents and (ii)
giving agents the ability to reason about each other’s mental states with
respect to a common goal (à la Cohen and Levesque [37]); which is a highly
non-trivial undertaking.

In this work, we take a first step in this direction by examining the extent
to which implicit communication aides coordination in multi-agent populations.
Following the work of De Greeff and Nolfi [41] in evolutionary settings, we
study implicit signals: signals generated by the physical position of an agent
as it interacts with its environment. Implicit signals are observed passively
by an agent’s teammates, and so require neither special sender-receiver
architectures nor reasoning about an agent’s mental states. For RL agents, we
distinguish implicit signals from explicit communication through each agent’s
actions and observations. As a simple example, consider the environment in
Section 3.1 where, at time $t$, agents $p_{1}$, $p_{2}$, and $e$ are described
by their positions $q_{1,t}$, $q_{2,t}$, and $q_{e,t}$ respectively. With
implicit signals, $p_{1}$ selects a movement action $a_{1,t}$ based on the
observation $o_{1,t}=[q_{1,t}\ q_{2,t}\ q_{e,t}]^{T}$—i.e. the only
information $p_{1}$ gets from $p_{2}$ is the information contained in
$p_{2}$’s physical position; and vice versa. With explicit communication,
$p_{1}$ emits a communicative action $m_{1,t}$ in addition to $a_{1,t}$ (and
same for $p_{2}$). In this case, $p_{1}$ receives the extended observation
$o_{1,t}=[q_{1,t}\ q_{2,t}\ q_{e,t}\ m_{2,t-1}]^{T}$ and can select actions
using the extra information $m_{2,t-1}$ that $p_{2}$ chose to share at the
previous time-step.

Experimentally, we study coordination and the role of implicit communication
with pursuit-evasion games [88]. Pursuit-evasion simulates an important
coordination task, foraging, where communication is especially impactful. To
accurately model the conditions under which coordination and communication
emerges in the animal kingdom, we prioritize decentralized multi-agent
learning. Despite the challenges posed by decentralized approaches [56], this
feature is critical in the emergence of animal communications and so we focus
on this important class of multi-agent learning frameworks to exploit
inspiration from the natural world. Moreover, to encourage teamwork, we target
pursuit-evasion games in which the pursuers are slower than the prey
(coordination is not needed with the pursuers have a velocity advantage).
Similar to Lowe et al. [126], we study pursuit-evasion as a MARL problem.

We show that, under these conditions, naive decentralized learning fails to
solve the pursuit-evasion task. There are a number of challenges that lead to
this outcome. First, decentralized learning is non-stationary [126]—with
multiple agents learning simultaneously, the learning problem is less stable
for each agent individually. Next, since we prioritize tasks that require
teamwork (e.g. pursuer speed less than evader speed), learning from scratch is
difficult, as agents are forced to learn how to interact with the environment
individually while simultaneously learning to coordinate with their teammates.
Finally, pursuit-evasion is a sparse reward task—pursuers receive reward only
when capturing the evader. During the early stages of training, when each
agent is following a randomly initialized policy, it is virtually impossible
for the agents to coordinate effectively enough to experience positive reward.

To address these challenges, we introduce a curriculum-driven approach for
solving difficult, sparse reward coordination tasks. Our strategy, combining
ideas from the ecological reinforcement learning [35] and automatic curriculum
learning [158] literature, is motivated by the following insights: (i) we can
create a curriculum over task difficulty by shaping the environment to the
current skill level of the cooperative agents; (ii) we can aide agents in
learning multi-agent team behaviors by forcing them to learn single-agent
behaviors first. More specifically, we first adopt an environment shaping
curriculum using velocity bounds, which allows pursuers to gather initial
experience at a velocity greater than that of the evader, and then tune their
strategies over time as velocity decreases. Then, we introduce a curriculum
over agent behavior that warm-starts cooperative multi-agent learning by first
seeding each agent with experience of successful single-agent behaviors.

Our first result confirms the importance of curriculum-driven multi-agent
learning. We compare the performance of our strategy to ablations over the
multi-agent curricula individually and show that, using our strategy,
decentralized agents learn to solve difficult coordination tasks, such as the
pursuit-evasion game.

Next, we stress-test both the strength of coordination and capacity for
implicit signaling of policies learned with our method. We compare the
performance of multi-agent coordination learned with our method against a set
of analytical and learned strategies that represent ablations over both
coordination and implicit signaling—i.e. outperforming one of these methods is
equivalent to surpassing that method’s level of sophistication in
coordination, capacity for implicit signaling, or both.

Empirical results show that our method significantly outperforms highly
sophisticated multi-agent strategies. Coordination strategies learned with our
method successfully complete the pursuit-evasion task at a speed ratio of 0.5
(i.e. the pursuers are moving at half the evader’s speed), whereas each of the
baseline methods fails to complete the pursuit-evasion task when pursuer speed
is only slightly below evader speed (speed ratio of 0.8).

Further, we hone in on the nature of each strategy’s coordination more
directly by examining agent behavior during the most important subsets of the
trajectory—those that immediately precede the accumulation of reward. In the
context of pursuit-evasion, we examine the distribution of pursuer locations
relative the evader at the time of capture. By comparing rotational symmetry
and rotational invariance in the agents’ capture distributions, we find that
our strategy learns structured coordination while simultaneously allowing
pursuers to make dynamic adjustments to their position relative the evader to
successfully achieve capture.

Finally, we examine the role of implicit signals (as introduced by De Greeff
and Nolfi [41]) more directly using measures of social influence. Influence
measures such as Instantaneous Coordination [92] quantify the extent to which
one agent’s behavior influences its teammates. We repurpose this method to
measure the exchange of implicit signals as position-based social influence.
Results of this study show that pursuers trained with our strategy exchange up
to 0.375 bits of information per time-step on average, compared to a maximum
of only 0.15 bits on average from the baseline methods. This indicates that
our method learns, and relies heavily on, the exchange of implicit signals.

Preview of contributions Our work is summarized by the following
contributions:

  1. 1.

We highlight the importance of studying implicit signals as a form of emergent
communication.

  2. 2.

We introduce a curriculum-driven learning strategy that enables cooperative
agents to solve difficult coordination tasks with sparse reward.

  3. 3.

We show that, using our strategy, pursuers learn to coordinate to capture a
superior evader, significantly outperforming sophisticated analytical and
learned methods. Coordination strategies learned with our method complete the
pursuit-evasion task at a speed ratio of $0.5$ (i.e. half the evader’s speed),
whereas each of the competing methods fails to complete the pursuit-evasion
task at any speed ratio below $0.8$.

  4. 4.

We examine the use of implicit signals in emergent multi-agent coordination
through position-based social influence. We find that pursuers trained with
our strategy exchange up to 0.375 bits of information per time-step on
average, compared to a maximum of only 0.15 bits on average from competing
methods, indicating that our method has learned, and relies heavily on, the
exchange of implicit signals.

####  3.2 Related Work

###### Emergent Communication

Emergent communication examines the process by which cooperative agents learn
communication protocols as a means to completing difficult multi-agent tasks
[111]. Recent work has shown that MARL agents converge upon useful
communication in referential games [75] and can even develop language-like
properties such as compositionality [26, 166] and Zipf’s Law [25] when exposed
to additional structural learning biases. More recently, this class of
techniques has expanded to include complex situated environments [40], high-
dimensional observations [39], and the negotiation of belief states [58].
Further work has shown that influential communication can be incentivized
through additional learning objectives (i.e. inductive biases) [51] and reward
shaping [92].

Implicit interactions are less well-studied in the emergent communication
literature, despite their importance to teamwork, as outlined in the human-
computer [118, 173] and human-robot interaction [27, 17, 103, 21] communities.
Implicit communication has been studied for cooperative multi-agent tasks [64,
69, 148], though not in the context of emergent behavior. Though some studies
have shown that agents can learn to communicate non-verbally through actions
and gestures [140], such forms of action-space communication [5] are examples
of non-verbal explicit communication, whereas our goal is to study completely
implicit signals. Most similar to our work is that of De Greeff and Nolfi
[41], which examines both implicit and explicit communication in evolutionary
settings. Our work can be interpreted as bridging these ideas with the MARL
literature.

###### Multi-Agent Reinforcement Learning

Multi-agent reinforcement learning (MARL) encompasses a large body of
literature extending RL techniques to multi-agent settings. In general, MARL
algorithms subscribe to either decentralized or centralized learning. With
decentralized learning (or independent learning), each agent is responsible
for updating its own policy (or Q-network) individually [197]. Though recent
work has shown that decentralized learning is feasible in complex environments
[43], it is often challenging, due to the non-stationary (and therefore
unstable) nature of the learning problem [110, 131]. Centralized techniques
stabilize multi-agent learning by allowing agents to share a joint Q-network
during training, then act independently at test-time [126, 57]. Centralization
has also proven useful for emergent communication, as agents can share
gradients directly through their communication channels [56]. Despite these
benefits, we prioritize decentralized learning because it more accurately
represents the learning problem that humans and animals face in the real-
world.

Recently, significant effort has been aimed at connecting ideas from the
curriculum learning literature [11] to RL [158]. Such methods have derived
curricula from virtually every aspect of the RL problem; including reward
shaping [10, 152], modifying initial state distributions [55], and
procedurally-generating sub-tasks [157, 167]. Some multi-agent curricula have
been shown to lead to more generally-capable RL agents [44]. Further work has
examined the environment’s role in generating curricula, leading to new
methods such as environment shaping [35] and unsupervised environment design
[45]. Of particular relevance is the work of Co-Reyes et al. [35], which
considers curricula that manipulate the dynamics of the RL environment to the
benefit of learning agents. Our work combines a velocity-based variant of
environment shaping with an additional curriculum for bootstrapping multi-
agent learning with single-agent experience, which itself is inspired by the
strategy employed by Yang et al. [218] for multi-goal learning.

####  3.3 Preliminaries

#####  3.3.1 Potential Field Navigation

Given an agent $i$ with position $q_{i}$, we can define a potential function
$U(q_{i},q_{\textrm{goal}})$ between $q_{i}$ and a target point
$q_{\textrm{goal}}$ such that the negative gradient
$F(q_{i},q_{\textrm{goal}})=-\nabla U(q_{i},q_{\textrm{goal}})$ specifies a
control law for $i$’s motion. For example, let
$U_{\textrm{att}}(q_{i},q_{\textrm{goal}})$ be a quadratic function of
distance between $q_{i}$ and a target point $q_{\textrm{goal}}$:

$U_{\textrm{att}}(q_{i},q_{\textrm{goal}})=\frac{1}{2}k_{\textrm{att}}\,d(q_{i},q_{\textrm{goal}})^{2}$
(3.1)

where $k_{\textrm{att}}$ is an attraction coefficient and $d(,)$ is a measure
of distance. The resulting force exerted on agent $i$ is:

$F_{\textrm{att}}=-\nabla
U_{\textrm{att}}(q_{i},q_{\textrm{goal}})=-k_{\textrm{att}}(q_{i}-q_{\textrm{goal}})$
(3.2)

In this work, the agent’s action-space is defined in terms of headings, so
only the direction of this force impacts our agents.

#####  3.3.2 Pursuit-evasion

Experimentally, we use the pursuit-evasion environment outlined in Section
2.4.1. Here we provide additional details that are specific to this work. We
assume the evader to be part of the environment, as defined by the potential
function:

$U_{\textrm{evade}}(\theta_{e})=\sum_{i}\bigg{(}\frac{1}{r_{i}}\bigg{)}\cos(\theta_{e}-\tilde{\theta}_{i})$
(3.3)

where $r_{i}$ and $\tilde{\theta}_{i}$ are the L2-distance and relative angle
between the evader and the $i$-th pursuer, respectively, and $\theta_{e}$ is
the heading of the evader. This objective is inspired by theoretical analysis
of escape strategies in the pursuit-evasion literature [161]. Intuitively,
Equation 3.3 pushes the evader away from pursuers, taking the largest bisector
between any two when possible. The goal of the pursuers—to capture the evader
as quickly as possible—is mirrored in the reward function, where
$r(s_{t},a_{t})=50.0$ if the evader is captured and $r(s_{t},a_{t})=-0.1$
otherwise. A derivation of Equation 3.3 and additional environmental details
are provided in Section A.1.1.

#####  3.3.3 Implicit Communication

For clarity, we restate the definitions of implicit vs. explicit communication
from Breazeal et al. [17] and implicit signals from De Greeff and Nolfi [41],
which we adopt throughout this work.

######  Definition 3.3.1 (Explicit Communication).

Communication that is “deliberate where the sender has the goal of sharing
specific information with the collocutor" [17].

######  Definition 3.3.2 (Implicit Communication).

Communication that conveys “information that [is] inherent in behavior but
which is not deliberately communicated" [17].

######  Definition 3.3.3 (Implicit Signal).

The “signal that is generated by the actual physical position of the [agents]
and that is detected by the other [agents]" [41].

In the context of RL agents, an implicit signal refers to positional
information observed by an agent’s teammates as part of the environmental
state $s_{t}$ or observation $o_{t}$ space, whereas explicit communication
involves sending/receiving messages over a dedicated communication channel. We
note that Definition 3.3.1 and Definition 3.3.2 rely on deliberation (or
intention), whereas Definition 3.3.3 does not. For the purposes of our
study—exploring the first-step in a bottom-up approach to emergent
communication—we therefore focus on implicit signals as a form of emergent
implicit communication.

#####  3.3.4 Instantaneous Coordination

Instantaneous Coordination (IC) is a measure of social influence between
agents [92]. IC is defined for two agents $i$ and $j$ as the mutual
information $\textrm{I}(a_{i}^{t};a_{j}^{t+1})$ between $i$’s action at time
$t$ and $j$’s action at the next time-step. Formally, assuming agent $i$’s
actions are drawn from the random variable $A_{i}$ with marginal distribution
$P_{A_{i}}$ (and similarly for agent $j$), we can rewrite IC using the
standard definition of mutual information as the Kullback-Leibler divergence
between the joint distribution and the product of the marginals:

$\displaystyle I(A_{i};A_{j})$
$\displaystyle=D_{\textrm{KL}}(P_{A_{i}A_{j}}||P_{A_{i}}\times P_{A_{j}})$
$\displaystyle=\sum_{\begin{subarray}{c}a_{i}\in\mathcal{A}_{i},\\\
a_{j}\in\mathcal{A}_{j}\end{subarray}}P_{A_{i}A_{j}}(a_{i},a_{j})\log\bigg{(}\frac{P_{A_{i}A_{j}}(a_{i},a_{j})}{P_{A_{i}}(a_{i})\times
P_{A_{j}}(a_{j})}\bigg{)}$

where $\mathcal{A}_{i}$ and $\mathcal{A}_{j}$ are the spaces over $A_{i}$ and
$A_{j}$, respectively. Intuitively, high IC is indicative of influential
behavior, while low IC indicates that agents are acting independently. We
highlight that, in the absence of explicit communicative actions, IC is a
measure of implicit signals (as defined in the previous section). This is
because agent $i$’s action at time $t$ inherently dictates $i$’s position
$q_{i}$ at time $t+1$, which is observed by $i$’s teammates. IC in this
context is therefore a measure of position-based social influence. Since this
work considers deterministic policies and uses IC at test-time, IC is computed
over Monte-Carlo estimates of the relevant distributions.

####  3.4 Curriculum-Driven DDPG

Our goal is to learn multi-agent coordination with decentralized training and,
in doing so, explore the role of implicit signaling in teamwork. However,
there are a number of issues with decentralized learning in difficult, sparse
reward environments, such as our pursuit-evasion game. First, though setting
$\lvert\vec{v}_{p}\rvert\leq\lvert\vec{v}_{e}\rvert$ is important for studying
teamwork, it places the pursuers at a severe deficit. In the early stages of
training—since each pursuer’s action selection is determined by the randomly
initialized weights of its policy network—the chance of slower pursuers
capturing the evader defined in Equation 3.3 is extremely low. The pursuers
are unlikely to obtain a positive reward signal, which is vital to improving
their policies. This issue is exacerbated by non-stationarity. In the case of
decentralized DDPG, multiple agents learning in the same environment causes
the value of state-action pairs for any one agent (as judged by its
Q-function) to change as a result of policy updates of other agents. This non-
stationarity leads to higher-variance gradient estimates and unstable
learning. Though recent advances in “centralized training, decentralized
execution" help in such cases [126], they violate our goal of decentralized
learning.

To address these challenges, we introduce a curriculum-driven method for
decentralized multi-agent learning in sparse reward environments. Our strategy
is motivated by the following principles: (i) we can create a curriculum over
task difficulty by shaping the environment to the current skill level of the
cooperative agents; (ii) we can aide agents in learning multi-agent team
behaviors by forcing them to learn single-agent behaviors first. More
specifically, we combine an environment shaping curriculum over agent
velocities with a behavioral curriculum for bootstrapping cooperative multi-
agent learning with successful single-agent experience. We refer to this
curriculum-driven variant of DDPG as CD-DDPG throughout the rest of this
paper.

#####  3.4.1 Velocity Ratio Curriculum

Curriculum learning [11] is a popular technique for solving complex learning
problems by breaking them down into smaller, easier to accomplish tasks.
Recent advances in ecological reinforcement learning [35] have introduced
environment shaping—in which properties, initial states, or the dynamics of an
environment are modified gradually—as a useful and more natural instantiation
of curriculum learning for RL agents (than, say, traditional reward shaping).
With this in mind, we construct a sequence of increasingly difficult pursuit-
evasion environments by incrementally lowering the ratio of pursuer speed to
evader speed ($\lvert\vec{v}_{p}\rvert/\lvert\vec{v}_{e}\rvert$).

More formally, we define a curriculum over velocity bounds. Let $\vec{v}_{0}$
be an initial setting of the environment’s velocity ratio
$\lvert\vec{v}_{p}\rvert/\lvert\vec{v}_{e}\rvert$. We anneal
$\lvert\vec{v}_{p}\rvert/\lvert\vec{v}_{e}\rvert$ to a target ratio
$\vec{v}_{\textrm{target}}$ over $v_{\textrm{decay}}$ epochs as:

$\vec{v}_{i}\leftarrow\vec{v}_{\textrm{target}}+(\vec{v}_{0}-\vec{v}_{\textrm{target}})*\max\bigg{(}\frac{(v_{\textrm{decay}}-i)}{v_{\textrm{decay}}},0.0\bigg{)}$
(3.4)

where $i$ represents the current training epoch and, in turn, $\vec{v}_{i}$
the current velocity ratio. In practice, we initialize the environment such
that $\vec{v}_{0}>1.0$ (i.e. pursuers are faster than the evader), then anneal
this ratio slowly as training progresses. This gives the pursuers an
opportunity enjoy a velocity advantage early on in training, then develop
increasingly coordinated strategies to capture the evader as
$\lvert\vec{v}_{p}\rvert/\lvert\vec{v}_{e}\rvert$ decays.

#####  3.4.2 Behavioral Curriculum

We combine the aforementioned velocity curriculum with a behavioral curriculum
that extends off-policy learning to allow for targeted single-agent
exploration early in the training process. As a consequence of the
deterministic policy gradient and importance sampling [182], the policy
gradient can be estimated in an off-policy manner—i.e. using trajectories
sampled from a separate behavior policy $\beta(a\mid s)$ where $\beta(a\mid
s)\neq\mu_{\phi}$. Formally, this means Equation 2.33 can be represented
equivalently as:

$\displaystyle J_{\beta}(\phi)$
$\displaystyle=\int_{\mathcal{S}}p^{\beta}Q_{\omega}(s,a)\mid_{s=s_{t},a=\mu_{\phi}(s_{t})}\textrm{d}s$
$\displaystyle=\mathbb{E}_{s\sim
p^{\beta}}[Q_{\omega}(s,a)\mid_{s=s_{t},a=\mu_{\phi}(s_{t})}]$

with the corresponding gradient:

$\nabla_{\phi}J_{\beta}(\phi)=\mathbb{E}_{s\sim
p^{\beta}}[\nabla_{a}Q_{\omega}(s,a)\mid_{s=s_{t},a=\mu(s_{t})}\nabla_{\phi}\mu(s)\mid_{s=s_{t}}]$

where $p^{\beta}$ is the state distribution of the behavior policy $\beta$.

Our behavioral curriculum takes advantage of off-policy learning by splitting
training into two exploration phases that use distinct behavior policies
$\beta_{0}$ and $\beta_{\mu}$, respectively. The key is that we define
$\beta_{0}$ strategically to be a supervisory policy that collects successful
single-agent experience and $\beta_{\mu}$ to be a standard exploration policy
($\epsilon-$greedy for discrete actions, random noise for continuous actions).
In multi-agent settings, defining $\beta_{0}$ this way allows each agent to
learn how to interact with the environment first, before learning to
coordinate with teammates. Without this curriculum, agents are forced to learn
both simultaneously.

In our pursuit-evasion environment, we define $\beta_{0}$ as follows:

$\beta_{0}=-\nabla U_{\textrm{att}}(q_{p_{i}},q_{e})$ (3.5)

where $U_{\textrm{att}}$ is the attractive potential-field defined in Equation
3.1. Note that $\beta_{0}$ is a greedy policy that runs directly towards the
evader. This strategy is obviously sub-optimal when
$\lvert\vec{v}_{p}\rvert/\lvert\vec{v}_{e}\rvert\leq 1.0$, but helps pursuers
learn to move in the direction of the evader when
$\lvert\vec{v}_{p}\rvert/\lvert\vec{v}_{e}\rvert>1.0$. In our experiments, we
use $\beta_{0}$ only during the first phase of the velocity curriculum. After
this phase, agents follow the standard DDPG behavior policy
$\beta_{\mu}=\mu_{\phi}(s_{t})+\mathcal{N}$, where $\mathcal{N}$ is the
Ornstein-Uhlenbeck noise process.

####  3.5 Results

Our evaluation addresses two primary questions: (i) Does our curriculum-driven
strategy enable decentralized agents to learn to coordinate in difficult