清华北大等发布SelfPlay强化学习最新综述

论文题目：强化学习中自我对战方法的调查

研究机构：清华大学电子工程系、北京大学人工智能研究院、第四范式、腾讯、清华-伯克利深圳研究院论文链接：https://arxiv.org/abs/2408.01072

强化学习（RL）是机器学习中的重要范式，旨在通过与环境的交互来不断优化策略。基本问题建模基于马尔可夫决策过程（MDP）。代理观察状态，根据策略执行动作，接收相应的奖励并过渡到下一个状态。最终目标是找到最大化预期累积奖励的最优策略。

自我对弈通过与自己的副本或过去的版本交互来实现更稳定的策略学习过程。 Self-gaming在围棋、国际象棋、扑克、游戏等领域取得了一系列成功的应用。在这些场景中，超越人类专家的策略是通过自我博弈训练获得的。尽管自我博弈被广泛使用，但它也存在一些局限性，例如可能收敛到次优策略以及大量的计算资源需求。

本次综述的组织如下：首先，背景部分介绍了强化学习框架和基本博弈论概念。其次，在算法部分提出了统一的框架，并基于该框架将现有的自博弈算法分为四类进行系统的比较和分析。在后续的应用部分，我们将展示self-game如何应用到具体的复杂游戏场景中。最后，进一步讨论和总结了自我博弈中的未解决问题和未来研究方向。

背景

这部分分别介绍强化学习框架和博弈论基础知识。作为强化学习框架，我们考虑最通用的形式：部分可观察马尔可夫博弈（POMG），即每个智能体无法完全获取环境的所有状态的多智能体场景。

博弈论基础知识介绍了具体的博弈类型，包括（不）完全信息博弈和（不）完全信息博弈、标准博弈和扩展博弈、传递博弈和非传递博弈、阶段博弈和重复博弈、团队博弈等。它还介绍了博弈论框架的重要概念，包括最佳响应（BR）和纳什均衡（NE）。

复杂的游戏场景分析通常采用更高层次的抽象，即元游戏。元游戏不再关注个人行动，而是关注更高层次的复杂策略。在这个高抽象层次上，复杂的游戏场景可以被视为特殊的标准游戏，策略集由复杂的策略组成。元策略是混合策略，它将概率分配给策略集中的复杂策略。

在本节的最后，我们介绍了多种常用的自我博弈评估指标，包括纳什收敛（NASHCONV）、Elo、Glicko、全历史评级（WHR）和TrueSkill。

算法

我们定义了统一的自我博弈框架，将自我博弈算法分为四大类：传统自我博弈算法、PSRO系列算法、基于持续训练的系列算法、后悔最小化系列算法。

算法框架

首先，框架（算法1）的输入定义如下：

第一种：传统的自我博弈算法

传统的自我博弈算法从单一策略开始，逐渐扩大策略池，包括香草自我博弈（每个对手在训练时选择最新生成的策略）、虚构自我博弈（每个对手在训练时选择现有的训练策略）策略中均匀采样）、-uniform self-play（每个对手均按照训练时训练过的最近百分位数策略均匀采样）、Prioritized Fictitious Self-play（根据优先级函数计算当前训练的优先级）已完成策略的，训练时每个对手按照这个优先级进行采样），独立RL（训练时双方的策略都会改变，对手的策略不再固定）。

类型2：PSRO系列算法

与传统的自博弈算法类似，策略空间响应预言机（PSRO）系列算法也是从单一策略开始，通过计算ORACLE逐步扩大策略池。这些新添加的策略是当前元策略的近似BR。 PSRO系列与传统自博算法的主要区别在于PSRO系列使用了更复杂的MSS，旨在处理更复杂的任务。例如，-PSRO使用基于-rank的MSS来处理复杂的多人游戏。

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

PSRO系列算法主要面临两个挑战：首先，由于训练成本较大，近似的BR计算通常在每次迭代中被截断，这会将训练不足的策略添加到策略池中；第二，每次迭代都会重复学习基本技能，导致效率较低。为了应对这些挑战，基于连续训练系列的算法主张重复训练所有策略。与前面提到的两类最大的区别在于，连续训练系列算法同时训练整个策略池策略。此类算法采用多个训练周期，在每个训练周期中依次训练策略池中的所有策略，而不是通过逐渐扩大策略池进行训练。

类型4：遗憾最小化系列算法

清华北大等发布SelfPlay强化学习最新综述

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

各类算法对比总结图

应用

本节我们结合三类经典场景来介绍自博弈的经典应用：棋盘游戏，通常涉及完整的信息；纸牌游戏（包括麻将），通常涉及不完整的信息；和电子游戏，具有实时动作而不是简单的回合制游戏。

场景一：桌游

棋盘游戏领域绝大多数是完全信息游戏，棋局游戏领域因位置评估和蒙特卡罗树搜索这两项关键技术的引入而发生了革命性的变化。这两种技术都在国际象棋、跳棋、黑白棋和双陆棋等棋盘游戏中展现了超人的效果。相比之下，当这些技术应用于围棋时，只能达到业余水平的表现，因为围棋棋盘布局的多样性远远超过了上述棋盘游戏。直到DeepMind推出了AlphaGo系列，才发生了革命性的变化。 AlphaGo系列算法利用自博的力量，显着提升了性能，为围棋领域树立了新的标杆。

除了围棋之外，还有一种难度更高的国际象棋游戏，叫做“Stratego”。与大多数信息完全的棋类游戏不同，《军棋》是一款信息不完全的两人棋盘游戏。游戏分为两个阶段：部署阶段，玩家秘密布置自己的部队，为战略纵深奠定基础；游戏阶段，目标是推断对手的布局并夺取他们的旗帜。 DeepNash使用基于进化的自我博弈算法R-NaD达到了世界第三人类水平。

场景二：卡牌游戏

德州扑克是一种流行于欧美的扑克游戏，适合2至10名玩家。随着玩家数量的增加，游戏变得更加复杂。此外，还有三种投注形式：无限注、固定投注和底池限注。每种形式都有不同的游戏复杂性。在纸牌游戏中，游戏抽象对于简化游戏的复杂性、将游戏的大状态空间减少到更易于管理的数量至关重要。 Cepheus使用遗憾最小化系列算法CFR+来解决最简单的两人限注德州扑克游戏。对于更复杂的两人无限注德州扑克游戏，DeepStack 和Libratus 使用子游戏重新计算来实时做出决策，击败了职业德州扑克玩家。 Pluribus 比Libratus 更进一步，解决了六人无限注德州扑克问题。

斗地主既要考虑农民之间的合作，又要考虑农民与地主之间的竞争。斗地主也是一种不完全信息的游戏，这给游戏增加了不确定性和策略深度。 DeltaDou是第一个基于AlphaZero开发的达到专家级性能的算法。后来DouZero通过选择采样方法而不是树搜索方法来降低训练成本，并使用自博弈来获取训练数据。

麻将也会根据不完整的信息做出决定。此外，麻将的牌数更多，胜牌也更复杂，这对AI来说更具挑战性。 Suphx 成为第一个通过监督学习和自对弈强化学习达到人类专家水平的算法。由NAGA和腾讯设计的LuckyJ在在线平台上也达到了人类专家的水平。

场景三：电子游戏

与传统的桌游和卡牌游戏不同，电子游戏通常具有实时操作、较长的动作序列以及更广阔的动作空间和观察空间的特点。在《星际争霸》中，玩家需要收集资源、建造基地、组建军队。通过精心策划和战术执行，玩家需要让对方失去所有建筑物才能获胜。 AlphaStar利用监督学习、端到端强化学习和分层自对弈训练策略，在星际争霸II的1v1模式中击败了职业选手。

MOBA游戏需要两队玩家，每队控制自己独特的英雄，互相竞争以摧毁对方的基地。每个英雄都有独特的技能，在团队中扮演着特定的角色，不可能观察到整个地图。 OpenAI Five 在简化版Dota 2 中击败了世界冠军队伍，使用混合类型的自我对弈进行训练，其中Naive 自对弈概率为80%，Prioritized self-play 概率为20%。腾讯还在《王者荣耀》游戏的1v1和5v5模式中通过自我训练的方式击败了职业选手。

Google Research Football (GRF) 是一款开源足球模拟器。输入的是高级动作，需要考虑队友之间的配合以及两队之间的竞争，每队有11人。 TiKick利用WeKick的自博数据进行模仿学习，然后利用分布式离线强化学习来开发多智能体AI。 TiZero 将课程学习与自我游戏结合起来，无需专家数据，获得比TiKick 更高的TrueSkill 分数。

各场景类型对比总结图

讨论

自博弈方法因其独特的迭代学习过程和适应复杂环境的能力而表现出了优异的性能。但仍有许多方向值得进一步研究。

尽管许多算法是基于博弈论提出的，但当这些算法应用于复杂的现实场景时，理论与实际应用之间往往存在差距。例如，尽管AlphaGo、AlphaStar 和OpenAI Five 在实证上取得了成功，但缺乏正式的博弈论证明其有效性。

随着团队数量和团队内玩家数量的增加，自我博弈方法的可扩展性面临着巨大的挑战。例如，在OpenAI 5 中，英雄池的大小仅限于17 个英雄。从根本上来说，这是由于自博弈方法在计算和存储方面的训练效率有限：由于自博弈的迭代性质，代理反复与自己或过去的版本对弈，因此计算效率较低；自我博弈需要维护一个策略池。因此，对存储资源的需求比较高。