[新聞] DeepMind提出多智慧體強化學習新方法(星)

[zkow (逍遙山水憶秋年)]

面向星海爭霸：DeepMind提出多智慧體強化學習新方法

　文章來源：公眾號 機器之心　

　　（選自arXiv 機器之心編譯 參與：路雪、李澤南）

　　不久前 DeepMind 強化學習團隊負責人、AlphaGo 專案負責人現身 Reddit 問答，其
中一個問題是‘圍棋和星海爭霸 2 哪個更難？潛在技術障礙是什麼？’近日，DeepMind
發表論文，提出了多智慧體強化學習方法，有望為星海爭霸等遊戲的 AI 技術的開發提供
幫助。該論文也將出現在 12 月美國長灘舉行的 NIPS 2017 大會上。

　　深度強化學習結合深度學習 [57] 和強化學習 [92， 62] 來計算決策策略 [71，
 70]。傳統來說，單個智慧體與所處環境進行重複互動，從觀察結果中學習，進而反覆運
算地改善自己的策略。受近期深度強化學習成就的啟發，DeepMind 的研究人員對多智慧
體強化學習（multiagent reinforcement learning，MARL）重新燃起了興趣 [88， 16，
 97]。在 MARL 中，多個智慧體在一個環境中同時互動和學習，可能是圍棋和撲克中的競
爭模式，學習如何交流的合作模式，也可能是二者皆有。

　　MARL 最簡單的形式是獨立強化學習（independent RL，InRL），每個學習器不理會
其他智慧體，將所有互動作為自己（‘局部’）環境的一部分。這些局部環境是非穩態和
非瑪律可夫的 [55]，導致在很多演算法中缺乏收斂保證，除此之外，研究者還發現這些
策略會與其他智慧體的策略產生過擬合，從而無法實現很好的泛化效果。強化學習社區對
環境過擬合的研究還很少 [100， 67]，但是 DeepMind 的研究人員認為這在多智慧體設
置中尤其重要，該設置中一個智慧體必須根據觀察到的其他智慧體的行為動態地作出反應
。經典的技術是收集或逼近額外資訊如聯合值（joint value）[60， 18， 28， 54]、使
用適應性學習率 [12]、調整更新頻率 [47， 79]，或對其他智慧體的動作進行線上動態
回應 [61， 49]。但是，近期研究中出現了一些特例 [21， 78]，他們關注（重複）矩陣
博弈（matrix game）和/或完全可觀察的環境。

　　有多個建議能夠在多智慧體設置中處理部分可觀測環境。當模型完全可知，且設定是
與兩名玩家完全對抗時，可以使用策略反覆運算方法，該方法基於使用專家級抽象（
expert abstraction）可以進行很好擴展的遺憾最小化（regret minimization）[26，
 14， 45， 46]。近日，研究者將這些方法和深度學習結合起來，創建了無限下注德州撲
克專家級 AI 系統 DeepStack [72]。大量研究在通用設置下，通過擴展信念狀態和來自
 POMDP 的貝葉斯更新 [27]，處理去中心化合作問題 [74， 77]。這些模型具備較強的表
達能力，得出的演算法也比較複雜。在實踐中，由於難解性，研究者通常使用近似式（
approximate form），通過採樣或利用結構來確保模型保持優秀性能 [40， 2， 66]。

　　在這篇論文中，DeepMind 的研究者介紹了一種新的指標，用於量化獨立學習器學得
策略的關聯效果，並展示了過擬合問題的嚴重性。這些協調問題在完全可觀測的環境中已
經得到充分研究 [68]：DeepMind 的研究者在部分可觀測的混合合作/競爭設置中觀察到
了類似問題，並證明其嚴重性隨著環境可觀測的程度降低而增加。DeepMind 的研究者提
出一種基於經濟推理（economic reasoning）的新型演算法 [80]，該演算法使用（i）深
度強化學習來計算對策略分佈的最佳回應，（ii）博弈論實證分析（empirical
game-theoretic analysis）來計算新的元策略分佈。研究者為去中心化執行進行中心化
訓練：策略以分離的神經網路的形式呈現，智慧體之間沒有梯度共用或架構共用。基本形
式使用中心化支付矩陣（payoff table），但在需要更少空間的分散式、非中心化形式中
該矩陣被移除。

圖 1：Double Oracle 演算法。圖 1：Double Oracle 演算法。

　　DeepMind 的研究人員展示了他們的主要概念性演算法：策略空間回應 oracle（
policy-space response oracles，PSRO）。該演算法是 Double Oracle 演算法的自然泛
化，其中元博弈是策略而非動作。它還是 Fictitious Self-Play 的泛化 [38， 39]。與
之前的研究不同，該演算法可以插入任何元求解器以計算新的元策略。在實踐中，無需任
何域知識，使用參數化策略（函數逼近器，function approximator）泛化至狀態空間。
圖 4：（a）兩玩家 Leduc 撲克中 DCH 參數在 NashConv 上的效果。左：解耦 PRD；中
：解耦 RM；右：Exp3。（b）MAUC 對抗 cfr500 的滲透圖。圖 4：（a）兩玩家 Leduc
撲克中 DCH 參數在 NashConv 上的效果。左：解耦 PRD；中：解耦 RM；右：Exp3。（b
）MAUC 對抗 cfr500 的滲透圖。

　　DeepMind 也展望了新方法的未來應用方向，研究人員正在考慮保持基於策略差異損
失懲罰的差異性，一般回應圖拓撲，即時語言遊戲和 RTS 遊戲等環境，以及其他需要進
行預測的架構，如對立建模、在輔助任務中進行未來狀態估測。DeepMind 還希望研究快
速線上適應及其與計算心智理論的關係，以及對使用繼任者特徵的類似策略進行泛化（遷
移）的 oracle。

　　論文：A Unified Game-Theoretic Approach to Multiagent Reinforcement
Learning

　　論文連結：https：//arxiv.org/abs/1711.00832

　　要想實現通用智慧，智慧體必須學習如何在共用環境中與他人進行互動：這就是多智
慧體強化學習（multiagent reinforcement learning，MARL）遇到的挑戰。最簡單的形
式是獨立強化學習（independent reinforcement learning，InRL），每個智慧體將自己
的經驗作為（非穩態）環境的一部分。這篇論文中，我們首先觀察到，使用 InRL 學得的
策略能夠在訓練過程中與其他智慧體的策略產生過擬合，但在執行過程中無法實現充分的
泛化。我們引入了一種新的指標：共策略關聯（joint-policy correlation），對該效果
進行量化。我們介紹了一種用於通用 MARL 的演算法，該演算法基於深度強化學習生成的
多種策略的幾乎最佳回應，還進行博弈論實證分析來計算策略選擇的元策略。該演算法是
之前演算法的泛化，如 InRL、iterated best response、double oracle 和
 fictitious play（虛擬對局）。之後，我們展示了一種可擴展的實現，使用解耦元求解
器（meta-solver）減少記憶體需求。最後，我們在兩種部分可觀測的設置（gridworld
coordination games 和撲克）種展示了該策略的通用性。

http://sports.sina.com.cn/go/2017-11-04/doc-ifynmzrs7030271.shtml

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.233.93.166
※ 文章網址: https://www.ptt.cc/bbs/StarCraft/M.1509809455.A.40F.html
※ 編輯: zkow (118.233.93.166), 11/04/2017 23:31:14
推 syldsk: 嗯嗯，跟我想的一樣
推 henry1915: 可惡 我paper寫得慢了一點QQ
推 goal56: 看不懂
推 c60203: 我也是這樣認為
推 xxxddd748: 嗯嗯我也是想說該從這個方向前進
→ zseineo: 那堆數字感覺應該編輯掉
推 GLaDOS1105: 不舒服
推 Sechslee: 太硬了 看不懂
推 Adonisy: 嗯,論文被搶先了
推 woodghost: 在下資質愚鈍 請問這要怎麼應用在AI打星海上?
推 iamten: 重點：有望 提供幫助  就是還不行啦
推 dispatchadv: 想請教：AI領域，有沒有一看就知道騙科專經費的？
推 Timba: 有... 就是沒有演算法 一堆資料一堆判斷 就是
推 dispatchadv: 謝賜教，原來如此，真有趣www
推 g9911761: 可以講中文嗎