编者按：本文来自微信公众号“机器之心”（ID：almosthuman2014），参与：一鸣、杜伟，36氪经授权发布。
DeepMind 在强化学习领域具有很高的学术声誉。从 AlphaGo 到 AlphaStar，每一项研究都取得了举世瞩目的成就，但就在最近，DeepMind 的一篇有关多智能体强化学习的论文被华为英国研究中心「打脸」。华为论文指出，DeepMind 的这项研究存在多个问题。
研究者认为，如果要复现近日 DeepMind 登上《Nature》子刊的论文，需要动用高达一万亿美元的算力，这是全球所有算力加起来都不可能实现的。
那么，DeepMind 的这份研究是什么，按照华为论文的说法，存在的问题是什么呢？
华为英国研发机构论文：https://arxiv.org/abs/1909.11628
DeepMind 论文：https://arxiv.org/pdf/1903.01373.pdf
被怼的 DeepMind 论文
作为 DeepMind「阿尔法」家族的一名新成员，α-Rank 于今年 7 月登上了自然子刊《Nature Scientific Reports》。研究人员称，α-Rank 是一种全新的动态博弈论解决办法，这种方法已在 AlphaGo、AlphaZero、MuJoCo Soccer 和 Poker 等场景上进行了验证，并获得了很好的结果。
华为论文计算的花销成本（以美元计）如下图 2 所示，其中考虑到了英伟达 Tesla K80 GPU 能够以每秒 0.9 美元、最高 5.6 GFlop/s 的单精度下运行。
图 2：计算α-Rank 时构造转换矩阵 T 的花销成本。
这里请注意，当前全球计算机的总算力约为 1 万亿美元（红色平面）。投影轮廓线表明，由于α-Rank「输入」的算力需求呈指数级增长，用 10 个以上的智能体进行多智能体评估是根本不可能的。
最后，在论文中，华为研究人员提出了一个对α-Rank 的解决办法，名为：α^α-Rank。该方法使用了随机优化策略，能够大幅度的降低计算复杂度。
α-Rank 原理
α-Rank 是 DeepMind 提出的一项强化学习研究，主要针对的是多智能体强化学习的场景。强化学习是一种利用智能体在搜索空间进行探索，并根据其选择的策略给予恰当奖励，使其逐渐收敛到最佳策略上的方法。和一般的强化学习不同，多智能体强化学习中有多个智能体，多个智能体和环境进行交互时就会带来比单个智能体复杂得多的情况。
在多智能体系统中，每个智能体都会通过与所在环境的交互来获取奖励值（reward），进而学习改善自己的策略，并获得该环境下行动的最优策略。在单智能体强化学习中，智能体所在的环境是稳定不变的。但是，在多智能体强化学习中，环境是复杂、动态的，因此不可避免地会给学习过程带来诸多困难。
MARL 最简单的形式是独立强化学习（independent RL，InRL），每个学习器不理会其他智能体，将所有互动作为自己（「局部」）环境的一部分。此外，还有许多智能体和环境以及彼此之间进行交互的研究，智能体彼此之间需要协作，形成联合策略（joint strategy）。要评估智能体选择的策略，就需要对联合策略进行评价。
因此，在可扩展的多智能体强化学习策略评估和学习中存在两个主要的困难。首先，联合策略空间（即所有智能体的策略总和）会随着智能体数量的增加而快速增长。其次，这种多智能体的游戏很可能会演变成一种「石头剪刀布」的循环行为，使得评价策略的好坏变得很困难。为了解决第二个问题，很多多智能体强化学习研究只能将智能体研究转换为博弈论的方法，按照最终博弈结果所得到的的固定分数进行评价。
最近，在解决多智能强化学习这一任务上，DeepMind 又提出了一个名为α-Rank 的方法。这是一个基于图和博弈论的多智能体协作评估解决方案。α-Rank 采用了马尔科夫-康利链（Markov Conley Chains），用于表示游戏动态过程，并尝试计算一个固定的分布。对联合策略的排名按照分布产生。
具体而言，DeepMind 的这篇论文将评估多智能体的问题转换为一个马尔科夫链的固定分布。假设有 N 个智能体，每个智能体有 k 个策略，则该马尔科夫链可被定义为一个联合策略图，有着的转移矩阵。而要被计算的固定概率分布 ν∈R^k^N，用于解 Tν=ν。v 的质量函数就是联合策略的排名分数。这一方法的亮点在于将多智能体的联合策略作为一个固定分布，以便进行排名和评估。
图 1：有 3 个智能体。a）每个智能体有 3 个策略（用颜色区分）和 5 个副本。每个智能体集群有一个 Pi 值，用于衡量其选择的策略；b）当一个突变策略（红色星星）发生的时候；c）每个群体选择维持原有策略，或者选择突变策略。
在 α-Rank 中，N 个智能体的策略会通过突变和选择进行评价。开始时，智能体集群会构建多个学习器的副本，并假设每个集群中的所有智能体都会执行同一个固定策略。这样一来，α-Rank 会通过随机采样每个集群中的学习器，用于模拟多智能体的博弈环境。在游戏结束时，每个参与的智能体的能够得到一个收益，这个收益可以用于策略突变和选择。在这里，智能体面临一个概率选择——换成突变策略、维持原有策略，或者随机选择一个和前两个不一样的新策略。这一过程持续，目标是决定一个主要的进化方法，并在所有集群的智能体中传播。
反驳理由
华为论文的反驳理由主要是根据α*-*Rank 的计算复杂度进行批判的。α-Rank 声称能够根据智能体的数量在多项式时间内解出问题，但华为论文认为实际的复杂度会随着智能体数量呈几何级别的增长，其实就是一个 NP 困难问题。
α-Rank 的计算复杂度太高
原始的α-Rank 研究声称其算法可解，因为随着联合策略的数量增加，其算法可在多项式时间内完成。根据这一定义，如果α-Rank 有多项式的复杂度，则计算时间应当和公式：O (N × k)^d，（d 和 N（智能体数量）、K（策略数量）独立）相称。而如果算法要求计算一个固定概率分布，有着一个 k^N 行和列的转移矩阵，则时间复杂度应该是 O（k^N）。很显然，这个结果是几何级的，因此不可解。华为论文的研究者认为，α -Rank 中计算最高的联合策略过程是一个 NP 困难问题。
从以上的计算复杂度研究可以得出一个结论，如果按照α-Rank 的方法计算一个固定概率分布，有着ε个固定策略，且精确度参数ε大于 0，可以有多种算法进行计算，计算复杂度如下表 1 所示。而任何一种现有的计算这个固定概率分布的方法都会因智能体的数量增长呈现几何级的复杂度增长。
表 1：以 N（智能体数量）×K（策略数量）表作为输入时的时间和空间复杂度比较。
α-Rank 的输入定义不清
除了计算复杂度问题，华为论文对α-Rank 的输入进行了讨论。DeepMind 的论文给出了这些智能体的复杂度计算结果，并声明了它们的可解性。但是，华为论文想要阐明的一点是，在没有正式定义输入的情况下，此类定义并不能反映真正的底层时间复杂度，因此很难声称这些智能体的可解性。
为此，华为论文举了解决旅行推销员问题的例子，这位旅行推销员需要造访一系列城市，同时又要按照最短的路线返回最初的城市。尽管大家都知道旅行推销员问题属于一种 NP 困难问题，但按照α-Rank 的思路，这一问题可以简化为「元城市」规模的多项式时间（线性，如可解决）问题，这并不是一种有效的声明。
华为论文指出，即使可以说排列数量确定的情况下可以在多项式复杂度中解决旅行推销员问题，这并不能说明任何类似的算法都是可解的。即使算法可以在多项式时间内处理问题，但其空间是几何级规模的，这并不能说明它是可解决的。因此，要说解决了复杂度的问题，就需要对输入做调整。
一万亿算力都打不住
在以上问题都没有清楚解决的情况下，华为论文只能按照推测，将α-Rank 的输入考虑作为指数级的收益矩阵。接着，他们进行了一项实验，对仅执行算法 1 中第 3 行的扩展性评估花销进行了计算，同时也考虑到了 DeepMind 另一篇论文《α-Rank: Multi-Agent evaluation by Evolution》中的任务。
华为论文计算了α-Rank 算法 1 中第 3 行的扩展性评估的花销成本。
此外，构建公式 2 中 T 所需的浮点运算总量为。
公式 2
而就构建上述公式 2 中的 T 而言，华为论文计算的花销成本（以美元计）如下图 2 所示，其中考虑到了英伟达 Tesla K80 GPU 能够以每秒 0.9 美元、最高 5.6 GFlop/s 的单精度下运行。
图 2：计算α-Rank 时构造转换矩阵 T 的花销成本。
这里请注意，当前全球计算机的总算力约为 1 万亿美元（红色平面）。投影轮廓线表明，由于α-Rank「输入」的算力需求呈指数级增长，用十个以上的智能体进行多智能体评估是根本不可能的。
同样有必要注意一下的是，华为论文的分析没有考虑存储 T 或计算平稳分布的花销，因而他们的分析是乐观的。
此外，如果将α-Rank 的输入加入收益矩阵并按照 DeepMind 论文的实验跑 AlphaZero，即使用上全球所有算力，也得花上超过 5200 年。
其他的算法也都不可行——在华为研究人员估算下，即使将收益矩阵加入α-Rank 跑 DeepMind 几个著名算法需要用到的资金花费和时间都是天文数字。注意：在这里预设使用全球所有的算力。
华为提出改进方法α^α-Rank
华为在其论文中采用了一种随机优化方法，该方法通过对收益矩阵的随机采样而获得解决方案，同时无需存储指数大小的输入。与上表 1 中的内存需求相反，这一方法的复杂度为 O(Nk)，每次迭代的复杂度为线性。有必要注意一下的是，在启动任何数字指令之前，大多数其他方法需要存储指数大小的矩阵。尽管在理论上没有导致时间复杂度的减弱，但华为论文利用 double-oracle 启发式来扩展其算法，进而实现了联合策略下的空间减小。事实上，华为论文中的实验表明，α^α-Rank 可以在大型策略空间的数百次迭代下收敛至正确的顶级策略。
华为提出的改进方法。
华为论文表明其α^α-Rank 具有可扩展性，能够成功地在无人驾驶汽车模拟和伊辛模型（Ising model，一种具有数千万可能策略的设置）获得最优策略。他们注意到，当前 SOTA 方法的性能远远无法满足此等规模的需求。α-Rank 认为 4 个智能体最多能够使用 4 种策略。华为论文中的所有实验仅仅是在 64GB 内存和 10 核心英特尔 i9 CPU 的单机上运行的。
图 5：大规模多智能体评估。（a）无人驾驶模拟中最优联合策略组合的收敛性；（b）伊辛模型的平衡状态。
封面图来自pexels，原题目《你的算法耗尽全球GPU算力都实现不了，DeepMind阿尔法系列被华为怒怼，曾登Nature子刊》
