多智能体强化学习新工作

这次介绍一下我们在多智能体强化学习上的一篇新的工作：Collaborative Q-learning (CollaQ)。这个工作是Facebook AI Research和UC Berkeley合作的，由BAIR Open Research Commons支持（Announcing the BAIR Open Research Commons）。

代码已开源：

facebookresearch/CollaQ3分钟简介视频：http://yuandong-tian.com/collaQ.mp4

文章见：Multi-Agent Collaboration via Reward Attribution Decomposition

一些AI打游戏视频见https://sites.google.com/view/multi-agent-collaq-public

这篇文章主要想解决的问题是，如何更好地在复杂环境下同时训练多个智能体相互协作，并且让它们在未重新训练的情况下，自动适应环境和其它智能体的变化。在多智能体星际争霸（StarCraft II Multi-agent Challenge, SMAC）的环境下，我们提出的方法（CollaQ）达到了比较好的效果，比之前的SoTA胜率要高了40%，如果增加、减少、或是替换智能体，不训练或是微调的情况下，协作仍然可以继续进行，并且比之前的SoTA胜率高30%。

那么这个是如何做到的呢？

这篇文章我们试图从第一性原理出发，思考多智能体协作应当如何建模。首先，如果我们不做任何思考，把多智能体协作当成单智能体建模，会发生什么事呢？在这种情况下，假设我们有K个智能体，考虑值函数 $+_{\mathrm{joint}}+(+_1,++_2,+…,++_+)$ 。理想情况下，有了这个值函数，那么每时每刻每个智能体的下一步最优行动，就能通过最大化这个值函数来找到。实际情况下没人这么用，因为有以下的三点问题：

• $V_\mathrm{joint}$ 的样本复杂度是指数级的；
• $V_\mathrm{joint}$ 无法做到分布式执行（Decentrized Execution），也即是说，对某个智能体来说，寻找自己的最优行动时，需要知道所有其它智能体的状态。在实际情况中这个就需要有中央总控制，不满足分布式的条件；
• $V_\mathrm{joint}$ 在使用时，无法自动适应环境和其它智能体的变化。

那要怎么才能解决这个问题呢？一个自然的想法是往深里想一想，智能体之间为什么要协作？在利益相同的情况下，我们假设协作的原因是因为存在“你帮我做任务A方便，而我帮你做任务B方便”这样的情况。这就引出了如下的最大化目标函数：

其中 $V_i$ 是第i个智能体的值函数。注意这个值函数是依赖于第i个智能体被委派的任务（或者奖励 $\mathbf{r}_i$ ）的，在文中我们叫它perceived rewards。不同的委派奖励 $\mathbf{r}_i$ ，对应的值函数也不同，当然智能体的行为也会不同。 $\mathrm{r}_e$ 是总的外部奖励，目标函数中的约束是希望委派奖励的加权和不要超过外部奖励（不然所有的值函数都会奔着正无穷而去）。

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

这样听起来，就通过委派奖励这个中间变量，把智能体之间的行为，在形式上解耦了。这就是为什么会有对 $V_i$ 求和的目标函数出现。不同的委派奖励，就会对应不同智能体的行为。那我们想要找的，当然是最优的委派奖励 $\{\mathbf{r}^*_i\}$ ，让智能体间的协作效益最大化。

但这样问题就来了，要解出最优委派奖励 $\{\mathbf{r}^*_i\}$ ，还需要知道当前所有智能体的状态。这样不就绕圈子回去了吗？但幸运的是，在满足某些条件的情况下，对于第i个智能体，我们找到一个近似最优的委派奖励 $\{\mathbf{\hat+r}_i\}$ ，满足以下两条。其一，它离最优解比较近；其二，它只依赖于第i个智能体及其附近其它智能体的状态。有了前者，委派奖励就不是无的放失，有了后者，分布式执行就有了保障。

知道这个“近似最优解”的存在性之后，我们并不显式将其算出（因为这个代价仍然太大），而是利用这个结构，对第i个智能体的Q函数做相应的分解。具体来说，利用在委派奖励上的泰勒展开，我们可以得到这样的分解：

第一项叫作 $Q_\mathrm{alone}$ ，也即假设所有其它智能体都不存在情况下的Q值；第二项叫作 $Q_\mathrm{collab}$ ，只建模当前智能体和其它人的交互。第一项只用当前智能体状态作为输入特征，以减少样本复杂度；第二项则加入正则项（MARA Loss），让它在只观察到当前智能体的时候，取值为零。实验表明，这个加进去的正则项极大提高了性能，间接印证了理论分析。

通过这样的分解，我们得到了CollaQ。CollaQ在一些多智能体星际争霸的“极度困难”（super-hard）任务上得到了相当不错的效果。比如说在MMM2这类需要复杂多兵种（Marine，医疗船，光头兵）合作的情况下，CollaQ仅用2M的步数（environment step）就达到了80%以上的胜率，显示出它更有效的训练样本利用率。有一局我们甚至看到它通过精妙的微操，把电脑打得溃不成军，在全歼对方之后，已方还能剩9个兵（见https://youtu.be/NyT8njh4cj4）

另外如前所说，CollaQ训练出来的AI，在变化环境或者增多、减少、及替换智能体的情况下也有不错的表现。代码已开源，欢迎大家使用！

我们接下来还会有一些很有意思的工作出来，敬请期待。