無論有沒有去過賭場,相信大多數(shù)人都不會對老虎機(jī)感到陌生。作為賭場里最常見的娛樂設(shè)備,老虎機(jī)不僅在現(xiàn)實(shí)中廣受人們歡迎,它也頻繁出現(xiàn)在電視電影乃至動畫片中,連一些常見的APP里都有它的身影。
往機(jī)器里投入硬幣后,玩家需要拉下拉把轉(zhuǎn)動玻璃框中的圖案,如果三個圖案一致,玩家能獲得所有累積獎金;如果不一致,投入的硬幣就會被吞入累積獎金池。這個問題看似簡單,但很多人也許都忽視了,其實(shí)它和圍棋、游戲一樣,也是個強(qiáng)化學(xué)習(xí)問題。
首先,我們要明確一點(diǎn)——老虎機(jī)問題是表格型解決方案工具的一種。之所以這么說,是因?yàn)槲覀兛梢园阉锌赡艿臓顟B(tài)放進(jìn)一個表格中,然后讓表格告訴我們需要了解的問題狀態(tài),繼而為解決問題找出切實(shí)的解決方案。
k-armed Bandit Problem
單臂老虎機(jī):只有一根側(cè)面拉桿
假設(shè)我們有一臺K臂老虎機(jī),每根拉桿都能提供固定的一定數(shù)額的金錢,一次只能拉下一根拉桿,但我們不知道它們的具體回報是多少。在這個情景中,k根拉桿可以被視為k種不同的動作(action),拉下拉桿的總次數(shù)T是我們的總timestep。整個任務(wù)的目標(biāo)是實(shí)現(xiàn)收益的最大化。
設(shè)在第t次拉下拉桿時,我們采取的動作是At,當(dāng)時獲得的回報是Rt。那么對于任意動作a,它的動作值(value)q?(a)是:
這個等式表示的是無論何時,如果我們選擇動作a,我們獲得的實(shí)際回報就應(yīng)該等于動作a的預(yù)期回報。
把上面這個句子再讀三四遍,你覺得它行得通嗎?如果我們事先已經(jīng)知道拉下這個拉桿的最大收益是多少,那出于貪婪的目的,我們肯定每次都會選最好的動作,然后使最終回報最大化。但在強(qiáng)化學(xué)習(xí)問題中,貪婪算法并不一定等同于最優(yōu)策略,這一步的貪婪可能會對下一步產(chǎn)生負(fù)面影響。
雖然很困難,但我們真的很想實(shí)現(xiàn)q?(a),所以對于timestep t,設(shè)Qt(a)是q?(a)的近似值:
那么我們又該怎么獲得Qt(a)?
注:上文中的回報(reward)和動作值(value)不是同一個概念?;貓笾傅氖菆?zhí)行動作后的當(dāng)場回報,動作值是一個長期的回報。如果你吸毒了,一小時內(nèi)你很high,回報很高,但長期來看,你獲得的動作值就很可怕了。需要注意的是,因?yàn)橘€博機(jī)只需要一個動作,所以這里的q?(a)不是未來回報之和,只是期望回報,它和其他地方的q?(a)也不一樣(雖然有濫用符號之嫌,但還是請多包涵啦)。
動作值方法
函數(shù)Qπ(x, a)表示從狀態(tài)x出發(fā),執(zhí)行動作a后再使用策略π帶來的累計(jì)獎賞,稱為“狀態(tài)-動作值函數(shù)”(state-action value function)?!苤救A《機(jī)器學(xué)習(xí)》
首先,我們需要估計(jì)動作值,再據(jù)此決定要采取的行動。
估算動作值
求解q?(a)近似值的一種簡單方法是使用樣本平均值:
上述等式看起來好像有什么說法,但它其實(shí)很簡單——選擇動作a時,我們獲得的平均回報是多少。這個均值可以被視為q?(a)的近似值,因?yàn)閾Q幾個符號,我們就能發(fā)現(xiàn)這就是強(qiáng)大數(shù)定律(SLLN)的表達(dá)式。
換句話說,它意味著Qt(a)必須收斂于q?(a):
比起概率收斂,這種收斂更強(qiáng)大,但它其實(shí)也沒法保證Qt(a)一定能收斂。
動作選擇規(guī)則:貪婪
“貪婪者總是一貧如洗?!碑?dāng)面對巨大誘惑時,一些人會因?yàn)樨澙吩竭^自己的底線,去吸毒,去犯罪,但他們在獲得短暫快感的同時也失去了更多東西。強(qiáng)化學(xué)習(xí)中同樣存在類似的問題,如果它是貪婪的,它會找出迄今為止最大的動作值:
并依據(jù)這個動作值去選擇每一步動作。這樣做的后果是智能體從頭到尾只會選擇同一套動作,而從不去嘗試其他動作,在很多情況下,這樣的策略并不是最優(yōu)策略。
動作選擇規(guī)則:?-Greedy
那么我們該怎么糾正它的貪婪?之前我們在《強(qiáng)化學(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ù)之前的動作值估計(jì),我們有:
它也可以被寫成:
看起來SGD可以在這里發(fā)揮一些作用。如果它是平穩(wěn)的,那q?(a)收斂的概率就是100%;如果它不平穩(wěn),我們一般不會希望Rn=Rn-1,因?yàn)楫?dāng)前回報會影響當(dāng)前的動作值。
這里我們把權(quán)重1/n替換成α(α∈(0,1]):
這是一個指數(shù)平均值,它在幾何上衰減之前回報的權(quán)重。設(shè)函數(shù)αn(a)是第n個timestep,也就是第n次拉下拉桿時某個特定獎勵的權(quán)重。因?yàn)槔匣C(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ù)計(jì)算,最后可以獲得一項(xiàng)α(1-α)n-iRi,因?yàn)棣列∮?,所以給予R的權(quán)重隨著介入獎勵次數(shù)的增加而減少。
因?yàn)樽罴褎幼髦禃r非平穩(wěn)的,所以我們不想收斂到一個特定的價值。
動作選擇規(guī)則:樂觀的初始值
到目前為止,我們必須非常隨意地設(shè)定Q1(a)的初始值,它本質(zhì)上是一組用于初始化的超參數(shù)。這里有個小訣竅,我們可以設(shè)初始值Q1(a)=C?a,其中C>q?(a)?a。
這樣之后,因?yàn)镼n(a)比估計(jì)值偏高,這時智能體會積極探索其他動作,當(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è)的概率)。
這里有兩個重點(diǎn):
樣本數(shù)量非常少,我們的邊界非常松散。我們不知道目前的假設(shè)是否是最好的假設(shè)。
我們的假設(shè)越大,PAC(近似正確)學(xué)習(xí)的約束就越松散。
置信上限(UCB)是一個非常強(qiáng)大的算法,它可以用類似Bias-Variance權(quán)衡的方法來解決不同的問題。在老虎機(jī)問題中,我們可以把timestep t當(dāng)成假設(shè)集大小M,因?yàn)殡S著t逐漸增加,an也會逐漸增加,相應(yīng)的At就很難選擇。
每選一次a,不確定項(xiàng)就會減少,分母Nt(a)增加;另一方面,每一次選擇了a以外的行為,t會增加但Nt(a)不會改變,不確定評估值會增加。
梯度老虎機(jī)算法
截至目前,我們一直在努力估計(jì)q?(a),但如果說這個問題還有除了行動值以外的解決方法呢?比如我們該如何學(xué)習(xí)一個動作的偏好?
設(shè)動作偏好為Ht(a),它和回報無關(guān),只是一個動作相對于另一個動作的重要性。那么At應(yīng)該符合gibbs分布(也就是機(jī)器學(xué)習(xí)的softmax分布):
對于這個式子,我們該怎么基于梯度計(jì)算最大似然估計(jì)?首先,我們對Ht(a)做梯度上升,因?yàn)樗俏覀兊淖兞?。我們想最大化E(Rt):
Ht(a)的更新規(guī)則如下所示:
gibbs分布分解:
這只是整個梯度的一個偏導(dǎo)數(shù)。那么b≠a的動作呢?下面是省略計(jì)算過程的結(jié)果:
由此可得:
因?yàn)椋?/p>
相應(yīng)的,這個等式也是成立的:
由上述等式可得:
因?yàn)閝?(a,t)被包含在動作a的預(yù)期值內(nèi),它也可以被寫成Rt。那等式里的Xt是什么?坦率地說,你想它是什么它就是什么,嚴(yán)謹(jǐn)起見,我們可以設(shè)Xt是Rt的平均值。
計(jì)算梯度后獲得新的更新規(guī)則:
其中a是t時采取的動作。由于找到a的期望值很困難,我們可以用隨機(jī)值來更新:
選擇動作的簡單方法是計(jì)算argmaxaπt(a),問題就解決了。
備注
下面是上述算法的一個比較圖:
盡管簡單的方法表現(xiàn)不太好,但對很多強(qiáng)化學(xué)習(xí)問題來說,它們也稱得上是最先進(jìn)的算法了。
-
算法
+關(guān)注
關(guān)注
23文章
4709瀏覽量
95338 -
強(qiáng)化學(xué)習(xí)
+關(guān)注
關(guān)注
4文章
269瀏覽量
11597
原文標(biāo)題:強(qiáng)化學(xué)習(xí)——多臂老虎機(jī)問題
文章出處:【微信號:jqr_AI,微信公眾號:論智】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
Facebook推出ReAgent AI強(qiáng)化學(xué)習(xí)工具包
深度強(qiáng)化學(xué)習(xí)實(shí)戰(zhàn)
將深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)相結(jié)合的深度強(qiáng)化學(xué)習(xí)DRL
人工智能機(jī)器學(xué)習(xí)之強(qiáng)化學(xué)習(xí)
統(tǒng)計(jì)假設(shè)測試、多臂老虎機(jī)方法,揭示了多臂老虎機(jī)在實(shí)踐中的優(yōu)勢
深度強(qiáng)化學(xué)習(xí)到底是什么?它的工作原理是怎么樣的
強(qiáng)化學(xué)習(xí)在智能對話上的應(yīng)用介紹
MindSpore 首發(fā):隱私保護(hù)的 Bandit 算法,實(shí)現(xiàn)電影推薦

強(qiáng)化學(xué)習(xí)的基礎(chǔ)知識和6種基本算法解釋
強(qiáng)化學(xué)習(xí)與智能駕駛決策規(guī)劃
使用Arduino實(shí)現(xiàn)老虎機(jī)自動化

評論