DeepMind阿爾法被打臉，華為論文指出多項問題

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

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

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

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