田渊栋团队&UC伯克利新作:从第一性原理出发,多智能体协作该如何建模

  • A+
所属分类:体坛快讯

来源:新智元

在多智能体星际争霸(StarCraft II Multi-agent Challenge, SMAC)的环境下,我们提出的方法(CollaQ)达到了比较好的效果,比之前的SoTA胜率要高了40%。

如果增加、减少、或是替换智能体,不训练或是微调的情况下,协作仍然可以继续进行,并且比之前的SoTA胜率高30%。

这是田渊栋老师团队在多智能体强化学习上的一篇新的工作,是Facebook AI Research和UC Berkeley合作的,由BAIR Open Research Commons支持,代码已开源。

GitHub链接:

https://github.com/facebookresearch/CollaQ

原文地址:https://arxiv.org/abs/2010.08531

那么到底是如何做到的呢?

我们试图从第一性原理出发,思考多智能体协作应当如何建模。

首先,如果我们不做任何思考,把多智能体协作当成单智能体建模,会发生什么事呢?

在这种情况下,假设我们有K个智能体,考虑值函数 

 。

理想情况下,有了这个值函数,那么每时每刻每个智能体的下一步最优行动,就能通过最大化这个值函数来找到。

实际情况下没人这么用,因为有以下的三点问题:

的样本复杂度是指数级的;

 无法做到分布式执行(Decentrized Execution),也即是说,对某个智能体来说,寻找自己的最优行动时,需要知道所有其它智能体的状态。在实际情况中这个就需要有中央总控制,不满足分布式的条件;

在使用时,无法自动适应环境和其它智能体的变化。

那要怎么才能解决这个问题呢?

一个自然的想法是往深里想一想,智能体之间为什么要协作?

在利益相同的情况下,我们假设协作的原因是因为存在“你帮我做任务A方便,而我帮你做任务B方便”这样的情况

这就引出了如下的最大化目标函数:

决定委派奖励的目标函数。在给定了委派的奖励之后,我们假设每个智能体的值函数是可以分解的。

其中 

 是第i个智能体的值函数。注意这个值函数是依赖于第i个智能体被委派的任务(或者奖励 

 )的,在文中我们叫它perceived rewards。

不同的委派奖励 

,对应的值函数也不同,当然智能体的行为也会不同。

 是总的外部奖励,目标函数中的约束是希望委派奖励的加权和不要超过外部奖励(不然所有的值函数都会奔着正无穷而去)。

我们假设,每个智能体之所以会和别人协作,完全是因为委派的奖励不同。换种说法,有了委派奖励,智能体眼里就盯着奖励去了,再不用管其它智能体在干什么。

这样听起来,就通过委派奖励这个中间变量,把智能体之间的行为,在形式上解耦了。这就是为什么会有对 

 求和的目标函数出现。

不同的委派奖励,就会对应不同智能体的行为。那我们想要找的,当然是最优的委派奖励 

 ,让智能体间的协作效益最大化。

但这样问题就来了,要解出最优委派奖励

,还需要知道当前所有智能体的状态。这样不就绕圈子回去了吗?

但幸运的是,在满足某些条件的情况下,对于第i个智能体,我们找到一个近似最优的委派奖励 

 ,满足以下两条。

其一,它离最优解比较近

其二,它只依赖于第i个智能体及其附近其它智能体的状态

有了前者,委派奖励就不是无的放失,有了后者,分布式执行就有了保障。

虽然最优委派奖励很难计算,但可以证明,存在只依赖于局部智能体状态的近似最优委派奖励。

知道这个“近似最优解”的存在性之后,我们并不显式将其算出(因为这个代价仍然太大),而是利用这个结构,对第i个智能体的Q函数做相应的分解

具体来说,利用在委派奖励上的泰勒展开,我们可以得到这样的分解:

在CollaQ中,第i个智能体的Q函数分解

第一项叫作 

,也即假设所有其它智能体都不存在情况下的Q值;第二项叫作 

 ,只建模当前智能体和其它人的交互

第一项只用当前智能体状态作为输入特征,以减少样本复杂度;第二项则加入正则项(MARA Loss),让它在只观察到当前智能体的时候,取值为零。

实验表明,这个加进去的正则项极大提高了性能,间接印证了理论分析。

通过这样的分解,我们得到了CollaQ。CollaQ在一些多智能体星际争霸的“极度困难”(super-hard)任务上得到了相当不错的效果

比如说在MMM2这类需要复杂多兵种(Marine,医疗船,光头兵)合作的情况下,CollaQ仅用2M的步数(environment step)就达到了80%以上的胜率,显示出它更有效的训练样本利用率。

有一局我们甚至看到它通过精妙的微操,把电脑打得溃不成军,在全歼对方之后,已方还能剩9个兵(见youtu.be/NyT8njh4cj4

CollaQ和一些基线方法(如QMix,QTRAN,VDN,IDL等)的比较。相对基线方法,CollaQ的胜率有显著提升,加注意力机制效果更好。

另外如前所说,CollaQ训练出来的AI,在变化环境或者增多、减少、及替换智能体的情况下也有不错的表现。

代码已开源,欢迎大家使用!

3分钟简介视频:https://link.zhihu.com/?target=http%3A//yuandong-tian.com/collaQ.mp4

一些AI打游戏视频:https://link.zhihu.com/?target=https%3A//sites.google.com/view/multi-agent-collaq-public

  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: