强化学习中的自博弈方法

摘要

摘要——自博弈（Self-play）指的是代理与其自身的副本或过去的版本进行交互，这一概念在最近的强化学习研究中引起了广泛关注。本文首先阐明了自博弈的相关基础知识，包括多智能体强化学习框架和基本的博弈论概念。然后，本文提出了一个统一的框架，并在此框架下对现有的自博弈算法进行分类。此外，本文通过展示自博弈在不同场景中的作用，缩小了算法与其实践应用之间的差距。最后，本文强调了自博弈领域中的开放挑战和未来的研究方向。这篇论文为理解强化学习中多层面的自博弈领域提供了一个重要的指南。

I. 引言

强化学习（Reinforcement Learning, RL）是机器学习中的一个重要范式，其核心是通过与环境的交互来优化决策过程。RL 基本上是通过马尔可夫决策过程（Markov Decision Process, MDP）进行建模的，这是一个描述环境中状态、动作、状态转移和奖励的数学框架。在 MDP 中，智能体通过观察状态、根据定义的策略执行动作、接收相应的奖励，并过渡到下一个状态。RL 算法的主要目标是推导出最优策略，以在长期内实现最大化预期累积奖励。深度强化学习（Deep RL）通过使用深度神经网络作为函数逼近器扩展了传统的 RL。深度学习与 RL 的结合在处理高维状态空间方面发挥了关键作用，推动了许多复杂任务中的突破性进展。

此外，从单智能体到多智能体强化学习（Multi-Agent Reinforcement Learning, MARL）的转变引入了复杂的动态过程。在 MARL 中，智能体动作的相互依赖性带来了重大挑战，因为每个智能体所感知的环境对其而言都是非静态的。MARL 的主要问题包括协调、通信和均衡选择，特别是在竞争性场景中。这些挑战通常会导致在实现收敛、保持稳定性以及高效探索解决方案空间方面遇到困难。

借助博弈论——一种用于建模多个决策者互动的数学框架，自博弈作为解决 MARL 固有挑战的一种优雅方法出现。通过解决非静态性和协调问题，自博弈提供了一种让智能体与其自身的副本或过去版本互动的方式。这种方法承诺提供一个更稳定和可管理的学习过程。自博弈的能力扩展到了广泛的场景中，包括围棋、国际象棋、扑克以及视频游戏等领域，在这些场景中，它开发出了超越人类专家的策略。尽管自博弈的应用非常广泛且充满前景，但也伴随着一些局限性，例如可能收敛到次优策略以及显著的计算要求。

尽管一些研究通过经验博弈论分析（EGTA）提供了广泛的视角，但专注于自博弈的综合性综述却相对较少。其中，一些研究关注自博弈的理论安全性，而另一些则开发了自博弈的算法框架，但不幸的是，未能涵盖策略空间响应预言机（PSRO）系列算法。此外，还有一项研究专注于 PSRO。虽然这些不同的研究都有价值，但它们并没有提供能够全面捕捉自博弈广度和深度的视角。因此，本综述旨在弥合这一空白。

本文综述的组织结构如下：

• 第二部分介绍了自博弈的背景，包括 RL 框架和基本博弈论概念。
• 第三部分提出了一个统一的框架，并根据此框架将现有的自博弈算法分为四类，阐明了自博弈的全貌。
• 第四部分进行综合分析，展示自博弈如何应用于各种场景。
• 第五部分描述了自博弈中存在的开放问题，并探讨了未来的研究方向。
• 第六部分总结了对自博弈的综述。

II. 预备知识

A. 强化学习框架

在马尔可夫决策过程（Markov Decision Process, MDPs）中，智能体通过采取行动与环境互动，导致不同的状态以及与之相关的奖励。马尔可夫假设认为系统的演变完全由其当前状态决定，无需考虑历史状态。MDPs 可以扩展到多智能体设置，称为马尔可夫博弈（Markov Games），也称为随机博弈（Stochastic Games）。我们考虑最一般的形式：部分可观察马尔可夫博弈（Partially Observable Markov Games, POMGs），这指的是涉及多个智能体的场景，每个智能体无法访问环境的完整状态。相反，他们获得与环境相关的个体观察。一个 POMG $G$ 可以定义为 $G = (N, S, A, O, P, R, \gamma, \rho)$。$N = {1, \cdots, n}$ 表示 $n$ 个智能体。$S$ 是状态空间。$A = \prod_{i=1}^{n} A_i$ 是每个智能体的动作空间的乘积。类似地，$O = \prod_{i=1}^{n} O_i$ 是每个智能体的观察空间的乘积。$P : S \times A \times S \rightarrow [0, 1]$ 表示在给定每个智能体的动作的情况下，从一个状态转移到另一个状态的转移概率。$R = {R_1, \cdots, R_n}$，其中 $R_i : S \times A_i \rightarrow \mathbb{R}$ 表示智能体 $i$ 的奖励函数。$\gamma \in [0, 1]$ 是折扣因子。$\rho : S \rightarrow [0, 1]$ 描述初始状态分布。注意，如果是合作 MARL 问题，智能体可以共享相同的奖励函数。特别是当 $n = 1$ 时，$O_i = S$，环境设置返回到简单的 MDP。

在 RL 背景下，智能体根据以下协议与环境互动：在每个离散时间步 $t$，每个智能体 $i$ 从环境中接收观察 $o_{i,t}$ 并根据随机策略 $\pi_{\theta_i} : O_i \times A_i \rightarrow [0, 1]$ 选择动作，其中 $\theta_i$ 是参数。在接收到联合动作 $a_t = (a_{1,t}, \cdots, a_{n,t})$ 后，环境根据转移函数 $P$ 从当前状态 $s_t$ 转换到后续状态 $s_{t+1}$ 并向每个智能体 $i$ 发送奖励 $r_{i,t+1}$。智能体 $i$ 的最终目标是最大化预期折扣累积奖励：$$ \mathbb{E}^{\pi_{\theta_i} } \left[ \sum_{t=0}^{\infty} \gamma^t r_{i,t} \right] $$。

B. 博弈论概念

完美信息与不完美信息

在完美信息的游戏中，每次只有一个玩家行动。每个玩家对当前游戏状态、已经进行的所有动作的完整历史以及所有可能的未来变化都有完全的了解。如果没有满足这些条件，游戏就被认为是具有不完美信息的。在不完全信息的游戏中，至少有一个玩家不知道其他玩家的收益；否则，它是一个完全信息的游戏。

例如，围棋是一个既完美又完全信息的游戏。玩家对整个游戏结构有完全的了解，包括所有可能的走法，并且他们可以看到对手的每一个动作（完美信息）。此外，如果结果被认为是二元的，比如赢或输，那么玩家的收益对双方都是已知的（完全信息）。

正规形式与扩展形式

正规形式和扩展形式是博弈论中表示游戏的两种不同方式。如果一个游戏 $G $ 用正规形式表示，它可以表示为 $G = (N, \Pi, u) $。$N = {1, 2, \cdots, n} $ 表示玩家。$\Pi = \Pi_1 \times \cdots \times \Pi_n $ 是所有玩家的纯策略空间。向量 $\pi = (\pi_1, \cdots, \pi_n) \in \Pi $ 被称为策略配置。纯策略为玩家在游戏中的特定和确定性动作，而混合策略是在纯策略集合上的概率分布，允许随机动作。玩家 $i $ 的混合策略是概率分布 $\sigma_i \in \Delta(\Pi_i) $，其中 $\Delta $ 是一个概率单纯形。$u = (u_1, \cdots, u_n) $，其中 $u_i : \Pi \rightarrow \mathbb{R} $，是为每个玩家 $i $ 分配实数值收益的效用函数。如果对于所有 $\pi \in \Pi $，$\sum_{i} u_i(\pi) = 0 $，游戏是零和游戏，否则它是一般和游戏。如果 $\Pi_1 = \cdots = \Pi_n $ 并且收益在玩家策略的任何排列下都是不变的，游戏是对称的。如果涉及有限玩家（尤其是两名玩家），并且每个玩家都有有限的策略集合，正规形式的游戏可以直接用矩阵表示。

具体来说，在两名玩家的零和对称正规形式游戏中，玩家 1 和玩家 2 的纯策略空间是相同的，表示为 $\Pi $，使得 $\Pi = \Pi_1 = \Pi_2 $。由于效用函数 $u_1(\pi_i, \pi_j) = -u_2(\pi_i, \pi_j) $，我们可以简单地使用一个效用函数 $u $ 表示，对于所有 $\pi_i, \pi_j \in \Pi $，如果 $\pi_i $ 击败 $\pi_j $，则 $u(\pi_i, \pi_j) = -u(\pi_j, \pi_i) > 0 $。评估矩阵通过详细说明不同策略相互对抗的结果来捕捉游戏的结果：$A_{\Pi} = {u(\pi_i, \pi_j) : \pi_i, \pi_j \in \Pi \times \Pi} $。

如果游戏用扩展形式表示，它将顺序表示，说明玩家的移动顺序、玩家做出选择时的选项以及决策时每个玩家可用的信息。通常，一个扩展形式的游戏由一个游戏树表示。这个游戏树展示了决策的顺序和潜在条件性质。此外，如果玩家 $i $ 具有完美回忆，这意味着玩家 $i $ 记得他们过去采取的哪些行动。用扩展形式表示的游戏 $G $ 可以表示为 $G = (N \cup {c}, H, Z, P, I, A, u) $。$N = {1, 2, \cdots, n} $ 表示一组玩家。$c $ 是机会，可以被视为一个特殊的代理。$H $ 表示可能的历史集合，$Z \subseteq H $ 是终端历史的集合。移动顺序由函数 $P(h) \in N \cup {c} $ 表示，指示哪个玩家要移动，其中 $h \in H $。$I $ 表示信息集分区，$I_i $ 表示玩家 $i $ 的信息集分区。这意味着在不完美信息的游戏中，如果玩家 $i $ 达到一个历史 $h \in I_i $，其中 $I_i \in I $ 是一个特定的信息集，玩家 $i $ 无法区分它遇到的是哪一个特定的历史 $h \in I_i $。动作空间由 $A(h) $ 表示，对于非终端历史 $h \in H $。对于信息集 $I_i $ 中的所有非终端历史 $h $，可用的动作是相同的；否则，它们是可区分的。因此我们使用 $A(I_i) $ 表示信息集 $I_i $ 可用的动作。效用函数由 $u = (u_1, \cdots, u_n) $ 表示，其中 $u_i : Z \rightarrow \mathbb{R} $。这些组件共同定义了扩展形式游戏的结构和动态。此外，扩展形式游戏中的一个策略配置可以表示为 $\pi = (\pi_1, \cdots, \pi_n) $，其中 $\pi_i $ 将每个 $I_i \in I_i $ 映射到 $A(I_i) $ 上的概率分布。扩展形式游戏的一个子博弈是从单一初始节点开始的游戏的一部分，包括子博弈中任何节点的所有后继节点，并且包含与子博弈中任何节点相同的信息集的所有节点。

囚徒困境是一个经典的例子，用来说明博弈论中的各种概念。在囚徒困境的一个修改版本中，结果如下：

• 如果一个玩家认罪（C），另一个玩家撒谎（L），认罪者将服刑1年，而撒谎者将服刑8年。
• 如果两个玩家都选择认罪，他们每个人都将在监狱中服刑7年。
• 如果两个玩家都选择撒谎，他们每个人都将只在监狱中服刑2年。

这个经典场景被称为同时囚徒困境，两个玩家必须同时决定是否认罪或撒谎，而不知道对方的选择。以这种方式进行的游戏被称为静态游戏。正规形式表示特别适合静态游戏，因为它捕捉了决策的同时性质（如图1a所示）。另一个变体是顺序囚徒困境，第二个玩家在知道第一个玩家的动作后做出决定。这类游戏被称为动态游戏。扩展形式表示非常适合动态游戏，因为它可以清晰地说明移动的顺序和每个决策点时每个玩家可用的信息（如图1d所示）。

此外，正规形式表示也可以转换为扩展形式表示。例如，从图1a到图1b的转换涉及将同时决策用树结构表示。在这个扩展表示中，虚线表示某些状态属于相同的信息集。相反，扩展形式表示也可以转换为正规形式表示。例如，从图1d到图1c的转换涉及将顺序决策压缩成矩阵格式。在这种情况下，玩家2的纯策略空间是 $2 \times 2 = 4 $，反映了玩家2需要对玩家1可能采取的每个动作（认罪或撒谎）都有一个策略（例如，图1c中玩家2的一个纯策略表示为 C → C, L → C，意味着玩家2在知道玩家1选择认罪时选择认罪，并且当玩家2知道玩家1选择撒谎时，玩家2也选择认罪）。图1c中的其他符号遵循相同的逻辑。

与正规形式游戏相比，扩展形式游戏引入了顺序决策，增加了游戏结构的复杂性。扩展形式游戏还与马尔可夫博弈有着密切的关系。在同时移动的马尔可夫博弈中，智能体的动作对彼此是未知的，创造了多种历史，这些历史被压缩成一个信息集。游戏的效用是随时间折扣的奖励之和[28]。除了正规形式和扩展形式游戏以及马尔可夫博弈之外，复杂马尔可夫或扩展形式博弈的分析通常采用更高层次的抽象：元博弈。元博弈有助于探索这些游戏中的政策学习，关注的不是孤立的行动，而是从游戏动态中产生的更广泛的策略。在这个高级正规形式的背景下，政策群体由当前玩家采用的策略组成。元策略是在元博弈中分配给政策群体中策略的概率的混合策略。

传递性游戏与非传递性游戏

对于我们主要关注两名玩家的零和对称游戏，在一个传递性游戏中，策略或结果遵循传递关系。形式上，对于所有 $\pi_i, \pi_j, \pi_k \in \Pi $，如果 $u(\pi_i, \pi_j) > 0 $ 且 $u(\pi_j, \pi_k) > 0 $，则必须遵循 $u(\pi_i, \pi_k) > 0 $。这种传递性质简化了策略景观，允许对策略进行序数排名。相反，在非传递性游戏中，存在 $\pi_i, \pi_j, \pi_k \in \Pi $ 使得 $u(\pi_i, \pi_j) > 0 $ 且 $u(\pi_j, \pi_k) > 0 $，但 $u(\pi_i, \pi_k) \leq 0 $。这引入了策略之间的循环关系，从而使游戏变得复杂。复杂性通常导致混合策略均衡，玩家在多个策略中随机选择以最大化他们的预期收益。非传递性游戏的一个典型例子是石头-剪刀-布，其中没有单一策略能够统一支配所有其他策略。在现实世界的环境中，游戏展现出超越理论模型的复杂性。[29] 认为现实世界的游戏有两个显著特点：首先，实践通常会带来性能提升；其次，有大量质的不同的策略，每种策略都有其独特的优势和劣势。在这样的游戏中，策略形成一个类似于旋转顶部的几何拓扑，其中垂直轴代表策略的性能，径向轴代表最长循环的长度。

阶段游戏与重复游戏：

• 阶段游戏（或一次性游戏）：是指只玩一次的游戏，即玩家之间的一次性互动。囚徒困境就是一个著名的阶段游戏例子。

• 重复游戏：是基于阶段游戏的游戏，多次进行游戏。形式上，基于阶段游戏 $G $ 的重复游戏定义为进行 $T $ 期的 $G $，其中 $T $ 可以是有限的或无限的。重复游戏中的策略是历史相关的，意味着它们可以根据过去所有的游戏序列来决定。值得注意的是，阶段游戏或重复游戏可以是正规形式或扩展形式表示的。

纳什均衡

为了简化，我们用 $\pi_i $ 表示玩家 $i $ 的策略，用 $\pi_{-i} $ 表示除玩家 $i $ 之外所有玩家的策略。给定 $\pi_{-i} $，玩家 $i $ 的最优响应（Best Response，BR）是最大化玩家 $i $ 收益的策略：

$$ BR_i(\pi_{-i}) = \arg \max_{\pi_i} u_i(\pi_i, \pi_{-i}) $$ 一个策略 $\pi^*i $ 是对策略 $\pi $ 的 $\epsilon $-最优响应（$\epsilon $-BR），如果：

$$ u_i(\pi^i , \pi) \geq u_i(BR_i(\pi_{-i}), \pi_{-i}) - \epsilon $$ 其中 $\epsilon $ 是预先指定的阈值。一个策略配置 $(\pi^_1, \pi^_2, \ldots, \pi^_n) $ 是一个纳什均衡（Nash Equilibrium，NE），如果对于每个玩家 $i $：

$$ u_i(\pi^_i , \pi^{-i}) \geq u_i(\pi_i, \pi^*) , \forall \pi_i $$ 这意味着，给定所有其他玩家的策略，没有玩家可以通过单方面改变他们的策略来获益。换句话说，纳什均衡是每个玩家选择的策略是对所有其他玩家选择的策略的最优响应的情况。一个策略配置 $(\pi^_1, \pi^_2, \ldots, \pi^*_n) $ 是一个 $\epsilon $-纳什均衡，如果对于每个玩家 $i $：

$$ u_i(\pi^_i , \pi^{-i}) \geq u_i(\pi_i, \pi^*) - \epsilon , \forall \pi_i $$ 这意味着，通过单方面改变策略，没有玩家可以通过超过 $\epsilon $ 的幅度来增加他们的收益。然而，在复杂游戏中计算纳什均衡通常是不可行的，导致一些研究者使用 $\alpha $-Rank [30] 和相关均衡（Correlated Equilibrium，CE）[31] 作为替代方案。此外，一些研究还采用复制动态（Replicator Dynamics）[32] 作为分析和理解这些游戏中策略演变的方法。

团队游戏

两名玩家零和游戏的框架可以自然地扩展到涵盖基于团队的零和游戏。Von Stengel 和 Koller 分析了涉及一个团队与一个对手对抗的零和正规形式游戏[33]。在这类团队游戏中，考虑一个由 $T = {1, 2, \cdots, n - 1} $ 表示的团队。玩家 $n $ 是对手（D）。在这类零和正规形式团队游戏中，对于任何玩家 $i, j \in T $，效用函数满足 $u_i(\pi) = u_j(\pi) = u_T(\pi) $ 且 $u_D(\pi) = -(n - 1)u_T(\pi) $。一个零和单团队单对手正规形式游戏也可以扩展到扩展形式游戏领域[34]。对于任何玩家 $i, j \in T $ 和所有终端节点 $z \in Z $，效用函数满足 $u_i(z) = u_j(z) = u_T(z) $ 且 $u_D(z) = -(n - 1)u_T(z) $。让 $I_T $ 表示为 $\bigcup_{i \in T} I_i $ 定义的信息集，让 $A_T $ 表示在 $I_T $ 内的信息集中可访问的动作集合。

在队友无法协调他们策略的情况下，团队最大化最小均衡（Team-maxmin Equilibrium，TME）成为最合适的解决方案[33]。我们用 $Q_i $ 表示玩家 $i $ 的序列集合，代表玩家 $i $ 采取的序列形式动作。序列形式策略由函数 $p_i : Q_i \rightarrow \mathbb{R} $ 封装，它将每个序列 $q \in Q_i $ 映射到其执行的关联概率。正式地，TME 表述为： $$ \arg \max_{p_1, \ldots, p_{n-1} } \min_{p_n} u_T \left( \sum_{i=1}^{n} p_i \right) $$ 类似于正规形式游戏[33]中的论点，也可以推断，在扩展形式游戏中，TME 唯一存在，除非有任何退化，并且这个 TME 与团队的 NE 的效用最大化对齐[34]。

C. 自博弈中的评估指标

在这一部分，我们介绍各种自博弈评估指标，包括NASHCONV（第II-C1节）、Elo（第II-C2节）、Glicko（第II-C3节）、WHR（第II-C4节）和TrueSkill（第II-C5节）。尽管NASHCONV用于衡量特定策略与纳什均衡的距离，其他四个指标则评估相对技能水平，并在表I中进行比较。值得注意的是，尽管存在许多其他评估指标，但这里突出显示的指标是在该领域中最广泛使用的。

表I：相对技能评估指标的比较

特性	Elo	Glicko	WHR	TrueSkill
不确定性建模		✓	✓	✓
随时获得评分		✓	✓	✓
一队中的多人		✓	✓	✓
贝叶斯基础		✓	✓	✓

1. NASHCONV：纳什收敛（NASHCONV）是衡量特定策略与纳什均衡偏离程度的指标。较低的NASHCONV值表明策略更接近纳什均衡，意味着没有玩家能从单方面偏离策略中获益。形式上，它定义为：

$$ \text{NASHCONV}(\pi) = \max_{\pi_i \in \Pi_i} u_i(\pi_i, \pi_{-i}) - u(\pi) $$

其中 $\pi $ 表示所有参与代理的联合策略配置。特别地，在两个玩家的背景下，这种偏离通常被称为可利用性。

2. Elo：Elo系统[35]基于这样一个假设，即每个玩家在每场比赛中的表现是一个正态分布的随机变量，平均值是玩家当前的评分。在玩家A和玩家B之间的比赛，$R_A $ 和 $R_B $ 是玩家A和玩家B的当前评分。玩家A和玩家B表现的概率密度函数分别为：

$$ f_A(x) = \frac{1}{\sqrt{2\pi\sigma} } e^{-\frac{(x-R_A)^2}{2\sigma^2} } $$

$$ f_B(x) = \frac{1}{\sqrt{2\pi\sigma} } e^{-\frac{(x-R_B)^2}{2\sigma^2} } $$

$E_A $ 和 $E_B $ 表示玩家A和玩家B的预期得分（或获胜概率）：

$$ E_A = \frac{1}{2} + \int_{-\infty}^{R_B-R_A} \frac{1}{\sqrt{2\pi\sigma} } e^{-\frac{x^2}{2\sigma^2} } dx $$

$$ E_B = \frac{1}{2} + \int_{-\infty}^{R_A-R_B} \frac{1}{\sqrt{2\pi\sigma} } e^{-\frac{x^2}{2\sigma^2} } dx $$ 为了方便，使用逻辑函数来近似概率（使用以10为底的逻辑曲线，并选择400来缩放和标准化评分差异）：

$$ E_A = \frac{1}{1 + 10^{(R_B-R_A)/400} } $$ $$ E_B = \frac{1}{1 + 10^{(R_A-R_B)/400} } $$ 注意 $E_A + E_B = 1 $。$S_A $ 是比赛对玩家A的实际结果（赢为1，平为0.5，输为0）。$S_B = 1 - S_A $。比赛结束后，根据实际结果与预期结果之间的差异来更新评分。调整由以下给出：

$$ \Delta R_A = K(S_A - E_A) $$ $$ \Delta R_B = K(S_B - E_B) $$

$K $ 是一个缩放因子，通常由应用的特定领域决定，并控制单场比赛可能的最大评分变化。如果两个玩家的评分几乎相同，则预期结果将接近0.5。任何一方的胜利都将导致他们的评分适度增加。相比之下，如果评分差异显著，预期结果将严重倾斜。如果评分较高的玩家获胜，他们的评分将增加一个远小于 $K $ 的值，反映了他们胜利的预期性。然而，如果评分较低的玩家获得意外的获胜，他们的评分将急剧上升，接近 $K $，标志着这一意外的胜利。更新后的评分变为：

$$ R'_A = R_A + \Delta R_A $$

$$ R'_B = R_B + \Delta R_B $$

然而，Elo系统存在挑战和局限性。首先，Elo系统假设所有比赛都同等重要，这在所有领域可能并不成立。其次，$K $ 通常保持不变，但对于新进入评分池的玩家或比赛重要性不同的情况，动态 $K $ 因子可能更合适。第三，标准Elo系统没有引入衰减机制来考虑在活动期间技能的潜在退化或提升。第四，基本的Elo系统专为一对一比赛设计。适应团队或多人场景，如团队运动或在线多人游戏，可能具有挑战性。最后，Elo评分系统的一个重要局限性是它不适用于表现出高水平非传递性的游戏[36]。

3. Glicko：Glicko系统通过引入玩家评分的不确定性或可靠性度量，即评分偏差，来改进Elo系统[37]。主要动机是考虑玩家表现的可变性以及技能随时间的潜在变化。Glicko-2系统，原始Glicko系统的扩展，进一步完善了这些概念并引入了评分波动率 $ \sigma $，表示玩家评分预期波动的程度[38]。在Glicko-2系统中，$ r $ 表示玩家的当前评分。$ RD $ 是玩家的评分偏差，而 $ \sigma $ 是玩家的波动率。将评分和评分偏差转换为Glicko-2尺度：

$$ \mu = \frac{r - 1500}{173.7178} $$

$$ \phi = \frac{RD}{173.7178} $$

然后，计算基于比赛结果的玩家评分估计方差 $ v $，计算玩家 $ i $ 击败对手玩家 $ j $ 的概率 $ E(\mu, \mu_j, \phi_j) $，以及仅基于比赛结果估计的改进 $ \Delta $：

$$ v = \left( \sum_{j=1}^{m} g(\phi_j)^2 {1 - E(\mu, \mu_j, \phi_j)} \right)^{-1} $$

$$ E(\mu, \mu_j, \phi_j) = \frac{1}{1 + \exp(-g(\phi_j)(\mu - \mu_j))} $$

$$ \Delta = v \sum_{j=1}^{m} g(\phi_j) {s_j - E(\mu, \mu_j, \phi_j)} $$

其中：

$$ g(\phi) = \frac{1}{\pi \sqrt{3\phi^2 + 1} } $$ 更新 $ \sigma $ 的过程更为复杂，需要迭代求解其新值 $ \sigma' $。然后计算新的 $ \mu' $ 和 $ \phi' $：

$$ \mu' = \mu + \frac{\phi'^2}{m} \sum_{j=1}^{m} g(\phi_j) {s_j - E(\mu, \mu_j, \phi_j)} $$

$$ \phi' = \frac{1}{\sqrt{\phi^*2 + \frac{1}{v} } } $$

其中：

$$ \phi^* = \sqrt{\phi^2 + \sigma'^2} $$ 计算完成后，将评分和评分偏差从Glicko-2尺度转换回：

$$ r' = 173.7178\mu' + 1500 $$

$$ RD' = 173.7178\phi' $$

4. WHR：整体历史评分（Whole-History Rating，WHR）系统[39]是一个贝叶斯评分系统，旨在从玩家的整个游戏历史中估计玩家的技能。它特别适用于处理玩家技能的时间动态。$ R_i(t) $ 表示玩家 $ i $ 在时间 $ t $ 的Elo评分。类似于公式(11)和(12)，$ E_A(t) $ 和 $ E_B(t) $ 表示玩家A和玩家B在时间 $ t $ 的预期得分（或获胜概率）：

$$ E_A(t) = \frac{1}{1 + 10^{(R_B(t)-R_A(t))/400} } $$

$$ E_B(t) = \frac{1}{1 + 10^{(R_A(t)-R_B(t))/400} } $$

此外，WHR假设每个玩家的评分是一个Wiener过程：

$$ r_i(t_2) - r_i(t_1) \sim N(0, |t_2 - t_1|\omega^2) $$

其中 $ \omega $ 是表示评分随时间变化的可变性的参数。因此，如果 $ r' = R_A(t_1) $，$ r'' = R_A(t_2) $：

$$ p(r''|r') = \frac{1}{\sqrt{2\pi\sigma^2} } e^{-\frac{(r''-r')^2}{2\sigma^2} } $$

其中 $ \sigma = \omega \sqrt{|t_2 - t_1|} $。此外，Wiener过程是无记忆的（或马尔可夫的）。$ R(t) $ 表示玩家A的评分，$ G $ 表示比赛结果的观察。得益于贝叶斯公式，WHR系统旨在解决：

$$ \arg \max_{R} p(R|G) = \arg \max_{R} \frac{p(G|R)p(R)}{p(G)} $$

$ p(G|R) $ 可以从公式(28)的乘积中得出，$ p(R) $ 可以从公式(31)的乘积中得出。利用牛顿方法的迭代过程，我们可以确定给定问题的解决方案。

5. TrueSkill：TrueSkill[40]是基于概率图模型的系统，它采用贝叶斯推断并适应于多个玩家在多个团队中的情况。TrueSkill 2[41]通过考虑玩家的经验、团队归属以及一些特定于游戏的因素（如击杀数）来扩展原始TrueSkill模型。为简单起见，我们使用以下场景介绍TrueSkill：团队1有玩家1，而团队2有玩家2和玩家3。最终，团队1击败了团队2。这是一个比原始论文[40]中介绍的情况更简单的案例。它可以在一个无向概率图模型中描述（图2）。每个玩家的技能，表示为 $ s_i $，由高斯分布 $ N(s_i; \mu_i, \text{var}_i) $ 表示。每个玩家的表现，表示为 $ p_i $，也由高斯分布 $ N(p_i; s_i, \beta^2) $ 表示。团队的表现由 $ t_i $ 表示。团队表现的差异由 $ d $ 表示。如果 $ d > \epsilon $，其中 $ \epsilon $ 是一个小的正常数阈值，则团队1击败团队2。TrueSkill算法在无向概率图的上下文中使用和积-乘积算法来更新机制，确保技能估计值经过迭代细化，从而为每个玩家提供准确可靠的评分。

III. 算法

基于现有的自博弈工作[18], [42]–[44]，我们提出了一个自博弈框架（算法1），它具有增强的表达能力和优越的泛化能力。该框架擅长处理多同质玩家的一般和游戏。值得注意的是，尽管同质玩家代表了异质玩家的一个特定子集，但后者可以通过扩展输入向量的维度来重新构建为前者，这本质上意味着嵌入了代理身份信息。此外，由于玩家是同质的，我们假设每个玩家共享相同的策略群体。为了阐明我们的框架，我们以更易于理解的方式描述它。所有玩家共享一个公共策略群体，其最大大小是固定的。在每次迭代中，都会初始化一个新的策略进行训练，并且从现有策略群体中采样对手策略。在此迭代期间，对手策略通常保持固定，只有正在训练的策略被更新。训练过程结束后，新策略替换策略群体中的一个策略。然后使用评估指标来评估更新后的策略群体的性能。根据此性能，调整下一个迭代的对手采样策略。此过程会重复进行。有关更详细和精确的描述，请参阅第III-A节。此外，我们将自博弈算法分为四个主要组别：传统自博弈算法（第III-B节）、PSRO系列（第III-C节）、基于持续训练的系列（第III-D节）和基于遗憾最小化的系列（第III-E节）。我们分析了这四个类别中的每个算法如何与我们的框架对齐，并在各自的部分中介绍了每个类别中的代表性算法。此外，在第III-F节中，我们讨论了这四个类别之间的差异以及它们与我们提出的框架的联系。我们还将解释为什么我们的框架比现有框架更通用。此外，我们在表II中总结了我们框架中每个类别的关键算法的主要元素。

类型一：传统自博弈算法

传统自博弈算法从单一策略开始，逐步扩展策略池，包括Vanilla self-play（训练时每次对手都选择最新生成的策略），Fictitious self-play（训练时每次对手都在现有训练完的策略中均匀采样），δ-uniform self-play（训练时每次对手都在现有训练完的最近的百分之δ策略中均匀采样），Prioritized Fictitious Self-play（根据优先级函数计算当前训练完的策略的优先级，训练时每次对手都根据这个优先级进行采样），Independent RL（训练时双方策略都会改变，对手策略不再固定）。

类型二：PSRO 系列算法

类似于传统自博弈算法，Policy-Space Response Oracle（PSRO）系列算法同样从单一策略开始，通过计算 ORACLE 逐步扩展策略池，这些新加入的策略是对当前元策略的近似 BR 。PSRO 系列与传统自博弈算法的主要区别在于，PSRO 系列采用了更复杂的MSS，旨在处理更复杂的任务。例如，α-PSRO 使用了基于 α-rank 的 MSS 来应对多玩家的复杂博弈。

类型三：持续训练系列算法

PSRO 系列算法中存在的两个主要挑战：首先，由于训练成本大，通常在每次迭代中截断近似BR计算，会将训练不充分的策略添加到策略池；其次，在每次迭代中会重复学习基本技能，导致效率较低。为了解决这些挑战，基于持续训练系列的算法提倡反复训练所有策略。与前面提到的两类最大区别是，持续训练系列算法同时训练整个策略池策略。这类算法采用多个训练周期，并在每个训练周期内依次训练策略池所有策略，而不再是通过逐步扩展策略池进行训练。

类型四：后悔最小化系列算法

另一类自博弈算法是基于后悔最小化的算法。基于后悔最小化的算法与其他类别的主要区别在于，它们优先考虑累积的长期收益，而不仅仅关注单次回合的表现。这种方法可以训练得到更具攻击性和适应性的策略，避免随着时间的推移被对手利用。这些算法要求玩家在多轮中推测并适应对手的策略。这种情况通常在重复博弈中观察到，而不是单回合游戏中。例如，在德州扑克或狼人游戏中，玩家必须使用欺骗、隐瞒和虚张声势的策略，以争取整体胜利，而不仅仅是赢得一局。

A. 框架定义

在算法1中，我们定义了一个基于[18], [42]–[44]的统一自博弈框架。首先，框架的输入定义如下：

• Π：策略群体Π中的每个策略 $ \pi_i $ 都是根据特定算法确定的策略条件函数 $ h(i) $ 来条件化的。我们将在下面的部分进一步介绍这个策略条件函数。为了简化，我们用 $ \pi_{h_i} $ 表示每个策略 $ \pi_i(\cdot|h(i)) $。值得注意的是，$ i $ 指的是策略群体中的第 $ i $ 个策略，而不是玩家。此外，超参数 $ N $ 表示Π的策略群体大小，而不是游戏玩家的数量。此外，Π可以以两种不同的方式初始化。首先，Π可以被认为是用N个占位符策略初始化的，这意味着实际上并没有对策略进行初始化。相反，每个策略将在训练迭代中实际初始化（算法1中的第3行）。我们称这种方法为占位符初始化。其次，Π可以与N个真实策略初始化，这些策略可能包括随机初始化或预训练模型。我们称这种方法为实际初始化。一个策略 $ \pi_{h_i} $ 被认为是一个无效策略如果它作为占位符策略；否则，它被认为是一个有效策略。此外，表II更清晰地说明了不同类别的主要自博弈算法中Π的初始化和 $ h(i) $ 的表达。

• Σ := $ { \sigma_i }^N_{i=1} \in \mathbb{R}^{N \times C_1} $：策略群体的交互矩阵。$ \sigma_i \in \mathbb{R}^{C_1} $ 表示策略 $ i $ 的对手采样策略。也就是说，$ \sigma_i $ 说明了如何采样对手的策略。例如，让 $ \sigma_i $ 表示每个对手策略的概率。在这种情况下，$ C_1 = N^{n-1} $，其中 $ n $ 表示玩家的数量。或者，$ \sigma_i $ 也可以被视为在采样网络内的采样参数。特别是，在两名玩家的游戏中，如果 $ C_1 = N $ 并且 $ \sigma_{ij} $ 表示策略 $ i $ 针对策略 $ j $ 进行优化的概率，Σ可以通过有向交互图来描述（图3）。值得注意的是，与原始PSRO框架[42]不同，这里的 $ \sigma_i $ 不是策略 $ i $ 的元策略。相反，在两名玩家的设置中，如果我们框架中的 $ \sigma_i $ 是对手针对策略 $ i $ 的元策略，我们的框架可以简化为原始的PSRO框架。

• F : $ \mathbb{R}^{N \times C_2} \rightarrow \mathbb{R}^{N \times C_1} $：一个元策略求解器（Meta-Strategy Solver，MSS）F接受性能矩阵 $ P := { p_i }^N_{i=1} \in \mathbb{R}^{N \times C_2} $ 作为输入，并产生一个新的交互矩阵 $ \Sigma \in \mathbb{R}^{N \times C_1} $ 作为输出。$ p_i $ 是策略 $ i $ 的性能。例如，$ p_i $ 可以被描述为相对技能，如Elo评分（$ C_2 = 1 $）或者可以被描述为收益张量（$ C_2 = N^{n-1} $，其中 $ n $ 是玩家的数量）。特别地，在两名玩家对称零和游戏中，预期收益可以作为评估指标。在这种情况下，Σ是一个方阵（$ C_2 = N $）。此外，表II总结了代表性自博弈算法的MSS。

接下来，框架内的核心过程如下：

• 对于所有时期 $ e \in [[E]] $（算法1中的第1行）：$ E $ 表示整个策略群体的总时期数。例如，如果算法只引入新策略而不更新现有策略，那么 $ E = 1 $。这意味着每次迭代中只有一个无效策略可能被选中进行训练，并转变为有效策略。在这里，策略群体大小 $ N $ 作为有效策略数量的上限。换句话说，我们使用 $ N $ 次迭代来优化策略。相反，如果有效策略在算法过程中多次更新，那么 $ E > 1 $。实际上，$ E $ 准确地反映了执行的更新次数。此外，表II总结了不同类别的自博弈算法中 $ E $ 的值。
• 初始化 $ \pi_{h_i} $（算法1中的第3行）：$ \pi_{h_i} $ 的初始化可以根据所使用的算法而有所不同。例如，它可以随机初始化，这表示从零开始学习过程。更常见的是，$ \pi_{h_i} $ 通过 $ \pi_{i-1}(\cdot|h(i-1)) $ 进行初始化，允许增量学习和基于最新训练策略的适应，以加速收敛。我们将为每个算法系列提供详细的初始化过程描述。这些也总结在表II中。
• ORACLE($ \pi_{h_i} $, $ \sigma_i $, Π)（算法1中的第4行）：ORACLE是一个抽象的计算实体，它返回符合特定标准的新策略。在这里，我们将ORACLE分为三种类型。（1）一种类型是最优响应（Best Response，BR）预言机，旨在识别对手策略的最优对策，包括找到纳什均衡[45]。然而，它通常需要大量的计算工作。这种计算需求可能是一个限制，特别是在复杂环境或大动作空间中。（2）为了减轻计算需求，引入了近似最优响应（Approximate Best Response，ABR）预言机，可以使用RL（算法2）、基于进化理论的方法（算法3）或遗憾最小化方法（算法4）等技术来计算。（3）此外，还有其他特别定制的ORACLE，要么为新的MSS[46], [47]量身定制，要么引入以增强多样性[48]–[50]。需要提及的是算法2、3和4的一些细节。$ \pi_{opp} $ 表示对手的策略。此外，在算法2中，离策略RL算法[2], [51]–[53]通常需要一个回放缓冲区来收集样本；然而，为了简化，它们没有明确包括。此外，算法2的第1行表明RL可能不总是产生符合特定标准的ABR。例如，AlphaGo Zero[9]规定新策略必须在对其前身的胜率超过55%。因此，有时需要验证新策略。此外，重要的是要注意算法3是专门为R-NaD[54]设计的，而算法4是专门为基于遗憾最小化的系列设计的。它们将在第III-C5节和第III-E节中详细介绍。
• EVAL(Π)（算法1中的第5行）：评估策略群体Π。有多种评估指标可用于衡量每个策略的性能。性能矩阵表示为 $ P := { p_i }^N_{i=1} \in \mathbb{R}^{N \times C_2} $。此外，只有有效策略将被评估以节省计算。值得注意的是，如果MSS产生一个与输入无关的恒定矩阵，可以跳过评估步骤以减少计算。展望未来，我们将自博弈算法分为四个主要组别。我们将详细分析这些类别中的每个算法如何与我们提出的框架对齐。

B. 传统自博弈算法

传统自博弈算法涉及智能体通过反复与自己对抗来改进策略，使它们能够探索各种策略并增强决策能力，而无需外部输入。这些算法可以从智能体训练对抗其最新版本开始，帮助识别和利用弱点。此外，其他方法涉及训练针对不同迭代中的一组策略，使智能体能够发展出更健壮和适应性强的策略。在本节中，我们将解释传统自博弈算法如何融入我们的框架，并介绍代表性的传统自博弈方法，从更简单形式到更复杂形式。

1. 融入我们的框架：我们可以将传统自博弈算法纳入我们提出的框架（算法1），使用以下设置。首先，策略群体Π使用占位符初始化，这意味着最初策略是占位符而不是实际初始化的策略。这个初始化方法是因为传统自博弈算法中的策略群体旨在每次迭代中增长。其次，我们设置 $ E = 1 $ 因为传统自博弈算法中，每次迭代只有一个无效策略可能被选中进行训练，从而转变为有效策略。在这里，策略群体大小 $ N $ 作为有效策略数量的上限。第三，被训练的策略 $ \pi_{h_i} $ 可以以一般方式初始化。例如，策略可以随机初始化，这表示从零开始学习过程。更常见的是，$ \pi_{h_i} $ 通过 $ \pi_{i-1}(\cdot|h(i-1)) $ 进行初始化，允许基于最新训练策略的增量学习和适应，以加速收敛。第四，由于传统自博弈算法中的策略没有条件，我们简单地设置 $ h(i) = \emptyset $。接下来，我们概述传统自博弈方案。为了简单起见，我们假设：假设1. 在两名玩家对称的游戏中，$ C_1 = N $，其中 $ \sigma_{ij} $ 表示策略 $ i $ 针对策略 $ j $ 进行优化的概率，导致 $ \sum_{j=1}^{N} \sigma_{ij} = 1 $，对于所有 $ i $。根据假设1，我们可以进一步推断出以下重要推论：推论1. 在传统自博弈算法中，交互矩阵Σ是一个下三角矩阵。

证明. 策略群体随时间逐渐增加。因此，当策略 $ i $ 被选中进行训练时，只有策略 $ j $（$ j \leq i $）已经被训练并持有有意义的结果。其他策略是无效策略。因此，我们只选择策略 $ j $，其中 $ j \leq i $，作为策略 $ i $ 的对手。

2. 纯自博弈：在纯自博弈[6]中，智能体通过与它们的最新版本竞争来训练，确保一致和对齐的学习。MSS的纯自博弈：

$$ F(P)_{ij} = \begin{cases} 1 & \text{if } j = i - 1 \ 0 & \text{otherwise} \end{cases} $$

无论P是什么，MSS产生相同的交互矩阵，类似于策略的迭代细化过程。尽管这个MSS很简单，但它在许多进一步的工作中被使用，因此我们称它为纯MSS。尽管纯自博弈在传递游戏中有效，但它可能导致智能体在非传递游戏中形成循环学习模式，如石头-剪刀-布。

3. 虚构自博弈：虚构博弈（Fictitious Play，FP）[55]是博弈论中的一种学习算法，其中每个玩家最佳响应对手策略的经验频率。如果对手的策略是静态的，FP可以找到纳什均衡。基于FP直觉，虚构自博弈（Fictitious Self-play，FSP）[13]被引入，使智能体与过去的自己版本进行对抗，以学习最优策略，增强纯自博弈的鲁棒性。神经虚构自博弈（Neural Fictitious Self-play，NFSP）[56]是结合深度学习技术的现代变体。它使用神经网络来近似最佳响应。在NFSP和FSP的原始版本中，使用了两种不同类型的智能体记忆：一种记录智能体自己的行为，另一种捕捉对手的行为。然而，在更近期的方法[42]中，经常使用随机抽样来近似对手的平均策略，消除了维护两种不同类型的智能体记忆的需要。因此，FSP的MSS：

$$ F(P)_{ij} = \begin{cases} \frac{1}{i-1} & \text{if } j \leq i - 1 \ 0 & \text{otherwise} \end{cases} $$

在FSP中，MSS继续生成一个恒定的交互矩阵。与纯自博弈相比，这种方法通过采样自己策略的旧版本作为对手策略，增强了策略的鲁棒性。

4. δ-均匀自博弈：δ-均匀自博弈是由[7]引入的。超参数δ在0和1之间变化，用于选择用于均匀抽样的最近δ（百分比）的策略，以生成对手策略。当策略 $ i $ 处于训练阶段时，根据推论1，只有前 $ i-1 $ 个策略具有意义。作为策略 $ i $ 的对手，我们从离散均匀分布 [$\delta(i - 1)$, $ i - 1 $] 中选择策略。当δ = 0时，系统保留了完整的历史记忆，而δ = 1意味着只使用最近的策略。因此，我们可以得到δ-均匀自博弈的MSS：

$$ F(P)_{ij} = \begin{cases} \frac{1}{f(i)} & \text{if } \delta(i - 1) \leq j \leq i - 1 \ 0 & \text{otherwise} \end{cases} $$

$$ f(i) = \max{\lceil (1 - \delta)(i - 1) \rceil, 1} $$

其中 $ \lceil \cdot \rceil $ 是天花板函数，它提供了大于或等于给定输入数的最小整数。在δ-均匀自博弈中，MSS生成一个恒定的交互矩阵。特别地，如果δ = 0，它对应于FSP，如果δ = 1，它对应于纯自博弈。

5. 优先级虚构自博弈：优先级虚构自博弈（Prioritized Fictitious Self-play，PFSP）[15]利用优先级函数为具有较高优先级的智能体分配更高的被选择概率。在这里，$ P $ 表示胜率，具体定义为 $ P_{ij} = \text{Prob}(\pi_i \text{ beats } \pi_j) $。PFSP的MSS由算法5给出。

算法5 PFSP元策略求解器

1. 函数 $ F(P) $
2. $ \sigma_{i+1,j} \leftarrow \frac{f(P_{i,j})}{\sum_{j \leq i} f(P_{i,j})} $，如果 $ j \leq i $
3. 将零追加到 $ \sigma_{i+1} $ 直到其长度为 $ N $。
4. 返回 $ \Sigma $

函数 $ f : [0, 1] \rightarrow [0, \infty) $ 是一个优先级函数。例如，$ f(x) = (1 - x)^p $ 表示对当前正在训练的策略有更高胜率的策略有更高的机会被选为对手。或者，$ f = x(1-x) $ 意味着水平相近的玩家更有可能被选为对手。此外，更广泛地讲，$ P $ 也可以通过其他指标进行评估。[14]中可以利用一个类似的MSS来为表现更好或更难击败的策略分配更高的概率。

6. 独立RL：独立RL是MARL中的一种完全分散的方法。这简化了学习过程，并且在竞争或对抗性设置中很有用，尽管在需要合作的情况下可能会导致次优结果。独立RL可以被视为自博弈算法的一个特例。在每次迭代中，被训练的策略 $ \pi_{h_i} $ 使用前一个策略 $ \pi_{i-1}(\cdot|h(i-1)) $ 进行初始化。独立RL的MSS简化为单位矩阵：

$$ F(P)_{ij} = \begin{cases} 1 & \text{if } i = j \ 0 & \text{otherwise} \end{cases} $$

独立RL与纯自博弈的不同之处在于如何处理训练期间的对手策略。在纯自博弈中，对手策略通常是固定的，使得训练过程是静态的。相比之下，在独立RL中，对手策略随着正在训练的策略而演变，导致非静态训练过程。此外，如果在独立RL中使用离策略RL方法，那么收集的样本仍然可以用于训练，即使它们是由不同策略生成的。这允许代理更有效地利用过去经验，并从更广泛的情境中学习。

C. PSRO系列算法

类似于传统自博弈算法，PSRO系列算法从单一策略开始，通过引入新的预言机逐渐扩展策略空间。这些预言机是策略，它们近似于当前其他代理的元策略的最佳响应。此外，PSRO采用实证博弈论分析（EGTA）来更新元策略分布，从而在策略选择中引入一定程度的探索，以减少过拟合的风险。

1. 融入我们的框架：PSRO系列算法也可以整合到我们提出的框架（算法1）中。首先，与PSRO系列算法类似，我们使用占位符初始化Π。其次，我们也设置 $ E = 1 $，并且 $ N $ 可以被认为是原始PSRO算法中策略群体大小的上限。第三，在我们的玩家策略 $ \pi_{h_i} $ 中也可以以一般方式初始化。第四，由于PSRO系列算法的策略不使用任何条件，我们简单地设置 $ h(i) = \emptyset $。第五，与PSRO系列算法相比，我们框架中的关键区别在于如何定义 $ \sigma_i $。与作为策略的元策略不同，在我们的框架中，$ \sigma_i $ 是对手采样策略。这意味着 $ \sigma_i $ 这里表示对手针对策略 $ i $ 的元策略。第六，与传统自博弈方法相比，PSRO系列的MSS通常更复杂。例如，一些MSS结合了不同类型的博弈均衡概念[45]–[47]。为了简化，我们也遵循假设1。与传统自博弈算法类似，我们可以使用类似推论1的证明得出推论2。

推论2. 在PSRO系列算法中，交互矩阵Σ是一个下三角矩阵。

证明. 与PSRO系列算法类似，交互矩阵Σ是一个下三角矩阵。

2. 双重预言机：双重预言机（DO）[45]传统上只应用于两名玩家的正规形式游戏。在这种情况下，我们可以使用收益矩阵作为评估矩阵。交互矩阵可以初始化为全零，反映了策略之间初始时没有交互。然后，DO的MSS可以描述为算法6中所述。对手采样策略 $ \sigma_i $ 对应于对手在限制游戏中的纳什均衡策略。因此，DO中的预言机是一个最佳响应（BR）而不是近似最佳响应（ABR），计算针对当前纳什均衡对手策略的最佳响应。在两名玩家正规形式游戏的背景下，DO理论上可以实现完整游戏的纳什均衡。

算法6 基于纳什均衡的元策略求解器

1. 函数 $ F(P) $
2. $ \sigma_{i+1} \leftarrow \text{SOLVE-NASH}(P_{1:i}, 1:i) $ // 对手的纳什均衡元策略。
3. 将零追加到 $ \sigma_{i+1} $ 直到其长度为 $ N $。
4. 返回 $ \Sigma $

3. PSRO：PSRO[42]将DO扩展到不仅仅是两名玩家正规形式游戏的更复杂游戏中。这种方法首先引入了元策略求解器（MSS）的概念，这是一个比仅仅计算纳什均衡更广泛的概念。MSS框架允许在各种游戏设置中更灵活地表示战略解决方案。许多PSRO变体专注于设计新的MSS，以更好地捕捉这些更复杂游戏中战略博弈的不同方面。在原始PSRO框架中，预言机是使用RL技术计算的，类似于算法2中描述的。这使得算法能够有效处理大型和复杂的策略空间，使其适用于广泛的游戏场景。

4. PSRO变体：传统的PSRO算法在最近的研究中已经有许多扩展。一些研究专注于在不同场景中使PSRO在计算上更可行或实现快速收敛。通过建立RL工作者的层次结构，Pipeline PSRO[57]实现了PSRO的并行化，并同时提供了收敛保证。Efficient PSRO[58]引入了无限制-限制（URR）游戏，以缩小对手策略的选择范围，从而消除了传统PSRO中元游戏模拟的需要。与Pipeline PSRO类似，Efficient PSRO配备了并行解决URR的能力。此外，与PSRO传统上将群体策略的整合限制在游戏的初始状态不同，XDO[59]允许这种整合跨越所有信息状态。它确保了基于信息状态数量的线性收敛到近似纳什均衡，从而提高了其在扩展形式游戏中的可处理性。ODO[60]将在线学习的无遗憾分析与双重预言机方法结合起来，以提高收敛到纳什均衡的速度和平均收益。Anytime PSRO[61]和Self-play PSRO[62]旨在将较少被利用的策略纳入策略群体，从而促进更快的收敛。此外，随着代理数量的增加，确定最佳响应变得指数级困难。Mean-field PSRO[63]被引入以解决均场游戏中的这种复杂性。此外，由于在多玩家一般和游戏中计算纳什均衡在计算上是不可行的[64], [65]，以及在纳什均衡中的选择问题[66]，Müller等人提出了αPSRO[46]。而不是纳什均衡，α-rank[30]在多玩家一般和游戏中是唯一的，并且在多项式时间内可解，被引入MSS，并且纳入了一个基于偏好的最佳响应（PBR）预言机。类似于αPSRO，[47]提出了JPSRO以解决多玩家一般和游戏。它利用相关均衡（CE）和粗略相关均衡（CCE）的概念作为纳什均衡的替代品，使其在多玩家一般和游戏中计算上可行。它还提出了基于CE和CCE的MSS。在JPSRO的基础上，NeuPL-JPSRO[67]利用迁移学习的优势。除了共享参数 $ \theta $ 之外，NeuPL-JPSRO中的每个策略都由策略嵌入向量 $ v_i $ 特征化。这种方法避免了在每次迭代中从头开始训练的需要，从而提高了效率。其他研究专注于策略多样化，因为在高度传递的游戏中得出单一策略通常缺乏意义。[48]在两名玩家零和游戏中引入了一个开放式框架。这个框架增强了策略群体的多样性，并引入了一个游戏景观，它为开放式学习在几何上表示游戏中的潜在目标。该研究提出了两种算法：纳什响应PSRON和校正纳什响应PSROrN。两种算法都使用不对称收益矩阵作为它们的性能评估指标。类似于DO，它们采用基于纳什均衡的MSS（算法6）。与PSRON相比，PSROrN在ABR预言机中加入了一个额外的步骤，专注于他们击败或打平的对手，忽略他们输掉的对手。[49]使用行列式点过程[68]来评估多样性，并引入了多样化PSRO，将多样性项纳入PSRO预言机中。这种修改也可以很容易地在FP和αPSRO中实施。类似地，[50]制定了行为多样性和响应多样性，并将它们纳入PSRO预言机。策略空间多样性PSRO[69]定义了一个名为群体可利用性的多样性指标，有助于实现全游戏纳什均衡。

5. R-NaD：尽管R-NaD[54]最初被描述为利用带有正则化组件的进化博弈论。在这里，我们将其归类为具有特殊预言机计算技术的PSRO系列（算法3），它在两个阶段执行：第一阶段涉及根据调节策略转换奖励，使其依赖于策略，第二阶段应用复制动态[32]直到收敛到一个固定点。至关重要的是，在每次迭代中，加入策略群体Π的预言机来自奖励转换后的游戏，而不是原始问题的预言机。尽管如此，这种方法确保了策略将收敛到原始游戏的纳什均衡，前提是游戏是单调的。R-NaD的MSS是纯MSS，如公式(33)所述，与纯自博弈的MSS相同。这个方程式说明了在每次迭代中达到的固定点，预言机，被用作下一个迭代的正则化策略。

D. 基于持续训练的系列算法

PSRO系列算法面临两个主要挑战。首先，当预算有限时，通常需要在每次迭代中截断ABR操作符。这可能会引入次优训练的响应到群体中。其次，每次迭代中重新学习基本技能的冗余过程不仅效率低下，而且在面对越来越强大的对手时变得不可行[43]。为了解决这些挑战，基于持续训练的系列算法提倡反复持续地训练所有策略。也就是说，所有有效策略都可能被选中进行训练。

1. 融入我们的框架：我们可以将基于持续训练的系列算法纳入我们提出的框架（算法1），使用以下设置：首先，我们使用实际初始化来初始化Π，因为在基于持续训练的系列中，所有策略群体一起被训练，而不是策略群体随着每次迭代增长。其次，我们设置 $ E = E_{\text{max} } > 1 $，这代表了在策略群体中优化每个策略的最大次数。换句话说，每个独特的策略经历 $ E_{\text{max} } $ 次迭代训练。第三，由于每个策略都经历 $ E_{\text{max} } $ 次训练，我们使用 $ \pi_i(\cdot|h(i)) $ 来初始化 $ \pi_{h_i} $ 以确保策略更新是自引用的。因此，交互矩阵Σ通常不是一个下三角矩阵（推论3）。

推论3. 在基于持续训练的系列算法中，交互矩阵Σ通常不是一个下三角矩阵。

证明. 当策略 $ i $ 被选中进行训练时，策略 $ k $ （$ k \geq i $）已经被实际初始化并因此被认为是有效策略。此外，在时期 $ e $ （$ e > 1 $）中，策略 $ k $ 已经被更新并持有重要意义。因此，策略 $ k $，其中 $ k \geq i $，可能被选为策略 $ i $ 的对手。因此，交互矩阵Σ通常不是一个下三角矩阵。

2. FTW：Quake III Arena Capture the Flag是一个著名的3D多人第一人称视频游戏，其中两支队伍竞相尽可能多地夺取旗帜。For The Win (FTW)代理[70]旨在在这款游戏中达到人类水平的熟练程度。FTW的一个关键方面是它采用了基于RL的持续训练自博弈。具体来说，它并行训练一组 $ N $ 个不同策略，这些策略相互竞争和协作。当策略 $ i $ 正在进行训练时，FTW从群体中采样其队友和对手。特别地，在每个队伍只由一名成员组成的场景中，它可以无缝地整合到我们的框架中，使用以下MSS：

$$ F(P)_{ij} = \frac{1}{N} $$

这基本上意味着交互图是密集连接的。此外，所有策略都利用统一的策略网络参数化为 $ \phi $。因此，$ \pi_{h_i}(\cdot|h(i)) $ 可以恰当地描述为 $ \pi_{\phi}(\cdot|h(i)) $。而且，由于这些策略不受任何外部参数的条件限制，表示条件函数 $ h(i) = \emptyset $ 是直接的。

3. NeuPL：NeuPL[43]引入了另一个关键创新：它采用了一个统一的条件网络，其中每个策略针对特定的元游戏混合策略进行调整。这对于实现跨策略的迁移学习至关重要。由于NeuPL依赖于统一的条件网络，由 $ \theta $ 参数化，$ \pi_i(\cdot|h(i)) $ 可以简洁地表示为 $ \pi_{\theta}(\cdot|h(i)) $，条件是对手采样策略 $ h(i) = \sigma_i $。有趣的是，$ \sigma_i $ 可能不是来自MSS。相反，它被抽样为来自群体单纯形的样本。这种抽样机制导致更大的鲁棒性。

4. Simplex-NeuPL：Simplex-NeuPL[71]基于NeuPL构建，旨在实现任何混合最优性，这表明制定的策略应该在广泛的对手范围内表现出灵活性，包括那些可能不具备相等竞争力的对手。为了从几何角度对群体学习过程进行建模，Simplex-NeuPL引入了群体单纯形的概念。类似于它的前身，Simplex-NeuPL整合了一个条件网络来表征策略，表示为 $ \pi_{\theta}(\cdot|h(i)) $，条件是对手采样策略 $ h(i) = \sigma_i $。有趣的是，$ \sigma_i $ 可能不是来自MSS。相反，它被抽样为来自群体单纯形的样本。这种抽样机制导致更大的鲁棒性。