#  Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-
sum Games

Xiangyu Liu1, Hangtian Jia2, Ying Wen1, Yaodong Yang3, Yujing Hu2,
Yingfeng Chen2, Changjie Fan2 and Zhipeng Hu2
1Shanghai Jiao Tong University, 2Netease Fuxi AI Lab, 3University College
London Correspondence to Ying Wen<EMAIL_ADDRESS>
###### Abstract

Measuring and promoting policy diversity is critical for solving games with
strong non-transitive dynamics where strategic cycles exist, and there is no
consistent winner (e.g., Rock-Paper-Scissors). With that in mind, maintaining
a pool of diverse policies via open-ended learning is an attractive solution,
which can generate auto-curricula to avoid being exploited. However, in
conventional open-ended learning algorithms, there are no widely accepted
definitions for diversity, making it hard to construct and evaluate the
diverse policies. In this work, we summarize previous concepts of diversity
and work towards offering a unified measure of diversity in multi-agent open-
ended learning to include all elements in Markov games, based on both
Behavioral Diversity (BD) and Response Diversity (RD). At the trajectory
distribution level, we re-define BD in the state-action space as the
discrepancies of occupancy measures. For the reward dynamics, we propose RD to
characterize diversity through the responses of policies when encountering
different opponents. We also show that many current diversity measures fall in
one of the categories of BD or RD but not both. With this unified diversity
measure, we design the corresponding diversity-promoting objective and
population effectivity when seeking the best responses in open-ended learning.
We validate our methods in both relatively simple games like matrix game, non-
transitive mixture model, and the complex Google Research Football
environment. The population found by our methods reveals the lowest
exploitability, highest population effectivity in matrix game and non-
transitive mixture model, as well as the largest goal difference when
interacting with opponents of various levels in Google Research Football.

###  1 Introduction

Zero-sums games involve non-transitivity [2, 4] in the policy space, and thus
each player must acquire a diverse set of winning strategies to achieve high
unexploitability [33], which has been widely validated by recent studies of
constructing AIs with superhuman performance in sophisticated tasks, such as
StarCraft [29, 27] and DOTA2 [24, 36]. The non-transitivity in games means
there is not a dominating strategy and the set of strategies form a cycle
(e.g., the endless cycles among Rock, Paper and Scissors). It is the presence
of this special structure in games that requires players to maintain a diverse
set of policies. Otherwise, we only need to seek the strongest one. Formally,
the necessity of diversity for zero-sum games lies in three ways: (1) policy
evaluation: with the presence of non-transitivity, one cannot justify the
strength or weakness of a strategy through the outcome of the interaction with
a single type of opponent; (2) avoiding being exploited [23]: since in non-
transitive games a single strategy can be always beaten by another one, a
diverse set of strategies allows players to make corresponding responses when
encountering different opponents; (3) training adaptable strategies [31]: a
diverse set of training opponents helps gradually eliminate the weakness of a
strategy, which can adapt to a wide range of opponents with very few
interactions at test time.

The open-ended learning framework is a promising direction towards inducing a
population of distinct policies in zero-sum games via auto-curricula. Although
various open-ended algorithms have been proposed to derive diverse strategies
[2, 23, 6, 21], there are no consistent definitions for diversity. One of the
most intuitive principles to characterize diversity is to build metrics over
the trajectory or state-action distribution [6, 19]. However, this perspective
only focuses on the policy behaviors and ignores the reward attributes
inherited from the Markov decision process. We argue that this is not
reasonable since sometimes a slight difference in the policy can result in a
huge difference in the final reward like, in Maze. Contrary to this, another
line of works builds the diversity measure over empirical payoffs [23, 2],
thus revealing the underlying diverse behaviors of a strategy through the
responses when encountering distinct opponents.

In this work, based on all previous diversity concepts, we work towards
offering a unified view for diversity in an open-ended learning framework by
combining both the behavioral attribute and the response attribute of a
strategy. The behavioral diversity is formulated through the occupancy
measure, which is an equivalent representation of a policy. We hypothesize
that the diversity in policy behaviors should be revealed by differences in
the state-action distribution, and we use a general divergence family
$f$-divergence to indicate the novelty of a new policy. On the other hand,
gamescape [2] has been proposed to represent the response capacity of a
population of strategies. Based on gamescape, we formulate a new geometric
perspective to treat the response diversity by considering the distance to the
gamescape.

To summarize, in this paper, we provide the following contributions:

  * •

We formulate the concept of behavioral diversity in the state-action space as
the discrepancies of occupancy measures and analyze the optimization methods
in both normal-form games and general Markov games.

  * •

We provide a new geometric perspective on the response diversity as a form of
Euclidean projection onto the convex hull of the meta-game to enlarge the
gamescape directly and propose the optimization lower bound for practical
implementation.

  * •

We analyze the limitation of exploitability as the evaluation metric and
introduce a new metric with theoretical soundness called population
effectivity, which is a fairer way to represent the effectiveness of a
population than exploitability [15].

###  2 Preliminaries

####  2.1 Markov Games

The extension of Markov decision processes (MDPs) with more than one agents is
commonly modelled as Markov games [17]. A Markov game with $N$ agents is
defined by a tuple
$<N,\mathcal{S},\\{\mathcal{A}_{i}\\}_{i=1}^{N},P,\\{r_{i}\\}_{i=1}^{N},\eta,\gamma>$,
where $\mathcal{S}$ denotes the state space and $\mathcal{A}_{i}$ is the
action space for agent $i$. The function $P$ controls the state transitions by
the current state and one action from each agent:
$P:\mathcal{S}\times\mathcal{A}_{1}\times\dots\times\mathcal{A}_{N}\rightarrow\mathcal{P}(\mathcal{S})$,
where $\mathcal{P}(\mathcal{S})$ denotes the set of probability distributions
over the state space $\mathcal{S}$. Given the current state $s_{t}$ and the
joint action $(a_{1},\dots,a_{N})$, the transition probability to $s_{t+1}$ is
given by $P(s_{t+1}|s_{t},a_{1},\dots,a_{N})$. The initial state distribution
is given by $\eta:\mathcal{S}\rightarrow[0,1]$. Each agent $i$ also has an
associated reward function
$r_{i}:\mathcal{S}\times\mathcal{A}_{i}\times\dots\times\mathcal{A}_{N}\rightarrow\mathbb{R}$.
Each agent’s goal is to maximize the $\gamma$-discounted expected return
$R_{i}=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}r_{i}(s_{t},a_{i}^{t},a_{-i}^{t})]$,
where $-i$ is a compact representation of all complementary agents of $i$.
Specifically, for zero-sum games, the rewards satisfy that
$\sum_{i=1}^{N}r_{i}(s,\mathbf{a})=0$, and players need to behave
competitively to achieve higher rewards.

In multi-agent reinforcement learning (MARL) [34], each agent is equipped with
a policy $\pi_{i}:\mathcal{S}\times\mathcal{A}_{i}\rightarrow[0,1]$ and the
joint policy is defined by
$\bm{\pi}(\mathbf{a}|s)=\Pi_{i=1}^{N}\pi_{i}(a_{i}|s)$. In single-agent
reinforcement learning, occupancy measure is a principle way to characterize a
policy, which indicates how a policy covers the state-action space. Inspired
by the definition from the single-agent setting, we define the joint occupancy
measure in MARL induced by the joint policy $\bm{\pi}(\mathbf{a}|s)$ as:

######  Definition 1.

(Joint Occupancy Measure in MARL) Let
$\rho_{\bm{\pi}}(s):\mathcal{S}\rightarrow\mathbb{R}$ denote the normalized
distribution of state visitation by following the joint policy
$\bm{\pi}=(\pi_{i},\pi_{-i})$ in the environment:

$\displaystyle\rho_{\bm{\pi}}(s)=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}P(s_{t}=s|\bm{\pi})~{}.$
(1)

Then the distribution of state-action pairs
$\rho_{\bm{\pi}}(s,\mathbf{a})=\rho_{\bm{\pi}}(s)\bm{\pi}(\mathbf{a}|s)$ is
called occupancy measure of the joint policy $\bm{\pi}$.

####  2.2 Policy Space Response Oracle

Adapted from double oracle [22], policy space response oracle (PSRO) [15, 5]
has been serving as a powerful tool to solve the nash equilibrium (NE) in
zero-sum games. In PSRO, each player maintains a pool of policies, say
$\mathfrak{P}_{i}=\\{\pi_{i}^{1},\dots,\pi_{i}^{M}\\}$ for player $i$ and
$\mathfrak{P}_{-i}=\\{\pi_{-i}^{1},\dots,\pi_{-i}^{N}\\}$ for player $-i$. The
so-called meta game $\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}$ has
its $(k,j)$ entry as $\phi_{i}(\pi_{i}^{k},\pi_{-i}^{j})$, where the function
$\phi_{i}$ encapsulates the reward outcome for player $i$ like the winning
rate or expected return. When player $i$ adds a new policy $\pi_{i}^{M+1}$, it
will compute the best response to the mixture of its opponents:

$\displaystyle\operatorname{Br}(\mathfrak{P}_{-i})=\max_{\pi_{i}^{M+1}}\sum_{j}\sigma_{-i}^{j}\mathbb{E}_{\pi_{i}^{M+1},\pi_{-i}^{j}}[r_{i}(s,\mathbf{a})].$

where $\bm{\sigma}=(\sigma_{i},\sigma_{-i})$ is a distribution over policies
in $\mathfrak{P}_{i}$ and $\mathfrak{P}_{-i}$, which is usually a NE of
$\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}$.

The empirical gamescape is introduced by [2] to represent the expressiveness
of a population $\mathfrak{P}_{i}$ in the reward outcome level given the
opponent population $\mathfrak{P}_{-i}$:

######  Definition 2.

Given population $\mathfrak{P}_{i}$ and $\mathfrak{P}_{-i}$ with evaluation
matrix $\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}$, the
corresponding empirical gamescape (EGS) for $\mathfrak{P}_{i}$ is defined as

$\mathcal{G}_{\mathfrak{P}_{i}|\mathfrak{P}_{-i}}:=\\{\text{convex mixtures of
rows of }\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}\\}.$

Table 1: Comparisons of Different Algorithms. Method | Tool for Diversity | BD | RD | Game Type |
---|---|---|---|---|---
DvD | Determinant | $\checkmark$ | $\times$ | Single-agent |
PSRO${}_{\text{N}}$ | None | $\times$ | $\times$ | n-player general-sum game |
PSRO${}_{\text{rN}}$ |  $L_{1,1}$ norm | $\times$ | $\checkmark$ | 2-player zero-sum game |
DPP-PSRO | Determinantal point process | $\times$ | $\checkmark$ | 2-player general-sum game |
Our Methods | Occupancy measure & convex hull | $\checkmark$ | $\checkmark$ | n-player general-sum game |

####  2.3 Existing Diversity Measures

As the metric to measure the differences between models, diversity is an
important topic in many fields of machine learning, including generative
modelling [6], latent variable models [32], and robotics [1]. Specifically, in
reinforcement learning (RL), diversity is a useful tool for learning
transferable skills [7], boosting explorations [26], or collecting near-
optimal policies that are distinct in a meaningful way. Despite the importance
of diversity, as shown in Table 1, there has not been a consistent definition
of diversity for RL, and various diversity concepts are used. [21]
investigated behavioral diversity in multi-agent reinforcement learning
through expected action variation, which is modeled as the average total
variation distance of two action distributions under certain sampled states.
Considering the geometric perspective that the determinant of the kernel
matrix represents the volume of a parallelepiped spanned by feature maps, DvD
[25] proposed the concept of population diversity using the determinant of the
kernel matrix composed by the behavioral embeddings by multiple policies.
Thanks to the tools of empirical game theory analysis, diversity can be
modeled from the perspective of the empirical game. Effective diversity [2] is
formulated as the weighted $L_{1,1}$ norm of the empirical payoff matrix,
which emphasizes what opponents a policy can win against. Also inspired by
determinantal point process (DPP) [13, 35], [23] uses the expected cardinality
to measure the diversity of a population.

###  3 A Unified Diversity Measure

Motivated by bisimulation metric [8] to measure the similarity of two states
in MDPs:
$d\left(\mathbf{s}_{i},\mathbf{s}_{j}\right)=\max_{\mathbf{a}\in\mathcal{A}}(1-c)\cdot\left|\mathcal{R}_{\mathbf{s}_{i}}^{\mathbf{a}}-\mathcal{R}_{\mathbf{s}_{j}}^{\mathbf{a}}\right|+c\cdot
W_{1}\left(\mathcal{P}_{\mathbf{s}_{i}}^{\mathbf{a}},\mathcal{P}_{\mathbf{s}_{j}}^{\mathbf{a}};d\right)$,
which considers both the immediate reward and the following transition
dynamics, we want to build the metric to measure the similarity of two
policies in a given Markov game through the task-specific reward attributes
and the interaction between policy behaviors and transition dynamics. We will
firstly model the interaction between policy behaviors and transition dynamics
through the principled occupancy measure in MDPs, which encodes how a policy
behaves in a given state and how the state will transit. On the reward side,
the interaction responses with different opponents feature a policy, which can
be used for common diversity measures like DPP [23] and rectified Nash [2].

####  3.1 Behavioral Diversity via Occupancy Measure Mismatching

One fundamental way to characterize a policy in MDPs is through the
distribution of the state-action pair $(s,a)$. Formally, we define the
occupancy measure in multi-agent learning as the distribution of the joint
state-action distribution. It has been shown that there is a one-to-one
correspondence between the joint policy $\pi$ and the occupancy measure
$\rho_{\pi}$.

######  Proposition 1 (Theorem 2 of [28]).

If $\rho$ is valid occupancy measure, then $\rho$ is the occupancy measure for
$\pi_{\rho}(a\mid
s)=\rho(s,a)/\sum_{a^{\prime}}\rho\left(s,a^{\prime}\right)$, and $\pi_{\rho}$
is the only policy whose occupancy measure is $\rho$.

Usually, the policy $\pi$ is parameterized as a neural network, and tackling
the policy in the parameter space is intractable. However, due to the one-to-
one correspondence between the policy and occupancy measure, the occupancy
measure $\rho_{\pi}$ serves as a unique and informative representation for the
policy $\pi$. Therefore, we are justified in considering diversity from a
perspective of the occupancy measure.

Next, we will consider how to promote diversity in the framework of policy
space response oracle. Suppose after $t$ iterations of PSRO, the joint policy
aggregated according the distribution of nash is
$\bm{\pi_{E}}=(\pi_{i},\pi_{E_{-i}})$. The occupancy measure is given by
$\rho_{\bm{\pi_{E}}}$. For player $i$ in the $t+1$ iteration, it will seek the
new policy $\pi_{i}^{\prime}$, which can maximize the discrepancy between old
$\rho_{\bm{\pi_{E}}}$ and $\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}$.

$\displaystyle\max_{\pi_{i}^{\prime}}\operatorname{Div_{occ}}(\pi_{i}^{\prime})=D_{f}(\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}||\rho_{\pi_{i},\pi_{E_{-i}}})~{},$
(2)

where we use the general $f$-divergence to measure the discrepancy of two
distributions.

We firstly investigate the objective under the one-step game by giving the
following theorem:

######  Theorem 1.

By assuming the game is a one-step game (normal-form games, functional-form
games, etc.) and policies among players are independent, the behavioral
diversity can be simplified by:

$\displaystyle
D_{f}(\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}||\rho_{\pi_{i},\pi_{E_{-i}}})=\mathbb{E}_{s_{0}\sim\eta(s)}[D_{f}(\pi_{i}^{\prime}(\cdot|s_{0})||\pi_{i}(\cdot|s_{0}))]~{}.$
(3)

###### Proof.

See Appendix A.1. ∎

For more general Markov games, computing the exact occupancy measure is
intractable. However, notice that we are maximizing a $f$-divergence objective
of occupancy measures, while occupancy measure matching algorithms in
imitation learning try to minimize the same objective [12, 10, 9]. Leveraging
the powerful tool from occupancy measure matching, we here propose an
approximate method to maximize $\operatorname{Div_{occ}}$.

Prediction Error for Approximate Optimization. Inspired by random expert
distillation [30], a neural network $f_{\hat{\theta}}(s,\mathbf{a})$ is
trained to fit a randomly initialized fixed network $f_{\theta}(s,\mathbf{a})$
on the dataset of state-action pair $(s,\mathbf{a})\sim\rho_{\bm{\pi_{E}}}$.
Then we can assign an intrinsic reward
$r_{i}^{int}(s,\mathbf{a})=||f_{\hat{\theta}}(s,\mathbf{a})-f_{\theta}(s,\mathbf{a})||$
to the player, which will encourage the agent to visit the state-action with
large prediction errors, thus pushing occupancy measure of the new policy to
be different from the old one.

Alternative Solutions. There are also many other practical occupancy measure
matching algorithms. One popular paradigm is learning a discriminator
$D(s,\mathbf{a})$ to classify the state-action pair $(s,\mathbf{a})$ from the
distribution $\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}$ and the distribution
$\rho_{\bm{\pi_{E}}}$. Then the trained $D(s,\mathbf{a})$ can be used to
construct different intrinsic rewards, which will correspond to different
choices of $f$-divergence [12, 10, 9]. One major drawback of this paradigm is
that the discriminator depends on the new policy $\pi_{i}^{\prime}$ and needs
re-training once the policy $\pi_{i}^{\prime}$ is updated. Another popular
paradigm is to learn an intrinsic reward directly from the target distribution
$\rho_{\bm{\pi_{E}}}$ like the prediction error. Besides using the prediction
error, there are also other choices, including energy-based model (EBM) [18]
and expert variance [3]. However, those methods usually require specialized
training techniques.

####  3.2 Response Diversity via Convex Hull Enlargement

Take the two-player game for an example. In games with more than two players,
one can simply denote players other than player $i$ as player $-i$. Thanks to
the empirical payoff matrix, another fundamental way to characterize the
diversity of a new policy is through the reward outcome from the interaction
with many different opponents. Each row in the empirical payoff matrix embeds
how the corresponding row policy behaves against different opponent policies.
We are therefore justified in using the row vector of the empirical payoff
matrix to represent the corresponding row policy.

Formally, assume the row player maintains a pool of policies
$\mathfrak{P}_{i}=\\{\pi_{i}^{1},\dots,\pi_{i}^{M}\\}$ and the column player
maintains a pool of policies
$\mathfrak{P}_{-i}=\\{\pi_{-i}^{1},\dots,\pi_{-i}^{N}\\}$. The induced $(k,j)$
entry in the empirical payoff matrix
$\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}$ is given by
$\phi_{i}(\pi_{i}^{k},\pi_{-i}^{j})$, where the function $\phi_{i}$
encapsulates the reward outcome for player $i$ given the joint policy
$(\pi_{i}^{k},\pi_{-i}^{j})$. Now we can define the diversity measure induced
by the reward representations:

$\displaystyle\operatorname{Div_{rew}}(\pi_{i}^{M+1})=D(\mathbf{a}_{M+1}||\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}})$
(4)
$\displaystyle\mathbf{a}_{M+1}^{\top}:=(\phi_{i}(\pi_{i}^{M+1},\pi_{-i}^{j}))_{j=1}^{N}~{}.$
(5)

$D(\mathbf{a}_{M+1}||\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}})$
essentially measures the diversity of the new vector $\mathbf{a}_{M+1}$ given
the presence of row vectors in
$\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}$.

Inspired by the intuition of the convex hull that indicates the
representational capacity of a pool of policies, the diverse new policy should
seek to enlarge the convex hull of reward vectors as large as possible. To
characterize the contribution of a vector to the enlargement of the convex
hull directly, we define the novel diversity measure as a form of Euclidean
projection:

$\displaystyle\operatorname{Div_{rew}}(\pi_{i}^{M+1})$
$\displaystyle=\min_{\mathbf{1}^{\top}\bm{\beta}=1\atop\bm{\beta}\geq
0}||\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}^{\top}\bm{\beta}-\mathbf{a}_{n+1}||_{2}^{2}~{}.$
(6)

Unfortunately, there is no closed-form solution to this optimization problem.
To facilitate the optimization, we propose a practical and differential lower
bound:

######  Theorem 2.

For a given empirical payoff matrix $\mathbf{A}$ and the reward vector
$\mathbf{a}_{n+1}$, the lower bound of $\operatorname{Div_{occ}}$ is given by:

$\displaystyle\operatorname{Div_{rew}}(\pi_{i}^{M+1})\geq$
$\displaystyle\frac{\sigma_{\min}^{2}(\mathbf{A})(1-\mathbf{1}^{\top}(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{n+1})^{2}}{M}+||(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{n+1}||^{2}~{},$
(7)

where $(\mathbf{A}^{\top})^{\dagger}$ is the Moore–Penrose pseudoinverse of
$\mathbf{A}^{\top}$, and $\sigma_{\min}(\mathbf{A})$ is the minimum singular
value of $\mathbf{A}$.

###### Proof.

See Appendix A.2. ∎

Let $F(\pi_{i}^{M+1})$ be the right hand of the inequality. Then
$F(\pi_{i}^{M+1})$ serves as a lower bound of
$\operatorname{Div_{rew}}(\pi_{i}^{M+1})$.

###  4 A Unified Diverse Objective for Best Response

Equipped with the unified diversity measure, we are ready to propose the
diversity-aware response during each iteration of PSRO:

$\displaystyle\arg\max_{\pi_{i}^{\prime}}\mathbb{E}_{s,\mathbf{a}\sim\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}}[r(s,\mathbf{a})]+\lambda_{1}\operatorname{Div_{occ}}(\pi_{i}^{\prime})+\lambda_{2}\operatorname{Div_{rew}}(\pi_{i}^{\prime})~{}.$
(8)

If both $\lambda_{1}$ and $\lambda_{2}$ are $0$, then objective is a normal
best response.

####  4.1 On the Optimization of Diverse Regularizers

Discussions on Optimizing BD. As discussed in Section 3.1, diversity in the
occupancy measure level is fully compatible with the reinforcement learning
task since the agent can get an intrinsic reward $r_{i}^{int}(s,\mathbf{a})$
to indicate the novelty of a state-action pair $(s,\mathbf{a})$. Therefore, to
optimize the first two items in the objective, we only need to add the
original reward by the $\lambda_{1}$-weighted intrinsic reward. Another issue
we need to address is to sample $(s,\mathbf{a})$ from the distribution
$\rho_{\bm{\pi_{E}}}$, which has been mentioned in Section 3. Since
$\bm{\pi_{E}}$ is not a true policy but only a hypothetical policy aggregated
according to the mixture $(\sigma_{i},\sigma_{-i})$, sampling from
$\rho_{\bm{\pi_{E}}}$ is equivalent to sampling from
$\rho_{\pi_{i}^{k},\pi_{i}^{j}}$ with probability
$\sigma_{i}^{k}\sigma_{-i}^{j}$.

Discussions on Optimizing RD. Optimizing $\operatorname{Div_{rew}}$ is not so
easy since it involves an inner minimization problem. Fortunately, we have
derived a closed-form low-bound $F$, which can serve as a surrogate for the
outer maximization.

Assume the policy $\pi_{i}^{\prime}$ is parameterized by $\theta$ as
$\pi_{i}^{\prime}(\theta)$. Then the gradient of $F$ with respect to $\theta$
is given by:

$\begin{split}\frac{\partial
F(\pi_{i}^{\prime}(\theta))}{\partial\theta}&=\frac{\partial\mathbf{a}_{n+1}}{\partial\theta}\frac{\partial
F}{\partial\mathbf{a}_{n+1}}=\left(\frac{\partial\phi_{i}(\pi_{i}^{\prime}(\theta),\pi_{-i}^{1})}{\partial\theta},\dots,\frac{\partial\phi_{i}(\pi_{i}^{\prime}(\theta),\pi_{-i}^{N})}{\partial\theta}\right)\frac{\partial
F}{\partial\mathbf{a}_{n+1}}~{}.\end{split}$

$\frac{\partial F}{\partial\mathbf{a}_{n+1}}$ controls weights of the policy
gradient backpropagated from different opponents policies $\pi_{-i}$. For
practical implement, we sample an opponent $j$ according to the absolute
values of $\frac{\partial F}{\partial\mathbf{a}_{n+1}}$ and then train
$\pi_{i}^{\prime}$ against the opponent $\pi_{-i}^{j}$ using gradient descent
or ascent, which depends on the sign of the $j_{th}$ entry of $\frac{\partial
F}{\partial\mathbf{a}_{n+1}}$.

Joint Optimization. One issue worth our notice is that the update direction of
$\operatorname{Div_{rew}}$ will heavily rely on the initialization of
$\pi_{i}^{\prime}(\theta)$. A bad initialization of $\theta$ will make the
response diversity tell $\pi_{i}^{\prime}$ to update toward worse rewards.
Therefore, we propose to first optimize the first two items in the objective
jointly and then optimize $\pi_{i}^{\prime}$ using $\operatorname{Div_{rew}}$.
The final unified diverse response with gradient-based optimization is
described in Algorithm 1.

Algorithm 1 Gradient-based Optimization for Unified Diverse Response

1: Input: population $\mathfrak{P}_{i}$ for each $i$, meta-game
$\mathbf{A}_{\mathfrak{P_{i}}\times\mathfrak{P_{-i}}}$, state-action dataset
$\\{(s,\mathbf{a})\\}$, weights $\lambda_{1}$ and $\lambda_{2}$

2: $\sigma_{i},\sigma_{-i}\leftarrow\text{Nash on
}\mathbf{A}_{\mathfrak{P_{i}}\times\mathfrak{P_{-i}}}$

3: $\bm{\pi_{E}}\leftarrow\text{Aggregate according to
}\sigma_{i},\sigma_{-i}$

4: $r_{i}^{int}(s,\mathbf{a})$ $\leftarrow$ Train fixed reward from
distribution $(s,\mathbf{a})\sim\rho_{\bm{\pi_{E}}}$ by EBM or prediction
errors.

5: $\theta^{*}\leftarrow$ Train $\pi_{i}^{\prime}(\theta)$ against fixed
opponent policies $\pi_{E_{-i}}$ by single-agent RL algorithm with
$r_{i}(s,\mathbf{a})=r_{i}^{ext}(s,\mathbf{a})+\lambda_{1}r_{i}^{int}(s,\mathbf{a})$,
$r_{i}^{ext}$ is the original reward function.

6: $\frac{\partial F}{\partial\mathbf{a}_{n+1}}\leftarrow$ Simulate the reward
row vector $\mathbf{a}_{n+1}$ using new $\pi_{i}^{\prime}(\theta)$ and compute
$\frac{\partial F}{\partial\mathbf{a}_{n+1}}$ analytically.

7: $\hat{\theta}\leftarrow$ Train $\pi_{i}^{\prime}(\theta^{\star})$ against a
new mixture distribution $\sigma_{-i}+\lambda_{2}\frac{\partial
F}{\partial\mathbf{a}_{n+1}}$ of opponent policies.

8: Output: policy $\pi_{i}^{\prime}(\hat{\theta})$

In addition to the gradient-based optimization, we also provide other kinds of
optimization oracles suitable for different games. Pseudocodes can be found in
Appendix G.

####  4.2 Evaluation Metrics

Exploitability. Exploitability [15] measures the distance of a joint policy
from the Nash equilibrium. It shows how much each player gains by deviating to
their best responses:

$\displaystyle\operatorname{Expl}(\mathbf{\bm{\pi}})=\sum_{i=1}^{N}(\max_{\pi_{i}^{\prime}}\phi_{i}(\pi_{i}^{\prime},\pi_{-i})-\phi_{i}(\pi_{i},\pi_{-i}))~{}.$
(9)

Therefore, the smaller exploitability means the joint policy is closer to the
Nash equilibrium.

Population Effectivity. Note the limitation of exploitability is that it only
measures how exploitable a single joint policy is. Therefore, to evaluate the
effectiveness of a population, we first need to get an aggregated policy from
a population, and we usually use the Nash aggregated policy output by PSRO.
Since the Nash is computed over the meta game, which varies with the
opponents, the aggregation may be sub-optimal and cannot be used to represent
a population. Intuitively, the aggregation weights, and further, the
evaluation of a population should not be determined by the population that a
specific opponent holds. To address this issue, we propose a generalized
opponent-free concept of exploitability called Population Effectivity (PE) by
looking for the optimal aggregation in the worst cases:

$\displaystyle\operatorname{PE}(\\{\pi_{i}^{k}\\}_{k=1}^{N})=\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha}=1\atop\alpha_{i}\geq
0}\sum_{k=1}^{N}\alpha_{k}\phi_{i}(\pi_{i}^{k},\pi_{-i})~{}.$ (10)

PE is again a NE over a two-player zero-sum game, where the player owning the
population optimizes towards an optimal aggregation denoted by $\bm{\alpha}$,
while the opponent can search over the entire policy space. Next, we offer a
simple example to further illustrate the limitations of exploitability and
superiority of PE.

######  Example 1.

Consider the matrix game Rock-Scissor-Paper, where
$\phi_{1}(\pi_{1},\pi_{2})=\pi_{1}^{\top}\mathbf{A}\pi_{2}$ and
$\phi_{2}(\pi_{2},\pi_{1})=\pi_{2}^{\top}\mathbf{B}\pi_{1}$,
$\pi_{1}\in\mathbb{R}^{3}$, $\pi_{2}\in\mathbb{R}^{3}$,
$\mathbf{A}=\left[\begin{array}[]{ccc}0&1&-1\\\ -1&0&1\\\
1&-1&0\end{array}\right]$, $\mathbf{B}=-\mathbf{A}^{\top}$. Suppose player $1$
holds the population $\mathfrak{P}_{1}=\\{\left[\begin{array}[]{c}1\\\ 0\\\
0\end{array}\right],\left[\begin{array}[]{c}0\\\ 1\\\
0\end{array}\right],\left[\begin{array}[]{c}0\\\ 0\\\ 1\end{array}\right]\\}$,
i.e. $\\{\text{Rock},\text{Scissor},\text{Paper}\\}$ and
$\mathfrak{P}_{2}=\\{\left[\begin{array}[]{c}1\\\ 0\\\
0\end{array}\right]\\}$, i.e. $\\{\text{Rock}\\}$. Then the meta-game
$\mathbf{A}_{\mathfrak{P_{1}}\times\mathfrak{P_{2}}}=\left[\begin{array}[]{c}0\\\
-1\\\ 1\end{array}\right]$. The nash aggregated joint policy
$(\pi_{1},\pi_{2})=(\left[\begin{array}[]{c}0\\\ 0\\\
1\end{array}\right],\left[\begin{array}[]{c}1\\\ 0\\\ 0\end{array}\right])$.
Now we can compute $\operatorname{Expl}((\pi_{1},\pi_{2}))$ as:

$\displaystyle\operatorname{Expl}((\pi_{1},\pi_{2}))$
$\displaystyle=\max_{\pi_{1}^{\prime}}\phi_{1}(\pi_{1}^{\prime},\pi_{2})-\phi_{1}(\pi_{1},\pi_{2})+\max_{\pi_{2}^{\prime}}\phi_{2}(\pi_{2}^{\prime},\pi_{1})-\phi_{2}(\pi_{2},\pi_{1})$
(11)
$\displaystyle=\max_{\pi_{1}^{\prime}}\phi_{1}(\pi_{1}^{\prime},\pi_{2})+\max_{\pi_{2}^{\prime}}\phi_{2}(\pi_{2}^{\prime},\pi_{1})=2.$
(12)

Now notice that the contribution of player $1$ to the exploitability is
$\max_{\pi_{2}^{\prime}}\phi_{2}(\pi_{2}^{\prime},\pi_{1})$, which equals $1$.
However, it is not reasonable that player $1$ and $2$ have the same
contribution to the exploitability since player $1$ has a perfect diverse
policy set. Instead, if we use PE as the metric:

$\displaystyle\operatorname{PE}(\mathfrak{P}_{1})=0~{},$ (13)

which justifies that player $1$ has already found a perfect population.

In the following theorem, we show that PE is a generalized notion of
exploitability under certain conditions and has some desirable properties:

######  Theorem 3.

Population effectivity has the following properties:

P1. Equivalence: If $N=1$ and the underlying game $\phi_{i}(\cdot,\cdot)$ is a
symmetric two-player zero-sum game, PE is equivalent to exploitability.

P2. Monotonicity: If there are two populations $\mathfrak{P}_{i}$,
$\mathfrak{Q}_{i}$ and $\mathfrak{P}_{i}\subseteq\mathcal{Q}_{i}$, then
$\operatorname{PE}(\mathfrak{P_{i}})\leq\operatorname{PE}(\mathfrak{Q_{i}})$,
while the relationship for exploitability of the Nash aggregated policies of
$\mathfrak{P}_{i}$ and $\mathfrak{Q}_{i}$ may or may not hold.

P3. Tractability: If the underlying game $\phi_{i}(\cdot,\cdot)$ is a matrix
game, then computing PE is still solving a matrix game.

###### Proof.

See Appendix A.3. ∎

###  5 Experiments

To verify that our diversity-regularized best response algorithm can induce a
diverse and less exploitable population, we compare our methods with state-of-
the-art game solvers including Self-play [11], PSRO [15], PSROrN [2],
Pipeline-PSRO (P-PSRO) [20], DPP-PSRO [23]. In this section, we want to
demonstrate the effectiveness of our method to tackle the non-transitivity of
zero-sum games, which can be shown via higher PE, lower exploitability, and
diverse behaviors. Beyond the simple games, we also have the results on the
complex Google Research Football game, and our methods can still work. In all
the following experiments, we choose the appropriate diversity weights
$\lambda_{1}$ and $\lambda_{2}$ by extensive hyper-parameter tuning. We also
conduct ablation study by choosing different $\lambda_{1}$ and $\lambda_{2}$
in Appendix F. The environment details are in Appendix D, and the hyper-
parameter settings for each experiment are in Appendix E.3.

Real-World Games. [4] studies the properties of some complex real-world games,
including AlphaStar and AlphaGO. We test our method on the empirical games
generated through the process of solving these real-world games. In Figure
1(a), we report the exploitabilities of different algorithms during solving
the AlphaStar game, which contains the meta-payoffs for $888$ RL policies. We
report values of exploitability and PE during the growth of the population in
Figure 1(a) and Figure 1(b). The result shows that with our unified diversity
regularizer, our methods achieve the smallest exploitability and largest
population effectivity, while most baselines fail to recover the diverse
strategies and are easily exploited.

(a)

(b)

Figure 1: (a):Exploitability vs. training iterations (the number of times the
optimization oracle is called) on the AlphaStar game. (b): Negative Population
Effectivity vs. training iterations on the AlphaStar game. Ablation studies of
P-PSRO only with BD or RD are also reported. Figure 2: Exploration
trajectories during training process on Non-Transitive Mixture Games.

Non-Transitive Mixture Games. This zero-sum two-player game consists of $2l+1$
equally-distanced Gaussian humps on the 2D plane. Each player chooses a point
in the 2D plane, which will be translated into a $(2l+1)$-dimensional vector
$\pi_{i}$ with each coordinate being the density in the corresponding Gaussian
distribution. The payoff of the game is given
by:$\phi_{i}(\pi_{i},\pi_{-i})=\pi_{i}^{\top}\mathbf{S}\pi_{-i}+\mathbf{1}^{\top}(\pi_{i}-\pi_{-i})$.
According to the delicately designed $\mathbf{S}$, this game involves both the
transitive component and non-transitive component, which means the optimal
strategy should stay close to the center of the Gaussian and explore all the
Gaussian distributions equally.

We firstly visualize the exploration trajectories during different algorithms
solving the game in Figure 2. It shows that the best response algorithm
regularized by both BD and RD achieves the most diverse trajectories. Although
our algorithm finds the most diverse trajectories, such superiority is not
revealed by the metric of exploitability in the last row of Table 2. On the
other hand, we also report the PE values for the final population generated by
different algorithms in Table 2. It can found that our unified diversity
regularizer can always help PSRO dominate other baselines in terms of
population effectivity, which also justifies why PE is a better metric to
evaluate diverse populations. The details of computing approximate PE using
PSRO can be found in Appendix B.

Table 2: PE$\times 10^{2}$ for populations generated by different methods when
encountering opponents with varying strength on Non-transitive Mixture Games.
The OS (Opponent Strength) associated with the PE represents the strength of
the opponent during the process of using PSRO to solve it. More details can be
found in Appendix B. We also report the Exploitability$\times 10^{2}$ for each
population in last row.

PE(OS) | PSRO | PSROrN | P-PSRO | DPP-PSRO | P-PSRO w. RD | P-PSRO w. BD | P-PSRO w. BD&RD
---|---|---|---|---|---|---|---
PE($5$) | $-2.11\pm 0.13$ | $-2.11\pm 0.14$ | $40.20\pm 0.09$ | $40.49\pm 0.07$ | $40.42\pm 0.08$ | $40.19\pm 0.10$ | $\mathbf{40.54\pm 0.12}$
PE($10$) | $-13.18\pm 0.28$ | $-13.18\pm 0.28$ | $29.14\pm 0.19$ | $29.45\pm 0.13$ | $29.55+0.13$ | $29.05+0.21$ | $\mathbf{29.63\pm 0.26}$
PE($15$) | $-31.17\pm 0.37$ | $-31.17\pm 0.37$ | $11.03\pm 0.26$ | $11.49\pm 0.21$ | $\mathbf{11.63\pm 0.15}$ | $10.97\pm 0.29$ | $11.57\pm 0.33$
PE($20$) | $-49.12\pm 0.23$ | $-49.12\pm 0.24$ | $-6.78\pm 0.14$ | $-6.41\pm 0.10$ | $-6.52\pm 0.10$ | $-7.03\pm 0.21$ | $\mathbf{-6.37\pm 0.24}$
PE($25$) | $-54.59\pm 0.02$ | $-54.59\pm 0.01$ | $-12.51\pm 0.05$ | $-12.28\pm 0.04$ | $-12.42\pm 0.03$ | $-12.58\pm 0.02$ | $\mathbf{-12.18\pm 0.04}$
Expl | $54.66\pm 0.06$ | $54.90\pm 0.10$ | $\mathbf{13.21\pm 0.29}$ | $13.24\pm 0.33$ | $13.77\pm 0.40$ | $41.132\pm 1.06$ | $13.26\pm 0.24$

Google Research Football.

Figure 3: The average goal difference between all the methods and the built-in
bots with various difficulty levels $\theta$ ($\theta\in\left[0,1\right]$ and
larger $\theta$ means harder bot) on Google Research Football.

In addition to the experiments on relatively simple games, we also evaluate
our methods on a challenging real-world game named Google Research Football
(GRF) [14]. GRF simulates a complete football game under standard rules with
$11$ players on each team, and a normal match lasts for $3000$ steps. The
enormous exploration spaces, the long-time horizon, and the sparse rewards
problems in this game make it a challenging environment for modern
reinforcement learning algorithms. In such complex scenarios, the
exploitability of a certain policy or PE of a certain population would be hard
to calculate because both metrics involve a $\max$ or $\min$ operator, and the
approximate best response can be quite inaccurate for this complex game. Since
our goal is to find robust policies with strong capabilities in real-world
games, we compare the average goal differences between the aggregated policies
of different methods and the built-in bots with various difficulty levels of
GRF. The models within each aggregated policies are trained for $300000$ steps
under the generalized framework of Self-play [11] by selecting opponents
according to the probabilities output by different methods.

As depicted in Figure 3, policies trained by PSRO with both BD and RD achieve
the largest goal differences when playing against the built-in bots. Moreover,
they have an average of $\mathbf{60}$% win-rate over other baseline methods
(see the table in the Appendix C). We do not report the results of DPP-PSRO
since it needs evolutionary updates and cannot scale to such a complex
setting. We also abandon the pipeline trick for ease of implement since it
does not affect the relative performance among algorithms. Additionally, the
discussion of robustness of policies trained with different methods, the
network architectures, the hyperparameters, and other detailed experimental
setups can also be found in Appendix C.

###  6 Conclusions

This paper investigated a new perspective on unifying diversity measures for
open-ended learning in zero-sum games, which shapes an auto-curriculum to
induce diverse yet effective behaviors. To this end, we decomposed the
similarity measure of MDPs into behavioral and response diversity and showed
the most of the existing diversity measures for RL can be concluded into one
of the categories of them. We also provided the corresponding diversity-
promoting objective and optimization methods, which consist of occupancy
measure mismatching and convex hull enlargement. Finally, we proposed
population effectivity to overcome the limitation of exploitability in
measuring diverse policies for open-ended algorithms. Experimental results
demonstrated our method is robust to both highly non-transitive games and
complex games like the Google Research Football environment.

### Acknowledgments

This work is supported by Shanghai Sailing Program (21YF1421900). The authors
thank Minghuan Liu for many helpful discussions and suggestions.

### References

  * [1] Tucker Balch.  Behavioral diversity in learning robot teams.  Technical report, Georgia Institute of Technology, 1998.
  * [2] David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max Jaderberg, and Thore Graepel.  Open-ended learning in symmetric zero-sum games.  In International Conference on Machine Learning, pages 434–443. PMLR, 2019.
  * [3] Kiante Brantley, Wen Sun, and Mikael Henaff.  Disagreement-regularized imitation learning.  In International Conference on Learning Representations, 2019.
  * [4] Wojciech Marian Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafiei, David Balduzzi, and Max Jaderberg.  Real world games look like spinning tops.  arXiv preprint arXiv:2004.09468, 2020.
  * [5] Le Cong Dinh, Yaodong Yang, Zheng Tian, Nicolas Perez Nieves, Oliver Slumbers, David Henry Mguni, Haitham Bou Ammar, and Jun Wang.  Online double oracle.  arXiv preprint arXiv:2103.07780, 2021.
  * [6] Mohamed Elfeki, Camille Couprie, Morgane Riviere, and Mohamed Elhoseiny.  Gdpp: Learning diverse generations using determinantal point processes.  In International Conference on Machine Learning, pages 1774–1783. PMLR, 2019.
  * [7] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine.  Diversity is all you need: Learning skills without a reward function.  arXiv preprint arXiv:1802.06070, 2018.
  * [8] Norm Ferns, Prakash Panangaden, and Doina Precup.  Bisimulation metrics for continuous markov decision processes.  SIAM Journal on Computing, 40(6):1662–1714, 2011.
  * [9] Justin Fu, Katie Luo, and Sergey Levine.  Learning robust rewards with adversarial inverse reinforcement learning.  arXiv preprint arXiv:1710.11248, 2017.
  * [10] Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu.  A divergence minimization perspective on imitation learning methods.  In Conference on Robot Learning, pages 1259–1277. PMLR, 2020.
  * [11] Daniel Hernandez, Kevin Denamganaï, Yuan Gao, Peter York, Sam Devlin, Spyridon Samothrakis, and James Alfred Walker.  A generalized framework for self-play training.  In 2019 IEEE Conference on Games (CoG), pages 1–8. IEEE, 2019.
  * [12] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  arXiv preprint arXiv:1606.03476, 2016.
  * [13] Alex Kulesza and Ben Taskar.  Determinantal point processes for machine learning.  arXiv preprint arXiv:1207.6083, 2012.
  * [14] Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michał Zając, Olivier Bachem, Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al.  Google research football: A novel reinforcement learning environment.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4501–4510, 2020.
  * [15] Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel.  A unified game-theoretic approach to multiagent reinforcement learning.  arXiv preprint arXiv:1711.00832, 2017.
  * [16] P. Langley.  Crafting papers on machine learning.  In Pat Langley, editor, Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pages 1207–1216, Stanford, CA, 2000\. Morgan Kaufmann.
  * [17] Michael L Littman.  Markov games as a framework for multi-agent reinforcement learning.  In Machine learning proceedings 1994, pages 157–163. Elsevier, 1994\.
  * [18] Minghuan Liu, Tairan He, Minkai Xu, and Weinan Zhang.  Energy-based imitation learning.  arXiv preprint arXiv:2004.09395, 2020.
  * [19] Muhammad A Masood and Finale Doshi-Velez.  Diversity-inducing policy gradient: Using maximum mean discrepancy to find a set of diverse policies.  arXiv preprint arXiv:1906.00088, 2019.
  * [20] Stephen McAleer, John Lanier, Roy Fox, and Pierre Baldi.  Pipeline psro: A scalable approach for finding approximate nash equilibria in large games.  arXiv preprint arXiv:2006.08555, 2020.
  * [21] Kevin R McKee, Joel Z Leibo, Charlie Beattie, and Richard Everett.  Quantifying environment and population diversity in multi-agent reinforcement learning.  arXiv preprint arXiv:2102.08370, 2021.
  * [22] H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum.  Planning in the presence of cost functions controlled by an adversary.  In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 536–543, 2003.
  * [23] Nicolas Perez Nieves, Yaodong Yang, Oliver Slumbers, David Henry Mguni, and Jun Wang.  Modelling behavioural diversity for learning in open-ended games.  arXiv preprint arXiv:2103.07927, 2021.
  * [24] OpenAI.  Openai five.  https://blog.openai.com/openai-five/, 2018.
  * [25] Aldo Pacchiano, Jack Parker-Holder, Krzysztof Marcin Choromanski, and Stephen Roberts.  Effective diversity in population-based reinforcement learning.  2020\.
  * [26] Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts.  Effective diversity in population-based reinforcement learning.  arXiv preprint arXiv:2002.00632, 2020.
  * [27] Peng Peng, Ying Wen, Quan Yuan, Yaodong Yang, Zhenkun Tang, Haitao Long, and Jun Wang.  Multiagent bidirectionally-coordinated nets for learning to play starcraft combat games.  arXiv preprint arXiv:1703.10069, 2:2, 2017.
  * [28] Umar Syed, Michael Bowling, and Robert E Schapire.  Apprenticeship learning using linear programming.  In Proceedings of the 25th international conference on Machine learning, pages 1032–1039, 2008.
  * [29] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  Nature, 575(7782):350–354, 2019.
  * [30] Ruohan Wang, Carlo Ciliberto, Pierluigi Vito Amadori, and Yiannis Demiris.  Random expert distillation: Imitation learning via expert policy support estimation.  In International Conference on Machine Learning, pages 6536–6544. PMLR, 2019.
  * [31] Zhe Wu, Kai Li, Enmin Zhao, Hang Xu, Meng Zhang, Haobo Fu, Bo An, and Junliang Xing.  L2e: Learning to exploit your opponent.  arXiv preprint arXiv:2102.09381, 2021.
  * [32] Pengtao Xie, Jun Zhu, and Eric Xing.  Diversity-promoting bayesian learning of latent variable models.  In International Conference on Machine Learning, pages 59–68. PMLR, 2016.
  * [33] Yaodong Yang, Jun Luo, Ying Wen, Oliver Slumbers, Daniel Graves, Haitham Bou Ammar, Jun Wang, and Matthew E. Taylor.  Diverse auto-curriculum is critical for successful real-world multiagent learning systems.  In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’21, page 51–56, Richland, SC, 2021. International Foundation for Autonomous Agents and Multiagent Systems.
  * [34] Yaodong Yang and Jun Wang.  An overview of multi-agent reinforcement learning from game theoretical perspective.  arXiv preprint arXiv:2011.00583, 2020.
  * [35] Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang.  Multi-agent determinantal q-learning.  In International Conference on Machine Learning, pages 10757–10766. PMLR, 2020.
  * [36] Deheng Ye, Guibin Chen, Wen Zhang, Sheng Chen, Bo Yuan, Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, et al.  Towards playing full moba games with deep reinforcement learning.  arXiv preprint arXiv:2011.12692, 2020.

## Appendix for "Unifying Behavioral and Response Diversity for Open-ended
Learning in Zero-sum Games"

###  Appendix A Full Proof of Theorems

####  A.1 Proof of Theorem 1

To prove Theorem 1, we need the help of the following Lemma

######  Lemma 1.

If $P_{X,Y}=P_{X}P_{Y|X}$ and $Q_{X,Y}=Q_{X}P_{Y|X}$ then

$\displaystyle D_{f}(P_{X,Y}||Q_{X,Y})=D_{f}(P_{X}||Q_{X}).$ (14)

###### Proof.

See Proposition 7.1 in [3]. ∎

Now we can prove our Theorem 1.

###### Proof.

For games with only one step (normal-form games, functional-form games), there
is only one fixed state. Therefore, the distribution of state-action is
equivalent to the distribution of the action. Formally, for
$\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}$, we have:

$\displaystyle\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}(s,\mathbf{a})=(\pi_{i}^{\prime},\pi_{E_{-i}})(\mathbf{a})=\pi_{i}^{\prime}(a_{i})\pi_{-i}(a_{-i})~{},$
(15)

where the second equation comes from the assumption that policies are
independent. Similarly, for $\rho_{\pi_{i},\pi_{E_{-i}}}$, we also have:

$\displaystyle\rho_{\pi_{i},\pi_{E_{-i}}}(s,\mathbf{a})=(\pi_{i},\pi_{E_{-i}})(\mathbf{a})=\pi_{i}(a_{i})\pi_{-i}(a_{-i})~{}.$
(16)

Therefore, with the help of Lemma 1, we have:

$\displaystyle
D_{f}(\rho_{\pi_{i}^{\prime},\pi_{E_{-i}}}||\rho_{\pi_{i},\pi_{E_{-i}}})=D_{f}(\pi_{i}^{\prime}\pi_{-i}||\pi_{i}\pi_{-i})=D_{f}(\pi_{i}^{\prime}||\pi_{-i})~{}.$
(17)

∎

####  A.2 Proof of Theorem 2

Let us restate our Theorem 2

######  Theorem 2.

For a given empirical payoff matrix $\mathbf{A}\in\mathbb{R}^{M\times N}$ and
the reward vector $\mathbf{a}_{M+1}$ for policy $\pi_{i}^{M+1}$, the lower
bound of $\operatorname{Div_{occ}}$ is given by:

$\displaystyle\operatorname{Div_{rew}}(\pi_{i}^{M+1})\geq$
$\displaystyle\frac{\sigma_{\min}^{2}(\mathbf{A})(1-\mathbf{1}^{\top}(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1})^{2}}{M}+||(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{M+1}||^{2}~{},$
(18)

where $(\mathbf{A}^{\top})^{\dagger}$ is the Moore–Penrose pseudoinverse of
$\mathbf{A}^{\top}$, and $\sigma_{\min}(\mathbf{A})$ is the minimum singular
value of $\mathbf{A}$.

###### Proof.

$\begin{split}\min_{\mathbf{1}^{\top}\bm{\beta}=1\atop\bm{\beta}\geq
0}||\mathbf{A}^{\top}\bm{\beta}-\mathbf{a}_{M+1}||_{2}^{2}=&\min_{\mathbf{1}^{\top}\bm{\beta}=1\atop\bm{\beta}\geq
0}||\mathbf{A}^{\top}\bm{\beta}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1}||^{2}+||(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{M+1}||^{2}\\\
\geq&\min_{\mathbf{1}^{\top}\bm{\beta}=1}||\mathbf{A}^{\top}\bm{\beta}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1}||^{2}+||(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{M+1}||^{2}\\\
=&\min_{\mathbf{1}^{\top}\bm{\beta}=1}||\mathbf{A}^{\top}(\bm{\beta}-(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1})||^{2}+||(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{M+1}||^{2}\\\
\geq&\sigma_{\min}^{2}(\mathbf{A})\min_{\mathbf{1}^{\top}\bm{\beta}=1}||\bm{\beta}-(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1}||^{2}+||(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{M+1}||^{2}\\\
=&\frac{\sigma_{\min}^{2}(\mathbf{A})(1-\mathbf{1}^{\top}(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1})^{2}}{M}+||(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{M+1}||^{2}~{},\end{split}$

where the first equation comes from that we decompose $\mathbf{a}_{M+1}$ into
$\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1}+(\mathbf{I}-\mathbf{A}^{\top}(\mathbf{A}^{\top})^{\dagger})\mathbf{a}_{M+1}$.
The last equation comes from the analytic calculation of
$\min_{\mathbf{1}^{\top}\bm{\beta}=1}||\bm{\beta}-(\mathbf{A}^{\top})^{\dagger}\mathbf{a}_{M+1}||^{2}$
using Lagrangian. ∎

####  A.3 Proof of Theorem 3

Now let us first restate the propositions.

######  Proposition 1.

If $N=1$ and the underlying game $\phi_{i}(\cdot,\cdot)$ is a symmetric two-
player zero-sum game, PE is equivalent to exploitability.

To prove this, let us prove the following Lemma 2.

######  Lemma 2.

For any policy $\pi$ in two-player symmetric zero-sum games:

$\displaystyle\phi_{i}(\pi,\pi)=0~{}.$ (19)

###### Proof.

To begin with, due to the assumption that the game is symmetric, we get:

$\displaystyle\phi_{i}(\pi_{i},\pi_{-i})=\phi_{-i}(\pi_{-i},\pi_{i})~{}.$ (20)

Since the game is also zero-sum, we have:

$\displaystyle\phi_{-i}(\pi_{-i},\pi_{i})=-\phi_{i}(\pi_{-i},\pi_{i})~{}.$
(21)

By combing Equation 20 and Equation 33, for any $\pi_{i}$ and $\pi_{-i}$, we
get:

$\displaystyle\phi_{i}(\pi_{i},\pi_{-i})+\phi_{i}(\pi_{-i},\pi_{i})=0~{}.$
(22)

Let $\pi_{i}=\pi_{-i}=\pi$, we get what we need to prove:

$\displaystyle\phi_{i}(\pi,\pi)=0~{}.$ (23)

∎

Now we can begin proof of our proposition.

###### Proof.

To prove this theorem, we need a further assumption that PSRO maintains only
one population for two-player symmetric game, which is a quite common
practice. Therefore, the joint Nash aggregated policy satisfies that
$\bm{\pi_{E}}=(\pi_{i},\pi_{-i})$ satisfies $\pi_{i}=\pi_{-i}$. Therefore,
with the help of Lemma 2:

$\displaystyle\phi_{i}(\pi_{i},\pi_{-i})=\phi_{-i}(\pi_{-i},\pi_{i})=0~{}.$
(24)

Furthermore, exploitability for symmetric zero-sum game can be written as:

$\displaystyle\operatorname{Expl}(\bm{\pi_{E}})$
$\displaystyle=\sum_{i=1}^{2}\max_{\pi_{i}^{\prime}}\phi_{i}(\pi_{i}^{\prime},\pi_{-i})-\phi_{i}(\pi_{i},\pi_{-i})$
(25)
$\displaystyle=\sum_{i=1}^{2}\max_{\pi_{i}^{\prime}}\phi_{i}(\pi_{i}^{\prime},\pi_{-i})$
(26)
$\displaystyle=2\max_{\pi_{i}^{\prime}}\phi_{i}(\pi_{i}^{\prime},\pi_{-i})~{},$
(27)

where the last equation comes from the symmetry of the game and
$\pi_{i}=\pi_{-i}$.

For PE, it is calculated as:

$\displaystyle\operatorname{PE}(\\{\pi_{i}\\})$
$\displaystyle=\min_{\pi_{-i}^{\prime}}\phi_{i}(\pi_{i},\pi_{-i}^{\prime})$
(28)
$\displaystyle=-\max_{\pi_{-i}^{\prime}}\phi_{i}(\pi_{-i}^{\prime},\pi_{i})$
(29) $\displaystyle=-\frac{1}{2}\operatorname{Expl}(\bm{\pi_{E}})~{}.$ (30)

The second to last equation comes from Equation 22, and the last equation is
due to the assumption that $\pi_{i}=\pi_{-i}$. ∎

######  Proposition 2.

If there are two populations $\mathfrak{P}_{i}$, $\mathfrak{Q}_{i}$ and
$\mathfrak{P}_{i}\subseteq\mathcal{Q}_{i}$, then
$\operatorname{PE}(\mathfrak{P_{i}})\leq\operatorname{PE}(\mathfrak{Q_{i}})$,
while the relationship for exploitability of the Nash aggregated policies of
$\mathfrak{P}_{i}$ and $\mathfrak{Q}_{i}$ may or may not hold.

###### Proof.

We begin with proof of the monotonicity of PE. W.o.l.g, let us assume that
$\mathfrak{P}_{i}=\\{\pi_{i}^{k}\\}_{k=1}^{M}$,
$\mathfrak{Q}_{i}=\\{\pi_{i}^{k}\\}_{k=1}^{N}$, where $M\leq N$. Then for the
population effectivity of $\mathfrak{Q}_{i}$:

$\displaystyle\operatorname{PE}(\mathfrak{Q}_{i})=\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha}=1\atop\alpha_{i}\geq
0}\sum_{k=1}^{N}\alpha_{k}\phi_{i}(\pi_{i}^{k},\pi_{-i})~{}.$ (31)

where $\bm{\alpha}=(\alpha_{1},\cdots,\alpha_{N})^{\top}$. Let $\alpha_{i}=0$
for $M+1\leq i\leq N$, then we get:

$\displaystyle\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha}=1\atop\alpha_{i}\geq
0}\sum_{k=1}^{N}\alpha_{k}\phi_{i}(\pi_{i}^{k},\pi_{-i})$
$\displaystyle\geq\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha}=1,\alpha_{i}\geq
0\atop\alpha_{i}=0\ \forall M+1\leq i\leq
N}\sum_{k=1}^{N}\alpha_{k}\phi_{i}(\pi_{i}^{k},\pi_{-i})$ (32)
$\displaystyle=\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha^{\prime}}=1\atop\alpha_{i}^{\prime}\geq
0}\sum_{k=1}^{M}\alpha_{k}^{\prime}\phi_{i}(\pi_{i}^{k},\pi_{-i})$ (33)
$\displaystyle=\operatorname{PE}(\mathfrak{P}_{i})~{}.$ (34)

Now we conclude that:

$\displaystyle\operatorname{PE}(\mathfrak{Q}_{i})\geq\operatorname{PE}(\mathfrak{P}_{i})$
(35)

Regarding exploitability, the analysis comes from our Example 1. Suppose
player $1$ holds the population
$\mathfrak{P}_{1}=\\{\left[\begin{array}[]{c}\frac{1}{2}\\\ \frac{1}{2}\\\
0\end{array}\right]\\}$ and $\mathfrak{P}_{2}=\mathfrak{P}_{1}$. Apparently,
the Nash aggregated joint policy is

$\displaystyle\bm{\pi_{E}}^{\mathfrak{P}}=(\left[\begin{array}[]{c}\frac{1}{2}\\\
\frac{1}{2}\\\ 0\end{array}\right],\left[\begin{array}[]{c}\frac{1}{2}\\\
\frac{1}{2}\\\ 0\end{array}\right])~{},$ (42)

since there is only one policy in each players’ population.

Now consider another two populations
$\mathfrak{Q}_{1}=\\{\left[\begin{array}[]{c}\frac{1}{2}\\\ \frac{1}{2}\\\
0\end{array}\right],\left[\begin{array}[]{c}0\\\ 1\\\ 0\end{array}\right]\\}$
and $\mathfrak{Q}_{2}=\mathfrak{Q}_{1}$. Then the Nash aggregated joint policy
is given by:

$\displaystyle\bm{\pi_{E}}^{\mathfrak{Q}}=(\left[\begin{array}[]{c}0\\\ 1\\\
0\end{array}\right],\left[\begin{array}[]{c}0\\\ 1\\\ 0\end{array}\right]).$
(49)

With simple derivations, the exploitability for $\bm{\pi_{E}}^{\mathfrak{P}}$
and $\bm{\pi_{E}}^{\mathfrak{Q}}$ is:

$\displaystyle\operatorname{Expl}(\bm{\pi_{E}}^{\mathfrak{P}})=1.$ (50)
$\displaystyle\operatorname{Expl}(\bm{\pi_{E}}^{\mathfrak{Q}})=2.$ (51)

Now we can conclude that for player $1$ and player $2$, even their population
both get strictly enlarged ($\mathfrak{P}_{1}\subseteq\mathfrak{Q}_{1}$ and
$\mathfrak{P}_{2}\subseteq\mathfrak{Q}_{2}$), they become more exploitable:
$\operatorname{Expl}(\bm{\pi_{E}}^{\mathfrak{Q}})\geq\operatorname{Expl}(\bm{\pi_{E}}^{\mathfrak{P}})$.
∎

######  Proposition 3.

If the underlying game $\phi_{i}(\cdot,\cdot)$ is a matrix game, then
computing PE is still solving a matrix game.

###### Proof.

The proof follows some simple algebric manipulations. Note that for matrix
games, the reward function is given by:

$\displaystyle\phi_{i}(\pi_{i},\pi_{-i})=\pi_{i}^{\top}\mathbf{P}\pi_{-i}~{},$
(52)

where $\mathbf{P}$ is the payoff matrix. Then for population effectivity:

$\displaystyle\operatorname{PE}(\\{\pi_{i}^{k}\\}_{k=1}^{N})$
$\displaystyle=\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha}=1\atop\alpha_{i}\geq
0}\sum_{k=1}^{N}\alpha_{k}\phi_{i}(\pi_{i}^{k},\pi_{-i})$ (53)
$\displaystyle=\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha}=1\atop\alpha_{i}\geq
0}\sum_{k=1}^{N}\alpha_{k}(\pi_{i}^{k})^{\top}\mathbf{P}\pi_{-i}$ (54)
$\displaystyle=\min_{\pi_{-i}}\max_{\mathbf{1}^{\top}\bm{\alpha}=1\atop\alpha_{i}\geq
0}\bm{\alpha}^{\top}(\pi_{i}^{1},\cdots,\pi_{i}^{N})^{\top}\mathbf{P}\pi_{-i}~{}.$
(55)

Therefore, solving PE is still a matrix game with payoff matrix
$(\pi_{i}^{1},\cdots,\pi_{i}^{N})^{\top}\mathbf{P}$. ∎

###  Appendix B PE Approximation via PSRO

We have already mentioned the tractability for PE of matrix games in Theorem
3. However, for more general games, solving exact PE is still very hard. Since
PE is still computing an NE, we here propose using PSRO again as the
approximate solver. The only difference is that population of player $i$ is
already fixed by $\mathfrak{P}_{i}=\\{\pi_{i}^{k}\\}_{k=1}^{N}$. Therefore,
during iterations of PSRO, only player $-i$ needs to enlarge its population.
We now outline the algorithm PE($n$) in Algorithm 2. The intuition behind this
algorithm is that the opponent is enlarging its population gradually and
trying to exploit $\mathfrak{P}_{i}$. Therefore, the metric of PE is actually
testing how exploitable a population is by gradually constructing a real
adversarial! The opponent strength $n$ essentially represents how accurate
each best response is.

Algorithm 2 PE($n$)

1: Input: Population $\mathfrak{P}_{i}=\\{\pi_{i}^{k}\\}_{k=1}^{N}$, Opponent
Strength $n$, Number of iteraions $T$

2: $\mathfrak{P}_{-i}\leftarrow$ Initialize opponent population with one
random policy

3: $\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}\leftarrow$ Initialize
empirical payoff matrix

4: for $t=1$ to $T$ do

5: $\sigma_{i},\sigma_{-i}\leftarrow$ Nash Equilibrium on
$\mathbf{A}_{\mathfrak{P_{i}}\times\mathfrak{P_{-i}}}$

6: $\pi_{-i}^{t}(\theta)\leftarrow$ Initialize a new opponent policy

7: $\theta^{\star}\leftarrow$ Train $\pi_{-i}^{t}$ against mixture of
$\sum_{j}\sigma_{i}^{j}\pi_{i}^{j}$ with $n$ gradient steps

8:
$\mathfrak{P}_{-i}\leftarrow\mathfrak{P}_{-i}\cup\\{\pi_{-i}^{t}(\theta^{\star})\\}$

9: Compute missing entries in the evaluation matrix
$\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}$

10: end for

11: Output: Nash value on
$\mathbf{A}_{\mathfrak{P}_{i}\times\mathfrak{P}_{-i}}$

###  Appendix C Additional Experimental Results on Google Research Football

In real world games, we expect our models are robust enough to defeat all the
previous models in the model pool and show diverse behaviors to better exploit
the opponents. To further evaluate the performance of all the models generated
with different methods during the training process, we rank all the models
with the Elo rating system [2], and the results are shown in Figure 4. It can
be found that models generated by PSRO w. BD&RD outperform other methods and
reaches an Elo score of around $1300$. This implies that a combination of BD
and RD will essentially contribute to the generation of diverse opponents
during the training, so that the final models will be more robust and less
exploitable since they are more likely to be offered strong diverse opponents
and have the chance to learn to defeat them. Additionally, we also visualize
the policies of our methods when playing against other baseline methods and
verify our methods truly generate diverse behaviors (see
https://sites.google.com/view/diverse-psro/).

Figure 4: The Elo scores of all the models generated by different methods.
Shaded areas represent the standard deviation.

###  Appendix D Environment Details

####  D.1 Environment Details of Non-Transitive Mixture Model

In our experiments, we set $l=4$ and use $9$ Gaussian distributions in the
plane. This environment involves both transitivity and non-transitivity
because of the delicately designed $\mathbf{S}$ in the reward function
$\phi_{i}(\pi_{i},\pi_{-i})=\pi_{i}^{\top}\mathbf{S}\pi_{-i}+\mathbf{1}^{\top}(\pi_{i}-\pi_{-i})$.
$\mathbf{S}$ is constructed by:

$\mathbf{S}[i][k]=\left\\{\begin{array}[]{rcl}0&&k=i\\\
1&&0<(k-i)\bmod{(2l+1)}\leq l\\\ -1&&\text{otherwise}\\\ \end{array}\right.$

####  D.2 Environment Details of Google Research Football

Google Research Football (GRF) [4] is a physics-based 3D simulator where
agents can be trained to play football. The engine implements a full football
game under standard rules (such as goal kicks, side kicks, corner kicks,
etc.), with $11$ players on each team and $3000$ steps duration for a full
game. It offers several state wrappers (such as Pixels, SMM, Floats) and the
players can be controlled with $19$ discrete actions (such as move in $8$
directions, high pass, long pass, steal, etc.). The rewards include both the
scoring reward ($+1$ or $-1$) and the checkpoint reward, where the checkpoint
reward means that the agent will be reward with $+0.1$ if it is the first time
that the agent’s team possesses the ball in each of the checkpoint regions.

###  Appendix E Hyperparameter Settings

####  E.1 Hyperparameter Settings for Real-World Games

We report our hyperparameter setting for real-world metagames in Table 3.

Table 3: The hyperparameters of real-world metagames. Parameter | Value | Description
---|---|---
Learning rate | 0.5 | Learning rate for agents
Improvement threshold | 0.03 | Convergence criteria
Metasolver | Fictitious play | Method to compute NE
Metasolver iterations | 1000 |  $\\#$ of iterations of metasolver
Metasolver iterations for PE | 2000 |  $\\#$ of iterations to compute PE
$\\#$ of threads in pipeline | 1.0 | Number of learners in Pipeline-PSRO
$\\#$ of seeds | 5 |  $\\#$ of trials
$\lambda_{1}$ | 0.2 | Weight for BD
$\lambda_{2}$ | 0.2 | Weight for RD

####  E.2 Hyperparameter Settings for Non-Transitive Mixture Model

We report our hyperparameter setting for non-transitive mixture model in Table
4.

Table 4: The hyperparameters of non-transitive mixture model.

Parameter | Value | Description
---|---|---
Learning rate | 0.1 | Learning rate for agents
Optimizer | Adam | Gradient-based optimization
Betas | (0.9, 0.99) | Parameter for Adam
$N_{train}$ | 5 |  $\\#$ of iterations using GD per BR
$\pi_{i}$ | $\pi_{k}^{i}=\exp(-\left(x_{i}-\mu_{k}\right)^{\top}\Sigma\left(x_{i}-\mu_{k}\right)/2)$ | Policy parameterization
$\Sigma$ | $1/2\mathbf{I}$ | Covariance of each Gaussian
$u_{k}$ | $r(\cos(\frac{2\pi}{2l+1}k),\sin(\frac{2\pi}{2l+1}k))$ | Center of each Gaussian
$l$ | $4$ |  $9$ Gaussian distributions
$r$ | $5$ | Radius of each Gaussian
Metasolver | Fictitious play | Method to compute NE
Metasolver iterations | 1000 |  $\\#$ of iterations of metasolver
$\\#$ of threads in pipeline | 1.0 | Number of learners in Pipeline-PSRO
$\\#$ of iteration | 50 |  $\\#$ of training iterations for PSRO
$\\#$ of seeds | 5 |  $\\#$ of trials
$\lambda_{1}$ | $1$ | Weight for BD
$\lambda_{2}$ | $1500$ | Weight for RD
Decrease rate of $\lambda_{1}$ and $\lambda_{2}$ | $1-\frac{0.7}{1+\exp(-0.25(t-25))}$ | The weights will decrease as the iteration progresses, where $t$ is the current iteration
$\\#$ of iteration for PE | 30 |  $\\#$ of training iterations using PSRO for PE

####  E.3 Hyperparameter Settings for Google Research Football

States and Network Architecture. For GRF, We use a structured multi-head
vector as the states input. The information of each head is listed in Table 5:

Table 5: The states input for Google Research Football.

Head index | Length | Information
---|---|---
0 | 9 | Ball information (position, direction, rotation)
1 | 25 | Ball owner information (ball owned team id, ball owned player id)
2 | 25 | Active player information (id, position, direction, area of the field)
3 | 6 | Active player vs. ball (distance, 1/distance)
4 | 4 | Active player vs. ball player (distance, 1/distance)
5 | 66 | Active player vs. self-team players (position, distance, 1/distance, position cosine, direction cosine)
6 | 66 | Active player vs. oppo-team players (position, distance, 1/distance, position cosine, direction cosine)
7 | 88 | Self-team information (position, direction, tired factor, yellow card, active player, offside flag)
8 | 88 | Oppo-team information (position, direction, tired factor, yellow card, active player, offside flag)
9 | 32 | Goal keeper information (distance to self-player/oppo-player, nearest/farthest player information)
10 | 7 | Game mode information (one-hot)
11 | 29 | Legal action and sticky action information
12 | 76 | History (one-hot) actions of last four steps

The network structure is shown in Figure 5. The shapes of the fully-connected
layers for the input heads are: [$32,64,64,16,16,128\times 64,128\times
64,128\times 128,128\times 128,64,16,64,64$], followed by three fully-
connected layers (i.e. [$512\times 256\times 128$]) and finally output the
policy and value.

Figure 5: The shape of input states for each head and the general network
structure.

Hyperparameter Settings for Reinforcement Learning Oracle. We use IMPALA [1]
as the reinforcement learning algorithm to approximate the best response for
each opponent selected by different methods during the training process. The
hyperparameters are listed in Table 6.

Table 6: The hyperparameters of the IMPALA algorithm. Parameter | Value
---|---
Batch Size | 1024
Discount Factor ($\gamma$) | 0.993
Learning Rate | 0.00019896
Number of Actors | 100
Optimizer | Adam
Unroll Length/n-step | 1.0
Entropy Coefficient | 0.0001
Value Function Coefficient | 1.0
Grad Clip Norm | 0.5
Rho (for V-Trace) | 1.0
C (for V-Trace) | 1.0
$\lambda_{1}$ (Weight for BD) | 0.5
$\lambda_{2}$ (Weight for RD) | 0.5

Network Training Details. We carry out the experiments on six servers (CPU:
AMD EPYC $7542$ $128$-Core Processor, RAM: $500$G), with each one
corresponding to one of six methods (i.e. Self-play, PSRO, PSROrN, PSRO w. BD,
PSRO w. RD, PSRO w.BD&RD). For each experiment, the approximated best response
(i.e. checkpoint) is saved only when the win-rate against corresponding
opponent is stable during two checks (check frequency = $1000$ model steps,
and $\Delta_{winrate}<0.05$) or the training model step reaches an upper bound
(i.e. $50000$ model steps). The $\lambda_{1}$ and $\lambda_{2}$ we used for
both coefficients are $0.5$. For the Google Research Football environment
settings, we use both scoring reward and checkpoint reward for the training.

###  Appendix F Ablation Studies

We also conduct ablation study on the sensitivity of the diversity weights
$\lambda_{1}$ and $\lambda_{2}$ in real-world games, non-transitive mixture
model, and Google Research Football.

####  F.1 Real-World Games

We report the exploitability and PE by varying $\lambda_{1}$ in Figure 6(a),
6(b) and $\lambda_{2}$ in Figure 7(a), 7(b). It can be found that too large
weights can cause the slow convergence and too small weights prevent the
algorithm from finding populations with smaller exploitability and larger PE.

(a)

(b)

Figure 6: Ablation study on $\lambda_{1}$. (a):Exploitability vs. training
iterations. (b): Negative Population Effectivity vs. training iterations on
the AlphaStar game.
$\operatorname{cdf}(k)=\int_{-\infty}^{k}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^{2}}{2}}dx$
is the cumulative distribution function of the standard normal distribution.

(a)

(b)

Figure 7: Ablation study on $\lambda_{2}$. (a):Exploitability vs. training
iterations. (b): Negative Population Effectivity vs. training iterations on
the AlphaStar game.
$\operatorname{cdf}(k)=\int_{-\infty}^{k}\frac{1}{\sqrt{2\pi}}e^{-\frac{x^{2}}{2}}dx$
is the cumulative distribution function of the standard normal distribution.
Table 7: Exploitability$\times 10^{2}$ for populations generated by PSRO only
with BD with varied diversity weight $\lambda_{1}$.

$\lambda_{2}$ | $7.5$ | $15$ | $75$ | $750$ | $1500$ | $7500$
---|---|---|---|---|---|---
Expl | $\mathbf{14.57\pm 0.69}$ | $14.93\pm 1.87$ | $14.64\pm 1.48$ | $42.37\pm 10.12$ | $33.39\pm 5.71$ | $62.69\pm 10.90$

Table 8: Exploitability$\times 10^{2}$ for populations generated by PSRO only with RD with varied diversity weight $\lambda_{2}$. $\lambda_{2}$ | $0.5$ | $1.0$ | $5.0$ | $10.0$ | $50.0$
---|---|---|---|---|---
Expl | $16.23\pm 0.48$ | $\mathbf{14.06\pm 1.20}$ | $14.77\pm 0.09$ | $15.60\pm 1.11$ | $31.29\pm 12.93$

####  F.2 Non-Transitive Mixture Model

We report the exploitability of the final population generated by our
algorithm with different $\lambda_{1}$ in Table 7 and $\lambda_{2}$ in Table
8. In this game, we set both $\lambda_{1}$ and $\lambda_{2}$ to decrease
following the rate $1-\frac{0.7}{1+e^{(-0.25(t-25))}}$, where $t$ is the
current iteration. We can find that in terms of exploitability, PSRO with only
BD cannot help the population to achieve lower exploitability.

####  F.3 Google Research Football

We also carry out an ablation study on the weight of RD $\lambda_{2}$ (see
Table 9) in the GRF environment, where we fixed $\lambda_{1}$ to be $0.5$ and
show the results with different $\lambda_{2}$.

Table 9: The win-rate between the final policies of different methods after
trained for 300000 model steps. (We set $\lambda_{1}=\lambda_{2}=0.5$ as
default values for PSRO w. RD and PSRO w. BD&RD)

Method | Self-play | PSRO | PSROrN | PSRO w. BD | PSRO w. RD | PSRO w. BD&RD
---|---|---|---|---|---|---
PSRO w. RD ($\lambda_{2}=1.0$) | $0.62\pm 0.01$ | $0.49\pm 0.03$ | $0.65\pm 0.02$ | $0.47\pm 0.01$ | $0.28\pm 0.04$ | $0.33\pm 0.02$
PSRO w. RD ($\lambda_{2}=0.5$) | $0.68\pm 0.03$ | $\mathbf{0.61\pm 0.02}$ | $\mathbf{0.74\pm 0.03}$ | $0.54\pm 0.02$ | - | $0.43\pm 0.02$
PSRO w. RD ($\lambda_{2}=0.2$) | $0.63\pm 0.02$ | $0.48\pm 0.02$ | $0.68\pm 0.02$ | $0.50\pm 0.01$ | $0.45\pm 0.03$ | $0.28\pm 0.03$
PSRO w. BD&RD | $\mathbf{0.74\pm 0.02}$ | $\mathbf{0.78\pm 0.01}$ | $\mathbf{0.80\pm 0.05}$ | $\mathbf{0.69\pm 0.02}$ | $\mathbf{0.57\pm 0.02}$ | -

Algorithm 3 Optimization for Matrix Games

1: Input: population $\mathfrak{P}_{i}$ for each $i$, meta-game
$\mathbf{A}_{\mathfrak{P_{i}}\times\mathfrak{P_{-i}}}$, weights $\lambda_{1}$
and $\lambda_{2}$, learning rate $\mu$

2: $\sigma_{i},\sigma_{-i}\leftarrow\text{Nash on
}\mathbf{A}_{\mathfrak{P_{i}}\times\mathfrak{P_{-i}}}$

3: $\bm{\pi_{E}}\leftarrow$ Aggregate according to $\sigma_{i},\sigma_{-i}$

4: $\pi_{i}^{\prime}(\theta)\leftarrow$ Initialize a new random policy for
player $i$

5: $\mathbf{BR}_{qual}\leftarrow$ Compute best response against mixture of
opponents $\sum_{k}\sigma_{-i}^{k}\phi_{i}(\cdot,\pi_{-i}^{k})$

6: while the reward $p$ improvement does not meet the threshold do

7: $\mathbf{BR}_{occ}\leftarrow\arg\max_{s_{j}}D_{f}(s_{j}||\pi_{i})$ for each
pure strategy $s_{j}$

8: $\mathbf{BR}\leftarrow$ Choose $\mathbf{BR}=\mathbf{BR}_{occ}$ with
probability $\lambda_{1}$ else $\mathbf{BR}=\mathbf{BR}_{qual}$

9: $\theta\leftarrow\mu\theta+(1-\mu)\theta_{\mathbf{BR}}$

10: $p\leftarrow$ Compute the payoff $p$ after the update according to
$\sum_{k}\sigma_{-i}^{k}\phi_{i}(\pi_{i}^{\prime}(\theta),\pi_{-i}^{k})$

11: end while

12: $\mathbf{BR}_{rew}\leftarrow\arg\max_{s_{j}}F(s_{j})$ for each pure
strategy $s_{j}$ with probability $\lambda_{2}$ else $\mathbf{BR}_{qual}$

13: $\theta\leftarrow\mu\theta+(1-\mu)\theta_{\mathbf{BR}_{rew}}$

14: Output: policy $\pi_{i}^{\prime}(\hat{\theta})$

Algorithm 4 Optimization for Differential Games

1: Input: population $\mathfrak{P}_{i}$ for each $i$, meta-game
$\mathbf{A}_{\mathfrak{P_{i}}\times\mathfrak{P_{-i}}}$, weights $\lambda_{1}$
and $\lambda_{2}$, number of gradient updates $N_{train}$

2: $\sigma_{i},\sigma_{-i}\leftarrow\text{Nash on
}\mathbf{A}_{\mathfrak{P_{i}}\times\mathfrak{P_{-i}}}$

3: $\bm{\pi_{E}}=(\pi_{i},\pi_{E_{-i}})\leftarrow\text{Aggregate according to
}\sigma_{i},\sigma_{-i}$

4: $\pi_{i}^{\prime}(\theta)\leftarrow$ Initialize a new random policy for
player $i$

5: for $j=1$ to $N_{train}$ do

6: $p_{j}\leftarrow$ Compute payoff against the mixture of opponents
$p_{j}=\sum_{k}\sigma_{-i}^{k}\phi_{i}(\pi_{i}^{\prime},\pi_{-i}^{k})$

7: $d_{j}^{\operatorname{occ}}\leftarrow$ Compute BD
$d_{j}^{\operatorname{occ}}=D_{f}(\pi_{i}^{\prime}||\pi_{i})$ as the
$f$-divergence between $\pi_{i}$ and $\pi_{i}^{\prime}$

8: $\mathbf{a}_{j}\leftarrow$ Compute new reward vector as
$\mathbf{a}_{j}=(\phi_{i}(\pi_{i}^{\prime},\pi_{-i}^{k}))_{k=1}^{|\mathfrak{P}_{-i}|}$

9: $d_{j}^{\operatorname{rew}}\leftarrow$ Compute the lower bound of RD as
$F(\mathbf{a}_{j})$ according to Theorem 2

10:
$l_{j}\leftarrow-(p_{j}+\lambda_{1}d_{j}^{\operatorname{occ}}+\lambda_{2}d_{j}^{\operatorname{rew}})$

11: Update $\theta$ to minimize $l_{j}$ by backpropagation

12: end for

13: Output: policy $\pi_{i}^{\prime}(\theta)$

###  Appendix G Simplified Optimization Method for Unified Diverse Response

In Algorithm 1, we have outlined using RL as the optimization oracle for
approximate best response. However, computing best response in real-world
metagames (matrix games) or non-transitive mixture model (differential games)
can be simplified, since the $f$-divergence objective can be simplified
according to Theorem 1 or the reward function $\phi_{i}$ is analytically
accessible. Now we provide the simplified optimization methods separately for
matrix games in Algorithm 3 and differential games in Algorithm 4.

### References

[1] Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom
Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, et al. Impala:
Scalable distributed deep-rl with importance weighted actor-learner
architectures. In International Conference on Machine Learning, pages
1407-1416. PMLR, 2018.

[2] Arpad E Elo. The rating of chessplayers, past and present. Arco Pub. 1978.

[3] Yury Polyanskiy. Definition and basic properties of f-divergences.
http://people.lids.mit.edu/yp/homepage/data/LN_fdiv.pdf

[4] Karol Kurach, Anton Raichuk, Piotr Stanczyk, MichaZajac, Olivier Bachem,
Lasse Espeholt, Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier
Bousquet, et al. Google research football: A novel reinforcement learning
environment. In Proceedings of the AAAI Conference on Articial Intelligence,
volume 34, pages 4501-4510, 2020.