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

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

首先，我們要明確一點——老虎機(jī)問題是表格型解決方案工具的一種。之所以這么說，是因為我們可以把所有可能的狀態(tài)放進(jìn)一個表格中，然后讓表格告訴我們需要了解的問題狀態(tài)，繼而為解決問題找出切實的解決方案。

k-armed Bandit Problem

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

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

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

這個等式表示的是無論何時，如果我們選擇動作a，我們獲得的實際回報就應(yīng)該等于動作a的預(yù)期回報。

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

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

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

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

動作值方法

函數(shù)Qπ(x, a)表示從狀態(tài)x出發(fā)，執(zhí)行動作a后再使用策略π帶來的累計獎賞，稱為“狀態(tài)-動作值函數(shù)”（state-action value function）?！苤救A《機(jī)器學(xué)習(xí)》

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

估算動作值

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

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

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

比起概率收斂，這種收斂更強大，但它其實也沒法保證Qt(a)一定能收斂。

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

“貪婪者總是一貧如洗?！碑?dāng)面對巨大誘惑時，一些人會因為貪婪越過自己的底線，去吸毒，去犯罪，但他們在獲得短暫快感的同時也失去了更多東西。強化學(xué)習(xí)中同樣存在類似的問題，如果它是貪婪的，它會找出迄今為止最大的動作值：

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

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

那么我們該怎么糾正它的貪婪？之前我們在《強化學(xué)習(xí)——蒙特卡洛方法介紹》一文中已經(jīng)介紹過ε-greedy：對于任何時刻t的執(zhí)行“探索”小概率ε<1，我們會有ε的概率會進(jìn)行exploration，有1-ε的概率會進(jìn)行exploitation。這可以簡單理解成拋硬幣，除了正面和反面，它還有一個極小的立起來的概率。

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

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

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

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

它也可以被寫成：

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

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

這是一個指數(shù)平均值，它在幾何上衰減之前回報的權(quán)重。設(shè)函數(shù)αn(a)是第n個timestep，也就是第n次拉下拉桿時某個特定獎勵的權(quán)重。因為老虎機(jī)問題只需考慮動作a，所以這個函數(shù)也可以簡化成α(a)。

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

條件一

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

條件二

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

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

這些猜想都是正確的，但(0,1]這個閾值也有它存在的價值。我們在之前的Qn+1=Qn+αn(Rn+Qn)上繼續(xù)計算，最后可以獲得一項α(1-α)n-iRi，因為α小于1，所以給予R的權(quán)重隨著介入獎勵次數(shù)的增加而減少。

因為最佳動作值時非平穩(wěn)的，所以我們不想收斂到一個特定的價值。

動作選擇規(guī)則：樂觀的初始值

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

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

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

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

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

其中，

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

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

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

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

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

這里有兩個重點：

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

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

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

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

梯度老虎機(jī)算法

截至目前，我們一直在努力估計q?(a)，但如果說這個問題還有除了行動值以外的解決方法呢？比如我們該如何學(xué)習(xí)一個動作的偏好？

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

對于這個式子，我們該怎么基于梯度計算最大似然估計？首先，我們對Ht(a)做梯度上升，因為它是我們的變量。我們想最大化E(Rt)：

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

gibbs分布分解：

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

由此可得：

因為：

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

由上述等式可得：

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

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

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

選擇動作的簡單方法是計算argmaxaπt(a)，問題就解決了。

備注

下面是上述算法的一個比較圖：

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