MARL:多智能体强化学习入门第二讲
由small_q创建,最终由qxiao 被浏览 145 用户
第二讲 MARL中经典算法的简单介绍
在这一讲中,我们会介绍一下在MARL中常见的一些算法,并进行简单的归类与整理,同时简单地介绍下这些经典算法解决的是什么类型的问题,出发点是什么等等背景。并在之后的几讲中对提出算法的paper进行更详细的介绍,同时会在github上开个仓库 ,简单地实现一下这些经典算法。
\
MAS背景回顾
距离上次的第一讲已有些时间,这里就重新简单地介绍一下多智能体(MAS)的背景。如果用一句话简单地介绍MAS的话,那么其实可以这么说:考虑多个agent之间交互的系统。MAS很大部分是基于single agent进行数量上的扩展,并在扩展之后考虑agent之间交互的研究方向。
不严谨地说,single agent你可以理解成一个独立AI所应该具有的能力,比如计算机视觉(CV)中的:辨识一个物体是什么,辨识一张人脸是谁,这一类人类视觉的能力;或者比如自然语言处理(NLP)与语言方向的研究:理解一段话的含义,可以做阅读理解,能够听懂不同口音的语音的含义(身为福建人觉得这个很重要!)等等。这些方面其实都可以理解成一个独立的人类(AI)所具有的一项项skill。
还是不严谨地说,multiagent system呢,我认为是关注在多个agent直接的交互。这一点其实很有意义,在现实世界中,很多情况下将问题建模成多个agent更符合常理,同时也更自然。比如现在的无人车控制,如果你真考虑让无人车上路,那么你其实特别需要考虑是这些无人车之间怎么交互,一辆车如果突然刹车了对其他车的影响要怎么解决?怎么样合理规划路线,让道路不拥堵?如果是不停的有车离开,有车加入的ad-hoc形式的呢?这样的问题也可以考虑用single agent的角度来考虑,就是一个超级大脑来控制,但是single agent必然会带啦很多问题,比如单点故障,是否有相应的计算能力等等。而如果将每一辆车都看成一个agent,那么就自然很多了!
\
MARL算法介绍
在上一讲中,我简单地提到我对MAS的兴趣集中在MARL中,在MARL中的实验环境通常是分为一下几种:完全合作的任务,完全竞争的任务,混合着竞争与合作的任务
\
完全合作的任务
在完全合作的环境中,agents与环境进行交互与学习,在交互与学习的过程中,agents获得相同的reward信号,即如果它们合作做的很好,那么就告诉给它们正的reward,如果它们并没有合作,或者没有做的比较好的时候,就不给予reward,甚至给予负的reward(cost),更一般地说法:agent具有相同的奖励函数(如果有不同的reward,那么也可以将这些reward相加,那么就可以转化成这样同一个reward的性质了,目的就是最大化全局的reward)。
所以,在这类的环境中,学习目标当然是:最大化折扣累计回报了。即所有agent一起努力,将大家的reward最大化。因为agent之间的目标并不冲突,所以可以直接地将single agent的算法直接运用过来(注意一下,因为reward函数相同,所以这个思路很直接),那么用过来就会有一个建模的问题:我是应该single agent还是multiagent呢?
single agent就是将所有agent的action看成一个action的向量,所以这个single agent的学习目标是学习出一个policy能够在每个state下做出相应的action向量,让折扣累积收益最大。
multiagent的角度呢,就是将每个agent单独拿出来学习,每个agent决定一个action,从集中式的action向量拆分成一个个独立的action。这样的方法就是independent q-learning。
但是直接independent q-learning会带来一些效率与其他的问题,比如agent直接的action可能会相互影响,导致最终收敛到的policy并不是全局最优的policy。比如:最优的策略是所有agent采用相同的action,一旦有一个action不同就给予很大的惩罚,那么在学习探索的过程中,因为惩罚的存在,agent可能很难学到这个最优的policy。
之后这部分可能涉及的算法有:JAL,FMQ,Team-Q,Distributed-Q,OAL
\
完全竞争的任务
在完全竞争的环境中,可以很直观地理解为:每个agent都是只关心自己的reward,想要最大化自己的reward,并不考虑自己想要最大化自己的reward的action对于他人的影响。(有点像:我死后哪怕洪水滔天那种感觉)
一个比较常见的环境就是:两个agent在环境中交互,他们的reward互相为相反数,即 。在这样的环境中,最大化自己的reward就是最效果对手的reward,所以agent间不能存在合作与竞争的可能,这样的环境很常见,很多双人的棋类的游戏的reward经常就这样进行设计,比如围棋,alphago的目的就是最大化自己的胜率,最小化对手的胜率。
在这种环境中做planing的话,一种很经典的做法就是冯诺伊曼的minimax的算法,这里就不展开来讲,但是我们可以把这个思想扩展到MARL中agent的学习过程,比如minimax Q-learning: 这个任务中,我们只会介绍minimax Q-leanring,因为很多在混合着竞争与合作的任务中算法的思想是可以迁移到完全竞争的环境中的
\
混合着竞争与合作的任务
这是我觉得最有趣的实验环境,在这个环境中,agent依然是独立获得自己的reward,但是reward的设计非常有意思,当每个agent只考虑最大化自己的reward时,反而可能会使得自己的reward与另外agent的reward陷入更差的情况。以囚徒困境来讲:
当agent想要最大化自己的reward时,每个agent都会选择背叛-背叛,因为在这种情况下:当另外的agent选择合作时,我能获得5的reward,比3高;当另外的agent选择竞争时,我能获得1的reward,比0高,这也就是所谓的nash均衡。所以当两个agent都这么考虑的话,最终就是竞争-竞争,agent的reward都是1,但是其实我们观察局面,会发现可能存在一种更好的结果,那就是:合作-合作,这样的话,双方的reward都是3,3比1好,同时两个agent的total reward为6,比任意的情况都好。
但是很多情况下我们并不知道另外一个agent会是什么类型,环境的reward是什么类型,所以其实学习出Nash均衡的策略在这样的环境中是一种保守的选择,虽然没有合作-合作好,但是确保了自己的reward,从这个角度出发,有:Nash-Q。Nash-Q或许好,但是我们却希望能够在学习中尝试与对手合作,达成合作-合作的局面,如果不可以的话,最终再收敛到竞争-竞争的局面。
所以在这种情况下会有很多有趣的问题,我们也会介绍更多的算法:WoLF-IGA,WoLF-PHC,GIGA,GIGA-WoLF,CE-Q等等算法。