[[211446]]

本文介紹了來(lái)自倫敦大學(xué)學(xué)院（UCL）Thomas Anthony、Zheng Tian 與 David Barber 的深度學(xué)習(xí)與樹搜索研究。該論文已被 NIPS 2017 大會(huì)接收。

二元處理機(jī)制理論

「二元處理機(jī)制」認(rèn)為，人類的推理包括兩種不同種類的思考方法。如下圖所示，系統(tǒng) 1 是一個(gè)快速的、無(wú)意識(shí)的、自動(dòng)化的思考模式，它也被稱為直覺。系統(tǒng) 2 是一個(gè)慢速的、有意識(shí)的、顯式的、基于規(guī)則的推理模式，它被認(rèn)為是一種進(jìn)化上的最新進(jìn)展。

圖片出處：https://www.slideshare.net/AshDonaldson/behaviour-design-predicting-irrational-decisions

在學(xué)習(xí)完成某項(xiàng)具有挑戰(zhàn)性的規(guī)劃任務(wù)（例如棋牌類游戲）時(shí)，人類會(huì)同時(shí)運(yùn)用這兩種處理方式：準(zhǔn)確的直覺可以快速地選擇有利路線，這使我們慢速的分析推理更加高效。而持續(xù)的深入學(xué)習(xí)又能逐漸提升直覺，從而使更準(zhǔn)確的直覺回饋到更強(qiáng)大的分析中，這就形成了一個(gè)閉合的學(xué)習(xí)回路。換言之，人類是通過(guò)既快又慢的思考方式來(lái)學(xué)習(xí)的 [1]。

目前的深度強(qiáng)化學(xué)習(xí)存在什么問(wèn)題？

在當(dāng)前的深度強(qiáng)化學(xué)習(xí)算法中，例如策略梯度（Policy Gradient）和 DQN3[3], 神經(jīng)網(wǎng)絡(luò)在選擇動(dòng)作的時(shí)候沒(méi)有任何前瞻性；這個(gè)和系統(tǒng) 1 類似。與人類直覺不同的是，這些強(qiáng)化學(xué)習(xí)算法在訓(xùn)練的過(guò)程中并沒(méi)有一個(gè)「系統(tǒng) 2」來(lái)給它們推薦更好的策略。

AlphaGo 這類 AI 算法的一個(gè)缺陷之處在于，它們使用了人類專業(yè)玩家的數(shù)據(jù)庫(kù) [4]。在訓(xùn)練的初始階段，強(qiáng)化學(xué)習(xí)智能體會(huì)模仿人類專家的行動(dòng)—而只有經(jīng)歷這樣的初始階段，它們才會(huì)開始潛在地學(xué)習(xí)更強(qiáng)大的超人類玩法。但是這種算法從某種程度而言并不令人滿意，因?yàn)樗鼈兛赡軙?huì)嚴(yán)重偏向某人類玩家的風(fēng)格，從而忽視潛在的更好策略。同時(shí)，人類專家數(shù)據(jù)庫(kù)在游戲領(lǐng)域中或許可得，而如果我們想要在其他情況下訓(xùn)練出一個(gè) AI 機(jī)器，也許我們并沒(méi)有這種可用的數(shù)據(jù)庫(kù)。因此，從零開始訓(xùn)練出一個(gè)最先進(jìn)的棋牌游戲玩家對(duì) AI 而言是一項(xiàng)主要挑戰(zhàn)。

專家迭代 (ExIt)

專家迭代（ExIt）是我們?cè)?2017 年 5 月介紹的一個(gè)通用學(xué)習(xí)框架。它能夠在不需要模仿人類策略的情況下就訓(xùn)練出強(qiáng)大的 AI 機(jī)器。

ExIt 可被視為模仿學(xué)習(xí)（Imitation Learning）的延伸，它可以擴(kuò)展至連頂尖人類專家也無(wú)法達(dá)到滿意表現(xiàn)的領(lǐng)域中。在標(biāo)準(zhǔn)的模仿學(xué)習(xí)中，學(xué)徒被訓(xùn)練以模仿專家的行為。ExIt 則將此方法延伸至一種迭代學(xué)習(xí)過(guò)程。在每一次迭代中，我們都會(huì)執(zhí)行一次專家提升（expert improvement）步驟，在這個(gè)過(guò)程中我們會(huì)依靠（快速的）學(xué)徒策略來(lái)改善（相對(duì)較慢的）專家的表現(xiàn)。

ExIt

象棋這類棋類游戲或許可以幫助我們更直觀地了解這個(gè)概念。在這類游戲中專家就類似于慢手下棋的棋手（每一步都花好多時(shí)間來(lái)決策），而學(xué)徒就像在下快棋（每一步都花很少時(shí)間決定如何走）。

一份獨(dú)立的研究顯示，玩家會(huì)在同一個(gè)位置考慮多個(gè)可能的行動(dòng)，深入（緩慢）地思考每一步可能的行動(dòng)。她會(huì)分析在當(dāng)前位置哪幾手棋會(huì)成功而哪幾手棋會(huì)失敗。當(dāng)在未來(lái)遇到相似的棋局時(shí)，她之前的學(xué)習(xí)所培養(yǎng)出來(lái)的直覺就會(huì)迅速告訴她哪幾手棋會(huì)可能更好。這樣即使在快棋設(shè)置下，她依然可以表現(xiàn)不俗。她的直覺就來(lái)源于她模仿自己之前通過(guò)深度思考計(jì)算而獲得的強(qiáng)大策略。人類不可能僅僅通過(guò)快棋而變成卓越的棋手，更深入的研究是學(xué)習(xí)過(guò)程中必需的部分。

對(duì)人工智能游戲機(jī)器而言，這種模仿是可以實(shí)現(xiàn)的，例如，將一個(gè)神經(jīng)網(wǎng)絡(luò)擬合到另一個(gè)「機(jī)器專家」的某一步棋。在短時(shí)間之內(nèi)通過(guò)模仿目前所見到的專家的行動(dòng)，學(xué)徒就可以學(xué)習(xí)到一個(gè)快棋策略。這里的關(guān)鍵點(diǎn)在于，假設(shè)在這個(gè)游戲背后存在一個(gè)潛在的結(jié)構(gòu)，機(jī)器學(xué)習(xí)就能夠讓學(xué)徒將它們的直覺泛化到以前沒(méi)有見到過(guò)的狀態(tài)中去采取快速?zèng)Q策。也就是說(shuō)，學(xué)徒?jīng)]有僅僅是從有限的，固定的專家棋譜數(shù)據(jù)庫(kù)中創(chuàng)建一個(gè)行動(dòng)查詢表，而是能將所學(xué)泛化到其他棋局狀態(tài)中。所以神經(jīng)網(wǎng)絡(luò)既起著泛化的作用，也起到了模仿專家玩家的作用。

假設(shè)學(xué)徒通過(guò)模仿目前所見到的所有專家行動(dòng)學(xué)到了一個(gè)快速?zèng)Q策，那么它就可以被專家所用。當(dāng)專家希望采取行動(dòng)的時(shí)候，學(xué)徒會(huì)很快地給出一些備選行動(dòng)，然后專家會(huì)進(jìn)行深入考慮，并且也許在這個(gè)慢速思考的過(guò)程中，專家還會(huì)繼續(xù)受到學(xué)徒的敏銳直覺的指引。

在這個(gè)階段的最后，專家會(huì)在學(xué)徒的輔助下采取一些行動(dòng)，這樣，每一步行動(dòng)通常都會(huì)比僅由專家或者僅由學(xué)徒單獨(dú)做出的行動(dòng)要好。

接下來(lái)，上述的過(guò)程可以從學(xué)徒重新模仿（新）專家推薦的行動(dòng)開始，反復(fù)進(jìn)行下去。這會(huì)形成一個(gè)完整的學(xué)習(xí)階段的迭代，迭代過(guò)程將持續(xù)，直到學(xué)徒收斂。

從二元處理機(jī)制方面來(lái)看，模仿學(xué)習(xí)（imitation learning）步驟類似于人類通過(guò)研究實(shí)例問(wèn)題來(lái)提升直覺，然而專家提升（expert improvement）步驟則類似于人類利用自己已經(jīng)得到提升的直覺去指導(dǎo)未來(lái)的分析。

樹搜索和深度學(xué)習(xí)

ExIt 是一種通用的學(xué)習(xí)策略，學(xué)徒和專家可以用不同的形式具體化。在棋牌類游戲中，蒙特卡洛樹搜索（Monte Carlo Tree Search）是一個(gè)強(qiáng)大的游戲策略 [6]，是專家角色的天然候選者。深度學(xué)習(xí)已經(jīng)被證明是一種模仿強(qiáng)悍玩家的成功方法 [4]，所以我們將它作為學(xué)徒。

在專家提升（expert improvement）階段，我們使用學(xué)徒來(lái)指引蒙特卡洛樹搜索算法，讓它朝著更有希望的方向行動(dòng)，這有效地減少了游戲樹搜索的寬度和深度。以這種方式，我們就能夠把在模仿學(xué)習(xí)中得到的知識(shí)返回來(lái)用在規(guī)劃算法中。

棋牌游戲 HEX

Hex 是一款經(jīng)典的兩玩家棋牌游戲，玩家在 n×n 的六邊形格子上角逐。玩家顏色分為黑和白，輪流將代表自己顏色的棋子放在空格子中，如果有一列依次相連的黑子從南到北連在了一起，那么黑方獲勝。如果有一列依次相連的白子從東到西連通，那么白方獲勝。

5×5 的 Hex 棋盤示例

上面是一個(gè) 5×5 的棋盤，其中白方獲勝。Hex 有深度策略，這使得它對(duì)機(jī)器而言極具挑戰(zhàn)性，它巨大的動(dòng)作集合和連接規(guī)則意味著它和圍棋給人工智能帶來(lái)的挑戰(zhàn)有些類似。然而，與圍棋相比，它的規(guī)則更加簡(jiǎn)單，而且沒(méi)有平局。

Hex 的規(guī)則很簡(jiǎn)單，因此數(shù)學(xué)分析方法非常適用於此，目前最好的機(jī)器玩家 MoHex[7] 使用的是蒙特卡洛樹搜索和巧妙的數(shù)學(xué)思想。自 2009 年，MoHex 在所有的計(jì)算機(jī)游戲奧林匹克 Hex 競(jìng)賽中戰(zhàn)無(wú)不勝。值得注意的是，MoHex 使用了人類專家數(shù)據(jù)庫(kù)訓(xùn)練展開策略 (rollout policy)。

讓我們一起驗(yàn)證，在不使用任何專業(yè)知識(shí)和人類專家棋譜的情況下（游戲規(guī)則除外），ExIt 訓(xùn)練策略是否可以訓(xùn)練出一個(gè)勝過(guò) MoHex 的 AI 玩家。為此，我們使用蒙特卡羅樹搜索作為專家，由學(xué)徒神經(jīng)網(wǎng)絡(luò)來(lái)引領(lǐng)專家。我們的神經(jīng)網(wǎng)絡(luò)是深度卷積神經(jīng)網(wǎng)絡(luò)的形式，具有兩個(gè)輸出策略–一個(gè)給白方，另一個(gè)給黑方（細(xì)節(jié)參見 [5]）。

修正過(guò)的蒙特卡羅樹搜索公式可實(shí)現(xiàn)專家提升（expert improvement）： 

這里，s 是一個(gè)棋局狀態(tài)，a 是一個(gè)在狀態(tài) s 下可能被采取的行動(dòng)。UCT(s,a) 是蒙特卡羅樹搜索中所使用的樹 [6] 的經(jīng)典上置信區(qū)間（Upper Confidence Bound），后面所加的那一項(xiàng)能幫助神經(jīng)網(wǎng)絡(luò)學(xué)徒指導(dǎo)專家搜索更佳的行動(dòng)。其中π̂ 是學(xué)徒的策略（在狀態(tài) s 中對(duì)于每個(gè)潛在行動(dòng) a 的相對(duì)優(yōu)勢(shì)），n(s,a) 是搜索算法在狀態(tài) s 做出行動(dòng) a 的當(dāng)前訪問(wèn)次數(shù)；w 是為了平衡專家的慢思考和學(xué)徒的快思考而經(jīng)驗(yàn)性選擇的權(quán)重因子。該附加項(xiàng)使神經(jīng)網(wǎng)絡(luò)學(xué)徒引領(lǐng)搜索至更有希望的行動(dòng)，并且更快地拒絕不佳的行動(dòng)。 

為了在每一個(gè)模仿學(xué)習(xí)階段生成用以訓(xùn)練學(xué)徒的數(shù)據(jù)，批處理方法每次都重新生成數(shù)據(jù)，拋棄之前迭代中產(chǎn)生的所有數(shù)據(jù)。因此，我們同時(shí)也考慮了一個(gè)僅保存有限的最新生成數(shù)據(jù)的在線版本，以及一個(gè)保留所有數(shù)據(jù)的在線版本，但是隨著與最強(qiáng)玩法對(duì)應(yīng)的最新專家的增多，數(shù)據(jù)會(huì)成指數(shù)增長(zhǎng)。在下圖中我們對(duì)比了一些不同的方法：從訓(xùn)練的時(shí)間去衡量每一種學(xué)習(xí)策略網(wǎng)絡(luò)的強(qiáng)度（測(cè)量 ELO 分?jǐn)?shù)）。 

我們還展示了僅僅使用一個(gè)更傳統(tǒng)的強(qiáng)化學(xué)習(xí)方法，通過(guò)自我對(duì)弈（self play）學(xué)到策略 π̂ (a|s) 的結(jié)果（換言之不使用蒙特卡羅樹搜索）。這正是 AlphaGo 訓(xùn)練策略網(wǎng)絡(luò)時(shí)所用的方法。上圖的結(jié)果證明：ExIt 訓(xùn)練方法比傳統(tǒng)方法更高效。值得注意的是，在這個(gè)例子中訓(xùn)練還沒(méi)有完全收斂，在更充足的訓(xùn)練時(shí)間下，學(xué)徒還能進(jìn)一步提升能力。 

在論文中 [5]，我們也運(yùn)用了另一種能提升棋手性能的機(jī)制，也就是能夠讓學(xué)徒估計(jì)在自己獨(dú)自下棋時(shí)獲勝的概率的價(jià)值網(wǎng)絡(luò) Vπ̂ (s)。策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)被結(jié)合起來(lái)以幫助指導(dǎo)最終受學(xué)徒輔助的蒙特卡羅樹搜索玩家（apprentice-aided MCTS player）。策略網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)使用一個(gè)和（1）近似，但是又有所修改（包含了學(xué)徒在 s 狀態(tài)的價(jià)值）的方程指導(dǎo)最終的 MCTS 玩家。（細(xì)節(jié)參考 [5]） 

我們最終的 MCTS 玩家表現(xiàn)超越了最著名的 Hex 機(jī)器玩家 MoHex，在 9X9 的棋局中勝率是 75%?？紤]到訓(xùn)練沒(méi)有完全收斂，表示這個(gè)結(jié)果更加卓越。[9] 中展示了一些我們使用 ExIt 訓(xùn)練游的游戲機(jī)器玩家與目前最優(yōu)的 MoHex 玩家對(duì)陣的情況。我們對(duì)比了從同一個(gè)狀態(tài)開始時(shí)不同算法的玩法。論文 [5] 中有更多的例子。 

ExIt（黑方）VS MoHex（白方） 

MoHex（黑方）VS ExIt（白方）

ExIt 為何會(huì)如此成功？ 

部分原因模仿學(xué)習(xí)一般比強(qiáng)化學(xué)習(xí)容易，因此 EXIT 要比像 REINFORCE 等任意模型（model-free）的算法更成功。 

此外，唯有在搜索中，相對(duì)其他選擇來(lái)說(shuō)，沒(méi)有缺點(diǎn)的行動(dòng)才會(huì)被 MCTS 推薦。因此 MCTS 的選擇會(huì)比大多數(shù)潛在對(duì)手的選擇更好。相比之下，在常規(guī)的自我對(duì)弈（網(wǎng)絡(luò)自身充當(dāng)對(duì)手角色）中，行動(dòng)都是基于打敗當(dāng)前僅有的一個(gè)對(duì)手而推薦的，（因此所訓(xùn)練的棋手很有可能對(duì)當(dāng)前的非最優(yōu)對(duì)手過(guò)擬合）。我們認(rèn)為這就是為什么 EXIT（使用 MCTS 作為專家時(shí)）會(huì)如此成功的關(guān)鍵因素 –事實(shí)上學(xué)徒在與很多對(duì)手的對(duì)戰(zhàn)中都能取得良好的表現(xiàn)。 

與 ALPHAGO ZERO 的關(guān)系 

AlphaGo Zero[10]（在我們的工作 [11] 發(fā)表之后的幾個(gè)月之后問(wèn)世）也實(shí)現(xiàn)了一種 ExIt 風(fēng)格的算法，并且證明，在圍棋中可以在不使用人類棋手棋譜的情況下達(dá)到當(dāng)前最佳水平。論文 [5] 中給出了詳細(xì)的對(duì)比。

總結(jié) 

專家迭代是一種新的強(qiáng)化學(xué)習(xí)算法，它受啟發(fā)于人類思維的二元處理機(jī)制理論。ExIt 將強(qiáng)化學(xué)習(xí)分解為兩個(gè)獨(dú)立的子問(wèn)題：泛化和規(guī)劃。規(guī)劃在具體分析的基礎(chǔ)上執(zhí)行，并且在找到了強(qiáng)大的策略之后將之泛化。這將允許智能體做長(zhǎng)期規(guī)劃，并進(jìn)行更快速的學(xué)習(xí)，即使在極具挑戰(zhàn)的問(wèn)題也能達(dá)到高水平表現(xiàn)。這個(gè)訓(xùn)練策略在棋牌類人工智能玩家中是非常強(qiáng)大的，不需要任何人類專家的棋譜就能達(dá)到當(dāng)前最佳性能。