ICML論文|阿爾法狗CTO講座: AI如何用新型強化學習玩轉圍棋撲克遊戲

6月19日（美國時間）在紐約舉行的國際機器學習大會（ICML）上，來自谷歌、Facebook以及頂尖研究學府的科學家們通過論文和講座，分享了最尖端的機器學習研究成果。其中，谷歌DeepMind科學家David Silver在講座「深度增強學習」中分享了深度神經網絡在各項實際應用中的算法。雖然David Silver不如DeepMind CEO Demis Hassabis那麼為人所知，實際上，他正是DeepMind圍棋團隊一直雪藏的主程式設計師。 

從左到右：David Silver、Demis Hassabis和圍棋冠軍李世石。圖片來源：BI。

David Silver以班級最優成績從劍橋大學畢業，正是在劍橋他與Demis Hassabis相識，據稱也正是Hassabis教會了Silver如何下圍棋。畢業後，Silver成立了遊戲公司 Elixir 並擔任CTO及程序負責人，贏得了一系列科技創新獎項。2004年Silver開始攻讀PHD，期間聯合引入了初代圍棋程序的算法，該算法當時在9 x 9的棋盤打贏人類。Silver從DeepMind創立之初便一直擔任顧問，2013年全職加入團隊，2014年穀歌收購了DeepMind。今年3月，DeepMind的人工智慧算法AlphaGo在19 x 19的標準棋盤上打贏了人類圍棋冠軍。Hassabis對英國《衛報》說：「我們曾經幻想著今生可以做這樣的事情（創造強大的AI），所以，我們19歲的自己如果知道了，應該會感到安心。」

Silver此次ICML的講座主要探討應用廣泛的增強學習技術。「人工智慧的一個主要目標，是創造具有通用目標的代理，能夠在眾多具有挑戰性的任務中高效運行。為實現這一目標，我們需要將增強學習（RL）代理與強大、靈活的表徵結合起來。RL的關鍵概念是利用神經網絡來獲得這種表徵的力量。這場講座中，我們將介紹一系列深度神經網絡用於估值函數、策略或者環境模型的算法。我們將呈現各個領域內最頂尖的研究結果，包括Atari遊戲、3D導航任務、持續控制以及圍棋。」

講座中提到，DeepMind的強化學習的不只應用於Atari遊戲、撲克和圍棋，還包括導航領域中的3D世界和迷宮，控制物理系統中如何進行操作、走路和遊泳等動作，還有在用戶交互層面的推薦、優化和個人化等等。

今年8月，Demis Hassabis等人工智慧技術先驅們將來到雷鋒網(公眾號：雷鋒網)「人工智慧與機器人創新大會」。在此，我們為大家分享David Silver的論文《不完美信息遊戲中的深度強化學習自我對戰》。本篇論文主要以撲克進行實驗，探討深度強化學習與普通強化學習相比的優勢。研究此類遊戲不只是可以讓程序打贏人類大師，還可以幫助開發算法，應用於更複雜的真實世界環境中，例如機場和網絡安全、金融和能源貿易、交通管制和疏導，幫助人們在不完美的信息和高維度信息狀態空間中進行決策。深度強化學習不需要依賴人類專家的原有知識，這解決了遊戲的可擴展性問題，未來算法可以不依賴成本高昂的人類專家，也不用擔心受到偏見等非理性因素的影響，就能幫助決策。論文的另一位作者是倫敦大學學院的研究學生 Johannes Heinrich。

論文摘要

許多真實世界應用可以描述為不完美信息遊戲的擴展版本。對於這些挑戰巨大的領域，之前的研究主要集中在計算手工抽象出來的納什均衡。這篇論文中，我們引入第一個可擴展的端到端方法，無需預先具備任何知識，就能學會模擬納什均衡。我們的方法將虛擬自我對戰與深度強化學習結合起來。當應用在德州撲克時，神經虛擬自我對戰（NFSP）達到了一種納什均衡，而普通的強化學習方法則出現了偏離。在限制德州拿住撲克中（一種真實世界規模的撲克遊戲），NFSP學會了一種很有競爭力的策略，實現了人類專家的能力和頂尖的方法。

1、簡介

歷史上，遊戲一直推動著人工智慧和機器學習的進步（Samuel, 1959; Tesauro, 1995; Campbell 等人, 2002; Riedmiller 等人, 2009; Gelly 等人, 2012; Bowling 等人, 2015）。遊戲理論將遊戲定義為一個衝突區域或者多方的合作（Myerson，1991）。之所以學習比較簡單的娛樂遊戲，其中一個目的是開發算法，可以擴展到更加複雜的真實世界遊戲，例如機場和網絡安全、金融和能源貿易、交通管制和疏導(Lambert III 等人, 2005; Nevmyvaka 等人, 2006; Bazzan, 2009; Tambe, 2011; Urieli & Stone, 2014; Durkota 等人, 2015)。大部分這些真實世界遊戲都需要進行決策，而決策基於不完美的信息以及高維度的信息狀態空間。不幸的是，許多已經應用到經典遊戲中的機器學習方法，在信息不完美的遊戲中缺少收斂的保證。另一方面，許多遊戲理論方法缺少抽取相關模式、並從數據中概況的能力。這讓大型遊戲的可擴展性有限，除非使用人類專家知識、啟發式方法和建模來將該領域抽象化至可控的規模。然而，獲取人類專業知識競猜需要昂貴的資源和時間。此外，人類很容易出現非理性的決策或者假設（Selten, 1990；Ariely & Jones，2008）。這讓我們希望開發算法，端到端地學習有用的策略。

這篇論文中我們引入NFSP，一個深度強化學習方法，可以學習模擬不完美信息遊戲的納什均衡。NFSP 代理的學習方法是與自己對戰，無需預先具有明確的知識。技術上來說，NFSP 利用神經網絡函數模擬，將虛擬自我對戰（FSP）（Heinrich 等人, 2015）擴展並實例化。一個 NFSP 代理由兩個神經網絡和兩種記憶組成。強化學習利用與代理同伴一起玩的記憶體驗來訓練神經網絡，預測行為的預期價值。代理自己行為的經驗（s_t，a_t）儲存在一個分開的記憶中，一個監督學習方法利用該記憶來訓練神經網絡，預測代理自己的平均行為。NFSP 代理可以通過從自己的行為的平均、常規策略和貪婪策略（貪婪策略將預測的估值最大化）中取樣，從而小心行事。NFSP 模擬虛擬對戰，這是在遊戲學習中一種流行的遊戲理論模型，在一些經典遊戲中收斂至納什均衡，例如雙玩家零和遊戲和多玩家潛在博弈。

我們在一個雙人零和計算機撲克遊戲中實證評估了我們的方法。在這個領域中，目前的遊戲理論方法使用啟發性方法，將遊戲抽象至一個可以駕馭的規模（Zinkevich 等人, 2007; Gilpin 等人, 2007； Johanson 等人，2013）。雖然限制德州拿住撲克（LHE）——一種真實世界規模的撲克遊戲——已經可以用目前的計算資源解決（Bowling 等人，2015），大部分其他撲克和真實世界遊戲如果不經過抽象化便無法觸及。我們的方法不依賴例如抽象化或者其他任何的預先知識。NFSP 代理利用深度強化學習來直接從其與遊戲互動的經驗中學習。當應用在德州撲克上的時候，NFSP 實現了一種納什均衡，而普通的強化學習方法出現了偏離。我們還將 NFSP 應用到 LHE，直接從原始輸入中學習。NFSP 學會了一種具有競爭力的策略，基於手工抽象化實現了頂尖方法的運行效果。

2、背景

在這個部分，我們展現一個對於強化學習方法、擴展式博弈論表述虛擬自我對戰的簡短概況。如需更加細節的闡述，我們推薦讀者閱讀 (Sutton & Barto, 1998), (Myerson, 1991), (Fudenberg, 1998) and (Heinrich 等人, 2015)。

2.1. 強化學習（RL）

強化學習（Sutton & Barto，1998）代理通常從與環境的互動中，學會將預期的未來獎勵最大化。環境通常是作為「馬爾可夫決策過程」（MDP）進行建模。代理基於策略行動，策略具體說明在MDP的每一個狀態中，可行行動的分布。代理的目標是改善自己的策略，從而最大化其收穫，是從 t 時間開始，代理累計未來回報的一個隨機變量：許多強化學習算法從過渡元組形式的連續「經驗」中學習，(s_t ,a_t ,r_t+1 ,s_t+1 )，其中 s_t 是 t 時間的狀態，a_t 是這個狀態中選擇的行動，r_t+1 是其後獲得的獎勵，s_t+1 是代理過渡進入的下一個狀態。一個普遍的目標是「學習行動價值函數」，，定義為在 s 狀態、遵循 π 策略、採取 a 行為後預計獲得的獎勵。如果代理學會自己正在遵循的策略，那麼代理的學習是「符合策略」的。在「偏離策略」的情況下，代理從其他代理的經驗中學習，或者學會一個其他的策略，例如一個以前的策略。

Q-學習（Watkins & Dayan，1992）是一種流行的偏離策略強化學習方法。它學會貪婪策略，這在每一個狀態下採取最高預估值的行動。通過將偏離政策強化學習應用到各自的過度元組，從而將過往的經驗儲存和回放，這被稱為經驗回放（Lin，1992）。擬合Q值迭代（FQI）（Ernst 等人, 2005）是一種批量學習方法，用Q-學習來回放經驗。神經擬合Q值迭代（NFQ）（Riedmiller，2005）和深度Q網絡（DQN）（Mnih 等人，2015）是FQI 的擴展，使用分別帶有批量和在線更新的神經網絡函數近似。

2.2. 擴展式博弈論表述

擴展式博弈論表述是一種涉及多個玩家的連續互動模型。假設玩家為理性的，每個玩家的目標是最大化自己在遊戲中的收穫。在不完美信息遊戲中，每個玩家至觀察到各自的「信息狀態」，換句話說，在撲克遊戲中，一個玩家只知道他自己的卡片，不知道其他玩家的卡片。每一個玩家選擇一個「行為策略」，將信息狀態匹配到可選行動的概率分布中。我們假設具有「完美回想能力」的遊戲，即，每個玩家目前的信息狀態包含玩家信息狀態和行動的數列，這個數列將玩家帶入目前的信息狀態。「實現概率」（Von Stengel，1996）決定玩家 i 行為策略 πⁱ 對實現信息狀態有利的概率。「策略描述」 π = （π¹，...，πⁿ） 是所有玩家的策略集合。π^-i 指的是， π 中除了 πⁱ 的所有策略。當給出一個固定的策略描述 π^-i，基於 π-i，玩家 i 實現最優回報表現的策略稱為「最優回應」。一個近似或者 ε-最佳回應，是不超過 ε 的次優回應。「納什均衡」是一種策略描述，其中每一個玩家的策略對於其他策略來說是一種最優回應。同樣的，一個近似或者 ε-納什均衡是一種 ε-最優的回應。在納什均衡中，沒有哪個玩家在偏離策略的時候能有收穫。因此，納什均衡可以作為一個理性自我對戰學習的定點。實際上，納什均衡是唯一一個理性代理有望在自我對戰中收斂的策略描述（Bowie & Veloso，2001）。

2.3. 虛擬自我對戰

「虛擬對戰」（Brown，1951）是一個從自我對戰中學習的遊戲理論模型。虛擬玩家選擇對應對手平均行為的最優回應。虛擬玩家的平均策略在特定遊戲類別中收斂於納什均衡，例如，雙玩家的零和遊戲和多玩家潛在博弈(Robinson, 1951; Monderer & Shapley, 1996)。Leslie & Collins （2006）引入了概括化的弱化虛擬對戰，具有與普通虛擬對戰相似的收斂保證，但是允許近似最優回應和擾動平均策略更新，使其特別適合機器學習。

虛擬對戰通常以正則形式定義，這比擴展式博弈論表述要低效得多。Heinrich 等人 （2015） 引入了「全寬度擴展式虛擬對戰」（XFP），讓虛擬玩家可以行為主義地、擴展式地更新策略，這造成了線性時間和空間的複雜度。一個關鍵結論是，對於一個正則形式策略的凸組合，

我們可以獲得一個等同於實現的行為主義策略 δ，方法是將其設定為與對應的實現概率凸組合成比例，

其中是在信息狀態 s 中策略的正則化常數。除了定義行為策略中虛擬玩家的全寬度平均策略更新，方程（1）規定了一種從此類策略的凸組合資料庫中取樣的方法。Heinrich 等人（2015）引入了「虛擬自我對戰」（FSP），一種基於樣本和機器學習類別的算法，可以近似 XFP。FSP 分別用強化和監督學習代替了最優回應計算和平均策略更新。尤為重要的是，FSP 代理在自我對戰中生成自己經驗的資料庫。每一個代理將其經驗過渡元組儲存在一個指定用於強化學習的記憶 M_RL 中。代理自己行為的經驗（s_t，a_t）的儲存在一個分開的記憶 M_SL 中，指定用於監督學習。自我對戰取樣的設定方式，讓代理的強化學習記憶近似一個其他玩家平均策略描述所定義的 MDP 的數據。類似地，代理的監督學習記憶近似代理自己平均策略的數據，可以通過監督分類習得。

3. 神經虛擬自我對戰

神經虛擬自我對戰（NFSP）是 FSP 的 進化版本，引入了多個擴展，例如神經網絡函數近似、蓄水池抽樣、預期動態和一個完全基於代理的方法。NFSP 代理與遊戲中其他玩家互動，記住自己遊戲轉換的經驗以及自己的行為。NFSP 將這些記憶看做兩個適合深度強化學習和監督分類的資料庫。代理還特別訓練一個神經網絡 F_Q ，使用偏離政策的強化學習，從資料庫 M_RL 中預測行為值 Q(s, a)。它產生的神經網絡定義代理的近似最優回應策略： β = ε-greedy (F_Q)，後者選擇一個概率為 ε 的隨機行為，否則則會選擇一個能夠最優化預測行為值的行為。NFSP 代理訓練一個分開的神經網絡 F_S，用監督分類在數據 M_SL 上模擬自己過去的行為。這個神經網絡將狀態匹配到行動概率，並定義代理的平均策略 π = F_S。遊戲中代理從其兩項策略 β 和 π 的混合中選擇自己的行為。

雖然虛擬玩家通常對於對手的平均策略採取最優回應，在連續時間動態虛擬遊戲（Shamma & Arslan，2005）中，玩家基於對手的平均正則策略的短期預測，來選擇最優回應。作者顯示了這項基於遊戲的恰當選擇，針對均衡點上虛擬玩家的 η 穩定性。NFSP 使用作為這項預期動態中使用的導數的離散時間近似。注意，是常見離散時間虛擬遊戲的正則化更新方向。為了讓一個 NFSP 代理計算出近似最優回應 βⁱ，對於其對手的預期平均策略描述代理迭代性地評估和最大化其行為值。實現的方法可以是基於和對手的預期策略 δ^-i 遊戲的經驗，進行偏離策略的強化學習，即，Q-學習或者 DQN。為確保代理的強化學習記憶 M_RL 包含這種經驗，NFSP 要求所有代理從中選擇他們的行為，其中 η ∈ R 被稱為「預期參數」。

虛擬遊戲通常追蹤玩家在遊戲中已選的正則形式最優回應策略的平均值。Heinrich 等人（2015）提出使用取樣和機器學習來生成數據，學習正則形式策略拓展形式的凸組合。例如，我們可以生成一組數據的擴展形式，方法是從整個遊戲時間中取樣，在凸組合中使用與其權重 1/T 成比例。NFSP 使用蓄水池取樣（Vitter，1985；Osborne 等人，2014）來記憶自己平均最優回應的經驗。代理的監督學習記憶 M_SL 是一個蓄水池，只有當它遵循近似最優回應策略 β 的時候才增加經驗。NFSP 代理常規性地訓練自己的平均策略網絡 π = F_S，與自己存儲在自己監督學習記憶中的平均行為相匹配，例如通過最優化過去行為的日誌概率。算法（1）呈現了使用 DQN 進行強化學習的 NFSP。

算法1：使用 DQN 進行強化學習的 NFSP。

4、實驗

我們在德州撲克（Southey 等人，2005）和限制德州拿住撲克中評估 NFSP 和相關算法。我們大部分的實驗學會策略描述的可利用性。在一個雙玩家零和遊戲中，一項策略描述的可利用性定義為，最優回應描述可以獲得的期望平均回報。2δ 的可利用性至少是一個 δ-納什均衡。

4.1. XFP 的強度

要理解函數近似如何與 FSP 互動，我們以一些簡單實驗開始，模擬近似，並從全寬度算法 XFP 中獲取錯誤樣本。首先，我們探索當用一個靠近梯度下降的增量平均過程代替 XFP 中使用的完美平均，會有什麼結果。然後，我們探索當用一個帶 ε 誤差的近似代替 XFP 中使用的同一個查表法，會有什麼結果。

圖1：定步長對於 LHE 遊戲中全寬度虛擬對戰表現的影響。

圖1顯示了帶有默認值 1/T 和策略更新定步長的 XFP 的表現。我們看見漸進提高了，但是針對更小步長的最初表現變低了。對於定步長，表現似乎是達到平穩、而非偏離。使用蓄水池取樣可以實現高效的定步長，為 1/T。但是，結果顯示指數平均的蓄水池取樣同樣可行，因為指數平均過往記憶會近似對應於使用一個定步長。

定步長為1的 XFP等同於一個全寬度迭代最優回應算法。雖然在有限完美信息雙玩家零和遊戲中這個算法收斂於納什均衡，結果顯示，在不完美信息中這就不能成立了。Yakovenko 等人（2016）引入的撲克-CNN 算法存儲少量過往策略，基於這些策略迭代性地計算新策略。代替那個集合中的策略類似於更新一個具有很大定步長的平均策略。這有可能導致類似圖1中顯示的問題。

圖2：當 LHE 遊戲在最優回應計算中加入均勻隨機噪音，XFP 的表現。

我們的 NFSP 代理在他們的策略中加入隨機探索，使用噪音隨機梯度來學習行動價值。因此，我們研究了在最優回應計算中加入隨機噪音的影響，XFP 通過動態編程來運行最優回應計算。在逆向歸納法的每一步，我們傳回一個帶有概率 ε 的均勻隨機行動的值，否則則傳回最佳行動的值。圖2顯示出，增加噪音時表現清一色地下降。但是，表現仍保持穩定，對於所有噪音等級來說都持續改善。

4.2. NFSP的收斂

我們實證研究了在 LHE 遊戲中 NFSP 收斂至納什均衡。我們還研究了去除或改變一些 NFSP 的組成部分是否會打破收斂。

我們的一項目標，是將對過往知識的依賴性最小化。因此，我們希望定義一個撲克遊戲中信息狀態的目標編碼。與其他計算機撲克的研究不同（Zinkevich 等人, 2007; Gilpin 等人, 2007; Johanson 等人, 2013），我們不進行任何高層級特徵的工程。撲克遊戲通常包含很多輪。在每一輪，新卡片發給玩家。我們將每一輪的卡片用一個「n 個中的第 k 個」編碼來表徵，例如，當 LHE 有一疊52張卡片，第二輪發出三張新卡。這樣，這一輪的編碼就使用長度為52的矢量和三個設為1的元素，其餘元素設為0。在 LHE 撲克遊戲中，玩家通常有3種可選的行為，即 {棄牌、根注、加注} 。注意，根據情景而定，跟注和加注可以分別稱為「讓牌」和「押注」。押注限制在每輪固定數量的加注之內。這樣，我們可以將押注歷史表徵為一個4維度的張量，即 {玩家、輪數、加注數量、採取行動} 。也就是說，單挑 LHE 遊戲中包含2個玩家、4輪、每輪0-4次加注和3個行動。這樣，我們可以將一個 LHE 押注歷史表徵為 2 x 4 x 5 x 3 張量。在單挑遊戲中，我們不需要編碼棄牌行為，因為如果一方放棄遊戲就結束了。這樣，我們可以將4維張量扁平化，成為一個長度為80的矢量。將4輪的卡牌都聯接起來，我們就可以將一個 LHE 的信息狀態編碼為一個長度為288的矢量。相似地，一個 LHE 的信息狀態可以編碼為一個長為30的矢量，因其包含6種卡片以及3個重複卡片、2輪、每輪0-2次加注以及3次行動。

要實現 LHE 中的學習，我們將 NFSP 手動校準為一個完全聯接的神經網絡，帶有1個隱含層、包含63個神經元和線性激活。然後，我們重複各種具有相同參數的神經架構的實驗。我們特別設置記憶大小為200K，M_RL 和 M_SL 分別為2M。M_RL 的功能是一個環形緩衝器，包含一個最近的經驗。M_SL 用蓄水池取樣更新。強化學習率和監督學習率分別設置為為 0.1 和 0.005，兩者都使用隨機梯度下降（SGD），沒有神經網絡隨機最優化的趨勢。每一個代理進行3次隨機梯度更新，遊戲中每128步、每個神經網絡中最小批次數量為128。DQN 算法的目標網絡每300次更新就重新調整。NFSP 的預期參數設置為 η = 0.1。ε-貪婪策略的探索從 0.06 開始，下降到0，與迭代次數的逆平方根成比例。

圖3：LHE 遊戲中的 NFSP 的學習表現。

圖3顯示了對於各種網絡架構， NFSP 趨近納什均衡。我們觀察到隨著網絡數量的增加，表現也清一色地增加。NFSP 實現了0.06的利用性，而全寬度 XFP 通常在1000輪全寬度迭代才能實現。

圖4：通過去除必須的 NFSP 組成部分，打破 LHE 遊戲中的學習表現。

為了研究 NSFP 各種組成部分的相關度，也就是說，蓄水池取樣和期望動態，我們進行了一個分離他們效果的實驗。圖4顯示，這些變動導致表現下降。特別是使用固定大小的滑動窗口來儲存代理自己行為的經驗，會導致偏離。對於一個0.5的高期望參數，NFSP 的表現進入了停滯。最終，使用指數平均蓄水池取樣進行監督學習記憶更新，導致了噪音表現。

4.3. 與DQN比較

之前已有多個穩定算法提出過用於深度強化學習，尤其是 DQN 算法（Mnih 等人，2015）。但是，這些算法的實證穩定性之前只在單一代理、完美（或接近完美）信息 MDP 中建立過。這裡，我們研究與 NFSP 相比，在多代理、信息不完美遊戲中的 DQN 穩定性。

圖5：在 LHE 遊戲中比較 DQN 的表現。

DQN 學會一種決定論的貪婪策略。這在 MDP 中足夠進行最優行為，算法就是為此而設計的。不過，在信息不完美遊戲通常要求最優行為的隨機策略。這樣，除了 DQN 的 ε-貪婪策略，我們將其行為存儲在一個監督學習記憶 M_SL 中，並學習其平均行為。這項平均策略不影響 DQN 的實施行為，因為它從來不會被執行。我們通過使用帶有期望參數 η = 1 的 NFSP，來實施這個 DQN 變量。我們將 DQN 大部分參數設置為與之前部分實驗中的 NFSP 相同。這是為了讓監督學習參數不直接影響 DQN 的表現。我們用以下所有參數的組合來訓練 DQN：學習比例 {0.2,0.1,0.05}，衰減探索開始於 {0.06,012}，增強學習記憶 {2m蓄水池，2m滑動窗口}。然後，我們選擇 DQN 表現最優的結果，將其與之前部分實驗中的 NFSP 表現相比較。DQN 在學習比例為0.1、探索從0.12開始和滑動窗口記憶為2m的時候，實現其最佳表現結果。

圖5顯示，DQN的決定論策略是高度可利用的，這是可以預見的，因為信息不完美遊戲通常要求隨機策略。DQN 的平均行為也沒有趨近納什均衡。這值得注意，因為 DQN 將其經驗存儲在一個回放記憶中，因此會高效地學會對手的平均行為，只要其回放記憶足夠大，可以對它進行追蹤。這與虛擬對戰很像。但是，因為 DQN 代理在自我對戰中使用 ε-貪婪策略，它們的經驗隨著時間高度相關，集中在一個狀態子集。我們相信這是 NFSP 在我們試驗中表現更好的主要原因。NFSP 代理在自我對戰中使用一種改變更慢的平均策略。這樣，它們的經驗改變更慢，導致它們的記憶中包含更穩定的數據分布。這會幫助它們訓練神經網絡，並適應彼此。其他常見的強化學習方法都被證明在撲克遊戲中具有類似的停滯表現（Ponsen 等人,2011; Heinrich & Silver, 2015)。

4.4. 限制德州拿住 （LHE）

我們將 NFSP 應用於非常流行的 LHE 遊戲。2008年，一個電腦程式第一次在公開競賽中打敗了人類 LHE 玩家，從此現代計算機代理被廣泛認為實現了超人表現（Newall，2013）。這種遊戲由 Bowling等人（2015）根本上解決。我們用 SmooCT 來評估我們的代理，這是一個在2014年年度計算機撲克競賽（ACPC）中獲得了三項銀牌的 Smooth UCT （Heinrich & Silver，2015）代理。學習表現以 mbb/h 來衡量，換句話說，在每一手最開始的時候玩家大盲注的千分之一。

我們手動校準了 NFSP，嘗試了9種配置。我們用以下的參數實現了最優表現。神經網絡完全聯接，有4個隱藏層，分別有1024、512、1024和512個具有線性激活的神經元。M_RL和M_SL的記憶容量分別設定為600k和30m。M_RL作為環形緩衝器，包含一個近期經驗。M_SL用指數平均的蓄水池取樣（Osborne等人，2014）更新，用最低概率0.25代替M_SL中的條目。我們使用沒有強化學習和監督學習趨勢的 SGD，將學習比例分別設置為0.1和0.01。每一個代理進行2次隨機梯度更新，遊戲中每256步、每個網絡的最小批次大小為256。DQN 算法的目標網絡是每1000次更新就重新調整。NFSP的預期參數設置為 η = 0.1。ε-貪婪策略的探索從0.08開始，衰退至0，比在 LHE 中更慢。除了 NFSP 的主要平均策略描述，我們還評估了最優回應和貪婪平均策略，它們決定論地分別選擇最大化預期行動值或者概率的行動。

圖6：與 SmooCT 對戰的表現。每次評估的標準誤差小於 10 mbb/h。

為了在單挑 LHE 中提供一些勝率的直覺，永遠棄牌的玩家會損失 750 mbb/h，人類專家玩家在在線高風險遊戲中通常達到40-60 mbb/h 的預期勝率。類似的，在2014 ACPC中，表現前一半的計算機代理自己實現了最高 60 mbb/h 的預期勝率。在訓練中，我們基於 SmooCT 周期性地評估 NFSP 的表現，每一個都玩25000手。圖6呈現了 NFSP 的學習表現。NFSP 的平均和貪婪平均策略描述顯示了一個穩定、相對統一的表現改善，並分別實現了大約-50 mbb/h 和-20 mbb/h 的勝率。最優回應策略描述在每次表現中體現了更多的噪音，大部分在 -50 到 0 mbb/h 的範圍內。我們還基於2014 ACPC中的前三名，評估了最終貪婪平均策略。表格1呈現了結果。

表格1

5. 相關研究

依賴人類專家知識可能會很昂貴，而且如果知識是次優的，可能會受到人類偏見和限制的影響。但是，許多已經應用在遊戲中的方法都依賴人類專家的知識。深藍在象棋中使用人類製造的評估函數（Campbell等人，2002）。在計算機圍棋中，Maddison等人（2015）和Clark & Storkey （2015）用人類專家下棋的數據來訓練深度神經網絡。在計算機撲克中，目前的遊戲理論方法使用啟發式方法來理解卡片強度，從而將遊戲抽象至可以駕馭的規模(Zinkevich等人, 2007; Gilpin等人, 2007; Johanson等人,2013)。Waugh等人（2015）最近將其中一種方法與函數近似相結合。然而，他們的全寬度算法必須暗中推導每一次迭代中的所有信息狀態，這在大的領域來說過於昂貴。與之相比，NFSP 專注在基於樣本的強化學習設定，其中遊戲的狀態不需要全部列舉，學習者甚至不需要有一個遊戲動態的模型。

許多遊戲中的成功應用依賴本地搜索（Campbell等人，2002；Browne等人，2012）。本地搜索算法在遊戲中，實時、有效地計劃決策，例如通過蒙特卡洛模擬或者有限深度逆向歸納法。但是，常見的基於模擬的本地搜索算法應用在信息不完美的撲克遊戲中時，已經證實會偏離（Ponsen等人，2011；Heinrich & Silver，2015）。而且，即便是遊戲理論方法在信息不完美遊戲中進行本地規劃時，通常也沒法實現不可利用的行為（Burch等人，2014；Ganzfried & Sandholm，2015；Lisy等人,2015）。本地搜索的另一個問題是，如果沒有注入原有知識來引導搜索，實時運行的成本有可能非常巨大。這引發了如何獲得這種原有知識的問題。Silver等人（2016）用人類專家數據訓練了卷積神經網絡，然後使用一個自我對戰強化學習過程來進一步優化這些網絡。通過使用這項神經網絡來引導高性能本地搜索，他們戰勝了圍棋大師。在這項研究中，我們不使用任何實時本地搜索來評估我們的代理。如果可以開發針對信息不完美遊戲的本地搜索方法，NFSP 訓練的策略可以是引導搜索的一個好選擇。

納什均衡是理性代理可以在自我對戰中有望收斂的唯一策略描述（Bowling & Veloso，2001）。TD-Gammon（Tesauro，1995）是一個世界級別的西洋雙陸棋代理，它的主要組成部分是一個用自我對戰強化學習訓練的神經網絡。雖然其算法基於臨時差異學習，在雙玩家、信息完美的零和遊戲中是可行的，可是在不完美遊戲中總體來說不能收斂。DQN（Mnih等人，2015）結合了臨時差異學習、經驗回放和深度神經網絡函數近似。它在大部分Atari遊戲中實現了人類等級的表現，從原始感覺輸入中學習。但是，這些Atari遊戲的設定是單一代理環境，潛在對手固定，並由Atari模擬器控制。我們的實驗顯示，DQN 代理在 LHE 遊戲中沒法實現納什均衡，其中玩家允許進行動態適應。Yakovenko等人（2016）在計算機撲克對戰中訓練了深度神經網絡，包括兩個在人類中非常流行的撲克遊戲。他們的網絡與基於啟發式方法和簡單的計算機程相比表現更強。人類專家玩家可以超越他們的代理，雖然其樣本大小不具有統計學意義。他們的方法在現實或理論中是否會收斂是個未知數。與之對比，我們實證證明了 NFSP 在 LHE 遊戲中收斂至近似納什均衡。而且，我們的方法是有原則的，是基於擴展式博弈論表述中的虛擬對戰理論。

6、結論

我們引入了 NFSP，第一個端到端深度強化學習方法，在不完美信息遊戲中以自我對戰學習近似納什均衡。NFSP 解決三個問題。

首先，NFSP 代理學習不需要具備原有知識。

第二，他們不依賴於實時本地搜索。

第三，他們在自我對戰中收斂至近似納什均衡。我們的實證結果提供了以下收穫：虛擬遊戲的表現隨著各種近似錯誤優雅地衰退；NFSP 在小撲克遊戲中能可靠地收斂於近似納什均衡，而 DQN 的貪婪和平均策略不能；NFSP 在真實世界規模的信息不完美遊戲中，從零學會一種有競爭力的策略，不需要使用明確的原有知識。

在這項研究中，我們專注於信息不完美的雙玩家零和遊戲。但是，虛擬對戰在合作性的潛在遊戲中，也能保證收斂至納什均衡。因此我們可以看到，NFSP 也可以成功應用於這些遊戲。而且，連續動作強化學習的最近進展（Lillicrap等人，2015）可以讓 NFSP 應用於連續動作遊戲，這是目前的遊戲理論方法沒法直接解決的問題。

via ICML

雷鋒網原創文章，未經授權禁止轉載。詳情見轉載須知。