DeepMind 在強化學(xué)習領(lǐng)域具有很高的學(xué)術(shù)聲譽。從 AlphaGo 到 AlphaStar，每一項研究都取得了舉世矚目的成就，但就在最近，DeepMind 的一篇有關(guān)多智能體強化學(xué)習的論文被華為英國研究中心「打臉」。華為論文指出，DeepMind 的這項研究存在多個問題。

研究者認為，如果要復(fù)現(xiàn)近日 DeepMind 登上《Nature》子刊的論文，需要動用高達一萬億美元的算力，這是全球所有算力加起來都不可能實現(xiàn)的。

那么，DeepMind 的這份研究是什么，按照華為論文的說法，存在的問題是什么呢？

被懟的 DeepMind 論文

作為 DeepMind「阿爾法」家族的一名新成員，α-Rank 于今年 7 月登上了自然子刊《Nature Scientific Reports》。研究人員稱，α-Rank 是一種全新的動態(tài)博弈論解決方法，這種方法已在 AlphaGo、AlphaZero、MuJoCo Soccer 和 Poker 等場景上進行了驗證，并獲得了很好的結(jié)果。

華為論文計算的花銷成本（以美元計）如下圖 2 所示，其中考慮到了英偉達 Tesla K80 GPU 能夠以每秒 0.9 美元、最高 5.6 GFlop/s 的單精度下運行。

圖 2：計算α-Rank 時構(gòu)造轉(zhuǎn)換矩陣 T 的花銷成本。

這里請注意，當前全球計算機的總算力約為 1 萬億美元（紅色平面）。投影輪廓線表明，由于α-Rank「輸入」的算力需求呈指數(shù)級增長，用 10 個以上的智能體進行多智能體評估是根本不可能的。

最后，在論文中，華為研究人員提出了一個對α-Rank 的解決方法，名為：α^α-Rank。該方法使用了隨機優(yōu)化策略，能夠大大降低計算復(fù)雜度。

α-Rank 原理

α-Rank 是 DeepMind 提出的一項強化學(xué)習研究，主要針對的是多智能體強化學(xué)習的場景。強化學(xué)習是一種利用智能體在搜索空間進行探索，并根據(jù)其選擇的策略給予恰當獎勵，使其逐漸收斂到最佳策略上的方法。和一般的強化學(xué)習不同，多智能體強化學(xué)習中有多個智能體，多個智能體和環(huán)境進行交互時就會帶來比單個智能體復(fù)雜得多的情況。

在多智能體系統(tǒng)中，每個智能體都會通過與所在環(huán)境的交互來獲取獎勵值（reward），進而學(xué)習改善自己的策略，并獲得該環(huán)境下行動的最優(yōu)策略。在單智能體強化學(xué)習中，智能體所在的環(huán)境是穩(wěn)定不變的。但是，在多智能體強化學(xué)習中，環(huán)境是復(fù)雜、動態(tài)的，因此不可避免地會給學(xué)習過程帶來諸多困難。

MARL 最簡單的形式是獨立強化學(xué)習（independent RL，InRL），每個學(xué)習器不理會其他智能體，將所有互動作為自己（「局部」）環(huán)境的一部分。此外，還有許多智能體和環(huán)境以及彼此之間進行交互的研究，智能體彼此之間需要協(xié)作，形成聯(lián)合策略（joint strategy）。要評估智能體選擇的策略，就需要對聯(lián)合策略進行評價。

因此，在可擴展的多智能體強化學(xué)習策略評估和學(xué)習中存在兩個主要的困難。首先，聯(lián)合策略空間（即所有智能體的策略總和）會隨著智能體數(shù)量的增加而快速增長。其次，這種多智能體的游戲很可能會演變成一種「石頭剪刀布」的循環(huán)行為，使得評價策略的好壞變得很困難。為了解決第二個問題，很多多智能體強化學(xué)習研究只能將智能體研究轉(zhuǎn)換為博弈論的方法，按照最終博弈結(jié)果所得到的的固定分數(shù)進行評價。

最近，在解決多智能強化學(xué)習這一任務(wù)上，DeepMind 又提出了一個名為α-Rank 的方法。這是一個基于圖和博弈論的多智能體協(xié)作評估解決方案。α-Rank 采用了馬爾科夫-康利鏈（Markov Conley Chains），用于表示游戲動態(tài)過程，并嘗試計算一個固定的分布。對聯(lián)合策略的排名按照分布產(chǎn)生。

具體而言，DeepMind 的這篇論文將評估多智能體的問題轉(zhuǎn)換為一個馬爾科夫鏈的固定分布。假設(shè)有 N 個智能體，每個智能體有 k 個策略，則該馬爾科夫鏈可被定義為一個聯(lián)合策略圖，有著的轉(zhuǎn)移矩陣。而要被計算的固定概率分布 ν∈R^k^N，用于解 Tν=ν。v 的質(zhì)量函數(shù)就是聯(lián)合策略的排名分數(shù)。這一方法的亮點在于將多智能體的聯(lián)合策略作為一個固定分布，以便進行排名和評估。

圖 1：有 3 個智能體。a）每個智能體有 3 個策略（用顏色區(qū)分）和 5 個副本。每個智能體集群有一個 Pi 值，用于衡量其選擇的策略；b）當一個突變策略（紅色星星）發(fā)生的時候；c）每個群體選擇維持原有策略，或者選擇突變策略。

在 α-Rank 中，N 個智能體的策略會通過突變和選擇進行評價。開始時，智能體集群會構(gòu)建多個學(xué)習器的副本，并假設(shè)每個集群中的所有智能體都會執(zhí)行同一個固定策略。這樣一來，α-Rank 會通過隨機采樣每個集群中的學(xué)習器，用于模擬多智能體的博弈環(huán)境。在游戲結(jié)束時，每個參與的智能體的可以獲得一個收益，這個收益可以用于策略突變和選擇。在這里，智能體面臨一個概率選擇——換成突變策略、維持原有策略，或者隨機選擇一個和前兩個不一樣的新策略。這一過程持續(xù)，目標是決定一個主要的進化方法，并在所有集群的智能體中傳播。

反駁理由

華為論文的反駁理由主要是根據(jù)α*-*Rank 的計算復(fù)雜度進行批判的。α-Rank 聲稱能夠根據(jù)智能體的數(shù)量在多項式時間內(nèi)解出問題，但華為論文認為實際的復(fù)雜度會隨著智能體數(shù)量呈幾何級別的增長，實際上是一個 NP 困難問題。

α-Rank 的計算復(fù)雜度太高

原始的α-Rank 研究聲稱其算法可解，因為隨著聯(lián)合策略的數(shù)量增加，其算法可在多項式時間內(nèi)完成。根據(jù)這一定義，如果α-Rank 有多項式的復(fù)雜度，則計算時間應(yīng)當和公式：O （N × k）^d，（d 和 N（智能體數(shù)量）、K（策略數(shù)量）獨立）相稱。而如果算法要求計算一個固定概率分布，有著一個 k^N 行和列的轉(zhuǎn)移矩陣，則時間復(fù)雜度應(yīng)該是 O（k^N）。很顯然，這個結(jié)果是幾何級的，因此不可解。華為論文的研究者認為，α -Rank 中計算最高的聯(lián)合策略過程是一個 NP 困難問題。

從以上的計算復(fù)雜度研究可以得出一個結(jié)論，如果按照α-Rank 的方法計算一個固定概率分布，有著ε個固定策略，且精確度參數(shù)ε大于 0，可以有多種算法進行計算，計算復(fù)雜度如下表 1 所示。而任何一種現(xiàn)有的計算這個固定概率分布的方法都會因智能體的數(shù)量增長呈現(xiàn)幾何級的復(fù)雜度增長。

表 1：以 N（智能體數(shù)量）×K（策略數(shù)量）表作為輸入時的時間和空間復(fù)雜度比較。

α-Rank 的輸入定義不清

除了計算復(fù)雜度問題，華為論文對α-Rank 的輸入進行了討論。DeepMind 的論文給出了這些智能體的復(fù)雜度計算結(jié)果，并聲明了它們的可解性。但是，華為論文想要闡明的一點是，在沒有正式定義輸入的情況下，此類定義并不能反映真正的底層時間復(fù)雜度，因此很難聲稱這些智能體的可解性。

為此，華為論文舉了解決旅行推銷員問題的例子，這位旅行推銷員需要造訪一系列城市，同時又要按照最短的路線返回最初的城市。盡管大家都知道旅行推銷員問題屬于一種 NP 困難問題，但按照α-Rank 的思路，這一問題可以簡化為「元城市」規(guī)模的多項式時間（線性，如可解決）問題，這并不是一種有效的聲明。

華為論文指出，即使可以說排列數(shù)量確定的情況下可以在多項式復(fù)雜度中解決旅行推銷員問題，這并不能說明任何類似的算法都是可解的。即使算法可以在多項式時間內(nèi)解決問題，但其空間是幾何級規(guī)模的，這并不能說明它是可解決的。因此，要說解決了復(fù)雜度的問題，就需要對輸入進行調(diào)整。

一萬億算力都打不住

在以上問題都沒有清楚解決的情況下，華為論文只能按照推測，將α-Rank 的輸入考慮作為指數(shù)級的收益矩陣。接著，他們進行了一項實驗，對僅執(zhí)行算法 1 中第 3 行的擴展性評估花銷進行了計算，同時也考慮到了 DeepMind 另一篇論文《α-Rank： Multi-Agent Evaluation by Evolution》中的任務(wù)。

華為論文計算了α-Rank 算法 1 中第 3 行的擴展性評估的花銷成本。

此外，構(gòu)建公式 2 中 T 所需的浮點運算總量為

。

公式 2

而就構(gòu)建上述公式 2 中的 T 而言，華為論文計算的花銷成本（以美元計）如下圖 2 所示，其中考慮到了英偉達 Tesla K80 GPU 能夠以每秒 0.9 美元、最高 5.6 GFlop/s 的單精度下運行。

圖 2：計算α-Rank 時構(gòu)造轉(zhuǎn)換矩陣 T 的花銷成本。

這里請注意，當前全球計算機的總算力約為 1 萬億美元（紅色平面）。投影輪廓線表明，由于α-Rank「輸入」的算力需求呈指數(shù)級增長，用十個以上的智能體進行多智能體評估是根本不可能的。

同樣值得注意的是，華為論文的分析沒有考慮存儲 T 或計算平穩(wěn)分布的花銷，因而他們的分析是樂觀的。

此外，如果將α-Rank 的輸入加入收益矩陣并按照 DeepMind 論文的實驗跑 AlphaZero，即使用上全球所有算力，也得花上超過 5200 年。

其他的算法也都不可行——在華為研究人員估算下，即使將收益矩陣加入α-Rank 跑 DeepMind 幾個著名算法需要用到的資金花費和時間都是天文數(shù)字。注意：在這里預(yù)設(shè)使用全球所有的算力。

華為提出改進方法α^α-Rank

華為在其論文中采用了一種隨機優(yōu)化方法，該方法通過對收益矩陣的隨機采樣而獲得解決方案，同時無需存儲指數(shù)大小的輸入。與上表 1 中的內(nèi)存需求相反，這一方法的復(fù)雜度為 O（Nk），每次迭代的復(fù)雜度為線性。值得注意的是，在啟動任何數(shù)字指令之前，大多數(shù)其他方法需要存儲指數(shù)大小的矩陣。盡管在理論上沒有導(dǎo)致時間復(fù)雜度的減弱，但華為論文利用 double-oracle 啟發(fā)式來擴展其算法，進而實現(xiàn)了聯(lián)合策略下的空間減小。事實上，華為論文中的實驗表明，α^α-Rank 可以在大型策略空間的數(shù)百次迭代下收斂至正確的頂級策略。

華為提出的改進方法。

華為論文表明其α^α-Rank 具有可擴展性，能夠成功地在無人駕駛汽車模擬和伊辛模型（Ising model，一種具有數(shù)千萬可能策略的設(shè)置）獲得最優(yōu)策略。他們注意到，當前 SOTA 方法的性能遠遠無法滿足此等規(guī)模的需求。α-Rank 認為 4 個智能體最多可以采用 4 種策略。華為論文中的所有實驗僅僅是在 64GB 內(nèi)存和 10 核心英特爾 i9 CPU 的單機上運行的。

圖 5：大規(guī)模多智能體評估。（a）無人駕駛模擬中最優(yōu)聯(lián)合策略組合的收斂性；（b）伊辛模型的平衡狀態(tài)。