Using Bifurcations for Diversity in Differentiable Games
在可微分博弈中使用分岔实现多样性

In machine learning, optimizing non-convex losses to local minima is critical in a variety of applications. Often, being able to select a specific type of minimum is important such as for policy optimization [1] or to avoid non-transferable features in supervised learning $[2,3]$$[2,3]$[2,3][2,3].
在机器学习中，将非凸损失优化为局部最小值在各种应用中都至关重要。通常，能够选择特定类型的最小值很重要，例如对于策略优化 [1] 或避免监督学习 $[2,3]$$[2,3]$[2,3][2,3] 中的不可转移特征。
However, an increasing number of applications require learning in games, generalizing single objective optimization to settings where each agent controls a different subset of parameters to optimize their own objective. Some examples are GANs [4, 5], actor-critic models [5], curriculum learning [6-9], hyperparameter optimization [10-15], adversarial examples [16, 17], learning models [18-20], domain adversarial adaptation [21], neural architecture search [22-26], multi-agent settings [27] and meta-learning [28-30].
然而，越来越多的应用程序需要在游戏中学习，将单目标优化推广到每个代理控制不同参数子集以优化自己的目标的设置。一些例子是 GAN [4， 5]、演员-评论家模型 [5]、课程学习 [6-9]、超参数优化 [10-15]、对抗性示例 [16， 17]、学习模型 [18-20]、领域对抗性适应 [21]、神经架构搜索 [22-26]、多智能体设置 [27] 和元学习 [28-30]。
There are two major challenges with learning in games: first, the learning dynamics can be unstable due to the nonstationarity induced by simultaneously learning agents, e.g. resulting in cycling dynamics rather than convergence. Second, different equilibria can result in vastly different rewards for the different agents. For example, in the iterated prisoners’ dilemma (Sec. 4.1), finding solutions that favor cooperation vs selfishness result in higher return for all agents; or in Hanabi, finding solutions that do not arbitrarily break
游戏中的学习有两个主要挑战：首先，由于同时学习代理引起的非平稳性，学习动态可能不稳定，例如导致循环动态而不是收敛。其次，不同的均衡会导致不同的主体获得截然不同的回报。例如，在迭代的囚徒困境（第 4.1 节）中，找到有利于合作而不是自私的解决方案会为所有主体带来更高的回报;或者在 Hanabi 中，寻找不会随意打破的解决方案

symmetries results in better coordination with humans [31].
对称性导致与人类的协调性更好[31]。
Recently, Ridge Rider (RR [32]) provided a general method for finding diverse solutions in single objective optimization, by following eigenvectors of the Hessian with negative eigenvalues. We generalize RR to multi-agent settings, each optimizing their own objective. The relevant generalization of the Hessian - the game Hessian - is not symmetric and thus, in general, has complex eigenvalues (EVals) and eigenvectors (EVecs). This leads to new types of bifurcation points, where small changes in initial parameters lead to very different optimization outcomes.
最近，Ridge Rider （RR [32]）提供了一种通用方法，通过遵循具有负特征值的 Hessian 特征向量，在单目标优化中寻找各种解决方案。我们将 RR 推广到多代理设置，每个设置都优化了自己的目标。Hessian 矩阵的相关泛化 - 游戏 Hessian 矩阵 - 不是对称的，因此，通常具有复特征值 （EVals） 和特征向量 （EVecs）。这导致了新型的分叉点，其中初始参数的微小变化会导致非常不同的优化结果。

Our method, Game Ridge Rider (GRR) branches from these novel bifurcation points along the (complex) EVecs to discover diverse solutions in these settings.
我们的方法 Game Ridge Rider （GRR） 从这些沿着（复杂）EVec 的新颖分叉点分支出来，以在这些环境中发现不同的解决方案。

Figure 1. We visualize the Game Ridge Rider (GRR) algorithm when branching at different types of bifurcations. We have two eigenvectors and can branch in opposite directions, so we have four paths displayed in different colors. Steps with the eigenvector have magenta boundaries. Top: For the small Iterated Prisoner’s Dilemma (IPD) finding then branching at the max entropy saddle allows us to find defect-defect and tit-for-tat solutions. Bottom: For the mixed problem of small IPD and matching pennies, branching at the Hopf bifurcation allows us to find both solutions.
图 1.我们在不同类型的分岔处分支时可视化了 Game Ridge Rider （GRR） 算法。我们有两个特征向量，可以向相反的方向分支，因此我们有四条路径以不同的颜色显示。具有特征向量的步骤具有洋红色边界。上图：对于小的迭代囚徒困境 （IPD） 结果，然后在最大熵鞍上分支，我们可以找到缺陷-缺陷和针锋相对的解决方案。下图：对于小 IPD 和匹配便士的混合问题，在 Hopf 分岔处进行分支可以让我们找到两种解决方案。

Appendix Table 2 summarizes our notation. Consider the minimization problem:
附录表 2 总结了我们的符号。考虑最小化问题：

We denote the gradient of the loss at parameters ${\mathit{\theta }}^j$${\mathit{\theta }}^j$theta^(j)\boldsymbol{\theta}^{j} by ${\mathit{g}}^j:=\mathit{g}\left({\mathit{\theta }}^j\right):={{\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}(\mathit{\theta })|}_{{\mathit{\theta }}^j}$${\mathit{g}}^j:=\mathit{g}\left({\mathit{\theta }}^j\right):={\left.{\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}(\mathit{\theta })\right|}_{{\mathit{\theta }}^j}$g^(j):=g(theta^(j)):=grad_(theta)L(theta)|_(theta^(j))\boldsymbol{g}^{j}:=\boldsymbol{g}\left(\boldsymbol{\theta}^{j}\right):=\left.\nabla_{\boldsymbol{\theta}} \mathcal{L}(\boldsymbol{\theta})\right|_{\boldsymbol{\theta}^{j}}. We can locally minimize the loss $\mathcal{L}$$\mathcal{L}$L\mathcal{L} using (stochastic) gradient descent with step size $\alpha$$\alpha$alpha\alpha.
我们用 ${\mathit{g}}^j:=\mathit{g}\left({\mathit{\theta }}^j\right):={{\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}(\mathit{\theta })|}_{{\mathit{\theta }}^j}$${\mathit{g}}^j:=\mathit{g}\left({\mathit{\theta }}^j\right):={\left.{\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}(\mathit{\theta })\right|}_{{\mathit{\theta }}^j}$g^(j):=g(theta^(j)):=grad_(theta)L(theta)|_(theta^(j))\boldsymbol{g}^{j}:=\boldsymbol{g}\left(\boldsymbol{\theta}^{j}\right):=\left.\nabla_{\boldsymbol{\theta}} \mathcal{L}(\boldsymbol{\theta})\right|_{\boldsymbol{\theta}^{j}} 表示 at 参数 ${\mathit{\theta }}^j$${\mathit{\theta }}^j$theta^(j)\boldsymbol{\theta}^{j} 的损失梯度。我们可以使用步长 $\alpha$$\alpha$alpha\alpha 的（随机）梯度下降 来局部最小化损失 $\mathcal{L}$$\mathcal{L}$L\mathcal{L} 。

Due to the potentially non-convex nature of $\mathcal{L}$$\mathcal{L}$L\mathcal{L}, multiple solutions can exist and simply following the gradient will not explore the parameter space.
由于 $\mathcal{L}$$\mathcal{L}$L\mathcal{L} 的潜在非凸性，可以存在多个解决方案，并且仅遵循梯度不会探索参数空间。

Ridge Rider (RR) [32] finds diverse solutions in gradient systems for single-objective minimization. RR first finds a saddle point, and then branches the optimization procedure following different directions (or “ridges”) given by the EVecs of the Hessian $\mathcal{H}={\mathrm{\nabla }}_{\mathit{\theta }}\mathit{g}={\mathrm{\nabla }}_{\mathit{\theta }}\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)$$\mathcal{H}={\mathrm{\nabla }}_{\mathit{\theta }}\mathit{g}={\mathrm{\nabla }}_{\mathit{\theta }}\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)$H=grad_(theta)g=grad_(theta)(grad_(theta)L)\mathcal{H}=\nabla_{\boldsymbol{\theta}} \boldsymbol{g}=\nabla_{\boldsymbol{\theta}}\left(\nabla_{\boldsymbol{\theta}} \mathcal{L}\right). Full computation of $\mathcal{H}$$\mathcal{H}$H\mathcal{H} —and its EVecs and EVals-is often prohibitively expensive; however, we can efficiently access a subset of the eigenspaces in libraries with efficient Hessianvector products $\mathcal{H}\mathit{v}={\mathrm{\nabla }}_{\mathit{\theta }}\left(\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)\mathit{v}\right)$$\mathcal{H}\mathit{v}={\mathrm{\nabla }}_{\mathit{\theta }}\left(\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)\mathit{v}\right)$Hv=grad_(theta)((grad_(theta)L)v)\mathcal{H} \boldsymbol{v}=\nabla_{\boldsymbol{\theta}}\left(\left(\nabla_{\boldsymbol{\theta}} \mathcal{L}\right) \boldsymbol{v}\right) [33-36]. Algorithm 1 summarizes the RR method.
Ridge Rider （RR） [32] 在梯度系统中发现了多种单目标最小化的解决方案。RR 首先找到一个鞍点，然后按照 Hessian $\mathcal{H}={\mathrm{\nabla }}_{\mathit{\theta }}\mathit{g}={\mathrm{\nabla }}_{\mathit{\theta }}\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)$$\mathcal{H}={\mathrm{\nabla }}_{\mathit{\theta }}\mathit{g}={\mathrm{\nabla }}_{\mathit{\theta }}\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)$H=grad_(theta)g=grad_(theta)(grad_(theta)L)\mathcal{H}=\nabla_{\boldsymbol{\theta}} \boldsymbol{g}=\nabla_{\boldsymbol{\theta}}\left(\nabla_{\boldsymbol{\theta}} \mathcal{L}\right) 的 EVecs 给出的不同方向（或“山脊”）对优化过程进行分支。完全计算 $\mathcal{H}$$\mathcal{H}$H\mathcal{H} — 及其 EVec 和 EVals — 通常成本高得令人望而却步;然而，我们可以有效地访问具有高效 Hessianvector 积 $\mathcal{H}\mathit{v}={\mathrm{\nabla }}_{\mathit{\theta }}\left(\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)\mathit{v}\right)$$\mathcal{H}\mathit{v}={\mathrm{\nabla }}_{\mathit{\theta }}\left(\left({\mathrm{\nabla }}_{\mathit{\theta }}\mathcal{L}\right)\mathit{v}\right)$Hv=grad_(theta)((grad_(theta)L)v)\mathcal{H} \boldsymbol{v}=\nabla_{\boldsymbol{\theta}}\left(\left(\nabla_{\boldsymbol{\theta}} \mathcal{L}\right) \boldsymbol{v}\right) 的库中特征空间的子集 [33-36]。流程图 1 总结了 RR 方法。

Instead of simply optimizing a single loss, optimization in games involves multiple agents each with a loss functions that potentially depend on other agents. Examples include multiplayer games (e.g. Go [37, 38] and Hanabi [39]), iterated prisoners’ dilemma (IPD) [40, 41] and generative adversarial networks (GANs) [4]. For simplicity, we look at 2-player games with players denoted by $A$$A$AA and $B$$B$BB. Each player wants to minimize their loss ${\mathcal{L}}_A,{\mathcal{L}}_B$${\mathcal{L}}_A,{\mathcal{L}}_B$L_(A),L_(B)\mathcal{L}_{A}, \mathcal{L}_{B} with their parameters ${\mathit{\theta }}_A\in {\mathbb{R}}^{d_A},{\mathit{\theta }}_B\in {\mathbb{R}}^{d_B}$${\mathit{\theta }}_A\in {\mathbb{R}}^{d_A},{\mathit{\theta }}_B\in {\mathbb{R}}^{d_B}$theta_(A)inR^(d_(A)),theta_(B)inR^(d_(B))\boldsymbol{\theta}_{A} \in \mathbb{R}^{d_{A}}, \boldsymbol{\theta}_{B} \in \mathbb{R}^{d_{B}}.
游戏中的优化不是简单地优化单个损失，而是涉及多个代理，每个代理都有一个可能依赖于其他代理的损失函数。例子包括多人游戏（如围棋 [37， 38] 和 Hanabi [39]）、迭代囚徒困境 （IPD） [40， 41] 和生成对抗网络 （GAN） [4]。为简单起见，我们看一下玩家用 $A$$A$AA 和 $B$$B$BB 表示的 2 人游戏。每个玩家都希望 ${\mathcal{L}}_A,{\mathcal{L}}_B$${\mathcal{L}}_A,{\mathcal{L}}_B$L_(A),L_(B)\mathcal{L}_{A}, \mathcal{L}_{B} 通过他们的 parameters ${\mathit{\theta }}_A\in {\mathbb{R}}^{d_A},{\mathit{\theta }}_B\in {\mathbb{R}}^{d_B}$${\mathit{\theta }}_A\in {\mathbb{R}}^{d_A},{\mathit{\theta }}_B\in {\mathbb{R}}^{d_B}$theta_(A)inR^(d_(A)),theta_(B)inR^(d_(B))\boldsymbol{\theta}_{A} \in \mathbb{R}^{d_{A}}, \boldsymbol{\theta}_{B} \in \mathbb{R}^{d_{B}} .

If ${\mathcal{L}}_B$${\mathcal{L}}_B$L_(B)\mathcal{L}_{B} and ${\mathcal{L}}_A$${\mathcal{L}}_A$L_(A)\mathcal{L}_{A} are differentiable in ${\mathit{\theta }}_B$${\mathit{\theta }}_B$theta_(B)\boldsymbol{\theta}_{B} and ${\mathit{\theta }}_A$${\mathit{\theta }}_A$theta_(A)\boldsymbol{\theta}_{A} we say the game is differentiable. Unfortunately, for a player to do gradient based optimization of their objective we must compute $d{\mathcal{L}}_B^{\ast }/d{\mathit{\theta }}_B$$d{\mathcal{L}}_B^{\ast }/d{\mathit{\theta }}_B$dL_(B)^(**)//dtheta_(B)d \mathcal{L}_{B}^{*} / d \boldsymbol{\theta}_{B} which often requires $d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$$d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$dtheta_(A)^(**)//dtheta_(B)d \boldsymbol{\theta}_{A}^{*} / d \boldsymbol{\theta}_{B}, but ${\mathit{\theta }}_A^{\ast }\left({\mathit{\theta }}_B\right)$${\mathit{\theta }}_A^{\ast }\left({\mathit{\theta }}_B\right)$theta_(A)^(**)(theta_(B))\boldsymbol{\theta}_{A}^{*}\left(\boldsymbol{\theta}_{B}\right) and its Jacobian are typically intractable. There are various algorithms to try to find solutions like Eq. 2, often efficiently approximating $d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$$d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$dtheta_(A)^(**)//dtheta_(B)d \boldsymbol{\theta}_{A}^{*} / d \boldsymbol{\theta}_{B} with a method rely on efficient Jacobian-vector products. We overview these in our related work (Appendix A).
如果 ${\mathcal{L}}_B$${\mathcal{L}}_B$L_(B)\mathcal{L}_{B} 和 ${\mathcal{L}}_A$${\mathcal{L}}_A$L_(A)\mathcal{L}_{A} 是可微的， ${\mathit{\theta }}_B$${\mathit{\theta }}_B$theta_(B)\boldsymbol{\theta}_{B} ${\mathit{\theta }}_A$${\mathit{\theta }}_A$theta_(A)\boldsymbol{\theta}_{A} 我们说博弈是可微的。不幸的是，对于玩家来说，要对他们的目标进行基于梯度的优化，我们必须计算 $d{\mathcal{L}}_B^{\ast }/d{\mathit{\theta }}_B$$d{\mathcal{L}}_B^{\ast }/d{\mathit{\theta }}_B$dL_(B)^(**)//dtheta_(B)d \mathcal{L}_{B}^{*} / d \boldsymbol{\theta}_{B} ，这通常需要 $d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$$d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$dtheta_(A)^(**)//dtheta_(B)d \boldsymbol{\theta}_{A}^{*} / d \boldsymbol{\theta}_{B} ，但 ${\mathit{\theta }}_A^{\ast }\left({\mathit{\theta }}_B\right)$${\mathit{\theta }}_A^{\ast }\left({\mathit{\theta }}_B\right)$theta_(A)^(**)(theta_(B))\boldsymbol{\theta}_{A}^{*}\left(\boldsymbol{\theta}_{B}\right) 其雅可比矩阵通常很难处理。有各种算法可以尝试找到像方程 2 这样的解， $d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$$d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$dtheta_(A)^(**)//dtheta_(B)d \boldsymbol{\theta}_{A}^{*} / d \boldsymbol{\theta}_{B} 通常使用依赖于高效雅可比向量积的方法进行有效近似。我们在相关工作（附录 A）中概述了这些内容。

One of the most straightforward optimization methods is to find local solutions with simultaneous SGD (SimSGD). This does not take into account $d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$$d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$dtheta_(A)^(**)//dtheta_(B)d \boldsymbol{\theta}_{A}^{*} / d \boldsymbol{\theta}_{B} and often fails to converge. Here, ${\mathit{g}}_A^j:={\mathit{g}}_A({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j)$${\mathit{g}}_A^j:={\mathit{g}}_A\left({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j\right)$g_(A)^(j):=g_(A)(theta_(A)^(j),theta_(B)^(j))\boldsymbol{g}_{A}^{j}:=\boldsymbol{g}_{A}\left(\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}\right) and ${\mathit{g}}_B^j:={\mathit{g}}_B({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j)$${\mathit{g}}_B^j:={\mathit{g}}_B\left({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j\right)$g_(B)^(j):=g_(B)(theta_(A)^(j),theta_(B)^(j))\boldsymbol{g}_{B}^{j}:=\boldsymbol{g}_{B}\left(\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}\right) are estimators for ${{\mathrm{\nabla }}_{{\mathit{\theta }}_A}{\mathcal{L}}_A|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$${\left.{\mathrm{\nabla }}_{{\mathit{\theta }}_A}{\mathcal{L}}_A\right|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$grad_(theta_(A))L_(A)|_(theta_(A)^(j),theta_(B)^(j))\left.\nabla_{\boldsymbol{\theta}_{A}} \mathcal{L}_{A}\right|_{\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}} and ${{\mathrm{\nabla }}_{{\mathit{\theta }}_B}{\mathcal{L}}_B|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$${\left.{\mathrm{\nabla }}_{{\mathit{\theta }}_B}{\mathcal{L}}_B\right|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$grad_(theta_(B))L_(B)|_(theta_(A)^(j),theta_(B)^(j))\left.\nabla_{\boldsymbol{\theta}_{B}} \mathcal{L}_{B}\right|_{\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}} :
最直接的优化方法之一是找到具有同步 SGD （SimSGD） 的局部解。这没有考虑到 $d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$$d{\mathit{\theta }}_A^{\ast }/d{\mathit{\theta }}_B$dtheta_(A)^(**)//dtheta_(B)d \boldsymbol{\theta}_{A}^{*} / d \boldsymbol{\theta}_{B} ，而且经常无法收敛。这里， ${\mathit{g}}_A^j:={\mathit{g}}_A({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j)$${\mathit{g}}_A^j:={\mathit{g}}_A\left({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j\right)$g_(A)^(j):=g_(A)(theta_(A)^(j),theta_(B)^(j))\boldsymbol{g}_{A}^{j}:=\boldsymbol{g}_{A}\left(\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}\right) 和 ${\mathit{g}}_B^j:={\mathit{g}}_B({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j)$${\mathit{g}}_B^j:={\mathit{g}}_B\left({\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j\right)$g_(B)^(j):=g_(B)(theta_(A)^(j),theta_(B)^(j))\boldsymbol{g}_{B}^{j}:=\boldsymbol{g}_{B}\left(\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}\right) 是 和 ${{\mathrm{\nabla }}_{{\mathit{\theta }}_B}{\mathcal{L}}_B|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$${\left.{\mathrm{\nabla }}_{{\mathit{\theta }}_B}{\mathcal{L}}_B\right|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$grad_(theta_(B))L_(B)|_(theta_(A)^(j),theta_(B)^(j))\left.\nabla_{\boldsymbol{\theta}_{B}} \mathcal{L}_{B}\right|_{\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}} 的 ${{\mathrm{\nabla }}_{{\mathit{\theta }}_A}{\mathcal{L}}_A|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$${\left.{\mathrm{\nabla }}_{{\mathit{\theta }}_A}{\mathcal{L}}_A\right|}_{{\mathit{\theta }}_A^j,{\mathit{\theta }}_B^j}$grad_(theta_(A))L_(A)|_(theta_(A)^(j),theta_(B)^(j))\left.\nabla_{\boldsymbol{\theta}_{A}} \mathcal{L}_{A}\right|_{\boldsymbol{\theta}_{A}^{j}, \boldsymbol{\theta}_{B}^{j}} 估计量：

We simplify notation by using the concatenation of all players parameters (or joint-parameters) $\mathit{\omega }:=[{\mathit{\theta }}_A,{\mathit{\theta }}_B]\in {\mathbb{R}}^d$$\mathit{\omega }:=\left[{\mathit{\theta }}_A,{\mathit{\theta }}_B\right]\in {\mathbb{R}}^d$omega:=[theta_(A),theta_(B)]inR^(d)\boldsymbol{\omega}:=\left[\boldsymbol{\theta}_{A}, \boldsymbol{\theta}_{B}\right] \in \mathbb{R}^{d} and the joint-gradient vector field $\hat{\mathit{g}}:{\mathbb{R}}^d\to {\mathbb{R}}^d$$\widehat{\mathit{g}}:{\mathbb{R}}^d\to {\mathbb{R}}^d$hat(g):R^(d)rarrR^(d)\hat{\boldsymbol{g}}: \mathbb{R}^{d} \rightarrow \mathbb{R}^{d}, which at the $j^{\text{th}}$$j^{\text{th }}$j^("th ")j^{\text {th }} iteration is denoted:
我们通过使用所有玩家参数（或联合参数） $\mathit{\omega }:=[{\mathit{\theta }}_A,{\mathit{\theta }}_B]\in {\mathbb{R}}^d$$\mathit{\omega }:=\left[{\mathit{\theta }}_A,{\mathit{\theta }}_B\right]\in {\mathbb{R}}^d$omega:=[theta_(A),theta_(B)]inR^(d)\boldsymbol{\omega}:=\left[\boldsymbol{\theta}_{A}, \boldsymbol{\theta}_{B}\right] \in \mathbb{R}^{d} 和联合梯度向量场 $\hat{\mathit{g}}:{\mathbb{R}}^d\to {\mathbb{R}}^d$$\widehat{\mathit{g}}:{\mathbb{R}}^d\to {\mathbb{R}}^d$hat(g):R^(d)rarrR^(d)\hat{\boldsymbol{g}}: \mathbb{R}^{d} \rightarrow \mathbb{R}^{d} 的串联来简化符号，在迭代时 $j^{\text{th}}$$j^{\text{th }}$j^("th ")j^{\text {th }} 表示为：

We can write the next iterate in (SimSGD) with a fixed-point operator ${\mathit{F}}_{\alpha }$${\mathit{F}}_{\alpha }$F_(alpha)\boldsymbol{F}_{\alpha} :
我们可以使用定点运算符 ${\mathit{F}}_{\alpha }$${\mathit{F}}_{\alpha }$F_(alpha)\boldsymbol{F}_{\alpha} 编写下一次迭代 （SimSGD）：

The Jacobian of the fixed point operator ${\mathit{F}}_{\alpha }$${\mathit{F}}_{\alpha }$F_(alpha)\boldsymbol{F}_{\alpha} is useful for analysis, including bounding convergence rates near fixed points and finding points where local changes to parameters may cause convergence to qualitatively different solutions. The fixed point operator’s Jacobian crucially depends on the Jacobian of our update $\hat{\mathit{g}}$$\widehat{\mathit{g}}$hat(g)\hat{\boldsymbol{g}}. When our update is the gradient, we call this the game Hessian because it generalizes the Hessian:
不动点运算符 ${\mathit{F}}_{\alpha }$${\mathit{F}}_{\alpha }$F_(alpha)\boldsymbol{F}_{\alpha} 的雅可比矩阵可用于分析，包括固定点附近的边界收敛速率，以及查找参数的局部更改可能导致收敛到定性不同的解的点。定点运算符的雅可比行列式在很大程度上取决于我们更新的 $\hat{\mathit{g}}$$\widehat{\mathit{g}}$hat(g)\hat{\boldsymbol{g}} 雅可比行列式。当我们的更新是梯度时，我们将其称为游戏 Hessian，因为它泛化了 Hessian：

For single-objective optimization $\hat{\mathcal{H}}$$\widehat{\mathcal{H}}$hat(H)\hat{\mathcal{H}} is the Hessian of the loss, which is symmetric and has real EVals yielding parameter updates which form a conservative gradient vector field. However, in games with multiple objectives, $\hat{\mathcal{H}}$$\widehat{\mathcal{H}}$hat(H)\hat{\mathcal{H}} is not symmetric and can have complex Evals, resulting in updates which form a non-conservative vector field.
对于单目标优化 $\hat{\mathcal{H}}$$\widehat{\mathcal{H}}$hat(H)\hat{\mathcal{H}} ，损失的 Hessian 矩阵是对称的，并且具有真正的 EVals 产生参数更新，从而形成一个保守的梯度向量场。但是，在具有多个目标的游戏中， $\hat{\mathcal{H}}$$\widehat{\mathcal{H}}$hat(H)\hat{\mathcal{H}} 不是对称的，并且可能具有复杂的 Evals，从而导致形成非保守向量场的更新。

The goal of RR was to obtain a method for finding diverse solutions in minimization. There are multiple ways to try to find solutions with RR, but we focus on finding separatrices -i.e., boundaries between phase space regions with different dynamical behavior. Crossing such boundaries leads to different solutions under our updates flow-and branching over these boundaries. Such a behavior of crossing regions and changing behavior is in fact a local bifurcations and a qualitative change in the behavior of the solutions.
RR 的目标是获得一种在最小化中寻找各种解的方法。有多种方法可以尝试用 RR 找到解，但我们专注于寻找分离——即具有不同动力学行为的相空间区域之间的边界。跨越这些边界会导致我们的更新流程下出现不同的解决方案，并跨越这些边界。这种跨越区域和改变行为的行为实际上是局部分叉和解行为的质变。

When applying RR in conservative gradient systems, saddle points and their EVecs play a key role in the shape of the phase portraits, which are a geometrical representation of the underlying dynamics. The negative EVecs often align with unstable manifolds that are orthogonal to our separatrices [42], thus giving directions in which we can perturb to find different solutions (Lemma 14.3 [43]). However, in non-conservative systems there are a variety of other local bifurcations [44] besides saddle points [45]. For example, by Thm. 11.2 of [43] if all EVals of have negative real part, except a conjugate non-zero pair of purely imaginary EVals, then a Hopf bifurcation occurs when changing the parameters causing the pair to cross the imaginary axis. A Hopf bifurcation is a critical point where the stability of a system switches resulting in a periodic solution.
在保守梯度系统中应用 RR 时，鞍点及其 EVec 在相位图的形状中起着关键作用，相位图是潜在动力学的几何表示。负 EVec 通常与与我们的分离正交的不稳定流形对齐 [42]，从而给出我们可以扰动以找到不同解的方向（引理 14.3 [43]）。然而，在非保守系统中，除了鞍点[45]之外，还有各种其他局部分叉[44]。例如，根据 [43] 的 Thm. 11.2，如果所有 的 EVal 都具有负实部，除了一对共轭非零的纯虚部 EVal，那么当改变参数导致对穿过虚轴时，就会发生 Hopf 分叉。Hopf 分岔是系统稳定性切换的关键点，导致周期性解。

In this section we introduce Game Ridge Rider (GRR), a generalization of Game Ridge Rider for learning in games. $RR$$RR$RRR R is not immediately applicable to complex EVals of the Hessian, because we would need to follow the complex EVecs, resulting in complex weights, and we may need to branch at points besides saddles. When the Hessian has real EVals, GRR is equivalent to RR.
在本节中，我们将介绍 Game Ridge Rider （GRR），这是 Game Ridge Rider 在游戏中学习的泛化。 $RR$$RR$RRR R 不能立即应用于 Hessian 的复 EVal，因为我们需要遵循复 EVec，从而产生复权重，并且我们可能需要在除 saddes 之外的点处进行分支。当 Hessian 矩阵具有实 EVals 时，GRR 等效于 RR。
Consider the framework for the RR method in Alg 1. We modify the components of GetRidges and EndRide, along with a proposed starting saddle. We also add a method for running different optimizers after branching with Evecs.
考虑 Alg 1 中 RR 方法的框架。我们修改了 GetRidges 和 EndRide 的组件，以及建议的起始鞍座。我们还添加了一个方法，用于在使用 Evecs 分支后运行不同的优化器。

GetRidges finds which EVals and EVecs we should explore from a given branching point. The EVecs of a matrix are not unique in-general, and may have complex entries for complex EVals. We only want real-valued updates when following our EVecs, so we select the choices with largest real part and norm one-this is the default in PyTorch [35]. For a conjugate pair of complex EVals, this selection of EVecs corresponds to spanning the (real-valued) plane that we would rotate in under repeated matrix multiplication of the EVec. This also specifies the order in which we explore the EVals, which we set to be the most negative EVals first. Note that we can explore in opposite directions along each negative EVec.
GetRidges 查找我们应该从给定分支点探索哪些 EVals 和 EVec。矩阵的 EVec 通常不是唯一的，并且可能具有复杂 EVal 的复杂条目。在遵循 EVec 时，我们只希望有实值更新，因此我们选择具有最大实部和范数 1 的选项——这是 PyTorch 中的默认值 [35]。对于一对复数 EVal 的共轭，这种 EVec 的选择对应于跨越我们在 EVec 的重复矩阵乘法下旋转的（实值）平面。这也指定了我们探索 EVals 的顺序，我们首先将其设置为最负的 EVals。请注意，我们可以沿着每个负 EVec 沿相反的方向进行探索。

EndRide is a heuristic that determines how long we follow an EVec. We experiment with stopping after a single step and stopping when the real part of the EVal goes from negative to zero. If we have noisy EVecs estimates, or we are not exactly at a separatrix, we may need to take multiple steps to find different solutions. We can attempt to find Hopf bifurcations by ending and branching when a complex EVals crosses the imaginary axis.
EndRide 是一种启发式方法，用于确定我们跟踪 EVec 的时间。我们尝试在单个步骤后停止，并在 EVal 的实部从负数变为零时停止。如果我们有嘈杂的 EVecs 估计，或者我们并不完全处于分离状态，我们可能需要采取多个步骤来找到不同的解决方案。当复 EVals 穿过虚轴时，我们可以尝试通过结束和分支来找到 Hopf 分叉。

Optimize is a method which runs an optimization procedure. In this work we explore following gradients SimSGD or LOLA [27] with user specified optimization parameters.
Optimize 是一种运行优化过程的方法。在这项工作中，我们探索了以下梯度 SimSGD 或 LOLA [27] 以及用户指定的优化参数。

Starting location ( ${\omega }^{\text{Saddle}}$${\omega }^{\text{Saddle }}$omega^("Saddle ")\omega^{\text {Saddle }} ) We start our method at some some ${\mathit{\omega }}^{\text{Saddle}}=\arg \underset{\mathit{\omega }}{min}|\hat{\mathit{g}}|$${\mathit{\omega }}^{\text{Saddle }}=\arg \underset{\mathit{\omega }}{min} |\widehat{\mathit{g}}|$omega^("Saddle ")=arg min_(omega)| hat(g)|\boldsymbol{\omega}^{\text {Saddle }}=\arg \min _{\boldsymbol{\omega}}|\hat{\boldsymbol{g}}|. There are often multiple saddles we can begin at, so for multi-agent Tabular RL - like the IPD - we heuristically begin at the maximum entropy saddle $\arg \underset{\mathit{\omega }}{min}|\hat{\mathit{g}}|-\beta H({\pi }_{\mathit{\omega }}(\mathit{a})),\beta >0$$\arg \underset{\mathit{\omega }}{min} |\widehat{\mathit{g}}|-\beta H\left({\pi }_{\mathit{\omega }}(\mathit{a})\right),\beta >0$arg min_(omega)| hat(g)|-beta H(pi_(omega)(a)),beta > 0\arg \min _{\boldsymbol{\omega}}|\hat{\boldsymbol{g}}|-\beta H\left(\pi_{\boldsymbol{\omega}}(\boldsymbol{a})\right), \beta>0 as in [32].
起始位置 （ ${\omega }^{\text{Saddle}}$${\omega }^{\text{Saddle }}$omega^("Saddle ")\omega^{\text {Saddle }} ） 我们从某个 . ${\mathit{\omega }}^{\text{Saddle}}=\arg \underset{\mathit{\omega }}{min}|\hat{\mathit{g}}|$${\mathit{\omega }}^{\text{Saddle }}=\arg \underset{\mathit{\omega }}{min} |\widehat{\mathit{g}}|$omega^("Saddle ")=arg min_(omega)| hat(g)|\boldsymbol{\omega}^{\text {Saddle }}=\arg \min _{\boldsymbol{\omega}}|\hat{\boldsymbol{g}}| 我们通常可以从多个鞍座开始，因此对于多代理表格 RL - 如 IPD - 我们启发式地从最大熵鞍开始， $\arg \underset{\mathit{\omega }}{min}|\hat{\mathit{g}}|-\beta H({\pi }_{\mathit{\omega }}(\mathit{a})),\beta >0$$\arg \underset{\mathit{\omega }}{min} |\widehat{\mathit{g}}|-\beta H\left({\pi }_{\mathit{\omega }}(\mathit{a})\right),\beta >0$arg min_(omega)| hat(g)|-beta H(pi_(omega)(a)),beta > 0\arg \min _{\boldsymbol{\omega}}|\hat{\boldsymbol{g}}|-\beta H\left(\pi_{\boldsymbol{\omega}}(\boldsymbol{a})\right), \beta>0 如 [32]。
The other components of ChooseFromArchive and UpdateRidge we did not change, but summarize below. See RR [32] for more details on their implementations.
我们没有更改 ChooseFromArchive 和 UpdateRidge 的其他组件，但总结如下。有关其实施方式的更多详细信息，请参见RR [32]。

ChooseFromArchive gives a search order on optimization branches - ex., BFS or DFS - by outputting an index to search and the updated archive of optimization branches.
ChooseFromArchive 通过输出要搜索的索引和优化分支的更新存档，在优化分支（例如 BFS 或 DFS）上提供搜索顺序。

UpdateRidge updates the currently followed EVec which potentially changed due to the optimization step.
UpdateRidge 会更新当前关注的 EVec，该 EVec 可能会因优化步骤而更改。

Algorithm 1 Game Ridge Rider (GRR)-red modifications
    Input: \(\boldsymbol{\omega}^{\text {Saddle }}, \alpha\), ChooseFromArchive, GetRidges,
            EndRide, Optimize, UpdateRidge
    \(\mathcal{A}=\operatorname{GetRidges}\left(\omega^{\text {Saddle }}\right) \quad\) \# Init. Archive
    while Archive \(\mathcal{A}\) non-empty do
        \(j, \mathcal{A}=\) ChooseFromArchive \((\mathcal{A})\)
        \(\left(\boldsymbol{\omega}^{j}, e_{j}, \lambda_{j}\right)=\mathcal{A}_{j}\)
        while EndRide \(\left(\boldsymbol{\omega}^{j}, e_{j}, \lambda_{j}\right)\) not True do
            \(\boldsymbol{\omega}^{i} \leftarrow \boldsymbol{\omega}^{j}-\alpha e_{j} \quad\) \# Step along the ridge \(e_{j}\)
            \(e_{j}, \lambda_{j}=\operatorname{UpdateRidge}\left(\boldsymbol{\omega}^{j}, e_{j}, \lambda_{j}\right)\)
        \(\boldsymbol{\omega}^{j}=\) Optimize \(\left(\boldsymbol{\omega}^{j}\right)\)
        \(\mathcal{A}=\mathcal{A} \cup \operatorname{GetRidges}\left(\boldsymbol{\omega}^{j}\right) \quad\) \# Add new ridges

We investigate using Game Ridge Rider on multi-agent learning problems. First, we make a range of twodimensional games, allowing us to qualitatively study new phenomena that occur in multi-agent settings. Next, we look at a higher dimensional experiment of learning strategies in the iterated prisoners’ dilemma (IPD). Our method is able to find a diverse set of solutions improving on baselines.
我们研究了使用 Game Ridge Rider 解决多智能体学习问题。首先，我们制作了一系列二维游戏，使我们能够定性地研究在多智能体设置中出现的新现象。接下来，我们着眼于迭代囚徒困境 （IPD） 中学习策略的更高维实验。我们的方法能够找到一组不同的解决方案来改进基线。

Our test problems described in full detail in Appendix Section B. 1 and summarized here. We visualize the strategy space for 2-parameter problems in Appendix Fig. 3.
我们的测试问题在附录 B. 1 节中进行了详细描述，并在此处进行了总结。我们在附录图 3 中可视化了 2 参数问题的策略空间。
Iterated Prisoners’ Dilemma (IPD): This game is an infinite sequence of the Prisoner’s Dilemma, where the future payoff is discounted by a factor $\gamma \in [0,1)$$\gamma \in [0,1)$gamma in[0,1)\gamma \in[0,1). Each agent is conditioned on the actions in the prior state, so there are 5 parameters for each agent - i.e., the probability of cooperating at start state or given both agents preceding actions. We interested in two Nash equilibria: Defect-Defect (DD) where agents are selfish (giving a poor reward), and tit-fortat (TT) where agents initially cooperate, then copy the opponents action (giving a higher reward).
迭代囚徒困境 （IPD）：这个游戏是囚徒困境的无限序列，其中未来的收益被贴现了一个因子 $\gamma \in [0,1)$$\gamma \in [0,1)$gamma in[0,1)\gamma \in[0,1) 。每个代理都以先前状态中的动作为条件，因此每个代理都有 5 个参数 - 即，在开始状态下合作的概率或给定两个代理在动作之前的概率。我们对两个纳什均衡感兴趣：缺陷-缺陷 （DD），其中代理是自私的（给予糟糕的奖励），以及 tit-fortat （TT），其中代理最初合作，然后复制对手的行动（给予更高的奖励）。
Small IPD: A is a 2-parameter simplification of IPD, which allows DD and TT Nash equilibria. This game allows us to visualize some of the optimization difficulties for the full-scale IPD, however, the game Hessian has strictly real EVals unlike the full-scale IPD.
小 IPD：A 是 IPD 的 2 参数简化，它允许 DD 和 TT 纳什均衡。该游戏允许我们可视化全尺寸 IPD 的一些优化难点，但是，与全尺寸 IPD 不同，Hessian 游戏具有严格的真实 EVals。

Matching Pennies: This is a simplified 2-parameter version of rock-paper scissors. The first player wins if they select the same, while the second player wins if they select different. This game has a Nash equilibrium where each player selects their action with uniform probability. This problem’s game Hessian has purely imaginary EVals unlike the small IPD, but only has a single solution and thus is a poor fit for evaluating RR which finds diversity of solutions.
Matching Pennies（匹配便士）：这是石头布剪刀的简化 2 参数版本。如果第一个玩家选择相同，则他们获胜，而第二个玩家如果选择不同，则获胜。这个游戏有一个纳什均衡，每个玩家都以均匀的概率选择他们的行动。与小 IPD 不同，这个问题的游戏 Hessian 具有纯虚的 EVals，但只有一个解，因此不适合评估找到解多样性的 RR。
Mixing Small IPD and Matching Pennies: This game interpolates between the Small IPD and matching pennies games with an interpolation factor $\tau \in [0,1]$$\tau \in [0,1]$tau in[0,1]\tau \in[0,1]. If $\tau =.25$$\tau =.25$tau=.25\tau=.25
混合小 IPD 和匹配便士：此游戏使用插值因子 $\tau \in [0,1]$$\tau \in [0,1]$tau in[0,1]\tau \in[0,1] 在小 IPD 和匹配便士游戏之间进行插值。如果 $\tau =.25$$\tau =.25$tau=.25\tau=.25