DeepMind阿爾法被打臉，華為論文指出多項(xiàng)問題

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

研究者認(rèn)為，如果要復(fù)現(xiàn)近日 DeepMind 登上《Nature》子刊的論文，需要?jiǎng)佑酶哌_(dá)一萬億美元的算力，這是全球所有算力加起來都不可能實(shí)現(xiàn)的。

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

被懟的 DeepMind 論文

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

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

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

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

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

α-Rank 原理

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

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

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

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

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

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

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

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

反駁理由

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

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

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

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

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

α-Rank 的輸入定義不清

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

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

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

一萬億算力都打不住

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

華為論文計(jì)算了α-Rank 算法 1 中第 3 行的擴(kuò)展性評(píng)估的花銷成本。

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

。

公式 2

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

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

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

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

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

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

華為提出改進(jìn)方法α^α-Rank

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

華為提出的改進(jìn)方法。

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

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