本文作者來(lái)自于清華大學(xué)電子工程系，北京大學(xué)人工智能研究院、第四范式、騰訊和清華-伯克利深圳學(xué)院。其中第一作者張瑞澤為清華大學(xué)碩士，主要研究方向?yàn)椴┺乃惴?。通訊作者為清華大學(xué)電子工程系汪玉教授、于超博后和第四范式研究員黃世宇博士。

自博弈（self-play）指的是智能體通過(guò)與自身副本或歷史版本進(jìn)行博弈而進(jìn)行演化的方法，近年來(lái)在強(qiáng)化學(xué)習(xí)領(lǐng)域受到廣泛重視。這篇綜述首先梳理了自博弈的基本背景，包括多智能體強(qiáng)化學(xué)習(xí)框架和博弈論的基礎(chǔ)知識(shí)。隨后，提出了一個(gè)統(tǒng)一的自博弈算法框架，并在此框架下對(duì)現(xiàn)有的自博弈算法進(jìn)行了分類(lèi)和對(duì)比。此外，通過(guò)展示自博弈在多種場(chǎng)景下的應(yīng)用，架起了理論與實(shí)踐之間的橋梁。文章最后總結(jié)了自博弈面臨的開(kāi)放性挑戰(zhàn)，并探討了未來(lái)研究方向。

• 論文題目：A Survey on Self-play Methods in Reinforcement Learning
• 研究機(jī)構(gòu)：清華大學(xué)電子工程系、北京大學(xué)人工智能研究院、第四范式、騰訊、清華-伯克利深圳學(xué)院
• 論文鏈接：https://arxiv.org/abs/2408.01072

引言

強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）是機(jī)器學(xué)習(xí)中的一個(gè)重要范式，旨在通過(guò)與環(huán)境的交互不斷優(yōu)化策略?；締?wèn)題建模是基于馬爾可夫決策過(guò)程（Markov decision process，MDP），智能體通過(guò)觀察狀態(tài)、根據(jù)策略執(zhí)行動(dòng)作、接收相應(yīng)的獎(jiǎng)勵(lì)并轉(zhuǎn)換到下一個(gè)狀態(tài)。最終目標(biāo)是找到能最大化期望累計(jì)獎(jiǎng)勵(lì)的最優(yōu)策略。

自博弈（self-play）通過(guò)與自身副本或過(guò)去版本進(jìn)行交互，從而實(shí)現(xiàn)更加穩(wěn)定的策略學(xué)習(xí)過(guò)程。自博弈在圍棋、國(guó)際象棋、撲克以及游戲等領(lǐng)域都取得了一系列的成功應(yīng)用。在這些場(chǎng)景中，通過(guò)自博弈訓(xùn)練得到了超越人類(lèi)專(zhuān)家的策略。盡管自博弈應(yīng)用廣泛，但它也伴隨著一些局限性，例如可能收斂到次優(yōu)策略以及顯著的計(jì)算資源需求等。

本綜述組織架構(gòu)如下：首先，背景部分介紹了強(qiáng)化學(xué)習(xí)框架和基礎(chǔ)的博弈論概念。其次，在算法部分提出了一個(gè)統(tǒng)一的框架，并根據(jù)該框架將現(xiàn)有的自博弈算法分為四類(lèi)，進(jìn)行系統(tǒng)的比較和分析。在之后的應(yīng)用部分中，展示自博弈具體如何應(yīng)用到具體的復(fù)雜博弈場(chǎng)景。最后，進(jìn)一步討論了自博弈中的開(kāi)放問(wèn)題和未來(lái)的研究方向，并進(jìn)行總結(jié)。

背景

該部分分別介紹了強(qiáng)化學(xué)習(xí)框架以及博弈論基本知識(shí)。強(qiáng)化學(xué)習(xí)框架我們考慮最一般的形式：部分可觀察的馬爾可夫博弈（partially observable Markov game, POMGs），即多智能體場(chǎng)景，且其中每個(gè)智能體無(wú)法完全獲取環(huán)境的全部狀態(tài)。

博弈論基礎(chǔ)知識(shí)介紹了博弈具體類(lèi)型，包括（非）完美信息博弈和（非）完全信息博弈、標(biāo)準(zhǔn)型博弈和擴(kuò)展型博弈、傳遞性博弈和非傳遞性博弈、階段博弈和重復(fù)博弈、團(tuán)隊(duì)博弈等。同樣也介紹了博弈論框架重要概念包括最佳回應(yīng)（Best responce, BR）和納什均衡 (Nash equilibrium, NE）等。

復(fù)雜的博弈場(chǎng)景分析通常采用更高層次的抽象，即元博弈（meta-game）。元博弈關(guān)注的不再是單獨(dú)的動(dòng)作，而是更高層的復(fù)雜策略。在這種高層次抽象下，復(fù)雜博弈場(chǎng)景可以看作是特殊的標(biāo)準(zhǔn)型博弈，策略集合由復(fù)雜策略組成。元策略（meta-strategies）是對(duì)策略集合中的復(fù)雜策略進(jìn)行概率分配的混合策略。

在該部分最后，我們介紹了多種常用的自博弈評(píng)估指標(biāo)，包括 Nash convergence（NASHCONV）、Elo、Glicko、Whole-History Rating（WHR） 和 TrueSkill。

算法

我們定義了一個(gè)統(tǒng)一的自博弈框架，并將自博弈算法分為四大類(lèi)：傳統(tǒng)自博弈算法、PSRO 系列算法、基于持續(xù)訓(xùn)練的系列算法和后悔最小化系列算法。

算法框架

首先，該框架（算法1）的輸入定義如下：

● : 在策略集合  中，每個(gè)策略  都取決于一個(gè)策略條件函數(shù) 。

● : 策略集合的交互矩陣。 描述了如何為策略  采樣對(duì)手。例如， 可以用每個(gè)對(duì)手策略采樣概率表示（此時(shí)  如下圖所示）。

● : 元策略求解器（Meta Strategy Solver，MSS）。輸入是表現(xiàn)矩陣 ，并生成一個(gè)新的交互矩陣  作為輸出。 表示策略  的表現(xiàn)水平。

該框架（算法1）的核心步驟說(shuō)明：

● 算法1偽代碼第1行： 表示整個(gè)策略集合的總訓(xùn)練輪數(shù)，也即策略池中每個(gè)策略的更新次數(shù)。

● 算法1偽代碼第3行：各個(gè)策略初始化可以選擇隨機(jī)初始化、預(yù)訓(xùn)練模型初始化或者是繼承之前訓(xùn)練完成的策略進(jìn)行初始化。

● 算法1偽代碼第4行：可以選用不同的 ORACLE 算法得到訓(xùn)練策略，最直接的方式是計(jì)算 BR 。但是由于對(duì)于復(fù)雜任務(wù)來(lái)說(shuō)，直接計(jì)算 BR 難度高，因此通常選擇訓(xùn)練近似BR來(lái)訓(xùn)練策略，可以采用強(qiáng)化學(xué)習(xí)（算法2），進(jìn)化算法（算法3），后悔最小化（算法4）等方法。

類(lèi)型一：傳統(tǒng)自博弈算法

傳統(tǒng)自博弈算法從單一策略開(kāi)始，逐步擴(kuò)展策略池，包括Vanilla self-play（訓(xùn)練時(shí)每次對(duì)手都選擇最新生成的策略），F(xiàn)ictitious self-play（訓(xùn)練時(shí)每次對(duì)手都在現(xiàn)有訓(xùn)練完的策略中均勻采樣），δ-uniform self-play（訓(xùn)練時(shí)每次對(duì)手都在現(xiàn)有訓(xùn)練完的最近的百分之δ策略中均勻采樣），Prioritized Fictitious Self-play（根據(jù)優(yōu)先級(jí)函數(shù)計(jì)算當(dāng)前訓(xùn)練完的策略的優(yōu)先級(jí)，訓(xùn)練時(shí)每次對(duì)手都根據(jù)這個(gè)優(yōu)先級(jí)進(jìn)行采樣），Independent RL（訓(xùn)練時(shí)雙方策略都會(huì)改變，對(duì)手策略不再固定）。

類(lèi)型二：PSRO 系列算法

類(lèi)似于傳統(tǒng)自博弈算法，Policy-Space Response Oracle（PSRO）系列算法同樣從單一策略開(kāi)始，通過(guò)計(jì)算 ORACLE 逐步擴(kuò)展策略池，這些新加入的策略是對(duì)當(dāng)前元策略的近似 BR 。PSRO 系列與傳統(tǒng)自博弈算法的主要區(qū)別在于，PSRO 系列采用了更復(fù)雜的MSS，旨在處理更復(fù)雜的任務(wù)。例如，α-PSRO 使用了基于 α-rank 的 MSS 來(lái)應(yīng)對(duì)多玩家的復(fù)雜博弈。

類(lèi)型三：持續(xù)訓(xùn)練系列算法

PSRO 系列算法中存在的兩個(gè)主要挑戰(zhàn)：首先，由于訓(xùn)練成本大，通常在每次迭代中截?cái)嘟艬R計(jì)算，會(huì)將訓(xùn)練不充分的策略添加到策略池；其次，在每次迭代中會(huì)重復(fù)學(xué)習(xí)基本技能，導(dǎo)致效率較低。為了解決這些挑戰(zhàn)，基于持續(xù)訓(xùn)練系列的算法提倡反復(fù)訓(xùn)練所有策略。與前面提到的兩類(lèi)最大區(qū)別是，持續(xù)訓(xùn)練系列算法同時(shí)訓(xùn)練整個(gè)策略池策略。這類(lèi)算法采用多個(gè)訓(xùn)練周期，并在每個(gè)訓(xùn)練周期內(nèi)依次訓(xùn)練策略池所有策略，而不再是通過(guò)逐步擴(kuò)展策略池進(jìn)行訓(xùn)練。

類(lèi)型四：后悔最小化系列算法

另一類(lèi)自博弈算法是基于后悔最小化的算法。基于后悔最小化的算法與其他類(lèi)別的主要區(qū)別在于，它們優(yōu)先考慮累積的長(zhǎng)期收益，而不僅僅關(guān)注單次回合的表現(xiàn)。這種方法可以訓(xùn)練得到更具攻擊性和適應(yīng)性的策略，避免隨著時(shí)間的推移被對(duì)手利用。這些算法要求玩家在多輪中推測(cè)并適應(yīng)對(duì)手的策略。這種情況通常在重復(fù)博弈中觀察到，而不是單回合游戲中。例如，在德州撲克或狼人游戲中，玩家必須使用欺騙、隱瞞和虛張聲勢(shì)的策略，以爭(zhēng)取整體勝利，而不僅僅是贏得一局。

各類(lèi)型算法比較與總結(jié)圖

應(yīng)用

在本節(jié)中，我們通過(guò)將三類(lèi)經(jīng)典場(chǎng)景來(lái)介紹自博弈的經(jīng)典應(yīng)用：棋類(lèi)游戲，通常涉及完全信息；牌類(lèi)游戲（包括麻將），通常涉及不完全信息；以及電子游戲，具有實(shí)時(shí)動(dòng)作而非簡(jiǎn)單回合制游戲。

場(chǎng)景一：棋類(lèi)游戲

棋類(lèi)游戲領(lǐng)域，絕大多數(shù)是完全信息游戲，曾因引入兩項(xiàng)關(guān)鍵技術(shù)而發(fā)生革命性變化：位置評(píng)估和蒙特卡羅樹(shù)搜索。這兩項(xiàng)技術(shù)在象棋、西洋跳棋、黑白棋、西洋雙陸棋等棋盤(pán)游戲方面展現(xiàn)了超越人類(lèi)的效果。相比之下，當(dāng)這些技術(shù)應(yīng)用于圍棋時(shí)，由于圍棋棋盤(pán)布局種類(lèi)遠(yuǎn)超于上述提到的棋類(lèi)游戲，因此僅能達(dá)到業(yè)余水平的表現(xiàn)。直到 DeepMind 推出了 AlphaGo 系列而發(fā)生了革命性的變化，AlphaGo 系列算法利用自博弈的強(qiáng)大功能顯著提升了性能，為圍棋領(lǐng)域設(shè)立了新的基準(zhǔn)。

除了圍棋，還有一種難度較高的棋類(lèi)游戲是“軍棋”（Stratego）。與大多數(shù)完全信息的棋類(lèi)游戲不同，“軍棋”是一個(gè)兩人參與的不完全信息棋盤(pán)游戲。游戲分為兩個(gè)階段：部署階段，玩家秘密安排他們的單位，為戰(zhàn)略深度奠定基礎(chǔ)；以及游戲階段，目標(biāo)是推斷對(duì)手的布局并奪取他們的旗幟。DeepNash 采用基于進(jìn)化的自博弈算法 R-NaD 達(dá)到了世界第三的人類(lèi)水平。

場(chǎng)景二：牌類(lèi)游戲

德州撲克（Texas Hold’em）是一種歐美流行的撲克游戲，適合 2 到 10 名玩家，當(dāng)玩家數(shù)量增加，游戲變得更加復(fù)雜。此外，有三種下注形式：無(wú)限注、固定注和底池限注。每種形式在具有不同的游戲復(fù)雜度。在牌類(lèi)游戲中，游戲抽象對(duì)于簡(jiǎn)化游戲復(fù)雜程度至關(guān)重要，可以將游戲的龐大狀態(tài)空間減少到更容易處理的數(shù)量。Cepheus 采用后悔最小化系列算法 CFR+ 解決了最容易的雙人有限注德州撲克。對(duì)于更復(fù)雜的雙人無(wú)限注德州撲克，DeepStack 和 Libratus 采用子博弈重新計(jì)算的方式來(lái)實(shí)時(shí)做出決策，擊敗職業(yè)德州撲克選手。Pluribus 在 Libratus 基礎(chǔ)上更進(jìn)一步解決了六人無(wú)限注德州撲克。

斗地主需要同時(shí)考慮農(nóng)民之間的合作和農(nóng)民地主之間的競(jìng)爭(zhēng)。斗地主同樣是不完全信息博弈，這為游戲增加了不確定性和策略深度。DeltaDou 是基于 AlphaZero 開(kāi)發(fā)的首個(gè)實(shí)現(xiàn)專(zhuān)家級(jí)斗地主表現(xiàn)的算法。之后的 DouZero 通過(guò)選擇采樣方法而非樹(shù)搜索方法來(lái)降低訓(xùn)練成本，采用自博弈獲取訓(xùn)練數(shù)據(jù)。

麻將同樣基于不完全信息做出決策，此外，麻將的牌數(shù)更多，獲勝牌型也更為復(fù)雜，對(duì) AI 更具挑戰(zhàn)性。Suphx 通過(guò)監(jiān)督學(xué)習(xí)和自我博弈強(qiáng)化學(xué)習(xí)成為首個(gè)達(dá)到與人類(lèi)專(zhuān)家水平的算法。NAGA 和騰訊設(shè)計(jì)的 LuckyJ 同樣也在在線(xiàn)平臺(tái)上達(dá)到了人類(lèi)專(zhuān)家水平。

場(chǎng)景三：電子游戲

與傳統(tǒng)棋類(lèi)游戲和牌類(lèi)游戲不同，電子游戲通常具有實(shí)時(shí)操作、更長(zhǎng)的動(dòng)作序列以及更廣泛的動(dòng)作空間和觀察空間。在星際爭(zhēng)霸（StarCraft）中，玩家需要收集資源、建設(shè)基地并組建軍隊(duì)，通過(guò)精心的計(jì)劃和戰(zhàn)術(shù)執(zhí)行，使對(duì)方玩家失去所有建筑物，來(lái)取得勝利。AlphaStar 使用監(jiān)督學(xué)習(xí)、端到端的強(qiáng)化學(xué)習(xí)和分層自博弈訓(xùn)練策略，在星際爭(zhēng)霸II的 1v1 模式比賽中擊敗了職業(yè)玩家。

MOBA游戲要求兩支玩家隊(duì)伍各自操控他們獨(dú)特的英雄，互相競(jìng)爭(zhēng)以摧毀對(duì)方的基地。每個(gè)英雄都有獨(dú)特的技能，并在隊(duì)伍中扮演特定的角色，也無(wú)法觀測(cè)全部地圖。OpenAI Five 在簡(jiǎn)化版本的 Dota 2 中擊敗了世界冠軍隊(duì)，其訓(xùn)練過(guò)程使用混合類(lèi)型自博弈，有 80% 的概率進(jìn)行 Naive self-play，20% 的概率使用 Prioritized self-play。騰訊同樣采用自博弈訓(xùn)練在王者榮耀游戲 1v1 和 5v5 模式中都擊敗了職業(yè)選手。

Google Research Football（GRF）是一個(gè)開(kāi)源的足球模擬器，輸入是高層次的動(dòng)作，需要考慮隊(duì)友之間的合作和兩個(gè)隊(duì)伍之間的競(jìng)爭(zhēng)，且每隊(duì)有 11 人。TiKick 通過(guò) WeKick 的自博弈數(shù)據(jù)進(jìn)行模仿學(xué)習(xí)，再利用分布式離線(xiàn)強(qiáng)化學(xué)習(xí)開(kāi)發(fā)了一個(gè)多智能體AI。TiZero將課程學(xué)習(xí)與自博弈結(jié)合，無(wú)需專(zhuān)家數(shù)據(jù)，達(dá)到了比TiKick更高的TrueSkill評(píng)分。

各場(chǎng)景類(lèi)型比較與總結(jié)圖

討論

自博弈方法因其獨(dú)特的迭代學(xué)習(xí)過(guò)程和適應(yīng)復(fù)雜環(huán)境的能力而表現(xiàn)出卓越的性能，然而，仍有不少方向值得進(jìn)一步研究。

雖然許多算法在博弈論理論基礎(chǔ)上提出，但在將這些算法應(yīng)用于復(fù)雜的現(xiàn)實(shí)場(chǎng)景時(shí)，往往存在理論與現(xiàn)實(shí)應(yīng)用的差距。例如，盡管 AlphaGo、AlphaStar 和 OpenAI Five 在實(shí)證上取得了成功，但它們的有效性缺乏正式的博弈論證明。

隨著團(tuán)隊(duì)數(shù)量和團(tuán)隊(duì)內(nèi)玩家數(shù)量的增加，自博弈方法的可擴(kuò)展性面臨顯著挑戰(zhàn)。例如，在 OpenAI Five 中，英雄池的大小被限制在僅17個(gè)英雄。根本上是由于自博弈方法在計(jì)算和存儲(chǔ)兩個(gè)方面訓(xùn)練效率有限：由于自博弈的迭代特性，智能體反復(fù)與自身或過(guò)去的版本對(duì)戰(zhàn)，因而計(jì)算效率較低；自博弈需要維護(hù)一個(gè)策略池，因而對(duì)存儲(chǔ)資源需求較高。

憑借卓越的能力和廣泛的泛化性，大型語(yǔ)言模型（LLM）被認(rèn)為是實(shí)現(xiàn)人類(lèi)水平智能的潛在基礎(chǔ)。為了減少對(duì)人工標(biāo)注數(shù)據(jù)的依賴(lài)，自博弈方法被利用到微調(diào)LLM來(lái)增強(qiáng)LLM的推理性能。自博弈方法還在構(gòu)建具有強(qiáng)大戰(zhàn)略能力的基于 LLM 的代理方面做出了貢獻(xiàn)，在”外交“游戲中達(dá)到了人類(lèi)水平的表現(xiàn)。盡管近期取得了一些進(jìn)展，將自博弈應(yīng)用于 LLM 仍處于探索階段。

自我博弈面另一個(gè)挑戰(zhàn)是其在現(xiàn)實(shí)具身場(chǎng)景中無(wú)法直接應(yīng)用。其迭代特性需要大量的試驗(yàn)和錯(cuò)誤，很難直接在真實(shí)環(huán)境中完成。因此，通常只能在仿真器中進(jìn)行自博弈訓(xùn)練，再將自博弈有效部署到現(xiàn)實(shí)具身場(chǎng)景中，關(guān)鍵問(wèn)題仍在于克服 Sim2Real 差距。