1
| 本文作者： AI科技評論 | 2016-06-22 10:42 |
6月19日（美國時間）在紐約舉行的國際機(jī)器學(xué)習(xí)大會（ICML）上，來自谷歌、Facebook以及頂尖研究學(xué)府的科學(xué)家們通過論文和講座，分享了最尖端的機(jī)器學(xué)習(xí)研究成果。其中，谷歌DeepMind科學(xué)家David Silver在講座“深度增強(qiáng)學(xué)習(xí)”中分享了深度神經(jīng)網(wǎng)絡(luò)在各項實際應(yīng)用中的算法。雖然David Silver不如DeepMind CEO Demis Hassabis那么為人所知，實際上，他正是DeepMind圍棋團(tuán)隊一直雪藏的主程序員。 
從左到右：David Silver、Demis Hassabis和圍棋冠軍李世石。圖片來源：BI。
David Silver以班級最優(yōu)成績從劍橋大學(xué)畢業(yè)，正是在劍橋他與Demis Hassabis相識，據(jù)稱也正是Hassabis教會了Silver如何下圍棋。畢業(yè)后，Silver成立了游戲公司 Elixir 并擔(dān)任CTO及程序負(fù)責(zé)人，贏得了一系列科技創(chuàng)新獎項。2004年Silver開始攻讀PHD，期間聯(lián)合引入了初代圍棋程序的算法，該算法當(dāng)時在9 x 9的棋盤打贏人類。Silver從DeepMind創(chuàng)立之初便一直擔(dān)任顧問，2013年全職加入團(tuán)隊，2014年谷歌收購了DeepMind。今年3月，DeepMind的人工智能算法AlphaGo在19 x 19的標(biāo)準(zhǔn)棋盤上打贏了人類圍棋冠軍。Hassabis對英國《衛(wèi)報》說：“我們曾經(jīng)幻想著今生可以做這樣的事情（創(chuàng)造強(qiáng)大的AI），所以，我們19歲的自己如果知道了，應(yīng)該會感到安心?！?/p>
Silver此次ICML的講座主要探討應(yīng)用廣泛的增強(qiáng)學(xué)習(xí)技術(shù)。“人工智能的一個主要目標(biāo)，是創(chuàng)造具有通用目標(biāo)的代理，能夠在眾多具有挑戰(zhàn)性的任務(wù)中高效運(yùn)行。為實現(xiàn)這一目標(biāo)，我們需要將增強(qiáng)學(xué)習(xí)（RL）代理與強(qiáng)大、靈活的表征結(jié)合起來。RL的關(guān)鍵概念是利用神經(jīng)網(wǎng)絡(luò)來獲得這種表征的力量。這場講座中，我們將介紹一系列深度神經(jīng)網(wǎng)絡(luò)用于估值函數(shù)、策略或者環(huán)境模型的算法。我們將呈現(xiàn)各個領(lǐng)域內(nèi)最頂尖的研究結(jié)果，包括Atari游戲、3D導(dǎo)航任務(wù)、持續(xù)控制以及圍棋。”
講座中提到，DeepMind的強(qiáng)化學(xué)習(xí)的不只應(yīng)用于Atari游戲、撲克和圍棋，還包括導(dǎo)航領(lǐng)域中的3D世界和迷宮，控制物理系統(tǒng)中如何進(jìn)行操作、走路和游泳等動作，還有在用戶交互層面的推薦、優(yōu)化和個人化等等。
今年8月，Demis Hassabis等人工智能技術(shù)先驅(qū)們將來到雷鋒網(wǎng)“人工智能與機(jī)器人創(chuàng)新大會”。在此，我們?yōu)榇蠹曳窒鞤avid Silver的論文《不完美信息游戲中的深度強(qiáng)化學(xué)習(xí)自我對戰(zhàn)》。本篇論文主要以撲克進(jìn)行實驗，探討深度強(qiáng)化學(xué)習(xí)與普通強(qiáng)化學(xué)習(xí)相比的優(yōu)勢。研究此類游戲不只是可以讓程序打贏人類大師，還可以幫助開發(fā)算法，應(yīng)用于更復(fù)雜的真實世界環(huán)境中，例如機(jī)場和網(wǎng)絡(luò)安全、金融和能源貿(mào)易、交通管制和疏導(dǎo)，幫助人們在不完美的信息和高維度信息狀態(tài)空間中進(jìn)行決策。深度強(qiáng)化學(xué)習(xí)不需要依賴人類專家的原有知識，這解決了游戲的可擴(kuò)展性問題，未來算法可以不依賴成本高昂的人類專家，也不用擔(dān)心受到偏見等非理性因素的影響，就能幫助決策。論文的另一位作者是倫敦大學(xué)學(xué)院的研究學(xué)生 Johannes Heinrich。
論文摘要
許多真實世界應(yīng)用可以描述為不完美信息游戲的擴(kuò)展版本。對于這些挑戰(zhàn)巨大的領(lǐng)域，之前的研究主要集中在計算手工抽象出來的納什均衡。這篇論文中，我們引入第一個可擴(kuò)展的端到端方法，無需預(yù)先具備任何知識，就能學(xué)會模擬納什均衡。我們的方法將虛擬自我對戰(zhàn)與深度強(qiáng)化學(xué)習(xí)結(jié)合起來。當(dāng)應(yīng)用在德州撲克時，神經(jīng)虛擬自我對戰(zhàn)（NFSP）達(dá)到了一種納什均衡，而普通的強(qiáng)化學(xué)習(xí)方法則出現(xiàn)了偏離。在限制德州拿住撲克中（一種真實世界規(guī)模的撲克游戲），NFSP學(xué)會了一種很有競爭力的策略，實現(xiàn)了人類專家的能力和頂尖的方法。
1、簡介
歷史上，游戲一直推動著人工智能和機(jī)器學(xué)習(xí)的進(jìn)步（Samuel, 1959; Tesauro, 1995; Campbell 等人, 2002; Riedmiller 等人, 2009; Gelly 等人, 2012; Bowling 等人, 2015）。游戲理論將游戲定義為一個沖突區(qū)域或者多方的合作（Myerson，1991）。之所以學(xué)習(xí)比較簡單的娛樂游戲，其中一個目的是開發(fā)算法，可以擴(kuò)展到更加復(fù)雜的真實世界游戲，例如機(jī)場和網(wǎng)絡(luò)安全、金融和能源貿(mào)易、交通管制和疏導(dǎo)(Lambert III 等人, 2005; Nevmyvaka 等人, 2006; Bazzan, 2009; Tambe, 2011; Urieli & Stone, 2014; Durkota 等人, 2015)。大部分這些真實世界游戲都需要進(jìn)行決策，而決策基于不完美的信息以及高維度的信息狀態(tài)空間。不幸的是，許多已經(jīng)應(yīng)用到經(jīng)典游戲中的機(jī)器學(xué)習(xí)方法，在信息不完美的游戲中缺少收斂的保證。另一方面，許多游戲理論方法缺少抽取相關(guān)模式、并從數(shù)據(jù)中概況的能力。這讓大型游戲的可擴(kuò)展性有限，除非使用人類專家知識、啟發(fā)式方法和建模來將該領(lǐng)域抽象化至可控的規(guī)模。然而，獲取人類專業(yè)知識競猜需要昂貴的資源和時間。此外，人類很容易出現(xiàn)非理性的決策或者假設(shè)（Selten, 1990；Ariely & Jones，2008）。這讓我們希望開發(fā)算法，端到端地學(xué)習(xí)有用的策略。
這篇論文中我們引入NFSP，一個深度強(qiáng)化學(xué)習(xí)方法，可以學(xué)習(xí)模擬不完美信息游戲的納什均衡。NFSP 代理的學(xué)習(xí)方法是與自己對戰(zhàn)，無需預(yù)先具有明確的知識。技術(shù)上來說，NFSP 利用神經(jīng)網(wǎng)絡(luò)函數(shù)模擬，將虛擬自我對戰(zhàn)（FSP）（Heinrich 等人, 2015）擴(kuò)展并實例化。一個 NFSP 代理由兩個神經(jīng)網(wǎng)絡(luò)和兩種記憶組成。強(qiáng)化學(xué)習(xí)利用與代理同伴一起玩的記憶體驗來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，預(yù)測行為的預(yù)期價值。代理自己行為的經(jīng)驗（st，at）儲存在一個分開的記憶中，一個監(jiān)督學(xué)習(xí)方法利用該記憶來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，預(yù)測代理自己的平均行為。NFSP 代理可以通過從自己的行為的平均、常規(guī)策略和貪婪策略（貪婪策略將預(yù)測的估值最大化）中取樣，從而小心行事。NFSP 模擬虛擬對戰(zhàn)，這是在游戲?qū)W習(xí)中一種流行的游戲理論模型，在一些經(jīng)典游戲中收斂至納什均衡，例如雙玩家零和游戲和多玩家潛在博弈。
我們在一個雙人零和計算機(jī)撲克游戲中實證評估了我們的方法。在這個領(lǐng)域中，目前的游戲理論方法使用啟發(fā)性方法，將游戲抽象至一個可以駕馭的規(guī)模（Zinkevich 等人, 2007; Gilpin 等人, 2007； Johanson 等人，2013）。雖然限制德州拿住撲克（LHE）——一種真實世界規(guī)模的撲克游戲——已經(jīng)可以用目前的計算資源解決（Bowling 等人，2015），大部分其他撲克和真實世界游戲如果不經(jīng)過抽象化便無法觸及。我們的方法不依賴?yán)绯橄蠡蛘咂渌魏蔚念A(yù)先知識。NFSP 代理利用深度強(qiáng)化學(xué)習(xí)來直接從其與游戲互動的經(jīng)驗中學(xué)習(xí)。當(dāng)應(yīng)用在德州撲克上的時候，NFSP 實現(xiàn)了一種納什均衡，而普通的強(qiáng)化學(xué)習(xí)方法出現(xiàn)了偏離。我們還將 NFSP 應(yīng)用到 LHE，直接從原始輸入中學(xué)習(xí)。NFSP 學(xué)會了一種具有競爭力的策略，基于手工抽象化實現(xiàn)了頂尖方法的運(yùn)行效果。
2、背景
在這個部分，我們展現(xiàn)一個對于強(qiáng)化學(xué)習(xí)方法、擴(kuò)展式博弈論表述虛擬自我對戰(zhàn)的簡短概況。如需更加細(xì)節(jié)的闡述，我們推薦讀者閱讀 (Sutton & Barto, 1998), (Myerson, 1991), (Fudenberg, 1998) and (Heinrich 等人, 2015)。
2.1. 強(qiáng)化學(xué)習(xí)（RL）
強(qiáng)化學(xué)習(xí)（Sutton & Barto，1998）代理通常從與環(huán)境的互動中，學(xué)會將預(yù)期的未來獎勵最大化。環(huán)境通常是作為“馬爾可夫決策過程”（MDP）進(jìn)行建模。代理基于策略行動，策略具體說明在MDP的每一個狀態(tài)中，可行行動的分布。代理的目標(biāo)是改善自己的策略，從而最大化其收獲，是從 t 時間開始，代理累計未來回報的一個隨機(jī)變量：
許多強(qiáng)化學(xué)習(xí)算法從過渡元組形式的連續(xù)“經(jīng)驗”中學(xué)習(xí)，(st ,at ,rt+1 ,st+1 )，其中 st 是 t 時間的狀態(tài)，at 是這個狀態(tài)中選擇的行動，rt+1 是其后獲得的獎勵，st+1 是代理過渡進(jìn)入的下一個狀態(tài)。一個普遍的目標(biāo)是“學(xué)習(xí)行動價值函數(shù)”，
，定義為在 s 狀態(tài)、遵循 π 策略、采取 a 行為后預(yù)計獲得的獎勵。如果代理學(xué)會自己正在遵循的策略，那么代理的學(xué)習(xí)是“符合策略”的。在“偏離策略”的情況下，代理從其他代理的經(jīng)驗中學(xué)習(xí)，或者學(xué)會一個其他的策略，例如一個以前的策略。
Q-學(xué)習(xí)（Watkins & Dayan，1992）是一種流行的偏離策略強(qiáng)化學(xué)習(xí)方法。它學(xué)會貪婪策略，這在每一個狀態(tài)下采取最高預(yù)估值的行動。通過將偏離政策強(qiáng)化學(xué)習(xí)應(yīng)用到各自的過度元組，從而將過往的經(jīng)驗儲存和回放，這被稱為經(jīng)驗回放（Lin，1992）。擬合Q值迭代（FQI）（Ernst 等人, 2005）是一種批量學(xué)習(xí)方法，用Q-學(xué)習(xí)來回放經(jīng)驗。神經(jīng)擬合Q值迭代（NFQ）（Riedmiller，2005）和深度Q網(wǎng)絡(luò)（DQN）（Mnih 等人，2015）是FQI 的擴(kuò)展，使用分別帶有批量和在線更新的神經(jīng)網(wǎng)絡(luò)函數(shù)近似。
2.2. 擴(kuò)展式博弈論表述
擴(kuò)展式博弈論表述是一種涉及多個玩家的連續(xù)互動模型。假設(shè)玩家為理性的，每個玩家的目標(biāo)是最大化自己在游戲中的收獲。在不完美信息游戲中，每個玩家至觀察到各自的“信息狀態(tài)”，換句話說，在撲克游戲中，一個玩家只知道他自己的卡片，不知道其他玩家的卡片。每一個玩家選擇一個“行為策略”，將信息狀態(tài)匹配到可選行動的概率分布中。我們假設(shè)具有“完美回想能力”的游戲，即，每個玩家目前的信息狀態(tài)
包含玩家信息狀態(tài)和行動的數(shù)列
，這個數(shù)列將玩家?guī)肽壳暗男畔顟B(tài)?！皩崿F(xiàn)概率”（Von Stengel，1996）
決定玩家 i 行為策略 πi 對實現(xiàn)信息狀態(tài)
有利的概率?！安呗悦枋觥?π = （π1，...，πn） 是所有玩家的策略集合。π-i 指的是， π 中除了 πi 的所有策略。當(dāng)給出一個固定的策略描述 π-i，基于 π-i，玩家 i 實現(xiàn)最優(yōu)回報表現(xiàn)的策略稱為“最優(yōu)回應(yīng)”。一個近似或者 ε-最佳回應(yīng)，是不超過 ε 的次優(yōu)回應(yīng)。“納什均衡”是一種策略描述，其中每一個玩家的策略對于其他策略來說是一種最優(yōu)回應(yīng)。同樣的，一個近似或者 ε-納什均衡是一種 ε-最優(yōu)的回應(yīng)。在納什均衡中，沒有哪個玩家在偏離策略的時候能有收獲。因此，納什均衡可以作為一個理性自我對戰(zhàn)學(xué)習(xí)的定點。實際上，納什均衡是唯一一個理性代理有望在自我對戰(zhàn)中收斂的策略描述（Bowie & Veloso，2001）。
2.3. 虛擬自我對戰(zhàn)
“虛擬對戰(zhàn)”（Brown，1951）是一個從自我對戰(zhàn)中學(xué)習(xí)的游戲理論模型。虛擬玩家選擇對應(yīng)對手平均行為的最優(yōu)回應(yīng)。虛擬玩家的平均策略在特定游戲類別中收斂于納什均衡，例如，雙玩家的零和游戲和多玩家潛在博弈(Robinson, 1951; Monderer & Shapley, 1996)。Leslie & Collins （2006）引入了概括化的弱化虛擬對戰(zhàn)，具有與普通虛擬對戰(zhàn)相似的收斂保證，但是允許近似最優(yōu)回應(yīng)和擾動平均策略更新，使其特別適合機(jī)器學(xué)習(xí)。
虛擬對戰(zhàn)通常以正則形式定義，這比擴(kuò)展式博弈論表述要低效得多。Heinrich 等人 （2015） 引入了“全寬度擴(kuò)展式虛擬對戰(zhàn)”（XFP），讓虛擬玩家可以行為主義地、擴(kuò)展式地更新策略，這造成了線性時間和空間的復(fù)雜度。一個關(guān)鍵結(jié)論是，對于一個正則形式策略的凸組合，
我們可以獲得一個等同于實現(xiàn)的行為主義策略 δ，方法是將其設(shè)定為與對應(yīng)的實現(xiàn)概率凸組合成比例，
其中
是在信息狀態(tài) s 中策略的正則化常數(shù)。除了定義行為策略中虛擬玩家的全寬度平均策略更新，方程（1）規(guī)定了一種從此類策略的凸組合數(shù)據(jù)庫中取樣的方法。Heinrich 等人（2015）引入了“虛擬自我對戰(zhàn)”（FSP），一種基于樣本和機(jī)器學(xué)習(xí)類別的算法，可以近似 XFP。FSP 分別用強(qiáng)化和監(jiān)督學(xué)習(xí)代替了最優(yōu)回應(yīng)計算和平均策略更新。尤為重要的是，F(xiàn)SP 代理在自我對戰(zhàn)中生成自己經(jīng)驗的數(shù)據(jù)庫。每一個代理將其經(jīng)驗過渡元組
儲存在一個指定用于強(qiáng)化學(xué)習(xí)的記憶 MRL 中。代理自己行為的經(jīng)驗（st，at）的儲存在一個分開的記憶 MSL 中，指定用于監(jiān)督學(xué)習(xí)。自我對戰(zhàn)取樣的設(shè)定方式，讓代理的強(qiáng)化學(xué)習(xí)記憶近似一個其他玩家平均策略描述所定義的 MDP 的數(shù)據(jù)。類似地，代理的監(jiān)督學(xué)習(xí)記憶近似代理自己平均策略的數(shù)據(jù)，可以通過監(jiān)督分類習(xí)得。
3. 神經(jīng)虛擬自我對戰(zhàn)
神經(jīng)虛擬自我對戰(zhàn)（NFSP）是 FSP 的 進(jìn)化版本，引入了多個擴(kuò)展，例如神經(jīng)網(wǎng)絡(luò)函數(shù)近似、蓄水池抽樣、預(yù)期動態(tài)和一個完全基于代理的方法。NFSP 代理與游戲中其他玩家互動，記住自己游戲轉(zhuǎn)換的經(jīng)驗以及自己的行為。NFSP 將這些記憶看做兩個適合深度強(qiáng)化學(xué)習(xí)和監(jiān)督分類的數(shù)據(jù)庫。代理還特別訓(xùn)練一個神經(jīng)網(wǎng)絡(luò) FQ ，使用偏離政策的強(qiáng)化學(xué)習(xí)，從數(shù)據(jù)庫 MRL 中預(yù)測行為值 Q(s, a)。它產(chǎn)生的神經(jīng)網(wǎng)絡(luò)定義代理的近似最優(yōu)回應(yīng)策略： β = ε-greedy (FQ)，后者選擇一個概率為 ε 的隨機(jī)行為，否則則會選擇一個能夠最優(yōu)化預(yù)測行為值的行為。NFSP 代理訓(xùn)練一個分開的神經(jīng)網(wǎng)絡(luò) FS，用監(jiān)督分類在數(shù)據(jù) MSL 上模擬自己過去的行為。這個神經(jīng)網(wǎng)絡(luò)將狀態(tài)匹配到行動概率，并定義代理的平均策略 π = FS。游戲中代理從其兩項策略 β 和 π 的混合中選擇自己的行為。
雖然虛擬玩家通常對于對手的平均策略采取最優(yōu)回應(yīng)，在連續(xù)時間動態(tài)虛擬游戲（Shamma & Arslan，2005）中，玩家基于對手的平均正則策略
的短期預(yù)測，來選擇最優(yōu)回應(yīng)。作者顯示了這項基于游戲的恰當(dāng)選擇，針對均衡點上虛擬玩家的 η 穩(wěn)定性。NFSP 使用
作為這項預(yù)期動態(tài)中使用的導(dǎo)數(shù)的離散時間近似。注意，
是常見離散時間虛擬游戲的正則化更新方向。為了讓一個 NFSP 代理計算出近似最優(yōu)回應(yīng) βi，對于其對手的預(yù)期平均策略描述
代理迭代性地評估和最大化其行為值
。實現(xiàn)的方法可以是基于和對手的預(yù)期策略 δ-i 游戲的經(jīng)驗，進(jìn)行偏離策略的強(qiáng)化學(xué)習(xí)，即，Q-學(xué)習(xí)或者 DQN。為確保代理的強(qiáng)化學(xué)習(xí)記憶 MRL 包含這種經(jīng)驗，NFSP 要求所有代理從
中選擇他們的行為，其中 η ∈ R 被稱為“預(yù)期參數(shù)”。
虛擬游戲通常追蹤玩家在游戲中已選的正則形式最優(yōu)回應(yīng)策略的平均值
。Heinrich 等人（2015）提出使用取樣和機(jī)器學(xué)習(xí)來生成數(shù)據(jù)，學(xué)習(xí)正則形式策略拓展形式的凸組合。例如，我們可以生成一組數(shù)據(jù)
的擴(kuò)展形式，方法是從整個游戲時間中取樣，在凸組合中使用
與其權(quán)重 1/T 成比例。NFSP 使用蓄水池取樣（Vitter，1985；Osborne 等人，2014）來記憶自己平均最優(yōu)回應(yīng)的經(jīng)驗。代理的監(jiān)督學(xué)習(xí)記憶 MSL 是一個蓄水池，只有當(dāng)它遵循近似最優(yōu)回應(yīng)策略 β 的時候才增加經(jīng)驗。NFSP 代理常規(guī)性地訓(xùn)練自己的平均策略網(wǎng)絡(luò) π = FS，與自己存儲在自己監(jiān)督學(xué)習(xí)記憶中的平均行為相匹配，例如通過最優(yōu)化過去行為的日志概率。算法（1）呈現(xiàn)了使用 DQN 進(jìn)行強(qiáng)化學(xué)習(xí)的 NFSP。
算法1：使用 DQN 進(jìn)行強(qiáng)化學(xué)習(xí)的 NFSP。
4、實驗
我們在德州撲克（Southey 等人，2005）和限制德州拿住撲克中評估 NFSP 和相關(guān)算法。我們大部分的實驗學(xué)會策略描述的可利用性。在一個雙玩家零和游戲中，一項策略描述的可利用性定義為，最優(yōu)回應(yīng)描述可以獲得的期望平均回報。2δ 的可利用性至少是一個 δ-納什均衡。
4.1. XFP 的強(qiáng)度
要理解函數(shù)近似如何與 FSP 互動，我們以一些簡單實驗開始，模擬近似，并從全寬度算法 XFP 中獲取錯誤樣本。首先，我們探索當(dāng)用一個靠近梯度下降的增量平均過程代替 XFP 中使用的完美平均，會有什么結(jié)果。然后，我們探索當(dāng)用一個帶 ε 誤差的近似代替 XFP 中使用的同一個查表法，會有什么結(jié)果。
圖1：定步長對于 LHE 游戲中全寬度虛擬對戰(zhàn)表現(xiàn)的影響。
圖1顯示了帶有默認(rèn)值 1/T 和策略更新定步長的 XFP 的表現(xiàn)。我們看見漸進(jìn)提高了，但是針對更小步長的最初表現(xiàn)變低了。對于定步長，表現(xiàn)似乎是達(dá)到平穩(wěn)、而非偏離。使用蓄水池取樣可以實現(xiàn)高效的定步長，為 1/T。但是，結(jié)果顯示指數(shù)平均的蓄水池取樣同樣可行，因為指數(shù)平均過往記憶會近似對應(yīng)于使用一個定步長。
定步長為1的 XFP等同于一個全寬度迭代最優(yōu)回應(yīng)算法。雖然在有限完美信息雙玩家零和游戲中這個算法收斂于納什均衡，結(jié)果顯示，在不完美信息中這就不能成立了。Yakovenko 等人（2016）引入的撲克-CNN 算法存儲少量過往策略，基于這些策略迭代性地計算新策略。代替那個集合中的策略類似于更新一個具有很大定步長的平均策略。這有可能導(dǎo)致類似圖1中顯示的問題。
圖2：當(dāng) LHE 游戲在最優(yōu)回應(yīng)計算中加入均勻隨機(jī)噪音，XFP 的表現(xiàn)。
我們的 NFSP 代理在他們的策略中加入隨機(jī)探索，使用噪音隨機(jī)梯度來學(xué)習(xí)行動價值。因此，我們研究了在最優(yōu)回應(yīng)計算中加入隨機(jī)噪音的影響，XFP 通過動態(tài)編程來運(yùn)行最優(yōu)回應(yīng)計算。在逆向歸納法的每一步，我們傳回一個帶有概率 ε 的均勻隨機(jī)行動的值，否則則傳回最佳行動的值。圖2顯示出，增加噪音時表現(xiàn)清一色地下降。但是，表現(xiàn)仍保持穩(wěn)定，對于所有噪音等級來說都持續(xù)改善。
4.2. NFSP的收斂
我們實證研究了在 LHE 游戲中 NFSP 收斂至納什均衡。我們還研究了去除或改變一些 NFSP 的組成部分是否會打破收斂。
我們的一項目標(biāo)，是將對過往知識的依賴性最小化。因此，我們希望定義一個撲克游戲中信息狀態(tài)的目標(biāo)編碼。與其他計算機(jī)撲克的研究不同（Zinkevich 等人, 2007; Gilpin 等人, 2007; Johanson 等人, 2013），我們不進(jìn)行任何高層級特征的工程。撲克游戲通常包含很多輪。在每一輪，新卡片發(fā)給玩家。我們將每一輪的卡片用一個“n 個中的第 k 個”編碼來表征，例如，當(dāng) LHE 有一疊52張卡片，第二輪發(fā)出三張新卡。這樣，這一輪的編碼就使用長度為52的矢量和三個設(shè)為1的元素，其余元素設(shè)為0。在 LHE 撲克游戲中，玩家通常有3種可選的行為，即 {棄牌、根注、加注} 。注意，根據(jù)情景而定，跟注和加注可以分別稱為“讓牌”和“押注”。押注限制在每輪固定數(shù)量的加注之內(nèi)。這樣，我們可以將押注歷史表征為一個4維度的張量，即 {玩家、輪數(shù)、加注數(shù)量、采取行動} 。也就是說，單挑 LHE 游戲中包含2個玩家、4輪、每輪0-4次加注和3個行動。這樣，我們可以將一個 LHE 押注歷史表征為 2 x 4 x 5 x 3 張量。在單挑游戲中，我們不需要編碼棄牌行為，因為如果一方放棄游戲就結(jié)束了。這樣，我們可以將4維張量扁平化，成為一個長度為80的矢量。將4輪的卡牌都聯(lián)接起來，我們就可以將一個 LHE 的信息狀態(tài)編碼為一個長度為288的矢量。相似地，一個 LHE 的信息狀態(tài)可以編碼為一個長為30的矢量，因其包含6種卡片以及3個重復(fù)卡片、2輪、每輪0-2次加注以及3次行動。
要實現(xiàn) LHE 中的學(xué)習(xí)，我們將 NFSP 手動校準(zhǔn)為一個完全聯(lián)接的神經(jīng)網(wǎng)絡(luò)，帶有1個隱含層、包含63個神經(jīng)元和線性激活。然后，我們重復(fù)各種具有相同參數(shù)的神經(jīng)架構(gòu)的實驗。我們特別設(shè)置記憶大小為200K，MRL 和 MSL 分別為2M。MRL 的功能是一個環(huán)形緩沖器，包含一個最近的經(jīng)驗。MSL 用蓄水池取樣更新。強(qiáng)化學(xué)習(xí)率和監(jiān)督學(xué)習(xí)率分別設(shè)置為為 0.1 和 0.005，兩者都使用隨機(jī)梯度下降（SGD），沒有神經(jīng)網(wǎng)絡(luò)隨機(jī)最優(yōu)化的趨勢。每一個代理進(jìn)行3次隨機(jī)梯度更新，游戲中每128步、每個神經(jīng)網(wǎng)絡(luò)中最小批次數(shù)量為128。DQN 算法的目標(biāo)網(wǎng)絡(luò)每300次更新就重新調(diào)整。NFSP 的預(yù)期參數(shù)設(shè)置為 η = 0.1。ε-貪婪策略的探索從 0.06 開始，下降到0，與迭代次數(shù)的逆平方根成比例。
圖3：LHE 游戲中的 NFSP 的學(xué)習(xí)表現(xiàn)。
圖3顯示了對于各種網(wǎng)絡(luò)架構(gòu)， NFSP 趨近納什均衡。我們觀察到隨著網(wǎng)絡(luò)數(shù)量的增加，表現(xiàn)也清一色地增加。NFSP 實現(xiàn)了0.06的利用性，而全寬度 XFP 通常在1000輪全寬度迭代才能實現(xiàn)。
圖4：通過去除必須的 NFSP 組成部分，打破 LHE 游戲中的學(xué)習(xí)表現(xiàn)。
為了研究 NSFP 各種組成部分的相關(guān)度，也就是說，蓄水池取樣和期望動態(tài)，我們進(jìn)行了一個分離他們效果的實驗。圖4顯示，這些變動導(dǎo)致表現(xiàn)下降。特別是使用固定大小的滑動窗口來儲存代理自己行為的經(jīng)驗，會導(dǎo)致偏離。對于一個0.5的高期望參數(shù)，NFSP 的表現(xiàn)進(jìn)入了停滯。最終，使用指數(shù)平均蓄水池取樣進(jìn)行監(jiān)督學(xué)習(xí)記憶更新，導(dǎo)致了噪音表現(xiàn)。
4.3. 與DQN比較
之前已有多個穩(wěn)定算法提出過用于深度強(qiáng)化學(xué)習(xí)，尤其是 DQN 算法（Mnih 等人，2015）。但是，這些算法的實證穩(wěn)定性之前只在單一代理、完美（或接近完美）信息 MDP 中建立過。這里，我們研究與 NFSP 相比，在多代理、信息不完美游戲中的 DQN 穩(wěn)定性。
圖5：在 LHE 游戲中比較 DQN 的表現(xiàn)。
DQN 學(xué)會一種決定論的貪婪策略。這在 MDP 中足夠進(jìn)行最優(yōu)行為，算法就是為此而設(shè)計的。不過，在信息不完美游戲通常要求最優(yōu)行為的隨機(jī)策略。這樣，除了 DQN 的 ε-貪婪策略，我們將其行為存儲在一個監(jiān)督學(xué)習(xí)記憶 MSL 中，并學(xué)習(xí)其平均行為。這項平均策略不影響 DQN 的實施行為，因為它從來不會被執(zhí)行。我們通過使用帶有期望參數(shù) η = 1 的 NFSP，來實施這個 DQN 變量。我們將 DQN 大部分參數(shù)設(shè)置為與之前部分實驗中的 NFSP 相同。這是為了讓監(jiān)督學(xué)習(xí)參數(shù)不直接影響 DQN 的表現(xiàn)。我們用以下所有參數(shù)的組合來訓(xùn)練 DQN：學(xué)習(xí)比例 {0.2,0.1,0.05}，衰減探索開始于 {0.06,012}，增強(qiáng)學(xué)習(xí)記憶 {2m蓄水池，2m滑動窗口}。然后，我們選擇 DQN 表現(xiàn)最優(yōu)的結(jié)果，將其與之前部分實驗中的 NFSP 表現(xiàn)相比較。DQN 在學(xué)習(xí)比例為0.1、探索從0.12開始和滑動窗口記憶為2m的時候，實現(xiàn)其最佳表現(xiàn)結(jié)果。
圖5顯示，DQN的決定論策略是高度可利用的，這是可以預(yù)見的，因為信息不完美游戲通常要求隨機(jī)策略。DQN 的平均行為也沒有趨近納什均衡。這值得注意，因為 DQN 將其經(jīng)驗存儲在一個回放記憶中，因此會高效地學(xué)會對手的平均行為，只要其回放記憶足夠大，可以對它進(jìn)行追蹤。這與虛擬對戰(zhàn)很像。但是，因為 DQN 代理在自我對戰(zhàn)中使用 ε-貪婪策略，它們的經(jīng)驗隨著時間高度相關(guān)，集中在一個狀態(tài)子集。我們相信這是 NFSP 在我們試驗中表現(xiàn)更好的主要原因。NFSP 代理在自我對戰(zhàn)中使用一種改變更慢的平均策略。這樣，它們的經(jīng)驗改變更慢，導(dǎo)致它們的記憶中包含更穩(wěn)定的數(shù)據(jù)分布。這會幫助它們訓(xùn)練神經(jīng)網(wǎng)絡(luò)，并適應(yīng)彼此。其他常見的強(qiáng)化學(xué)習(xí)方法都被證明在撲克游戲中具有類似的停滯表現(xiàn)（Ponsen 等人,2011; Heinrich & Silver, 2015)。
4.4. 限制德州拿住 （LHE）
我們將 NFSP 應(yīng)用于非常流行的 LHE 游戲。2008年，一個計算機(jī)程序第一次在公開競賽中打敗了人類 LHE 玩家，從此現(xiàn)代計算機(jī)代理被廣泛認(rèn)為實現(xiàn)了超人表現(xiàn)（Newall，2013）。這種游戲由 Bowling等人（2015）根本上解決。我們用 SmooCT 來評估我們的代理，這是一個在2014年年度計算機(jī)撲克競賽（ACPC）中獲得了三項銀牌的 Smooth UCT （Heinrich & Silver，2015）代理。學(xué)習(xí)表現(xiàn)以 mbb/h 來衡量，換句話說，在每一手最開始的時候玩家大盲注的千分之一。
我們手動校準(zhǔn)了 NFSP，嘗試了9種配置。我們用以下的參數(shù)實現(xiàn)了最優(yōu)表現(xiàn)。神經(jīng)網(wǎng)絡(luò)完全聯(lián)接，有4個隱藏層，分別有1024、512、1024和512個具有線性激活的神經(jīng)元。MRL和MSL的記憶容量分別設(shè)定為600k和30m。MRL作為環(huán)形緩沖器，包含一個近期經(jīng)驗。MSL用指數(shù)平均的蓄水池取樣（Osborne等人，2014）更新，用最低概率0.25代替MSL中的條目。我們使用沒有強(qiáng)化學(xué)習(xí)和監(jiān)督學(xué)習(xí)趨勢的 SGD，將學(xué)習(xí)比例分別設(shè)置為0.1和0.01。每一個代理進(jìn)行2次隨機(jī)梯度更新，游戲中每256步、每個網(wǎng)絡(luò)的最小批次大小為256。DQN 算法的目標(biāo)網(wǎng)絡(luò)是每1000次更新就重新調(diào)整。NFSP的預(yù)期參數(shù)設(shè)置為 η = 0.1。ε-貪婪策略的探索從0.08開始，衰退至0，比在 LHE 中更慢。除了 NFSP 的主要平均策略描述，我們還評估了最優(yōu)回應(yīng)和貪婪平均策略，它們決定論地分別選擇最大化預(yù)期行動值或者概率的行動。
圖6：與 SmooCT 對戰(zhàn)的表現(xiàn)。每次評估的標(biāo)準(zhǔn)誤差小于 10 mbb/h。
為了在單挑 LHE 中提供一些勝率的直覺，永遠(yuǎn)棄牌的玩家會損失 750 mbb/h，人類專家玩家在在線高風(fēng)險游戲中通常達(dá)到40-60 mbb/h 的預(yù)期勝率。類似的，在2014 ACPC中，表現(xiàn)前一半的計算機(jī)代理自己實現(xiàn)了最高 60 mbb/h 的預(yù)期勝率。在訓(xùn)練中，我們基于 SmooCT 周期性地評估 NFSP 的表現(xiàn)，每一個都玩25000手。圖6呈現(xiàn)了 NFSP 的學(xué)習(xí)表現(xiàn)。NFSP 的平均和貪婪平均策略描述顯示了一個穩(wěn)定、相對統(tǒng)一的表現(xiàn)改善，并分別實現(xiàn)了大約-50 mbb/h 和-20 mbb/h 的勝率。最優(yōu)回應(yīng)策略描述在每次表現(xiàn)中體現(xiàn)了更多的噪音，大部分在 -50 到 0 mbb/h 的范圍內(nèi)。我們還基于2014 ACPC中的前三名，評估了最終貪婪平均策略。表格1呈現(xiàn)了結(jié)果。
表格1
5. 相關(guān)研究
依賴人類專家知識可能會很昂貴，而且如果知識是次優(yōu)的，可能會受到人類偏見和限制的影響。但是，許多已經(jīng)應(yīng)用在游戲中的方法都依賴人類專家的知識。深藍(lán)在象棋中使用人類制造的評估函數(shù)（Campbell等人，2002）。在計算機(jī)圍棋中，Maddison等人（2015）和Clark & Storkey （2015）用人類專家下棋的數(shù)據(jù)來訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)。在計算機(jī)撲克中，目前的游戲理論方法使用啟發(fā)式方法來理解卡片強(qiáng)度，從而將游戲抽象至可以駕馭的規(guī)模(Zinkevich等人, 2007; Gilpin等人, 2007; Johanson等人,2013)。Waugh等人（2015）最近將其中一種方法與函數(shù)近似相結(jié)合。然而，他們的全寬度算法必須暗中推導(dǎo)每一次迭代中的所有信息狀態(tài)，這在大的領(lǐng)域來說過于昂貴。與之相比，NFSP 專注在基于樣本的強(qiáng)化學(xué)習(xí)設(shè)定，其中游戲的狀態(tài)不需要全部列舉，學(xué)習(xí)者甚至不需要有一個游戲動態(tài)的模型。
許多游戲中的成功應(yīng)用依賴本地搜索（Campbell等人，2002；Browne等人，2012）。本地搜索算法在游戲中，實時、有效地計劃決策，例如通過蒙特卡洛模擬或者有限深度逆向歸納法。但是，常見的基于模擬的本地搜索算法應(yīng)用在信息不完美的撲克游戲中時，已經(jīng)證實會偏離（Ponsen等人，2011；Heinrich & Silver，2015）。而且，即便是游戲理論方法在信息不完美游戲中進(jìn)行本地規(guī)劃時，通常也沒法實現(xiàn)不可利用的行為（Burch等人，2014；Ganzfried & Sandholm，2015；Lisy等人,2015）。本地搜索的另一個問題是，如果沒有注入原有知識來引導(dǎo)搜索，實時運(yùn)行的成本有可能非常巨大。這引發(fā)了如何獲得這種原有知識的問題。Silver等人（2016）用人類專家數(shù)據(jù)訓(xùn)練了卷積神經(jīng)網(wǎng)絡(luò)，然后使用一個自我對戰(zhàn)強(qiáng)化學(xué)習(xí)過程來進(jìn)一步優(yōu)化這些網(wǎng)絡(luò)。通過使用這項神經(jīng)網(wǎng)絡(luò)來引導(dǎo)高性能本地搜索，他們戰(zhàn)勝了圍棋大師。在這項研究中，我們不使用任何實時本地搜索來評估我們的代理。如果可以開發(fā)針對信息不完美游戲的本地搜索方法，NFSP 訓(xùn)練的策略可以是引導(dǎo)搜索的一個好選擇。
納什均衡是理性代理可以在自我對戰(zhàn)中有望收斂的唯一策略描述（Bowling & Veloso，2001）。TD-Gammon（Tesauro，1995）是一個世界級別的西洋雙陸棋代理，它的主要組成部分是一個用自我對戰(zhàn)強(qiáng)化學(xué)習(xí)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)。雖然其算法基于臨時差異學(xué)習(xí)，在雙玩家、信息完美的零和游戲中是可行的，可是在不完美游戲中總體來說不能收斂。DQN（Mnih等人，2015）結(jié)合了臨時差異學(xué)習(xí)、經(jīng)驗回放和深度神經(jīng)網(wǎng)絡(luò)函數(shù)近似。它在大部分Atari游戲中實現(xiàn)了人類等級的表現(xiàn)，從原始感覺輸入中學(xué)習(xí)。但是，這些Atari游戲的設(shè)定是單一代理環(huán)境，潛在對手固定，并由Atari模擬器控制。我們的實驗顯示，DQN 代理在 LHE 游戲中沒法實現(xiàn)納什均衡，其中玩家允許進(jìn)行動態(tài)適應(yīng)。Yakovenko等人（2016）在計算機(jī)撲克對戰(zhàn)中訓(xùn)練了深度神經(jīng)網(wǎng)絡(luò)，包括兩個在人類中非常流行的撲克游戲。他們的網(wǎng)絡(luò)與基于啟發(fā)式方法和簡單的計算機(jī)程相比表現(xiàn)更強(qiáng)。人類專家玩家可以超越他們的代理，雖然其樣本大小不具有統(tǒng)計學(xué)意義。他們的方法在現(xiàn)實或理論中是否會收斂是個未知數(shù)。與之對比，我們實證證明了 NFSP 在 LHE 游戲中收斂至近似納什均衡。而且，我們的方法是有原則的，是基于擴(kuò)展式博弈論表述中的虛擬對戰(zhàn)理論。
6、結(jié)論
我們引入了 NFSP，第一個端到端深度強(qiáng)化學(xué)習(xí)方法，在不完美信息游戲中以自我對戰(zhàn)學(xué)習(xí)近似納什均衡。NFSP 解決三個問題。
首先，NFSP 代理學(xué)習(xí)不需要具備原有知識。
第二，他們不依賴于實時本地搜索。
第三，他們在自我對戰(zhàn)中收斂至近似納什均衡。我們的實證結(jié)果提供了以下收獲：虛擬游戲的表現(xiàn)隨著各種近似錯誤優(yōu)雅地衰退；NFSP 在小撲克游戲中能可靠地收斂于近似納什均衡，而 DQN 的貪婪和平均策略不能；NFSP 在真實世界規(guī)模的信息不完美游戲中，從零學(xué)會一種有競爭力的策略，不需要使用明確的原有知識。
在這項研究中，我們專注于信息不完美的雙玩家零和游戲。但是，虛擬對戰(zhàn)在合作性的潛在游戲中，也能保證收斂至納什均衡。因此我們可以看到，NFSP 也可以成功應(yīng)用于這些游戲。而且，連續(xù)動作強(qiáng)化學(xué)習(xí)的最近進(jìn)展（Lillicrap等人，2015）可以讓 NFSP 應(yīng)用于連續(xù)動作游戲，這是目前的游戲理論方法沒法直接解決的問題。
via ICML
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
