多智能体强化学习_基于多智能体强化学习主宰星际争霸游戏

大家好，今天我们来介绍基于多智能体强化学习主宰星际争霸游戏这篇论文

Grandmaster level in StarCraft II using multi-agent reinforcement learning​

从Alphastar以后 利用强化学习的方法进行星际争霸2AI的又一大突破。

Part1 前言

游戏介绍(Introduction to the Game)

游戏简介

​ 既然是打星际争霸的论文，那么我们首先看下什么是星际争霸

《星际争霸II》是一个实时进行的战略游戏。你可以从上帝视角观察和指挥部队，争夺战场的控制权，并最终击败你的对手。游戏的单人游戏战役主要聚焦于人类种族，但你可以在多人游戏比赛中使用以下三个《星际争霸II》的种族的任意一个：人类、星灵和异虫。

每个种族都拥有其独特的单位；这些单位在战场上各自有其特定的角色。结合不同的单位来组成一支多功能的部队，是走向胜利的常规道路之一。

你能指挥的最基础的单位是工人。他们会采集资源，让你用来扩张基地，以及为你日渐庞大的部队招兵买马，同时他们也能建造新的建筑。一些高级单位在你的基地达到特定要求之后就会解锁，你需要建造特定建筑，或者研究相应的科技。

在多人游戏比赛中，如果你将地图上敌人的所有建筑都摧毁，或者敌人向你投降，那么你就赢得了比赛。

视频介绍

星际争霸介绍/video/127176032047104

总结来说:

1.《星际争霸2》是一款RTS（即时战略）游戏，说白了就是造农民采矿、造建筑、造兵、攀科技，最后派兵拆光对手的建筑。

2.与围棋相比，虽然都属于零和博弈，但还多了不完全信息(比如对手的信息是看不到的)、输入输出状态空间更庞大、存在海量先验信息、游戏预测困难的问题。

重大挑战与解决方案（Major challenges and solutions)

下面我们分别从游戏层面和算法层面解释这篇论文之前，强化学习解决星际争霸2AI遇到了哪些问题，以及这篇论文所做出的改进，箭头前面表示问题后面就是该论文的解决方案与改进。

游戏层面

群体博弈 -> League Learning

星际争霸2是一个多人即时战略游戏，所以涉及到群体博弈。

不完全信息 -> LSTM

不完全信息,对手的视野我们无法看到

长期规划/回报稀疏 -> TD(λ) & UGPO

一局游戏需要几万步决策，但是最后只有一个稀疏的奖励

实时控制(APM有限值)-> Monitoring layer

对于操作速度（action per minute，APM）有限制,要接近人的操作速度

超大状态空间 -> self-attention & scatter connection

由于是end to end 的训练方法，所以该模型的状态输入是每一帧图像。

超大动作空间 -> auto-regressive policy

动作空间组合数目较多，每一个动作都需要先选择一个对象（比如农民），选择动作的类型，然后可能还需要地图中选择作用的位置（比如走到某个位置），最后还需要选择什么时候进行下一个动作。

算法层面

自博弈循环 ->PFSP

​ 对于算法层面如果采用自博弈（自己和自己玩）的方法来学习与更新策略的话，随着学习的进行，可能会出现循环。类似有向图中的闭环

自博弈偏移 ->baseline condition (z)

如果纯使用自博弈来学习，学习到的策略可能不能有效对抗人类策略。

模型构建(Model Building)

先来给大家一个直观的感受，我们的智能体到底输入了(看到了什么)以及它是怎么认知的，以及最后他输出了什么。

首先输入的是小地图图像以及当前所有的兵种信息(这也是我在打星际的时候能看到的信息)通过神经网络层之后输出动作信息, (右下角就是他们选中的动作)其中包括选中谁、去哪里、去干什么等动作

下面我们来看一下整个模型的网络结构。

Part 2 网络结构

网络结构介绍

整体上使用AC框架，与强化学习中使用AC的Cartpole对比，Alphastar不是一般的将输入放在一起输入一个CNN，而是对于不同的输入类型，进行不同的操作，经过不同的网络输出。 总的来看，输入有基准特征(baseline features)，标量特征(scaler features)，实体列表(entities)和minimap组成。 值函数网络输出数值，而策略网络输出了五项内容。他们具体是什么，我们接下来具体分析。 Alphastar的网络结构设计的很精妙。我认为他的设计思路是对于一般特征的提取就用多层感知器对于图像信息的处理，它使用计算机视觉中常用的特征提取网络比如残差网络在所有用到了entities list的地方，它很巧妙的利用了entities序列和句子序列的相似，使用NLP中处理句子的模型提取实体列表的特征。

价值函数网络

z：论文中称它为statistic vector，从代码来看应该是从不同人类玩家l历史数据中抽取出来的建造顺序，以及单位、建筑、升级的顺序等信息。 Sc2的特点是Long term strategy 对于初始状态很敏感，联系密切。单独学习人类前20个建造物顺序可以大大减小可能的状态动作空间，加速收敛。 此外，从结果分析可以看出，加入观测的对手信息效果提升明显。 Baseline feature的概念受限于本人水平有限，加上论文中并没有详细说明。我认为有两种解释引用的是Counterfactual Multi-Agent Policy Gradients论文中的反事实基线的概念，具体可以参见PPT中的COMA论文baseline中的base是指以人类为基础进行学习

策略函数网络

注意：Alphastar不看主屏幕，只看小地图！小地图+单位列表+标量信息（时间，种族，科技情况，人口情况）已经包含了所有信息不同于Alphago只有前几手的棋盘。Alphastar存储过去的所有信息，将每一个time_step输入到LSTM，赋予各个时间段observation和action时序性。论文中的提到的 包含过去所有时刻的obs和action信息 就是 每个time step都按次序输入LSTMLSTM使得这个模型可以记住过去做的事情Eg: 一些建筑物只需要在初期建造， 即使它以后被拆除，（有了LSTM）即使entity list里面没有了，也不再建了 时间序贯性很重要Transorformer：不必多说，BERT肯定大家都听说过，非常火。在这里可以认为是输出了一个考虑了各个元素之间依赖的新的list。List的成员和输出词汇表（数据库）有关，没有查到相关资料

动作属性

查阅开源的Pysc2平台文档，得知动作class下有5个属性。

框架总览

首先根据所有信息

选择action type（what） 通过MLP确定delay(when) 同样使用MLP，确定是否要加入队列。因为APM有限制，有一些动作不能被立即执行，要加入Quene等待以后的时间执行。 对于动作的执行者(Which)，使用Pointer Network，直接获取entities作为input，output一个pointer直接指向input的一个元素。至于为什么选择Pointer network，笔者一开始甚至没有听说过pointer network。经过查阅资料，认为原因如下

​ Attention和pointer类似，传统的带有注意力机制的seq2seq模型的运行过程是这样的，先使用encoder部分对输入序列进行编码，然后对编码后的向量做attention，最后使用decoder部分对attention后的向量进行解码从而得到预测结果。但是作为Pointer Networks，得到预测结果的方式便是输出一个概率分布，也即所谓的指针。

​ 也就是说传统带有注意力机制的seq2seq模型输出的是针对输出词汇表的一个概率分布，而Pointer Networks输出的则是针对输入文本序列的概率分布。

​ 对于施法者选择，因为candidates是inputs的子集，选择pointer Network更加高效。

对于被执行者的选择(Who)，需要location或者entities的信息。对于entities序列，我们使用NLP方法处理，对于locations图片信息，我们使用CV方法处理。

下面我们来介绍该模型训练的方法

Part 3 训练部分

​ AlphaStar的训练过程最概括的表示是：先进行基于人类数据的监督学习，然后再进行使用联盟方法的强化学习。

全图流程：监督学习

通过匹配对抗(联盟学习)进行强化学习AlphaStar。

后文会对此进行更详细解释说明。

监督学习

AlphaStar的监督学习目标是：学习人类对单位的操作以及建筑建造的操作。其中建筑建造的单元和顺序需要单独列出来训练，因为很多情况下，一些操作必须要有一些建筑作为前提。

上图为论文给出的训练结构图。其中：

表示人类的观察数据（小地图数据） 代表着建筑操作的建造单元和建造顺序（阅读其伪代码可以发现，对于建筑单元和顺序的学习是有选择性的学习，在下文会对此进行解释）。 代表人类的实际操作动作。

可以看出，AlphaStar会根据小地图数据

和建造操作数据 行学习，并且以人类的操作作为标签进行训练，得到合适的输出的神经网络。经过训练后，其得到的是三个种族的神经网络各一个。

通过阅读伪代码，我们还了解到一些新的细节。

AlphaStar先使用较高技术的人类数据（MMR>3500），并且使用较高的学习（ ）率进行快速学习；然后使用极高技术的人类数据（MMR>6200），并且使用较低的学习率( )进行微调学习。 进行监督训练时，使用交叉熵损失MLE和L2规则损失共同作为损失函数进行训练。

伪代码中， 。

对于 ，其会选择性的学习。其具体过程是：首先，读取人类游戏回放数据，并且读取建筑单元build unit和建筑单元顺序build order数据，存入z列表；之后，其有一定概率舍弃一些建筑单元和顺序的数据。

在伪代码中，其读取建筑数据Bo（建筑顺序）和 （建筑单元），然后又初始化两个等长度的随机True-False数组 和 ，然后分别将 =与 相乘， 与 相乘，作为最后输出的建造数据 。

每个智能体的强化学习

首先要注意的是，此部分所介绍的是每个智能体的强化学习。

AlphaStar的强化学习目标是：基于AC框架，通过不断的与其他玩家（实际上是其他智能体或者自身，后面会有详细介绍）的对抗来进行学习。

上图为给出的训练结构图，其中：

代表人类的建造单元和建造顺序（防止智能体的建筑操作偏离人类情况）。 代表智能体观察到的信息（小地图图片）。 代表对手的一些信息（用于辅助训练，防止偏差过大）。 代表用于训练奖励（由 与 组合而成）。 代表伪奖励（其基于人类数据 生成，在后面会对其作用进行详细介绍）。 代表最终的胜利/平局/失败的奖励（对抗结果）。

训练流程如下：AlphaStar会将自身观察的数据信息

输入AC框架下的神经网络（为了降低方差，其也会将对手的信息 输入网络），输出策略 和值函数 。对于策略，其通过以相比监督学习网络输出的策略的散度、基于R_t使用V-Trace和UPGO的方式更新。对于值函数，其通过基于的TD()方式更新。

其中细节性的技术内容将在后文有详细介绍。

AlphaStar的群强化学习

个人认为，群强化学习思想是AlphaStar最为核心的思想。

群强化学习

群强化学习的核心思想是：创建一个联盟League，联盟内有很多个体；通过不断的让联盟内部的个体之间相互对抗来进行强化学习训练，使得每个个体都能得到提升。经过不断的内部对抗，其得到的不是一个极度强大的个体，而是一个十分强大的群体。

AlphaStar的联盟智能体

在AlphaStar的训练中，其创建了四类个体。四类个体分别为：主探索智能体（Main Agents）、主探索者（Main Exploiters）、联盟智能体（​League Exploiters）和历史参数个体（Past Players）。

主智能体 意义：最核心的智能体，是最终输出的AlphaStar。 特征：对抗对手：全部历史个体、主探索者、主智能体。 定期存储自身参数为一个player并加入到​Past Players中。 使用PFSP的方式匹配对手。

PFSP是一种为了高效率学习的匹配极值。在其伪代码中，每一个个体（包括历史个体与当前的三类智能体个体）都会记录与其他个体对抗的胜率，主智能体会优先选择胜率低的个体对抗。主观上的理解就是：与菜鸟对抗可能学不到什么知识，但是和大佬对抗就很可能学到新技巧。

主探索者 意义：用于寻找主智能体的弱点。特征：定期存储自身参数为一个player并加入到Past Players中。每存储一次自身参数，就会把自己还原为监督学习的参数。对抗对手：主智能体、主智能体的历史个体。 联盟智能体 意义：用于寻找整个群体的弱点。特征：定期存储自身参数为一个player并加入到Past Players中。没存储一次自身参数，就有25%概率将自己还原为监督学习的参数。 对抗对手：全部历史个体。 历史个体 意义：用于存储智能体的历史参数。

通过对伪代码的阅读，我们对联盟学习的框架进行了进一步的总结（实际上与上文中的框架图表达意义一致）：

每个智能体的大小可以代表其强度（也可以理解为时间先后关系，越早越小）。每个主智能体都会向Past Players中添加自身的历史参数。主智能体会与主探索智能体、主智能体、全部历史参数个体对抗。主探索者会与主智能体、主智能体的历史参数对抗；并且其每次存储参数都会还原自身参数为监督学习参数。联盟探索者会与权力历史参数个体对抗；并且每次存储参数都有25%概率回还原自身参数为监督学习参数。

AlphaStar联盟学习的技巧解释

定期存储自身参数为一个player并加入到Past Player，并且使用PFSP方式学习：实际上，通过记录历史参数并与其对抗的方式，可以使智能体克服追逐循环的情况（即很容易出现A战胜B，B战胜C，C又战胜A）。 联盟智能体和主探索智能体会将自身参数还原为监督学习的参数：因为智能体很可能会学习到一种很小众且有明显弱点的策略，但是其能够很好的击败一些智能体——即偏离人类的认知。因此需要对其参数进行还原。至于主智能体，其是最终的输出智能体，因此不能还原为监督学习的参数。 智能体的匹配机制：智能体会根据目标来匹配的对手。主智能体是最终的输出目标，因此必然要有极强的能力，即能够打败全部的个体；主探索者是为了在人类的基础上找到主智能体的弱点，因此对手均为主智能体及其历史；联盟探索者是为了在人类的基础上找到系统（群体）的弱点，因此对手均为全部的历史参数。

实际上，通过对伪代码的阅读，我们发现匹配机制要更加复杂。如有兴趣建议阅读其伪代码中的匹配函数。

联盟学习中的匹配的方式是为了更高效的学习而不是简单的随机。比如，主探索者在匹配对手时，会先观察其对主智能体的胜率——如果较低，则其余主智能体对抗；否则其会选择主智能体的历史中胜率较低的个体对抗。

下面我们来介绍一下本文的技术细节与成果分析

Part 4 技术细节 & 成果分析

首先我们回到论文中强化学习的流程示意图，看看这上面都写了哪些高级的技术：

KL散度

首先论文中用了KL技术来将人类策略和智能体学习到的策略来进行比较。那么什么是KL呢？一下摘自百度百科：

相对熵（relative entropy），又被称为Kullback-Leibler散度（Kullback-Leibler divergence）或信息散度（information divergence），是两个概率分布（probability distribution）间差异的非对称性度量。在在信息理论中，相对熵等价于两个概率分布的信息熵（Shannon entropy）的差值。

还是不太懂。那么看一下KL散度的公式：

离散形式与连续形式

结合百科上面的介绍，我们可以知道P(x)和Q(x)是两个分布，KL散度就是通过上面这两种形式的公式来衡量P(x)和Q(x)这两个分布的差异性。另外，KL散度还有一个性质：非负性，所以我们可以通过在数值上尽量减小KL散度的方式来使理论分布去逼近真实的分布。在AlphaStar中，理论分布是指通过神经网络输出的分布，真实分布是指人类的策略分布。

TD(λ)

在得到累积回报之后，智能体是如何利用这些累积回报来更新值函数的呢？由流程图所示，论文中用了TD(λ)算法。TD(λ)的更新算法如下所示：

其中

可以看到，TD(λ)实际上是传统时间差分方法与蒙特卡洛方法的融合，当λ=0时，只有当前的状态值更新：

当λ=1时，值函数的更新总量与蒙特卡洛方法相同：

伪奖励

图中的立即回报（Rewards）经过求和等操作后变成累积回报，然后经TD(λ)方法去更新值函数。实际上这里的立即回报不仅仅是真实的奖励，而且包括伪奖励（Pseudo Rewards，图中没有写，但是论文里有提及）。 什么是伪奖励呢？我翻遍了全网也没见到有很多大神讲解这一块儿。按照我对原论文的理解，大概可以这么想：

如图所示，智能体在状态St下选择了动作a（红色的那条线），到达了后继状态St+1并获得回报Rt+1。实际上从状态St可以转到四个不同的后继状态，但是在一次试验中智能体只能转到这后继四个状态中的一个，所以只能利用一个后继状态St+1和回报Rt+1去更新当前状态St。 从利用状态和回报的角度来看，上述的指利用真实回报的更新方式似乎有些浪费，没有充分利用上下文信息。从AlphaStar的角度来看，缺少伪奖励的设置可能会使得智能体的神经网络参数偏离人类的大方向，并且过早地收敛。如果可以通过某种方法，使得智能体在一次实验中同时得到这四个后继状态的反馈，岂不是能大大增加对状态和回报的利用效率？ 这就是设置伪奖励的出发点：在更新值函数v(St)时，不仅利用真实的奖励，同时为其他几个没有经过的状态设置伪奖励，让真实奖励和伪奖励一起去更新值函数。伪奖励的设置一般会稍大于真实的奖励，从而鼓励探索，避免过早的收敛。至于伪奖励的细节，请参阅Pseudo-reward Algorithms for Contextual Bandits with Linear Payoffff Functions这篇论文。

V-trace & IMPALA

智能体利用累积回报去更新策略π和值函数v的框架是IMPALA框架。什么是IMPALA呢？IMPALA是一个深度强化多任务学习架构，是A3C框架的一个改进版。IMPALA使用收集经验的体系结构，并将收集到的经验进一步传递给计算梯度的中央Learner，从而形成一个完全独立的行为和学习模型。同时，这种简单的架构，也使学习者能够加速使用显卡。如图：

图中有8个Actor和2个Learner。Actors并行地根据他们自己的策略进行采样，采样得到的数据到达一定量之后就将他们传输给中心的Learner，由Learner来利用这些数据进行策略梯度的计算以及策略的更新。每隔一段时间，Actor们将Learner的策略参数复制过来变为自己的参数。 这样一来，读者可能会问了：在学习过程中Actor和Learner的策略并不完全相同，如何解决这种Off-policy的问题呢？别急，论文中的V-trace方法就是用来解决这个问题的，即减小行为动作产生的时间与Learner估计渐变时间之间的误差。V-trace的公式比较复杂，详细的分析可以参见专栏。个人觉得V-trace的主要特点是里面两个类似于重要性因子的选取，其中一个决定收敛到什么样的值函数，另外一个决定收敛的速度。另外，为了防止过早收敛，V-trace方法里在Actor的梯度公式中加了一个熵作为惩罚，即

UPGO

最后一个要介绍的技术是UPGO（upgoing policy upgrade）。UPGO是策略更新的一种方法，在该方法中，策略更新的方向为

其中

分析这个回报G的分段函数形式，不难看出，只有当行为动作值函数优于当前的值函数时才去更新它，否则就还是使用原来的值函数，通过这样的方法来保证回报的选取是一致朝着更好的方向的，并且反向传播时不会太容易衰减掉。

结果分析

上图是论文中智能体Elo值（衡量智能体能力的数值，通过和历史策略打循环赛得到的分数）随学习的进行而变化的图。 从左到右，第一个红线AlphaStar Supervised表示只进行监督学习，没有进行强化学习时的水平；第二个红线AlphaStar Mid表示进行了一半强化学习时的水平（32块TPU上学习27天）；第三个红线AlphaStar Final表示强化学习完成后的水平（32块TPU上学习44天）。 从上到下，Main agents是我们所训练的主体，其分数随学习的进行而升高；League Agents由于每过一段时间都有一定的几率还原为人类策略模型的参数，因此策略的水平比较分散，总体上在Main agents和Main exploiters之间；Main exploiters由于每过一段时间也是会被还原为人类策略模型参数，因此一直保持在相对低的水平。

这两张图不是很好理解，以下分析摘自知乎专栏：

文章还弄了一个遵循特殊策略的 held-out 策略集合，main agents 和该集合中策略比赛的结果如图 b 所示。这反映了策略学习的绝对效果。图 c 反映了不同 agent 对应的不同纳什均衡分布，这个图有点不好理解：比如 ID=40 的 agent 在大概第 25 天被造出来之后，在大概之后的五天里面都还会经常能够战胜后面新学到的策略，但是大概在 30 天之后，新产生的所有策略都完全战胜 ID=40 的策略。这说明了整个策略集合的学习过程中，新的策略能够完全战胜以前的所有策略，而没有出现前面提到的训练过程中的循环（不稳定）的情况.

上图是为了说明学习到的策略具有比较高的多样性。同时可以发现Main agents的多样性其实是少于League exploiters和Main exploiters的。

上图定量分析了各个技术的作用。有趣的是，在直觉中我们以为，在其他条件相同的条件下，更高的手速会给智能体带来更高的分数。但根据图g，我们发现并非如此，智能体的水平随着APM限制的放宽先升高后降低；同时，论文所设置的手速限制恰恰落在了智能体水平最高峰附近。为什么手速限制的放宽反而可能导致智能体水平降低呢？论文给出的解释是，APM限制的放宽使得智能体需要在相同时间内做出更多的决策，这使得智能体需要学习更多的“微决策”“微操作”，从而可能放慢了智能体的学习速度，拉低了（训练时间不变的条件下）智能体的水平。