<mark id="oztn4"></mark>
1
| 本文作者： AI科技評論 | 2016-06-22 10:42 | 專題：ICML：國際機器學習會議 |
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 代理由兩個神經網絡和兩種記憶組成。強化學習利用與代理同伴一起玩的記憶體驗來訓練神經網絡，預測行為的預期價值。代理自己行為的經驗（st，at）儲存在一個分開的記憶中，一個監督學習方法利用該記憶來訓練神經網絡，預測代理自己的平均行為。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 時間開始，代理累計未來回報的一個隨機變量：
許多強化學習算法從過渡元組形式的連續“經驗”中學習，(st ,at ,rt+1 ,st+1 )，其中 st 是 t 時間的狀態，at 是這個狀態中選擇的行動，rt+1 是其后獲得的獎勵，st+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 對實現信息狀態
有利的概率。“策略描述” π = （π1，...，πn） 是所有玩家的策略集合。π-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 代理在自我對戰中生成自己經驗的數據庫。每一個代理將其經驗過渡元組
儲存在一個指定用于強化學習的記憶 MRL 中。代理自己行為的經驗（st，at）的儲存在一個分開的記憶 MSL 中，指定用于監督學習。自我對戰取樣的設定方式，讓代理的強化學習記憶近似一個其他玩家平均策略描述所定義的 MDP 的數據。類似地，代理的監督學習記憶近似代理自己平均策略的數據，可以通過監督分類習得。
3. 神經虛擬自我對戰
神經虛擬自我對戰（NFSP）是 FSP 的 進化版本，引入了多個擴展，例如神經網絡函數近似、蓄水池抽樣、預期動態和一個完全基于代理的方法。NFSP 代理與游戲中其他玩家互動，記住自己游戲轉換的經驗以及自己的行為。NFSP 將這些記憶看做兩個適合深度強化學習和監督分類的數據庫。代理還特別訓練一個神經網絡 FQ ，使用偏離政策的強化學習，從數據庫 MRL 中預測行為值 Q(s, a)。它產生的神經網絡定義代理的近似最優回應策略： β = ε-greedy (FQ)，后者選擇一個概率為 ε 的隨機行為，否則則會選擇一個能夠最優化預測行為值的行為。NFSP 代理訓練一個分開的神經網絡 FS，用監督分類在數據 MSL 上模擬自己過去的行為。這個神經網絡將狀態匹配到行動概率，并定義代理的平均策略 π = FS。游戲中代理從其兩項策略 β 和 π 的混合中選擇自己的行為。
雖然虛擬玩家通常對于對手的平均策略采取最優回應，在連續時間動態虛擬游戲（Shamma & Arslan，2005）中，玩家基于對手的平均正則策略
的短期預測，來選擇最優回應。作者顯示了這項基于游戲的恰當選擇，針對均衡點上虛擬玩家的 η 穩定性。NFSP 使用
作為這項預期動態中使用的導數的離散時間近似。注意，
是常見離散時間虛擬游戲的正則化更新方向。為了讓一個 NFSP 代理計算出近似最優回應 βi，對于其對手的預期平均策略描述
代理迭代性地評估和最大化其行為值
。實現的方法可以是基于和對手的預期策略 δ-i 游戲的經驗，進行偏離策略的強化學習，即，Q-學習或者 DQN。為確保代理的強化學習記憶 MRL 包含這種經驗，NFSP 要求所有代理從
中選擇他們的行為，其中 η ∈ R 被稱為“預期參數”。
虛擬游戲通常追蹤玩家在游戲中已選的正則形式最優回應策略的平均值
。Heinrich 等人（2015）提出使用取樣和機器學習來生成數據，學習正則形式策略拓展形式的凸組合。例如，我們可以生成一組數據
的擴展形式，方法是從整個游戲時間中取樣，在凸組合中使用
與其權重 1/T 成比例。NFSP 使用蓄水池取樣（Vitter，1985；Osborne 等人，2014）來記憶自己平均最優回應的經驗。代理的監督學習記憶 MSL 是一個蓄水池，只有當它遵循近似最優回應策略 β 的時候才增加經驗。NFSP 代理常規性地訓練自己的平均策略網絡 π = FS，與自己存儲在自己監督學習記憶中的平均行為相匹配，例如通過最優化過去行為的日志概率。算法（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，MRL 和 MSL 分別為2M。MRL 的功能是一個環形緩沖器，包含一個最近的經驗。MSL 用蓄水池取樣更新。強化學習率和監督學習率分別設置為為 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 的 ε-貪婪策略，我們將其行為存儲在一個監督學習記憶 MSL 中，并學習其平均行為。這項平均策略不影響 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個具有線性激活的神經元。MRL和MSL的記憶容量分別設定為600k和30m。MRL作為環形緩沖器，包含一個近期經驗。MSL用指數平均的蓄水池取樣（Osborne等人，2014）更新，用最低概率0.25代替MSL中的條目。我們使用沒有強化學習和監督學習趨勢的 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
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
專題
