無(wú)論有沒(méi)有去過(guò)賭場(chǎng)，相信大多數(shù)人都不會(huì)對(duì)老虎機(jī)感到陌生。作為賭場(chǎng)里最常見(jiàn)的娛樂(lè)設(shè)備，老虎機(jī)不僅在現(xiàn)實(shí)中廣受人們歡迎，它也頻繁出現(xiàn)在電視電影乃至動(dòng)畫(huà)片中，連一些常見(jiàn)的APP里都有它的身影。

往機(jī)器里投入硬幣后，玩家需要拉下拉把轉(zhuǎn)動(dòng)玻璃框中的圖案，如果三個(gè)圖案一致，玩家能獲得所有累積獎(jiǎng)金；如果不一致，投入的硬幣就會(huì)被吞入累積獎(jiǎng)金池。這個(gè)問(wèn)題看似簡(jiǎn)單，但很多人也許都忽視了，其實(shí)它和圍棋、游戲一樣，也是個(gè)強(qiáng)化學(xué)習(xí)問(wèn)題。

首先，我們要明確一點(diǎn)——老虎機(jī)問(wèn)題是表格型解決方案工具的一種。之所以這么說(shuō)，是因?yàn)槲覀兛梢园阉锌赡艿臓顟B(tài)放進(jìn)一個(gè)表格中，然后讓表格告訴我們需要了解的問(wèn)題狀態(tài)，繼而為解決問(wèn)題找出切實(shí)的解決方案。

k-armed Bandit Problem

單臂老虎機(jī)：只有一根側(cè)面拉桿

假設(shè)我們有一臺(tái)K臂老虎機(jī)，每根拉桿都能提供固定的一定數(shù)額的金錢(qián)，一次只能拉下一根拉桿，但我們不知道它們的具體回報(bào)是多少。在這個(gè)情景中，k根拉桿可以被視為k種不同的動(dòng)作（action），拉下拉桿的總次數(shù)T是我們的總timestep。整個(gè)任務(wù)的目標(biāo)是實(shí)現(xiàn)收益的最大化。

設(shè)在第t次拉下拉桿時(shí)，我們采取的動(dòng)作是At，當(dāng)時(shí)獲得的回報(bào)是Rt。那么對(duì)于任意動(dòng)作a，它的動(dòng)作值（value）q?(a)是：

這個(gè)等式表示的是無(wú)論何時(shí)，如果我們選擇動(dòng)作a，我們獲得的實(shí)際回報(bào)就應(yīng)該等于動(dòng)作a的預(yù)期回報(bào)。

把上面這個(gè)句子再讀三四遍，你覺(jué)得它行得通嗎？如果我們事先已經(jīng)知道拉下這個(gè)拉桿的最大收益是多少，那出于貪婪的目的，我們肯定每次都會(huì)選最好的動(dòng)作，然后使最終回報(bào)最大化。但在強(qiáng)化學(xué)習(xí)問(wèn)題中，貪婪算法并不一定等同于最優(yōu)策略，這一步的貪婪可能會(huì)對(duì)下一步產(chǎn)生負(fù)面影響。

雖然很困難，但我們真的很想實(shí)現(xiàn)q?(a)，所以對(duì)于timestep t，設(shè)Qt(a)是q?(a)的近似值：

那么我們又該怎么獲得Qt(a)？

注：上文中的回報(bào)（reward）和動(dòng)作值（value）不是同一個(gè)概念。回報(bào)指的是執(zhí)行動(dòng)作后的當(dāng)場(chǎng)回報(bào)，動(dòng)作值是一個(gè)長(zhǎng)期的回報(bào)。如果你吸毒了，一小時(shí)內(nèi)你很high，回報(bào)很高，但長(zhǎng)期來(lái)看，你獲得的動(dòng)作值就很可怕了。需要注意的是，因?yàn)橘€博機(jī)只需要一個(gè)動(dòng)作，所以這里的q?(a)不是未來(lái)回報(bào)之和，只是期望回報(bào)，它和其他地方的q?(a)也不一樣（雖然有濫用符號(hào)之嫌，但還是請(qǐng)多包涵啦）。

動(dòng)作值方法

函數(shù)Qπ(x, a)表示從狀態(tài)x出發(fā)，執(zhí)行動(dòng)作a后再使用策略π帶來(lái)的累計(jì)獎(jiǎng)賞，稱為“狀態(tài)-動(dòng)作值函數(shù)”（state-action value function）。——周志華《機(jī)器學(xué)習(xí)》

首先，我們需要估計(jì)動(dòng)作值，再據(jù)此決定要采取的行動(dòng)。

估算動(dòng)作值

求解q?(a)近似值的一種簡(jiǎn)單方法是使用樣本平均值：

上述等式看起來(lái)好像有什么說(shuō)法，但它其實(shí)很簡(jiǎn)單——選擇動(dòng)作a時(shí)，我們獲得的平均回報(bào)是多少。這個(gè)均值可以被視為q?(a)的近似值，因?yàn)閾Q幾個(gè)符號(hào)，我們就能發(fā)現(xiàn)這就是強(qiáng)大數(shù)定律（SLLN）的表達(dá)式。

換句話說(shuō)，它意味著Qt(a)必須收斂于q?(a)：

比起概率收斂，這種收斂更強(qiáng)大，但它其實(shí)也沒(méi)法保證Qt(a)一定能收斂。

動(dòng)作選擇規(guī)則：貪婪

“貪婪者總是一貧如洗。”當(dāng)面對(duì)巨大誘惑時(shí)，一些人會(huì)因?yàn)樨澙吩竭^(guò)自己的底線，去吸毒，去犯罪，但他們?cè)讷@得短暫快感的同時(shí)也失去了更多東西。強(qiáng)化學(xué)習(xí)中同樣存在類似的問(wèn)題，如果它是貪婪的，它會(huì)找出迄今為止最大的動(dòng)作值：

并依據(jù)這個(gè)動(dòng)作值去選擇每一步動(dòng)作。這樣做的后果是智能體從頭到尾只會(huì)選擇同一套動(dòng)作，而從不去嘗試其他動(dòng)作，在很多情況下，這樣的策略并不是最優(yōu)策略。

動(dòng)作選擇規(guī)則：?-Greedy

那么我們?cè)撛趺醇m正它的貪婪？之前我們?cè)凇稄?qiáng)化學(xué)習(xí)——蒙特卡洛方法介紹》一文中已經(jīng)介紹過(guò)ε-greedy：對(duì)于任何時(shí)刻t的執(zhí)行“探索”小概率ε<1，我們會(huì)有ε的概率會(huì)進(jìn)行exploration，有1-ε的概率會(huì)進(jìn)行exploitation。這可以簡(jiǎn)單理解成拋硬幣，除了正面和反面，它還有一個(gè)極小的立起來(lái)的概率。

雖然當(dāng)智能體“頭腦發(fā)熱”時(shí)，它還是會(huì)義無(wú)反顧地貪婪，但相比貪婪策略，?-Greedy隨機(jī)選擇策略（不貪婪）的概率是ε/|A(s)|。

癥結(jié)：非平穩(wěn)的動(dòng)作值

導(dǎo)致這種現(xiàn)象的主要原因是動(dòng)作值會(huì)隨時(shí)間推移發(fā)生變化，即之前我們研究的時(shí)靜態(tài)地拉桿，而不是隨機(jī)的、動(dòng)態(tài)的拉桿。以動(dòng)作值為例，比起我們之前假設(shè)的q?(a)，它更應(yīng)該被表示成q?(a, t)。

依據(jù)之前的動(dòng)作值估計(jì)，我們有：

它也可以被寫(xiě)成：

看起來(lái)SGD可以在這里發(fā)揮一些作用。如果它是平穩(wěn)的，那q?(a)收斂的概率就是100%；如果它不平穩(wěn)，我們一般不會(huì)希望Rn=Rn-1，因?yàn)楫?dāng)前回報(bào)會(huì)影響當(dāng)前的動(dòng)作值。

這里我們把權(quán)重1/n替換成α（α∈(0,1]）：

這是一個(gè)指數(shù)平均值，它在幾何上衰減之前回報(bào)的權(quán)重。設(shè)函數(shù)αn(a)是第n個(gè)timestep，也就是第n次拉下拉桿時(shí)某個(gè)特定獎(jiǎng)勵(lì)的權(quán)重。因?yàn)槔匣C(jī)問(wèn)題只需考慮動(dòng)作a，所以這個(gè)函數(shù)也可以簡(jiǎn)化成α(a)。

為了保證上式能收斂，我們還需要一些其他條件。

條件一

上式表示對(duì)于任何初始值Q1∈?，它都滿足q?(a)∈?。這個(gè)條件要求保證timestep足夠大，以最終克服任何初始條件或隨機(jī)波動(dòng)

條件二

這個(gè)式子表示這些timestep將“足夠小以確保能收斂到一個(gè)小值”。簡(jiǎn)而言之，第二個(gè)條件保證最終timestep會(huì)變小，以保證收斂。

既然如此，我們之前為什么要設(shè)αn(a)=α∈(0,1]呢？它不是一個(gè)常數(shù)嗎？這樣的閾值會(huì)不會(huì)影響收斂？

這些猜想都是正確的，但(0,1]這個(gè)閾值也有它存在的價(jià)值。我們?cè)谥暗腝n+1=Qn+αn(Rn+Qn)上繼續(xù)計(jì)算，最后可以獲得一項(xiàng)α(1-α)n-iRi，因?yàn)棣列∮?，所以給予R的權(quán)重隨著介入獎(jiǎng)勵(lì)次數(shù)的增加而減少。

因?yàn)樽罴褎?dòng)作值時(shí)非平穩(wěn)的，所以我們不想收斂到一個(gè)特定的價(jià)值。

動(dòng)作選擇規(guī)則：樂(lè)觀的初始值

到目前為止，我們必須非常隨意地設(shè)定Q1(a)的初始值，它本質(zhì)上是一組用于初始化的超參數(shù)。這里有個(gè)小訣竅，我們可以設(shè)初始值Q1(a)=C?a，其中C>q?(a)?a。

這樣之后，因?yàn)镼n(a)比估計(jì)值偏高，這時(shí)智能體會(huì)積極探索其他動(dòng)作，當(dāng)它越來(lái)越接近q?(a)時(shí)，智能體就開(kāi)始貪婪了。換句話說(shuō)，假設(shè)我們?cè)O(shè)當(dāng)前拉桿的樂(lè)觀回報(bào)是3，但智能體嘗試一次后，發(fā)現(xiàn)回報(bào)只有1，低于預(yù)期值，于是它會(huì)把其他拉桿全部嘗試一遍。雖然前期效率很低，但到后期，智能體已經(jīng)掌握哪些拉桿會(huì)產(chǎn)生高值，效果就接近“貪婪”了。

這種方法時(shí)可行的，在某種程度上，如果時(shí)間充裕，這個(gè)過(guò)程也可以被看作是模擬退火。但從整體來(lái)看，樂(lè)觀初始值前期的大量“exploration”是不必要的，它對(duì)于非平穩(wěn)問(wèn)題來(lái)說(shuō)不是最好的答案。

動(dòng)作選擇規(guī)則：置信上限選擇

在機(jī)器學(xué)習(xí)系統(tǒng)中，Bias與Variance往往不可兼得：如果要降低模型的Bias，就一定程度上會(huì)提高模型的Variance；如果要降低Variance，Bias就會(huì)不可避免地提高。針對(duì)兩者間的trade-off，下面的式子是一個(gè)很好的總結(jié)：

其中，

R(f)是假設(shè)f的（理論上）的風(fēng)險(xiǎn)；

R(f< *)是在假設(shè)集H中，假設(shè)f的最小風(fēng)險(xiǎn)；

M是假設(shè)集|H|的大小；

N是其中的樣本數(shù)；

δ是一個(gè)常數(shù)（如果非要知道這個(gè)常數(shù)是什么，只能說(shuō)它是我們選擇一個(gè)差的假設(shè)的概率）。

這里有兩個(gè)重點(diǎn)：

樣本數(shù)量非常少，我們的邊界非常松散。我們不知道目前的假設(shè)是否是最好的假設(shè)。

我們的假設(shè)越大，PAC（近似正確）學(xué)習(xí)的約束就越松散。

置信上限（UCB）是一個(gè)非常強(qiáng)大的算法，它可以用類似Bias-Variance權(quán)衡的方法來(lái)解決不同的問(wèn)題。在老虎機(jī)問(wèn)題中，我們可以把timestep t當(dāng)成假設(shè)集大小M，因?yàn)殡S著t逐漸增加，an也會(huì)逐漸增加，相應(yīng)的At就很難選擇。

每選一次a，不確定項(xiàng)就會(huì)減少，分母Nt(a)增加；另一方面，每一次選擇了a以外的行為，t會(huì)增加但Nt(a)不會(huì)改變，不確定評(píng)估值會(huì)增加。

梯度老虎機(jī)算法

截至目前，我們一直在努力估計(jì)q?(a)，但如果說(shuō)這個(gè)問(wèn)題還有除了行動(dòng)值以外的解決方法呢？比如我們?cè)撊绾螌W(xué)習(xí)一個(gè)動(dòng)作的偏好？

設(shè)動(dòng)作偏好為Ht(a)，它和回報(bào)無(wú)關(guān)，只是一個(gè)動(dòng)作相對(duì)于另一個(gè)動(dòng)作的重要性。那么At應(yīng)該符合gibbs分布（也就是機(jī)器學(xué)習(xí)的softmax分布）：

對(duì)于這個(gè)式子，我們?cè)撛趺椿谔荻扔?jì)算最大似然估計(jì)？首先，我們對(duì)Ht(a)做梯度上升，因?yàn)樗俏覀兊淖兞俊Ｎ覀兿胱畲蠡疎(Rt)：

Ht(a)的更新規(guī)則如下所示：

gibbs分布分解：

這只是整個(gè)梯度的一個(gè)偏導(dǎo)數(shù)。那么b≠a的動(dòng)作呢？下面是省略計(jì)算過(guò)程的結(jié)果：

由此可得：

因?yàn)椋?/p>

相應(yīng)的，這個(gè)等式也是成立的：

由上述等式可得：

因?yàn)閝?(a,t)被包含在動(dòng)作a的預(yù)期值內(nèi)，它也可以被寫(xiě)成Rt。那等式里的Xt是什么？坦率地說(shuō)，你想它是什么它就是什么，嚴(yán)謹(jǐn)起見(jiàn)，我們可以設(shè)Xt是Rt的平均值。

計(jì)算梯度后獲得新的更新規(guī)則：

其中a是t時(shí)采取的動(dòng)作。由于找到a的期望值很困難，我們可以用隨機(jī)值來(lái)更新：

選擇動(dòng)作的簡(jiǎn)單方法是計(jì)算argmaxaπt(a)，問(wèn)題就解決了。

備注

下面是上述算法的一個(gè)比較圖：

盡管簡(jiǎn)單的方法表現(xiàn)不太好，但對(duì)很多強(qiáng)化學(xué)習(xí)問(wèn)題來(lái)說(shuō)，它們也稱得上是最先進(jìn)的算法了。