你的演算法耗盡全球GPU算力都實現不了，DeepMind阿爾法系列被華為怒懟，曾登Nature子刊

近日，DeepMind 之前時間發表在 Nature 子刊的論文被嚴重質疑。來自華為英國研發中心的研究者嘗試實驗了 DeepMind 的方法，並表示該論文需要的算力無法實現。

機器之心報道，參與：一鳴、杜偉。

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

研究者認為，如果要復現近日 DeepMind 登上《Nature》子刊的論文，

需要動用高達一萬億美元的算力，這是全球所有算力加起來都不可能實現的。

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

華為英國研發機構論文：

https：//

arxiv。org/abs/1909。1162

8

DeepMind 論文：

https：//

arxiv。org/pdf/1903。0137

3。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）伊辛模型的平衡狀態。