通过奖励随机化发现多智能体游戏中多样性策略行为,清华、UC伯克利等研究者提出全新算法RPG

在这篇论文中,研究者提出了一个在 reward-space 进行探索的新算法 RPG(Reward-Randomized Policy Gradient),并且在存在多个纳什均衡 (Nash Equilibrium, NE) 的挑战性的多智能任务中进行了实验验证,实验结果表明,RPG 的表现显著优于经典的 policy/action-space 探索的算法,并且发现了很多有趣的、人类可以理解的智能体行为策略。除此之外,论文进一步提出了 RPG 算法的扩展:利用 RR 得到的多样性策略池训练一个新的具备自适应能力的策略。

在法国启蒙思想家卢梭(Jean-Jacques Rousseau)的《论人类不平等起源》中,提到这样一个猎鹿(StagHunt)故事:一群猎人安静地在陷阱旁等待鹿的出现,猎到鹿的收益较大,可以让所有猎人都吃饱,但是由于鹿十分机敏,需要大家都耐心等待。这个时候一只兔子出现了,兔子体型较小,一人便可以成功捕猎,但是相应的收益也很小。

于是每一个猎人有了两个选择:继续等待鹿的出现还是立刻跳起来捕兔?如果猎人选择立刻捕兔,那么他可以捕到兔,得到较小的收益;如果猎人选择继续等待鹿,若所有其他猎人也都选择了继续等待鹿,那么他们最终可以猎到鹿,得到最大收益,但是一旦有任何一个其他猎人选择立刻捕兔,那么选择等待鹿的猎人只能挨饿(既没有捕兔,也没有机会再猎到鹿)。

图 1:StagHunt 游戏,a>b>=d>c

我们考虑 2 个猎人的情况,然后把各种情况的收益抽象出来,就引出了博弈论中非常经典的 2x2 矩阵游戏 StagHunt。如图 1 所示,每个猎人可以执行两种动作:猎鹿(Stag,缩写为 S)和捕兔(Hare,缩写为 H),如果两个猎人都选择猎鹿(S,S),可以得到最大收益 a(吃饱);如果两人都选择捕兔(H,H),得到较小收益 d(需分享兔子);如果一人猎鹿一人捕兔(S,H),那么捕兔的人得到收益 b(独自吃兔),而猎鹿的人得到最小收益 c(挨饿)。这些收益情况满足大小关系  a (吃饱)> b (独自吃兔子)>=d (两个人分享兔子)> c (挨饿)。

图 2:PPO 在 StagHunt 游戏中的表现,其中,a=4,b=3,d=1,10 个随机种子

在这个游戏中存在两个纯策略纳什均衡(Nash Equilibrium,NE):一个是 Stag NE,即两个猎人都选择等待鹿,每一个猎人都可以得到很高的回报,但这是一个风险很高的合作策略。因为一旦其中一个猎人选择不合作,该猎人本身的收益不会发生剧烈变化 -- 从最大收益 a(吃饱)变为收益 b(独自吃兔),然而,对另一名猎人来说损失却是巨大的 -- 从最大收益 a(吃饱)变为最小收益 c(挨饿)。而这个损失(也就是 a-c)越大,意味着猎人选择合作的风险也就越高。另一个纳什均衡Hare NE,即两个猎人都选择捕兔,尽管每个猎人只能得到较低的回报,但这是一个保守的策略,因为无论对方怎么选,自己都会获得一定的收益 -- 对方选猎鹿,自己获得较大收益 b(独自吃兔),对方选捕兔,自己获得较小收益 d(分享兔子)。在这个任务中,现有的强化学习算法会收敛到哪个 NE 呢?作者做了一个实验,固定 a=4,b=3,d=1,变化 c 的取值,从图 2 可以看出:自猎鹿的惩罚越大,现有的算法收敛到 Stag NE 的概率会越低,也就是更倾向于选择保守的捕兔策略。这与之前的分析是也是吻合的。

那么,如何才能让强化学习收敛到收益最优的策略呢?为了解决这个问题,来自清华大学北京大学、UC 伯克利等机构的研究者提出了一个简单有效的技术,奖励随机化(Reward Randomization,RR)。不同于传统强化学习中的在状态空间(state-space)中进行探索(exploration)的方法,奖励随机化是一个在奖励空间(reward-space)进行探索的方法。这项研究已被 ICLR 2021 大会接收为 Poster 论文。

论文地址:https://arxiv.org/abs/2103.04564

如图 3 所示,在一个奖励设置比较极端的游戏里,强化学习通常很难探索到最优策略(左图,灰色区域表示可能收敛到最优解的子空间,由于奖励极端而非常狭小);但是同样的策略在其他奖励设置的游戏中可能很容易被探索到(右图)。这就演变出论文的核心观点:通过奖励随机化对原始游戏(StagHunt)的奖励(reward)进行扰动,将问题转化为在扰动后的游戏中寻找合作策略,然后再回到原始游戏中进行微调(fine-tune),进而找到最优策略。

图 3:奖励随机化的示意图

进一步地,论文将奖励随机化和策略梯度法(Policy Gradient,PG)相结合,提出一个在 reward-space 进行探索的新算法 RPG(Reward-Randomized Policy Gradient)。实验结果表明,RPG 的表现显著优于经典的 policy/action-space 探索的算法,并且作者还利用 RPG 发现了很多有趣的、人类可以理解的智能体行为策略。

首先,论文在 GridWorld 中进行了实验,其中有一个任务叫 Monster-Hunt(如图 4 所示),这个任务设定是这样的:图中分别用黄色和蓝色表示两个智能体(Agent),他们可以在 5*5 格子中移动,红色表示怪兽(Monster),怪兽可以在格子中随机游走,并且怪兽有一个特点是它会朝着离自己最近的智能体移动。绿色表示食物苹果(Apple),苹果不能移动。如果两个智能体同时碰到了怪兽,那么每个智能体将会获得 + 5 奖励,如果智能体单独碰到了怪兽,那么他将会受到 - 2 惩罚,智能体也可以吃苹果,每个苹果将会带来 + 2 奖励。显然,在这个任务中存在两个纳什均衡,即两个智能体同时遇到怪兽(高风险,高收益)或者各自去吃苹果(低风险,低收益)。

图 4:Monster-Hunt 任务示意图

图 5:在 Monster-Hunt 任务中不同算法的性能对比

图 5 给出了 RPG 与不同算法对比的结果,这些算法包括标准的策略梯度法、智能体共享奖励的策略梯度法、population-based 算法和一些探索(exploration)算法,包括 MAVEN, Count-based 和 Diayn。可以看出 RPG 在这个任务中显著优于 baseline。并且从图中可以注意到,即便 RR 阶段并没有找到最优策略,RPG 依然可以通过 fine-tune 阶段进一步提升性能,找到最优策略。那么,RPG 到底发现了哪些策略呢?除了自然的各自单独吃苹果和单独碰到 Monster,作者还发现了另外两种合作策略:图 6(a)展示的是发现的次优合作策略,游戏开始后,两个智能体会移动到 5*5 格子的同一个角落,然后合体原地不动,因为怪兽的一个特点是会朝着离自己最近的智能体移动,因此两个智能体原地不动也会一起碰到怪兽,得到较高的收益,这个合作策略看起来也十分合理,那么还有没有更优的合作策略呢?答案是有的,图 6(b)展示的是 RPG 发现的最优策略,游戏开始后,两个智能体会首先汇合,然后合体一起朝着怪兽移动,加上怪兽也会朝着智能体移动,这就大大加快了一起碰到怪兽的速度,因而可以得到更高的收益。图 7 是最优合作策略的演示动图。

图 6:Monster-Hunt 任务中两种不同合作策略

图 7 Monster-Hunt 任务中最优合作策略演示

接下来介绍在论文中首次开源的新环境 Agar.io,这也是该论文的一大贡献。Agar.io 是一个非常流行的在线多玩家游戏(游戏地址:http://agar.io),每个玩家可以通过鼠标控制运动方向来吃掉比自己小的智能体(可以是食物,也可以是其他玩家)。论文只考虑 2 个玩家的情况,下图(a)表示任务的示意图,同样用黄色和蓝色表示两个智能体。红色表示地图中随机生成的食物,玩家通过吃掉食物或者其他比自己小的玩家来获得奖励(奖励大小等于吃掉的质量),同理如果丢掉了质量也会受到相当的惩罚。下图(b)表示的是玩家常见的行为,例如用过分裂(Split)提高移动速度完成捕食,分裂后的部分也可以合并(Merge)。随着智能体质量的增大,移动速度也越来越慢,因此捕猎的难度也越来越大,玩家需要合作才能获得更高的收益。然而,当两个玩家距离较近时,质量较大的玩家极有可能选择攻击对于质量较小的玩家,从而立刻获得奖励,导致合作破裂。因此,对于质量较小的玩家,这种合作策略风险很高。

图7 Agar.io 任务示意图

如果你是玩家,你会选择什么策略呢?带着这个问题,看一下 RPG 发现的 7 种有趣的、人类可以理解的玩家策略。

(1)Cooperative strategy(合作策略,图 8):两个玩家合作将食物驱赶至某一区域,然后分别捕食。

图 8 (a)Agar.io 任务中的合作策略(Cooperate)

图 8 (b)合作演示

(2)Aggressive strategy(倾向攻击策略,图 9):两个玩家当两个玩家距离较近时,质量较大的玩家选择捕食质量较小玩家。

图 9 (a)Agar.io 任务中的攻击策略(Attack)

图 9 (b)攻击演示

(3)Non-cooperative strategy(非合作策略,图 10):两个玩家各自单独捕食。

图 10 Agar.io 任务中单独捕食策略(Non-cooperate)

图 11 Agar.io 任务中偶尔攻击策略(Aggressive cooperative)

(4)Aggressive cooperative strategy(偶尔攻击策略,图 11):两个玩家大部分时间选择合作,偶尔也会发生攻击行为。

(5)Sacrifice strategy(献祭策略,图 12):游戏开始后,两个玩家各自捕食,一段时间后,质量较小的玩家会在地图边界等待,将自己献祭给质量较大的玩家,由质量较大的玩家控制所有质量进行捕食。

图 12 (a)Agar.io 任务中献祭策略(Sacrifice)

图 12 (b)献祭演示

(6)Perpetual strategy(永动机策略,图 13):游戏开始后,两个玩家各自捕食,一段时间后,质量较大的玩家会在地图边界等待,质量较小的玩家驱赶食物向质量较大玩家靠拢,然后捕食,之后质量较大的玩家会非常小心地吃掉一部分质量较小的玩家,而质量较小的玩家剩下的部分会继续出去驱赶食物。一段时间后,两个玩家会交换角色,周而复始,因此称为永动机。

图 13 (a)Agar.io 任务中永动机策略(Perpetual)

图 13 (b)永动机演示

(7)Balance strategy(均衡策略,图 14):由 RPG fine-tune 之后得到的最优策略实际上是一种在互相献祭,单独捕食和合作之间的平衡策略,从图 14 可以看出,尽管 RPG 学到的策略合作行为略低,但它的收益最高。

图 14 RPG 学出了均衡策略(Balance)

论文的最后给出了 RPG 算法的扩展:利用策略随机化得到的多样性策略池训练一个新的具备自适应能力的策略(Adaptive policy),为了验证策略的适应性,作者在 Agar.io 种做了一个很有趣的实验:在游戏玩到一半时切换对手玩家的策略,然后与 Oracle 策略进行对比,如图 15 所示。例如,当对手玩家策略由合作型切换为竞争型,Adaptive 策略得到的奖励略低于竞争型策略,但显著高于合作型策略;当对手玩家策略由竞争型切换为合作型,Adaptive 策略得到的奖励略低于合作型策略,但显著高于竞争型策略。证明训练后的策略确实具有自适应性。

图 15 Agar.io 任务中 Adaptive 策略与 Oracle 策略结果对比,注意,只统计切换策略后的奖励

以上就是论文的主要内容,更多详细的实验和分析可以查看论文原文,论文的源码以及开发的 Agar.io 环境已经开源,代码指路:https://github.com/staghuntrpg/RPG。

参考链接:
论文介绍主页:https://sites.google.com/view/staghuntrpg


入门加州大学伯克利分校强化学习清华大学
相关数据
清华大学机构

清华大学(Tsinghua University),简称“清华”,由中华人民共和国教育部直属,中央直管副部级建制,位列“211工程”、“985工程”、“世界一流大学和一流学科”,入选“基础学科拔尖学生培养试验计划”、“高等学校创新能力提升计划”、“高等学校学科创新引智计划”,为九校联盟、中国大学校长联谊会、东亚研究型大学协会、亚洲大学联盟、环太平洋大学联盟、清华—剑桥—MIT低碳大学联盟成员,被誉为“红色工程师的摇篮”。 清华大学的前身清华学堂始建于1911年,因水木清华而得名,是清政府设立的留美预备学校,其建校的资金源于1908年美国退还的部分庚子赔款。1912年更名为清华学校。1928年更名为国立清华大学。1937年抗日战争全面爆发后南迁长沙,与北京大学、南开大学组建国立长沙临时大学,1938年迁至昆明改名为国立西南联合大学。1946年迁回清华园。1949年中华人民共和国成立,清华大学进入了新的发展阶段。1952年全国高等学校院系调整后成为多科性工业大学。1978年以来逐步恢复和发展为综合性的研究型大学。

http://www.tsinghua.edu.cn/
相关技术
纳什均衡技术

纳什平衡,又称为非合作赛局博弈,是在非合作博弈状况下的一个概念解,在博弈论中有重要地位,以约翰·纳什命名。 如果某情况下无一参与者可以通过独自行动而增加收益,则此策略组合被称为纳什均衡点。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

博弈论技术

博弈论,又译为对策论,或者赛局理论,应用数学的一个分支,1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》,标志着现代系统博弈理论的的初步形成,因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

北京大学机构

北京大学创办于1898年,初名京师大学堂,是中国第一所国立综合性大学,也是当时中国最高教育行政机关。辛亥革命后,于1912年改为现名。2000年4月3日,北京大学与原北京医科大学合并,组建了新的北京大学。原北京医科大学的前身是国立北京医学专门学校,创建于1912年10月26日。20世纪三、四十年代,学校一度名为北平大学医学院,并于1946年7月并入北京大学。1952年在全国高校院系调整中,北京大学医学院脱离北京大学,独立为北京医学院。1985年更名为北京医科大学,1996年成为国家首批“211工程”重点支持的医科大学。两校合并进一步拓宽了北京大学的学科结构,为促进医学与人文社会科学及理科的结合,改革医学教育奠定了基础。

官网,http://www.pku.edu.cn/
暂无评论
暂无评论~