强化学习中自博弈方法的研究综述

摘要 ——自博弈通过让智能体与自身的副本或过去版本进行交互，近年来在强化学习领域引起了广泛关注。本文首先介绍了自博弈的基本概念，包括多智能体强化学习框架和博弈论的基础知识。接着，本文提出了一个统一的框架，并在该框架内对现有的自博弈算法进行了系统分类。通过详细分析自博弈在不同场景中的应用，本文搭建了算法与实际应用之间的桥梁。此外，本文还强调了自博弈面临的开放挑战及未来的研究方向。本综述为理解强化学习中自博弈的多维景观提供了重要的参考和指导。

索引词 ——自博弈、强化学习、博弈论、多智能体

I 引言

强化学习（RL）是机器学习中的一个重要范式，旨在通过与环境的交互优化决策过程。它通常通过马尔可夫决策过程（MDP）建模，MDP是一个数学框架，用于描述由状态、动作、转移和奖励组成的环境。在MDP中，智能体通过观察当前状态、执行策略定义的动作、接收相应的奖励，并转移到下一个状态来进行操作。RL算法的核心目标是找到最优策略，以最大化长期的预期累积奖励。深度强化学习进一步扩展了传统RL，通过深度神经网络作为函数逼近器，使其在处理高维状态空间时展现出巨大优势，推动了复杂任务中的多项突破。

本综述的组织结构如下：

• 第II节：介绍自博弈的背景，包括RL框架和基本的博弈论概念。

• 第III节：提出一个统一框架，并基于此框架将现有自博弈算法分为四大类，以明确自博弈的现状。

• 第IV节：进行综合分析，展示自博弈在不同场景中的应用。

• 第V节：描述自博弈中的开放问题，并探讨未来研究方向。

• 第VI节：对自博弈领域进行总结。

II 预备知识

在这一部分，我们首先介绍强化学习的框架，进而介绍自博弈中使用的基本博弈论概念和典型评估指标。

A. RL概念

在RL的背景下，智能体根据如下方式与环境进行交互：在每个离散时间步t，每个智能体i从环境中接收一个观测值Oi,t，并根据随机策略πθi: Oi × Ai → [0, 1]（其中θi是参数）选择一个动作。在接收到联合动作at = (a1,t,...,an,t)后，环境根据转移函数P从当前状态st过渡到后续状态st+1，并向每个智能体i发送一个奖励ri,t+1。智能体i的最终目标是最大化期望折扣累积奖励：Eπθi [∑∞t=0 γtri,t]。

B. 博弈论概念

1)（不）完美信 息和（不）完全信息：

2) 标准型和扩展型：

1. 标准博弈 ：这种博弈强调的是在一次性决策的情境下，每个玩家在做出选择时只知道自己的可用策略和收益，而不知道其他玩家的选择。所有玩家的决策同时进行，无法观察到对方的选择，常见的表示方法是通过赢利矩阵来展示各种策略组合下的结果。
2. 拓展博弈 ：在这类博弈中，博弈有多个阶段，玩家在博弈中的某个时刻做决策时，可以观察到之前发生的动作和事件。这种博弈通常通过决策树来表示，强调的是决策的序列和信息的演化，玩家需要根据先前的行动和可能的未来反应来制定策略。

囚徒困境是说明博弈论中各种概念的一个经典例子。在困境的一个修改版中(如图所示)：

• 如果一个玩家坦白（C），而另一个玩家撒谎（L），坦白者将入狱1年，而撒谎者将入狱8年。

• 如果两个玩家都选择坦白，他们都将入狱7年。

• 如果两个玩家都选择撒谎，他们都将只入狱2年。

这两种形式的博弈各有其表达方式，其中标准式可以转换为扩展式来表示信息集和决策路径，反之亦然。通过这些表示，可以更深入地分析和理解各种策略及其可能的结果。

图 1 囚徒困境的例子

除了标准型和扩展型博弈之外，还有在复杂的马尔可夫博弈或扩展型博弈中，元博弈（meta-game）作为一种高级抽象，经常被用于分析这些博弈。元博弈助于探索这些博弈内的策略学习，其焦点不是孤立的行动，而是由博弈动态产生的更广泛的策略。在高级的正规形式背景下，策略集由当前玩家所采用的策略组成。元策略是混合策略，它们在元博弈中为策略集分配概率。

3) 传递性博弈与非传递性博弈

• 传递性博弈 ：在这种博弈中，策略或结果遵循传递性关系。正式地，对于所有的策略πi, πj, πk ∈ Π，如果u(πi, πj) > 0 且 u(πj, πk) > 0，则必然有u(πi, πk) > 0。这种传递性属性简化了战略环境，允许对策略进行序数排名。
• 非传递性博弈 ：与传递性博弈相反，存在策略πi, πj, πk ∈ Π，使得u(πi, πj) > 0 和 u(πj, πk) > 0，但u(πi, πk) ≤ 0。这在策略之间引入了循环关系，从而使博弈复杂化。这种复杂性通常导致混合策略均衡，即玩家在多个策略之间随机选择以最大化其预期收益。非传递性博弈的一个典型例子是“石头-剪刀-布”，其中没有单一策略能够一致地胜过其他所有策略。

在现实世界环境中，博弈的复杂性超出了理论模型的范围。有文献认为，现实世界博弈有两个显著特征：首先，参与实践通常会导致性能提升；其次，存在大量性质上不同的策略，每种策略都有其独特的优势和劣势。在这样的博弈中，策略形成了一个类似于陀螺的几何拓扑结构，其中垂直轴代表策略的性能，径向轴代表最长循环的长度。

4) 阶段博弈与重复博弈

• 阶段博弈（或一次性博弈） ：只进行一次的博弈，即玩家之间的一次性交互。囚徒困境是一个著名的阶段博弈例子。
• 重复博弈 ：基于阶段博弈并多次进行的博弈。正式地，基于阶段博弈G的重复博弈定义为在T个周期内玩G，其中T可以是有限或无限的。重复博弈中的策略是历史依赖的，即它们可以依赖于过去所有回合的完整序列。值得注意的是，阶段博弈或重复博弈既可以以正常形式表示，也可以以扩展形式表示。

5）Nash Equilibrium（纳什均衡）

为了简化，我们用πi表示玩家i的策略，π−i表示除玩家i之外所有玩家的策略集合。给定π−i，玩家i的最佳响应（BR）是最大化玩家i收益的策略：

在扩展式博弈中，玩家的行为序列由Qi表示，代表玩家i采取的序列形式行动。序列形式策略由函数pi: Qi → R封装，该函数将每个序列q ∈ Qi映射到其执行的相关概率上。 ε-Best Response（ε-最佳响应） ： 策略πi 是策略π−i的ε-最佳响应，如果：

其中ε是一个预先指定的阈值。 定义 Nash Equilibrium（纳什均衡） ： 如果一个策略组合(π1*, π2*, ..., πn*)是一个Nash均衡（NE），对于每个玩家i：

这意味着，在给定其他所有玩家的策略下，没有玩家能通过单方面改变其策略来增加其收益。相应的，如果将收益增加拓展到不超过ε，则可以定义 ε-NE。然而，在复杂博弈中计算Nash均衡通常是不可行的，这导致一些研究人员利用α-Rank和相关均衡作为替代方案。此外，一些研究还采用复制者动态（Replicator Dynamics）作为分析和理解这些博弈中策略演化的方法。

6） 团队博弈

两人零和博弈框架可以自然地扩展到基于团队的零和博弈。Von Stengel和Koller分析了涉及单个团队与对手竞争的零和正常形式博弈。在这种团队博弈中，考虑一个由T = {1, 2, ..., n-1}表示的团队，玩家n是对手（D）。在这种零和正常形式团队博弈中，对于任意玩家i, j ∈ T，效用函数满足ui(π) = uj(π) = uT(π)和uD(π) = -(n-1)uT(π)。 零和单团队单对手正常形式博弈也可以扩展到扩展式博弈的领域。对于任意玩家i, j ∈ T和所有终端节点z ∈ Z，效用函数满足ui(z) = uj(z) = uT(z)和uD(z) = -(n-1)uT(z)。 在队友无法协调其策略的场景中，团队最大最小均衡（TME）成为最合适的解概念。我们用IT表示由Si∈T Ii定义的信息集，AT表示在IT内信息集中可访问的行动集合。 在队友无法协调策略的情况下，TME提供了一种解决方案，它确保了团队在面对对手时能够采取最优的应对策略，即使团队内部成员之间缺乏直接的沟通或协调。这种均衡概念在理解和分析多玩家团队竞争环境中非常有用。

玩家 i 的序列集合由 Qi 表示，它代表了玩家 i 所采取的序列形式行动。序列形式策略通过函数 pi : Qi →R来封装，该函数将每个序列 q ∈ Qi 映射到其对应的执行概率上。正式地，团队最大最小均衡（TME）的定义可以表述为：

对于序列形式博弈（如扩展式博弈），TME的计算可能更加复杂，因为它需要考虑到每个玩家在不同信息集上的行动序列及其概率分布。在实际应用中，TME的计算可能通过求解一个大型的线性规划问题或使用其他优化算法来实现。这些算法需要处理大量的约束条件，以确保得到的策略组合满足TME的定义和条件。类似于标准形式博弈中的论证，也可以推断出在扩展形式博弈中，如果不考虑任何退化情况，那么团队最大最小均衡（TME）是唯一存在的，并且这个TME与团队在纳什均衡下的效用最大化是一致的。

C. 自博弈评估指标

在本节中，我们介绍了多种自博弈评估指标，包括NASHCONV（第II-C1节）、Elo（第II-C2节）、Glicko（第II-C3节）、WHR（第II-C4节）和TrueSkill（第II-C5节）。其中，NASHCONV用于衡量与纳什均衡的距离，而其他四个指标则用于评估相对技能水平，并在表I中进行了比较。需要注意的是，尽管存在许多其他评估指标，但这里强调的指标是该领域中最广泛使用的。

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

1）NASHCONV：Nash收敛性（NASHCONV）

NASHCONV作为一种度量标准，用于测量特定策略与纳什均衡之间的偏差。较低的NASHCONV值意味着该策略更接近纳什均衡，暗示没有任何玩家可以通过单方面偏离该策略而获得利益。其正式定义如下：

其中，π 表示所有参与者的联合策略组合。特别地，在双玩家博弈的背景下，这种与纳什均衡的偏差通常被称为可利用性（exploitability）。即，如果某个策略的可利用性较低，那么它就更接近于一个纳什均衡，意味着没有任何玩家能通过单方面改变策略来获得更大的收益。

2) Elo

Elo系统基于一个假设运作，即每位玩家在每场博弈中的表现是一个正态分布的随机变量，其均值代表该玩家的当前等级分。在玩家A与玩家B之间的比赛中，RA 和 RB 分别代表玩家A和玩家B的当前等级分， EA 和 EB 分别表示玩家A和玩家B的预期得分（或获胜概率），可以表示为：

为了方便起见，我们使用逻辑函数来近似概率（使用以10为底的对数逻辑曲线，并选择400作为比例因子来缩放和归一化评分差异）：

请注意，EA + EB = 1。SA 是玩家A在比赛中的实际结果（胜为1，平为0.5，负为0）。SB = 1 - SA。比赛结束后，会根据实际结果与预期结果之间的差异来更新评分。调整公式为：

K 是一个缩放因子，通常由应用的具体领域决定，并控制单场比赛可能产生的最大评分变化。如果两名玩家的评分非常接近，那么预期结果将接近 0.5。任何一方获胜都会导致其评分适度增加。相反，如果评分差异显著，那么预期结果将严重偏向某一方。如果评分较高的玩家获胜，其评分将增加的值远小于 K，这反映了其胜利的预期性质。然而，如果评分较低的玩家获得意外胜利，其评分将激增，增加值接近 K，这表示了一场令人惊讶的逆转。

然而，Elo系统也存在挑战和局限性。首先，Elo系统假设所有博弈都同等重要，但这在所有领域可能并不成立。其次，K 值通常保持不变。然而，一个动态的 K 因子可能更合适，特别是对于新加入评分池的玩家或在博弈重要性不同的场景中。第三，标准的 Elo 系统没有引入衰减机制来考虑在不活跃期间技能可能下降或提高的情况。第四，基本的 Elo 系统是为一对一博弈设计的。将其适应团队或多人场景，如团队运动或在线多人博弈，可能具有挑战性。最后，Elo 评分系统的一个重要局限性是它不适合非传递性水平较高的博弈。

3）Glicko

Glicko 系统通过引入玩家评分中的不确定性或可靠性度量（称为评分偏差）来改进 Elo 系统。其主要动机是考虑玩家表现的差异性和技能随时间可能发生的变化。Glicko-2 系统是原始 Glicko 系统的扩展，它进一步细化了这些概念，并引入了评分波动性 σ，表示玩家评分预期波动的程度。

在 Glicko-2 系统中，r 表示玩家的当前评分，RD 表示玩家的评分偏差，σ 表示玩家的波动性。将评分和评分偏差转换为 Glicko-2 量表：

然后，计算 v，它表示基于 博弈 结果对玩家评分的估计方差；E(μ, μj, φj) 表示评分为 μ 的玩家击败评分为 μj 的对手 j 的概率；Δ 表示仅基于 博弈 结果 sj 的估计改进：

σ 的更新更为复杂，需要通过迭代过程来求解其新值 σ'。然后，计算新的 μ' 和 φ'：

计算完成后，将评分和评分偏差从 Glicko-2 量表转换回原量表：

4）WHR

全历史评分（WHR）系统是一个贝叶斯评分系统，旨在根据玩家的整个博弈历史来估计其技能。它特别适用于处理玩家技能的时间动态。Ri(t) 表示玩家 i 在时间 t 的 Elo 评分。类似于等式（11）和等式（12），EA(t) 和 EB(t) 分别表示在时间 t 时玩家 A 和玩家 B 的预期得分（或获胜概率）：

此外，WHR 假设每个玩家 i 的评分是一个维纳过程（Wiener process）：

给定 r ′= RA ( t 1) 和 r ′′= RA ( t 2)，其中 RA ( t ) 表示玩家 A 在时间 t 的 Elo 评分，我们可以利用维纳过程的性质来估计 r ′ 和 r ′′ 之间的关系。

那么评分的变化量 σ 可以用 ω 和时间差∣ t 2− t 1∣来表示，即 σ = ωp ∣ t 2− t 1∣，其中 p 是一个与具体实现相关的参数，可能用于调整时间差对评分变化的影响。

5）TrueSkill

当两个团队进行比赛时，TrueSkill 计算两个团队表现的差异 d 。如果 d > ϵ （其中 ϵ 是一个小的正阈值），则团队 1 击败团队 2。TrueSkill 的更新机制使用无向概率图模型中的和积消息传递算法来迭代地精炼技能估计，从而为每个玩家提供准确可靠的评分。

III 统一的自博弈框架

• 在我们的框架中，所有玩家共享一个共同的策略集（或策略网络），最大数量固定的种群。在每次迭代中，一个新的策略被初始化用于训练，对手策略从现有的策略群体中采样。在此迭代过程中，对手策略通常保持不变，而只有正在训练的策略会更新。在培训过程之后，新策略将替换策略总体中的某个策略。然后使用评估指标来评估更新后的策略群体的性能。基于这一表现，下一次迭代调整了对手的采样策略。重复此过程。

此外，我们将自我博弈算法分为四个主要组别：传统自我博弈算法（第III-B节）、PSRO系列（第III-C节）、基于持续训练的系列（第III-D节）和基于遗憾最小化的系列（第III-E节）。我们分析了这四类算法在各自部分中如何与我们的框架保持一致，并在每个类别中介绍了代表性算法。此外，在第三部分F中，我们讨论了这四类之间的差异以及它们与我们提出的框架的联系。我们还解释了为什么我们的框架比现有的框架更通用。此外，我们在表II中总结了每个类别框架内关键算法的主要元素。

A.框架定义

• 首先，Π可以被视为用N个占位符策略进行初始化，这意味着在实践中并没有对策略进行实际的初始化。相反，每个策略将在训练迭代中实际初始化（算法1中的第3行）。我们将这种方法称为占位符初始化。
• 其次，Π可以用N个真实策略进行初始化，这些策略可能包括随机初始化或预训练模型。我们将这种方法称为实际初始化。如果策略πih作为占位符策略，则被视为无效策略；否则，被视为有效策略。此外，表II更清晰地说明了主要自我博弈算法不同类别中Π的初始化和h(i)的表达式。Σ := {σi }Ni=1 ∈ RN ×C1：策略总体的交互矩阵。σi ∈ RC1表示策略i的对手采样策略。即，σi说明了如何针对策略i采样对手的策略。
• 例如，让σi表示每个对手策略的概率。在这种情况下，C1 = N^(n-1)，其中n表示玩家的数量。或者，σi也可以被视为采样网络内的采样参数。特别是在两人博弈中，如果C1 = N且σij表示策略i针对策略j进行优化的概率，则Σ可以用有向交互图来表示）。
• 要注意，与原始的PSRO框架不同，这里的σi不是策略i的元策略。相反，在两人设置中，如果我们的框架中的σi是针对策略i的对手的元策略，那么我们的框架可以简化为原始的PSRO框架。

当C1 = N，σij表示策略i相对于策略j优化的概率时，我们可以考虑各种传统的自我  博弈算法的例子：在顶部部分，我们将Σ∈R3×3定义为{σi}3i=1。在底部部分，我们展示了有向交互图，其中每个节点

• F : RN × C2 → RN × C1：一个 元策略求解器 （Meta-Strategy Solver, MSS）F 接受性能矩阵P := {pi}Ni=1 ∈ RN × C2作为输入，并输出一个元策略矩阵Σ := {σi}Ni=1 ∈ RN × C2，作为其输入，并产生一个新的交互矩阵∑∈RN×C1作为其输出。pi是策略i的表现。例如，pi可以描述为相对技能，如Elo评级（C2=1），也可以描述为收益张量（C2=Nn-1，其中n是参与者的数量）。特别地，在两人对称零和博弈中，预期收益可以作为评估指标。在这种情况下，∑是一个方阵（C2=N）。此外，表二总结了这四类代表性自我博弈算法的MSS。接下来，框架内的核心流程如下：• 对于 epoch e ∈ [[E]]（算法1第1行）：E表示整个策略群体的总迭代次数。例如，如果算法只将新策略引入群体而不更新现有策略，则E=1。这意味着，在每次迭代中，只有无效的政策才有可能被选择进行培训，并转化为有效的政策，而有效的政策则保持不变。相反，如果有效的政策在整个算法中多次更新，则E>1。事实上，E准确地反映了所执行的更新次数。此外，表二总结了不同类别的自我学习算法的E值。• 初始化πih（算法1第3行）：πih的初始化可以根据所使用的算法而变化。例如，它可以通过利用预先训练的模型或通过最近更新的策略进行随机初始化。我们为每个算法系列提供了初始化过程的详细说明。此外，这些内容在表二中进行了总结。
• ORACLE(πi，σi，Π)（算法1第4行）：ORACLE是一个抽象的计算实体，它返回一个符合特定标准的新策略。在这里，我们将ORACLE分为三种类型。
• 一种常见类型是BR预言机， 旨在识别针对对手策略的最佳应对策略，包括寻找NE。然而，这通常需要大量的计算工作。这种计算需求可能是一种限制，特别是在复杂的环境中或具有较大的动作空间的情况下。
• 为了减轻计算需求，引入了近似最佳响应（ABR）预言机，可以使用RL（算法2）、基于进化理论的方法（算法3）或遗憾最小化方法（算法4）等技术进行计算。
• 其他特制的ORACLE要么是为新的MSS量身定做的，要么是为了增强多样性而引入的。

B. 传统的自我博弈算法

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

1）融入统一的框架：

我们可以使用以下设置将传统的自我 博弈 算法纳入我们提出的框架（算法1）。

• 第一，Π使用占位符初始化，这意味着最初，这些策略是占位符，而不是实际初始化的策略。使用这种初始化方法是因为传统自我博弈算法中的策略群体旨在随着每次迭代而增长。
• 其次，我们设置E=1，因为在传统的自我博弈算法中，每次迭代中可能只选择一个无效的策略进行训练，从而将其转化为一个有效的策略。在这里，策略人口规模N作为人口中有效策略数量的上限。换句话说，我们使用N次迭代来优化策略。
• 第三，正在训练的策略πih可以以一般的方式初始化。例如，该策略可以随机启动，这意味着从头开始学习过程。更常见的是，πih由πi−1(·|h(i − 1))初始化，允许基于最新训练策略的增量学习和适应，以加速收敛。
• 第四，由于传统自博弈戏算法中的策略没有条件，我们简单地设置h(i) = ∅。

接下来，我们概述传统的自我博弈方案。为了简单起见，我们根据以下假设进行操作：假设1：在两人对称博弈中，C1=N，σij表示政策i针对政策j进行优化的概率，导致PNj=1σij=1，∀i。基于假设1，我们可以进一步推导出以下重要推论：推论1：在传统的自我博弈算法中，交互矩阵Σ是一个下三角矩阵。证明。保单数量会随着时间的推移而逐渐增加。因此，当选择策略i进行训练时，只有策略j（j≤i）已经过训练并具有有意义的结果。其他政策都是无效政策。因此，我们专门选择策略j（其中j ≤ i）作为策略i的对手。

2) 原始自我博弈：

在原始自我博弈中，智能体通过与最新版本竞争来训练，确保一致和协调的学习。原始自博弈MSS：

无论P是什么，MSS都会产生相同的交互矩阵，类似于策略的迭代优化过程。虽然这个MSS很简单，但它被用于许多进一步的工作中，所以我们称之为vanilla MSS。尽管原始自博弈在传递性博弈中是有效的，但它可能会导致代理在非传递性博弈中（如石头剪刀布）形成循环学习模式。

3) 虚拟自我博弈：

虚拟博弈（FP）是一种博弈论中的学习算法，其中每个玩家都能对对手使用的策略的经验频率做出最佳反应。如果对手的策略是静态的，FP可以找到NE。基于FP的直觉，引入了虚拟自我博弈（FSP），使智能体与过去的自己进行博弈，以学习最优策略，提高原始自我博弈的鲁棒性。神经虚拟自我博弈（NFSP）是一种现代变体，它将FSP与深度学习相结合技术。它使用神经网络来近似BR。在NFSP和FSP的原始版本中，使用了两种不同类型的代理记忆：一种用于记录代理自己的行为，另一种用于捕获对手的行为。然而，在最近的方法中，经常采用随机抽样来近似对手的平均策略，从而消除了维护两种不同类型代理记忆的需要。因此，FSP的MSS：

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

4) δ-均匀自博弈：

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

其中⌈·⌉是向上取整函数，它提供大于或等于给定输入数的最小整数。在δ-均匀自博弈中，MSS生成一个恒定的交互矩阵。特别地，如果δ=0，它对应于FSP，如果δ=1，它对应于普通的自博弈。

5）优先虚拟自我博弈：

优先虚拟自我博弈（PFSP）利用一个优先函数来为优先级更高的智能体分配更高的选择概率。在这里，P代表胜率，具体定义为Pij = Prob(πi击败πj)。PFSP的MSS由算法5给出。

函数f : [0, 1] → [0, ∞)是一个优先级函数。例如，f (x) = (1 − x)p，其中p > 0，表示针对当前训练策略的更强策略有更高的机会被选为对手。或者，f = x(1− x)意味着水平相似的玩家更有可能被选为对手。此外，从更广泛的角度来看，P也可以由其他指标进行评估。在中，可以使用类似的MSS来为表现更好或更难击败的策略分配更高的概率。

6) 独立RL：

独立RL是MARL中一种完全去中心化的方法。这简化了学习过程，在竞争或对抗环境中非常有用，但在需要合作的情况下可能会导致次优结果。独立RL可以被视为自我博弈算法的一个特例。在每次迭代中，要训练的策略πih使用之前的策略πi-1(·|h(i-1))进行初始化。独立RL的MSS简化为单位矩阵

独立RL与普通自我博弈之间的区别在于训练过程中如何处理对手的策略。在普通自我博弈中，对手的策略通常是固定的，这使得训练过程变得平稳。相比之下，在独立RL中，对手的策略随着正在训练的策略一起演变，导致训练过程变得非平稳。此外，如果在独立RL中使用离策略RL方法，那么即使样本是由不同的策略生成的，它们仍然可以用于训练。这允许智能体更有效地利用过去的经验，并从更广泛的场景中学习。

C. PSRO系列算法

类似于传统的自我博弈算法，PSRO系列算法从一个单一策略开始，并通过引入新的oracle（即针对其他智能体当前元策略的最优响应策略）来逐渐扩展策略空间。此外，PSRO还采用EGTA来更新元策略分布，从而在策略选择中引入一定程度的探索，以降低过拟合的风险。

1）融入统一的框架 ：

• 类似于传统的自我博弈算法，我们也使用占位符初始化来初始化Π。
• 我们设置E=1，N可以视为原始PSRO算法中策略种群大小的上限。
• 在PSRO系列算法的上下文中，我们的玩家πih的策略也可以以一般方式进行初始化。
• 我们简单地设置h(i)=∅，因为PSRO系列算法的 策略不需要任何的条件函数
• 我们的框架在定义σi的方式上与传统的PSRO模型有所不同。在我们的框架中，σi不是策略的元策略，而是对手采样策略。这意味着在PSRO系列算法中，σi代表针对策略i的对手的元策略。
• 第六，与传统自我博弈方法相比，PSRO系列的MSS通常更复杂。例如，一些MSS结合了来自不同类型博弈均衡的概念。

为了简化，我们也遵循假设1。类似于传统的自我博弈算法，我们可以推导出 推论2 ： 在PSRO系列算法中，交互矩阵Σ是一个下三角矩阵。

2）双Oracle：

双Oracle（DO）算法传统上仅应用于两人标准型博弈。在这种上下文中，我们可以利用收益矩阵作为评估矩阵。交互矩阵可以用全零初始化，以反映策略之间初始不存在交互的情况。然后，DO的MSS（混合策略集）可以如算法6中所述进行概述。对手采样策略σi对应于受限博弈中对手的纳什均衡策略。因此，在DO中，oracle是一个最佳响应（BR）而不是近似最佳响应（ABR），它计算的是针对受限博弈当前NE对手策略的最佳响应。在两人标准型博弈的上下文中，DO理论上可以实现完整博弈的纳什均衡。

3）PSRO:

PSRO（Policy Space Response Oracle）算法将双Oracle（DO）算法扩展到更复杂的博弈领域，超越了传统的两人标准型博弈。PSRO首先引入了MSS（混合策略集）的概念，这是一个比简单计算纳什均衡更广泛的概念。MSS框架允许在不同博弈设置下更灵活地表示战略解决方案。PSRO的许多变体都致力于设计新的MSS，以更好地捕捉这些更复杂博弈中战略博弈的不同方面。在原始的PSRO框架中，oracle是通过类似于算法2中描述的RL技术来计算的。这使得算法能够有效地处理庞大且复杂的策略空间，适用于广泛的博弈场景。

4）PSRO变体：

其他研究则侧重于策略多样性，因为在高度传递性博弈中推导单一策略通常意义不大。在两玩家零和博弈中引入了一个开放式的框架，该框架增强了策略种群的多样性，并引入了博弈景观（gamescape），它几何地表示了博弈中开放式学习的潜在目标。该研究提出了两种算法：Nash响应PSRON和修正Nash响应PSROrN。这两种算法都使用非对称收益矩阵作为其性能评估指标。与DO类似，它们采用基于Nash的MSS（算法6）。与PSRON相比，PSROrN在ABR oracle中增加了一个步骤，以关注它们打败或打平的对手，并忽略它们失败的对手。使用行列式点过程（determinantal point process）来评估多样性，并通过在PSRO oracle中引入多样性项来引入多样化PSRO。这种修改也可以很容易地应用于FP和α-PSRO。制定了行为多样性和响应多样性，并将它们纳入PSRO oracle中。策略空间多样性PSRO（Policy Space Diversity PSRO）定义了一个名为种群可剥削性的多样性度量，有助于实现全博弈的NE。

5）R-NaD：

尽管R-NaD最初被描述为利用带有正则化组件的进化博弈论，但在这里我们将其归类为具有特殊oracle计算技术（算法3）的PSRO系列。该技术分两个阶段执行：第一阶段根据正则化策略转换奖励，使其依赖于策略；第二阶段应用复制动态（replicator dynamics）直到收敛到固定点。重要的是，在每次迭代中，添加到策略种群Π中的oracle来自奖励转换后的博弈，而不是原始问题的oracle。然而，这种方法确保了只要博弈是单调的，策略就会收敛到原始博弈的NE。R-NaD的MSS是如等式（33）所述的普通MSS，与自博弈的普通MSS相同。该等式说明了每次迭代中达到的固定点（即oracle）被用作下一次迭代的正则化策略。

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

在PSRO算法系列中，存在两个主要挑战。首先，在有限的预算下操作时，通常需要在每次迭代中截断ABR操作，这可能会将次优训练的反应引入种群中。其次，每轮重新学习基本技能的冗余过程不仅效率低下，而且在面对越来越强大的对手时变得难以为继。为了应对这些挑战，基于持续训练的算法系列提倡对所有策略进行反复的持续训练。即，所有有效的策略都有可能被选中进行训练。

1）融入统一的框架：

我们可以使用以下设置将这些基于持续训练的算法系列集成到我们提出的框架（算法1）中：

• 我们使用实际初始化来初始化策略种群Π，因为在基于持续训练的算法系列中，策略种群中的所有策略都是一起训练的，而不是随着每次迭代而增长。
• 我们设置E = Emax > 1，这表示策略种群中每个策略优化的最大轮次。换句话说，每个独特的策略都会经历总共Emax次的迭代训练。
• 由于每个策略都经历了Emax次的训练，我们使用πi(·|h(i))来初始化πih。这意味着策略更新是自引用的。

为了简化，我们也采用了假设1。与推论1和推论2不同，考虑到所有策略的持续训练过程，我们推导出了 推论3 ： 在基于持续训练的算法系列中，交互矩阵Σ通常不是下三角矩阵。

2）FTW：

Quake III Arena Capture the Flag是一款著名的3D多人第一人称视频游戏，两队竞争以捕获尽可能多的旗帜。For The Win（FTW）代理被设计在该游戏中达到人类水平的熟练度。FTW的一个关键方面是其在RL中采用基于持续训练的自博弈。具体来说，它并行训练N个不同的策略，这些策略相互竞争和协作。当策略i正在接受训练时，FTW从种群中采样其队友和对手。特别地，在每个团队只包含一名成员的场景中，它可以无缝地集成到我们的框架中，使用后续的MSS：

这基本上意味着交互图是密集连接的。此外，所有策略都依赖于一个由φ参数化的统一策略网络。因此，πi(·|h(i))可以恰当地表示为π(·|h(i))。此外，由于这些策略不依赖于任何外部参数，因此可以直接将条件函数h(i)表示为∅（空集）。

3）NeuPL ：

NeuPL引入了另一个关键创新：它采用了一个统一的条件网络，其中每个策略都是针对特定的元博弈混合策略进行调整的。这对于实现跨策略迁移学习至关重要。由于NeuPL依赖于一个由θ参数化的统一条件网络，πi(·|h(i))可以简洁地表示为πθ(·|h(i))。此外，鉴于NeuPL中的策略依赖于对手采样策略σi，因此将h(i)定义为σi是恰当的。

4）Simplex-NeuPL：

Simplex-NeuPL在NeuPL的基础上进行了扩展，旨在实现任意混合最优性，这意味着制定的策略应该能够灵活地应对各种对手，包括那些可能不具备同等竞争力的对手。为了从几何角度模拟种群学习过程，Simplex-NeuPL引入了种群单纯形的概念。与其前身类似，Simplex-NeuPL集成了一个条件网络来表征策略，该策略表示为πθ(·|h(i))，其中h(i) = σi是条件对手采样策略。有趣的是，σi并非一定来自MSS，而是作为种群单纯形中的一个样本被抽取出来。这种采样机制增强了鲁棒性。

E. 基于遗憾最小化的算法系列

另一类自我博弈算法是基于遗憾最小化的。这类算法与其他类别的主要区别在于，它们优先考虑长时间内的累积收益，而不仅仅是单个回合。这种方法导致了更激进和适应性更强的策略，这对于避免在时间推移中被对手利用至关重要。此外，这些算法要求玩家在多轮博弈中推断并适应对手的策略。这种情况在重复博弈中更为常见，而不是在阶段博弈中。例如，在德州扑克或狼人杀等博弈中，玩家必须使用欺骗、隐藏和虚张声势来争取整体胜利，而不仅仅是赢得单场比赛。值得注意的是，虽然传统的基于遗憾最小化的自我博弈通常不使用强化学习，但随后的许多研究工作已经将遗憾最小化与RL相结合，以实现强大的性能。在本节中，我们还将详细讨论传统的基于遗憾最小化的方法，为理解如何将遗憾最小化与RL相结合以提高性能奠定基础。

1）融入统一的框架：

• 类似于传统的自我博弈算法和PSRO系列，我们使用占位符初始化来初始化策略集Π。
• 我们设置E=1，并将N视为优化策略的最大迭代次数。
• 我们使用πi-1(·|h(i-1))来初始化πih，以利用最新的训练策略。更具体地说，h(i) = h(i-1)且πh = πh-1。
• 在每个迭代i中，h(i)表示基于遗憾最小化的自我博弈算法需要存储的特定元素。重要的是要注意，基于遗憾最小化的系列算法非常依赖于h(i)中包含的信息。例如，在基本的反事实遗憾最小化（CFR）中，需要在h(i)中为每个玩家的每个信息集中的每个动作存储反事实遗憾，并且一旦h(i)确定，就通过遗憾匹配来定义相应的策略。我们将在第III-E2节中详细讨论基本的CFR。
• ABR操作在算法4中描述，其关键点是将新的基于遗憾最小化的信息纳入h(i)。值得注意的是，虽然原始的CFR同时更新所有玩家的遗憾，但这个oracle（算法4）按顺序更新每个玩家的遗憾。这意味着在迭代i中，玩家2的遗憾是在考虑玩家1已更新遗憾之后更新的。即，h(i)在迭代i期间是变化的。这种调整不仅已被证明在经验上加速了收敛速度，而且还具有理论上的误差界。
• 每个πih代表所有玩家的策略，在迭代i中，玩家j使用策略πih(j)。

此外，基于遗憾最小化的算法系列的MSS是如等式（33）中所述的普通MSS。我们可以推导出 推论4 ：在基于遗憾最小化的算法系列中，交互矩阵Σ是一个下三角矩阵。更具体地说，它是一个单位下移矩阵，仅在次对角线上有1，其余位置为0。

2）原始CFR：

Vanilla CFR 涉及维护策略和每个信息集的反事实遗憾。理论上，即时反事实遗憾是针对每个信息集的，这些即时反事实遗憾的聚合可以作为总体遗憾的上限。因此，问题可以从最小化总体遗憾到最小化每个信息集中的即时反事实遗憾来简化。这种简化显著降低了计算复杂度。接下来，对原始CFR进行更详细的描述。在本文中，πi用于表示迭代i的策略，而原始论文使用σ。进行这一变化是为了保持本文中讨论的一致性。此外，我们用j来表示玩家j，πi(j)表示玩家j在迭代i时使用的策略。反事实值vj(π,I)表示当除玩家j外的所有玩家都遵守策略π时，达到信息集I时的期望值：

在原论文中，这是一种未规范化的反事实效用形式。基于这个反事实值，即时反事实遗憾被定义为 ：

其中，πi|I→a 表示在第 i 次迭代中，玩家 j 在信息集 I 处以概率为 1 选择动作 a。此外，正的即时反事实遗憾是：

从理论上讲，总体平均遗憾 RjT 受正即时反事实遗憾之和的限制：

因此，基于上述讨论的理论，可以将遗憾最小化的整体问题分解为许多较小的遗憾最小化问题。这种方法使得对于规模不是过大的广延式博弈来说，问题变得易于管理。在实际应用中，主要关注的是即时反事实遗憾。为了简化讨论，我们经常在讨论中省略“即时”这个词，从而直接提及反事实遗憾。因此，与每个信息集 I 中的每个动作 a 相关联的反事实遗憾记录如下：

使用遗憾匹配算法来决定每个信息集中的策略：

基本的CFR算法有几个缺点。首先，它要求在每个迭代中遍历整个博弈树，这在博弈树较大的情况下计算上变得难以处理。尽管一些研究致力于通过博弈抽象来减小博弈树的大小，但更多的抽象可能导致性能下降。其次，它需要在每个迭代 i 中为每个信息集 I 中的每个动作 a 存储反事实遗憾 Ri(I, a)。在我们的框架（算法1）中，这些值被存储在 h(i) 中。这一要求带来了显著的存储挑战。

2）CFR节省时间的变体：

因此，许多研究主要通过两种主要方法来提高CFR的时间效率。第一种方法涉及修改遗憾计算以提高其速度。

另一种方法涉及采用抽样方法。虽然这种方法需要更多的迭代次数，但每次迭代的持续时间减少，最终减少了达到收敛所需的总时间。

蒙特卡洛CFR（MCCFR）概述了一个将抽样融入CFR的框架。该方法将终端历史划分为块，每次迭代从这些块中进行抽样，而不是遍历整个博弈树。这使得可以计算每个玩家的抽样反事实值，从而产生即时反事实遗憾，这些遗憾在期望上与原始CFR的反事实遗憾相匹配。原始CFR代表了一个特殊情况，即所有历史都被划分为一个块。

MCCFR通常以三种形式出现：

• 结果抽样MCCFR，其中每个块对应一个历史；
• 外部抽样MCCFR，其对对手和机会节点进行抽样；
• 以及机会抽样MCCFR，其仅关注机会节点。
• 此外，将机会抽样扩展为朴素机会抽样、对手/公共机会抽样、自我/公共机会抽样和公共机会抽样。这些方法在处理公共和私有机会节点的抽样方式上有所不同。一些研究还专注于学习如何减少MCCFR的方差以加速收敛。

除了这两种主要方法外，其他研究还发现热启动和修剪技术也可以加速CFR的收敛。

3）CFR节省空间的变体：

在每个迭代中存储每个信息集的策略和遗憾需要大量的存储空间。在完全信息博弈中，通过分解来减小问题求解的规模；即，我们解决子博弈而不是整个博弈。然而，这种方法在不完全信息博弈中面临挑战。困难在于定义子博弈，因为它们可能与信息集的边界相交，从而使其划分变得复杂。CFR-D是一种具有理论保证的分解不完全信息博弈的开创性方法。博弈被分为主干部分（称为“主干”）和几个子博弈。它假设在不完全信息博弈中，子博弈可以被概念化为不分割任何信息集的树林。在每个迭代中，对主干中的两名玩家应用CFR，并使用求解器来确定子博弈中的反事实最佳响应。该过程包括使用来自子博弈根部的反事实值来更新主干，并更新该根部的平均反事实值。在这些更新之后，子博弈的解决方案被丢弃。CFR-D通过仅保存位于主干和每个子博弈根部（在每个迭代i中表示为I∗）的信息集的值Ri (I∗ , a)，来最小化存储需求，从而在存储效率与解决子博弈所需时间之间进行权衡。DeepStack使用的Continue-Resolving技术和Libratus使用的Safe and Nested Subgame Solving技术也体现了类似的思想。我们将在第IV-B1节中讨论这些方法，并探讨它们在德州扑克特定背景下的应用。

4）CFR的估计方式变体：

因此每个中间迭代的策略仍然取决于优势网络的输出：h(i) = V (I , a|θp )。尽管存在相似性，但Deep CFR通过其数据收集和在更大规模的扑克博弈中证明的有效性，与Double Neural CFR区分开来。此外，Single Deep CFR（SD-CFR）表明，训练平均策略网络是不必要的，只需要一个优势网络。在SD-CFR的基础上，DREAM利用学习到的基线，在只在每个决策点采样一个动作的无模型设置中保持低方差。此外，优势遗憾匹配行动者-评论家（ARMAC）将回顾性策略改进的思想与CFR相结合。

F. 统一框架的再思考

传统的自博弈算法和PSRO系列（Policy Space Response Oracle）存在许多相似之处。它们最初都只需要一个随机初始化的策略，并随着训练的进行，策略集逐渐扩大。因此，在我们的框架中，我们使用占位符初始化来初始化策略集，并为这两类算法设置E=1。交互矩阵通常是下三角矩阵（推论1和推论2）。PSRO系列与传统自博弈算法的主要区别在于，PSRO系列采用了更复杂的MSS（Meta-Strategy Solver，元策略求解器），旨在处理更复杂的任务。例如，α-PSRO特别使用了一种基于α排名的MSS来处理多玩家总和博弈。

我们的框架是建立在PSRO和NeuPL的基础上的。在这里，我们概述了我们的框架与这两个现有框架之间的差异。我们的框架与PSRO的主要区别在于使用了一个交互矩阵Σ 来表示对手采样策略，从而能够整合更复杂的竞争动态。此外，在我们的框架中，σi表示对手采样策略，它指定了如何针对策略i采样对手的策略，而不是策略i的元策略。此外，我们的框架还引入了策略条件函数h(i)，这使得我们的框架比NeuPL更通用，其中NeuPL中的策略以σi为条件。这一增强使我们的框架具有更高的表达能力。此外，我们还描述了如何以三种不同的方式计算oracle（算法1中的第4行）（算法2、算法3和算法4），以提供更清晰的理解。据我们所知，我们的框架是第一个将基于遗憾最小化的系列算法集成的自博弈框架，这是一个重要的自博弈范式。

IV. 应用分析

在本节中，我们通过将场景分为三组来介绍自博弈的标志性应用：棋盘 博弈 （通常涉及完全信息）、纸牌 博弈 和麻将（通常涉及不完全信息）以及电子 博弈 （以实时动作为主，而非回合制）。然后，我们展示了自博弈在这些复杂场景中的具体应用，并在表III中提供了这些应用的比较分析。

A. 棋盘博弈

棋盘 博弈 领域，其中大多数是完全信息 博弈 ，这些 博弈 中的策略生成方法曾因两项关键技术的引入而发生革命性变化：位置评估（position evaluation）和蒙特卡洛树搜索（MCTS）。这些方法经过轻微修改后，在解决如国际象棋、跳棋、五子棋、双陆棋和拼字 博弈 等棋盘博弈中展现出了超人的效果。然而，将这些技术应用于拥有约2.1 × 10¹⁷⁰种棋盘配置的围棋时，其表现仅能达到业余水平。鉴于此，我们的讨论将特别聚焦于围棋，以说明自博弈的应用。此外，我们还将讨论范围扩大到包括战棋（stratego）在内的不完全信息棋盘博弈，这与大多数基于完全信息的棋盘博弈大有不同。