本文禁止轉(zhuǎn)載

原文:Guest Post (Part I): Demystifying Deep Reinforcement Learning

兩年前, 一個名叫deepmind的倫敦小公司往Arxiv上傳了一篇前沿的論文讓深度學(xué)習(xí)玩Atari游戲. 這篇文章展示了計算機(jī)如何僅僅通過觀察屏幕上的像素和分?jǐn)?shù)的增加來玩Atari上邊的2600個游戲. 成果引人注目, 因為這些游戲和分?jǐn)?shù)都被設(shè)計成挑戰(zhàn)人類的. 同樣的模型, 不需要任何的改動, 就可以用來學(xué)習(xí)不同的游戲, 而且其中的三個算法的表現(xiàn)甚至比人類要好.

從那時起针余，它就被譽(yù)為通用人工智能的第一步--一種可以在各種環(huán)境中生存的人工智能饲鄙，而不是局限于比如下棋這種嚴(yán)格的領(lǐng)域。毫無懸念Deepmind很快的被Google收購, 而且一直走在深度學(xué)習(xí)的前列. 2015年2月的論文通過強(qiáng)化學(xué)習(xí)達(dá)到人類的控制水平被<自然>雜志當(dāng)做特色封面,<自然>雜志是科學(xué)界最權(quán)威的雜志之一. 這篇文章中, 他們在49款不同的游戲中應(yīng)用了同樣的模型, 在一半的游戲中有著超人的表現(xiàn).

當(dāng)深度模型在監(jiān)督與非監(jiān)督學(xué)習(xí)領(lǐng)域在各個社區(qū)廣泛傳播的時候, 深度學(xué)習(xí)依然保有一定的神秘性, 這篇文章我們將嘗試解密這種技術(shù)以及其背后的基本原理.本文的受眾人群是已經(jīng)有了機(jī)器學(xué)習(xí)背景且有一點神經(jīng)網(wǎng)絡(luò)基礎(chǔ), 卻沒有時間深入鉆研強(qiáng)化學(xué)習(xí)的人.

以下是大綱:

1. 強(qiáng)化學(xué)習(xí)的主要挑戰(zhàn)有哪些?我們將在這涵蓋信度分配問題(credit assignment problem)和探索/利用困境( exploration-exploitation dilemma)
2. 如何用數(shù)學(xué)形式表達(dá)強(qiáng)化學(xué)習(xí)?我們將定義馬爾可夫決策過程(Markov Decision Process)并用它推導(dǎo)強(qiáng)化學(xué)習(xí).
3. 如何制定長期策略?我們將定義衰減未來激勵(discounted future reward)這將是下一節(jié)算法的基礎(chǔ).
4. 如何評估/估計未來的回報?我們將定義和解釋簡單基于表的Q-learning(Simple table-based Q-learning)算法
5. 如果狀態(tài)空間過大如何處理?我們將看到如何使用深度神經(jīng)網(wǎng)絡(luò)替代Q表.
6. 我們?nèi)绾巫屗嬲_始運行?我們將在這討論經(jīng)驗回放技術(shù)(Experience replay), 通過神經(jīng)網(wǎng)絡(luò)穩(wěn)定學(xué)習(xí).
7. 這就完事兒了?我們最后會討論探索/利用困境的幾個解決方案.

強(qiáng)化學(xué)習(xí)

回憶一下打磚塊游戲(Breakout), 這個游戲里邊你控制屏幕底部的一個滑塊來回接住并反彈一個小球來把上半塊屏幕磚敲碎. 每次敲碎一塊磚, 磚塊消失且分?jǐn)?shù)增加.

Figure 1: Atari Breakout game. Image credit: DeepMind.

假設(shè)要教一個神經(jīng)網(wǎng)絡(luò)去學(xué)習(xí)怎么玩這個游戲. 神經(jīng)網(wǎng)絡(luò)的輸入就應(yīng)該是屏幕的圖像, 而輸出應(yīng)該就是三種動作之一, 左/右還有發(fā)射球. 如果把它當(dāng)成分類游戲也算有道理 -- 對于每一個屏幕圖像, 你需要向左/向右(移動滑塊)或者發(fā)射(小球).聽起來簡單明了?這是肯定的, 但后續(xù)需要訓(xùn)練大量樣本.當(dāng)然也可以記錄骨灰級玩家的游戲過程, 但是我們不會真的像這樣去學(xué)習(xí).不需要一個一個屏幕圖像過并讓別人成千上萬次告訴我們怎么做. 只需要當(dāng)它偶爾做了正確行為就給出反饋即可, 這樣我們自己就能搞明白怎么做.

這就是強(qiáng)化學(xué)習(xí)試圖去解決的任務(wù).強(qiáng)化學(xué)習(xí)介于監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)之間.鑒于監(jiān)督學(xué)習(xí)對于每個訓(xùn)練樣本都有一個明確的標(biāo)簽, 而非監(jiān)督學(xué)習(xí)完全沒有標(biāo)簽, 強(qiáng)化學(xué)習(xí)中則有著稀疏而且延時的標(biāo)簽.被控主體(Agent,以下簡稱主體)必須根據(jù)這些激勵在這個環(huán)境中去學(xué)習(xí)去執(zhí)行動作.

雖然意思已經(jīng)表達(dá)的很直白了, 實際應(yīng)用中卻有著數(shù)不清的坑.比如說, 當(dāng)敲到一個磚塊的時候, 在游戲里就會得分, 然而這通常和之前做什么動作沒有多大關(guān)系. 難做的活早就在把滑塊停在正確的位置把球彈出去就干完了.這個難題有個名字就叫信度分配問題(credit assignment problem), 比如, 哪個動作影響了得分, 多大程度影響.

如果找到了一個可以得到確定分?jǐn)?shù)的策略, 那么是糾結(jié)于此方案還是繼續(xù)實驗可以得到更大激勵的策略?在上邊的打磚塊游戲里邊, 一個簡單測策略是把滑塊一直停在屏幕的最左邊等在那. 當(dāng)發(fā)射的時候, 球會更多的向左飛行, 這樣很容易就能在游戲結(jié)束前得10分. 是就滿意如此還是想要更好?這就叫做探索/利用困境( exploration-exploitation dilemma) - 繼續(xù)利用已知的方案還是探索更好的辦法.

強(qiáng)化學(xué)習(xí)是一個人類如何去學(xué)習(xí)的重要模型(同樣也是動物學(xué)習(xí)的模型).父母的褒獎, 學(xué)校的分?jǐn)?shù), 工作的工資 -- 這些都是激勵的實例.信度分配問題和探索/利用困境在日常商業(yè)與人際關(guān)系頻繁出現(xiàn). 這就是為什么研究這個問題如此重要, 而游戲給嘗試出新方法提供了一個極好的環(huán)境.

馬爾可夫決策過程

現(xiàn)在的問題是, 如何把強(qiáng)化學(xué)習(xí)形式化, 使之可以推導(dǎo)? 一種比較普遍的方法是把他用馬爾可夫決策過程表示出來.

假設(shè)你就是一個主體(Agent), 在一個環(huán)境中(比如打磚塊游戲), 環(huán)境處于一個確定的狀態(tài)之中(比如滑塊的位置, 球的飛行方向, 每個磚塊是否存在等等). 主體能在環(huán)境中做出特定的行為(比如向左或者向右移動滑塊). 這些行為有時會獲得激勵(比如分?jǐn)?shù)的增加). 行為使環(huán)境轉(zhuǎn)化到一個新的狀態(tài), 在新的狀態(tài)下主體可以做新的動作, 如此循環(huán)往復(fù).選擇行為的方式被稱為策略. 環(huán)境通常是隨機(jī)的, 這意味著它的下一個狀態(tài)某種意義上也是隨機(jī)的(比如丟了一個球后, 發(fā)射新的時候, 它的方向是隨機(jī)的)

Figure 2: Left: reinforcement learning problem. Right: Markov decision process.

狀態(tài)和行為的集合與狀態(tài)的轉(zhuǎn)移規(guī)則一起構(gòu)成了馬爾可夫決策過程. 這個過程(比如一個游戲)的一個片段(episode)是一個由狀態(tài)/行為/激勵組成的有限序列:

Markov decision process episode

這里的si ai 和 r(i+1)分別代表了狀態(tài),動作和在此狀態(tài)下執(zhí)行此動作后的獎勵. 片段以終態(tài)(terminal)sn (比如"游戲結(jié)束"屏幕)結(jié)尾. 馬爾可夫決策過程依賴于馬爾可夫猜想, 即下一個狀態(tài) s(i+1) 出現(xiàn)概率由當(dāng)前狀態(tài)si與動作ai決定. 而不是由前面那些狀態(tài)和動作決定.

衰減的未來激勵(Discounted Future Reward)

想要在長期表現(xiàn)優(yōu)秀, 不能僅僅只關(guān)注即時激勵, 也應(yīng)當(dāng)重視將來獲得的激勵. 如何達(dá)到這一點?

運行一個給定的馬爾可夫決策過程, 則很容易算出一個片段的總激勵(total reward):

Discounted Future Reward total reward

得到了這個, 從t點開始的未來總激勵(total future reward)可以表示為:

Discounted Future Reward total future reward

但是由于環(huán)境是隨機(jī)的, 我們永遠(yuǎn)不能確定下次使用同樣的動作會不會得到同樣的激勵. 未來經(jīng)歷的越多, 結(jié)果就越發(fā)散.出于這個原因通常使用衰減的未來激勵來替代上式:

Discounted Future Reward discounted future reward

這里的 γ 是代間衰減系數(shù), 離我們越遙遠(yuǎn), 考慮的就越少.容易看出, 衰減的未來激勵在t時的形式可以用t+1時同樣的結(jié)果表示:

Discounted Future Reward t + 1

如果設(shè)置衰減系數(shù) γ=0 , 則使得策略鼠目寸光,只看眼前利益(即時激勵), 想要在即時激勵與未來的激勵之間得到一個平衡, 就應(yīng)該設(shè)置一個衰減系數(shù), 比如γ=0.9, 如果環(huán)境是隨機(jī)的, 而且同樣的行為總是得到同樣的回報, 則可以設(shè)定γ=1
#譯者注: 其中蘊(yùn)含了一個哲理, 未來看的越清楚, 我們就會覺得未來越重要, 這樣就有更大的幾率獲得更高的激勵, 我們每個人都應(yīng)該努力去培養(yǎng)自己看清未來的能力

一個主體的優(yōu)秀的策略應(yīng)該總是選擇能夠最大化(衰減的)未來激勵

Q-learning(質(zhì)量學(xué)習(xí))

在Q-learning里邊, 我們定義一個函數(shù)Q(s, a)來代表當(dāng)我們在狀態(tài)s下執(zhí)行a動作的最大衰減未來激勵, 并且從這一點開始一直選取最優(yōu).

Q-learning

這個定義聽起來可能挺讓人迷糊. 如果僅僅知道當(dāng)前的狀態(tài)和動作而不知道后來的, 怎么去估計在游戲結(jié)束時候的得分? 這真的做不到.但作為一個理論構(gòu)想, 我們可以假設(shè)存在這么一個函數(shù).閉上眼睛默念五遍: "Q(s, a)存在, Q(s, a)存在...". 感受到了(洪荒之力?)?

如果你還沒整明白, 那就思考下這個函數(shù)所包含的含義. 假設(shè)你現(xiàn)在在某個狀態(tài)中, 要么執(zhí)行a動作, 要么執(zhí)行b動作. 你想執(zhí)行一個動作使得你最后得分最高. 一旦你手握這個Q函數(shù), 一切都easy了--選一個能得到最高的Q值的動作即可.

Q-learning π policy

這里的π代表著在每個狀態(tài)下選擇動作的策略.

好, 那如何取得Q函數(shù)呢? 讓我們回到某個轉(zhuǎn)換<s, a, r, s'>上來. 類似前一節(jié)介紹的衰減未來激勵, s狀態(tài)的Q值也可以用s'狀態(tài)的Q值來表示.

Q-learning Q-s'

這個式子稱為貝爾曼方程(Bellman equation), 想一下它還是挺符合邏輯的 -- (總的)未來最大激勵等于即時激勵加上下一狀態(tài)的(總的)未來最大激勵.

Q-learning的核心是可以迭代使用貝爾曼方程逼近Q函數(shù)在最簡單的情況下, Q函數(shù)是用一個以狀態(tài)作為行以動作作為列的表表示的. 簡單的Q-learning簡單到可以用下邊的偽代碼表示:

Q-learning code

算法里邊的α是學(xué)習(xí)率, 即舊的Q值與新的Q值之差的考慮程度. 尤其當(dāng)α=1兩個Q[s,a]抵消, 更新的值完全和貝爾曼方程一致.

我們用來更新Q[s,a] 的 maxa’ Q[s’,a’]僅僅是一個近似值,而且在早期階段的學(xué)習(xí)中, 這個值可能完全就是錯的. 但這個近值在迭代的過程中越來越準(zhǔn)確, 而且他是收斂的. 因此如果一直這么更新下去, Q函數(shù)收斂并代表真正的Q值.

深度Q網(wǎng)絡(luò) (Deep Q Network)

打磚塊游戲的狀態(tài)可被認(rèn)為由滑塊的位置,球的位置與方向,每塊磚是否存在一起定義. 然而這些直觀的表現(xiàn)卻是特定游戲的特性. 怎么把它變成更通用的特性, 使它適用與所有的游戲? 一個顯而易見的選擇是游戲的像素 -- 他們隱含了游戲里邊所有關(guān)于狀態(tài)的信息, 除了球的速度和球的方向.如果使用兩個連續(xù)的圖像則會包含這兩個信息.

如果把和DeepMind論文一樣的模型應(yīng)用到游戲屏幕中- 取最后四幀圖像, 縮放到84×84然后做一個256階的灰度化 -- 可能會得到 256^(84844)大約10e67970種不同的狀態(tài).這意味著Q表將會有10e67970行, 比已知宇宙的原子數(shù)量還多!可能有人說有那么多種像素的組合(和因此產(chǎn)生的狀態(tài))不可能都發(fā)生 -- 可以使用一個稀疏的表, 只記錄已經(jīng)發(fā)生的狀態(tài). 即使如此, 大部分的狀態(tài)都極少能訪問到, 想要跑滿所有情況可能要等到地老天荒.理想的情況是我們希望能對沒有見過的狀態(tài)的Q值做一個不錯的推測.

這就正是深度學(xué)習(xí)踏足的領(lǐng)域. 神經(jīng)網(wǎng)絡(luò)非常擅長在高度結(jié)構(gòu)化的數(shù)據(jù)中找到優(yōu)良的特性. 可以使用一個神經(jīng)網(wǎng)絡(luò)來代表Q函數(shù), 使用狀態(tài)(連續(xù)4幀的屏幕)和動作作為輸入, 輸出Q值.或者, 只輸入游戲屏幕輸出每個動作對應(yīng)的Q值, 這種方法有個優(yōu)點,當(dāng)要更新Q值或者選出最大Q值的動作的時候, 需要做的僅僅是一次前向傳輸,然后就可以立刻得到所有動作的Q值.

Figure 3: Left: Naive formulation of deep Q-network. Right: More optimized architecture of deep Q-network, used in DeepMind paper.

Deepmind使用的神經(jīng)網(wǎng)絡(luò)如下:

Deep Q network Deepmind

這是一個擁有三層卷積層和兩層全連接層的神經(jīng)網(wǎng)絡(luò). 熟悉識別網(wǎng)絡(luò)的朋友們應(yīng)該意識到了這里沒有池化層. 但是仔細(xì)想一想, 池化層給你帶來了轉(zhuǎn)移的不確定性 -- 網(wǎng)絡(luò)對物體的位置變得不敏感. 雖然池化對于圖片分類網(wǎng)絡(luò)這個是有意義的, 但游戲中球的定位會潛在地決定游戲的激勵, 我們并不想丟掉這個信息.

網(wǎng)絡(luò)的輸入是四個84×84的灰度化游戲屏幕圖像. 輸出是每個動作對應(yīng)的Q值(Atari有18個不同的動作),Q值可以是任何實數(shù),可以通過簡單的平方差損失函數(shù)進(jìn)行回歸優(yōu)化.

Q-learning square loss

給定一個狀態(tài)轉(zhuǎn)移:< s, a, r, s’ >前邊提到的Q表更新算法必須替換如下:

1.把當(dāng)前狀態(tài)s進(jìn)行前向傳播, 得到所有動作的Q值.
2.把下一個狀態(tài)s'進(jìn)行前向傳播在所有的輸出中計算max Q(s’, a’).
3.設(shè)定此動作的Q值為 r + γmax Q(s’, a’)(使用第二步計算出的結(jié)果), 對于所有其他的動作, 設(shè)定和第一步的返回一樣的Q值, 使得他們的誤差為0
4.使用反向傳播算法更新權(quán)重

經(jīng)驗回放(Experience Replay)

現(xiàn)在我們已經(jīng)知道了如何在每一種狀態(tài)下使用Q-learning進(jìn)行激勵的估計, 如何使用卷積神經(jīng)網(wǎng)絡(luò)逼近q值.但結(jié)果發(fā)現(xiàn)使用非線性函數(shù)去逼近Q值不是很穩(wěn)定.想讓它收斂你還需要一大堆的技巧. 而且這很耗時, 如果使用單個GPU估計需要一周的時間....

一個重要的技巧叫做經(jīng)驗回放(Experience Replay), 玩游戲的所有經(jīng)歷$lt; s, a, r, s’ $gt;會被保存在一個重放記憶中.訓(xùn)練網(wǎng)絡(luò)的時候, 回放記憶中隨機(jī)的小批狀態(tài)轉(zhuǎn)移用來代替最近的狀態(tài)轉(zhuǎn)移用來訓(xùn)練. 這樣就打破了和后續(xù)訓(xùn)練樣本的相似性, 否則可能會使得模型陷入一個局部最優(yōu).不僅如此, 經(jīng)驗回放會使得任務(wù)變得更像監(jiān)督學(xué)習(xí), 簡化了算法的調(diào)試與檢測. 可以先收集人類玩游戲的經(jīng)驗, 然后在這些數(shù)據(jù)上邊訓(xùn)練.

探索/利用(Exploration-Exploitation)

Q-learning嘗試解決信度分配問題 -- 當(dāng)?shù)竭_(dá)讓游戲得分的關(guān)鍵性的那一時刻, 網(wǎng)絡(luò)進(jìn)行反向傳播, 但是到目前還沒接觸到探索/利用問題..

首先觀察, 當(dāng)Q表和Q網(wǎng)絡(luò)隨機(jī)初始化的時候, 它的預(yù)測也是隨機(jī)的.如果選出最高的Q值的的動作, 那這個動作也是隨機(jī)的而且這個主體做出了一個隨便的探索(exploration). 當(dāng)Q函數(shù)收斂時, 返回的Q值更一致而且探索的數(shù)量下降. 所以有人說探索是Q-learning算法的一部分. 但是這個探索是"貪婪"的, 它找到一個有效策略之后就不再改變了.

解決上邊問題一個簡單有效的方法是ε貪婪探索(ε-greedy exploration) 在選取動作時候有ε的可能選取一個隨機(jī)動作, 不這么做算法就會貪婪的選擇最高的Q值.在Deepmin的系統(tǒng)中,ε的值隨時間從1減到0.1 -- 在最開始的時候系統(tǒng)總是隨機(jī)的進(jìn)行移動去盡可能的探索空間的狀態(tài), 而后慢慢的穩(wěn)定到一個固定的探索比例.

深度Q-learning算法(Deep Q-learning Algorithm)

下邊的代碼給出了最終的帶經(jīng)驗回放的Q-learning算法:

Deep Q-learning Algorithm code

實際上Deepmin公司使用了更多的技巧 -- 比如目標(biāo)網(wǎng)絡(luò)(target network), 誤差修剪(error clipping), 激勵修剪(reward clipping)等等, 但這些不在本文討論的范圍之內(nèi).

這個算法最精彩的部分是可以學(xué)習(xí)任何東西. 你想想看, 由于Q函數(shù)是隨機(jī)初始化的, 最開始的輸出完全是垃圾. 而且我們使用這些垃圾(下一個狀態(tài)的最大Q值)作為網(wǎng)絡(luò)的最終目標(biāo).只是偶爾獲得一點點微小的激勵. 聽起來有點不切實際, 它怎么能學(xué)習(xí)到任何有意義的東西?實際上, 它確實學(xué)到了.

結(jié)語

從Q-learning第一次提出開始, 已經(jīng)提出了很多提高Q-learning的方法 -- 舉幾個來說: 雙Q-learning,有優(yōu)先級的經(jīng)驗回放, 對抗網(wǎng)絡(luò)架構(gòu)和 連續(xù)動作空間擴(kuò)展, 最前沿的進(jìn)展請看2015深度強(qiáng)化學(xué)習(xí)專題和ICLR 2016(搜索標(biāo)題"強(qiáng)化"), 但請注意Q-learning已經(jīng)被谷歌申請了專利

常言道, 人工智能任重道遠(yuǎn). 一旦知道它如何運轉(zhuǎn), 它看起來也就沒有那么"智能"了. 但Q網(wǎng)絡(luò)還是讓我感到驚艷.看他們整明白一個游戲就像觀察野外的動物 -- 通過它自己獲取激勵的過程.

致謝

感謝Ardi Tampuu, Tanel P?rnamaa, Jaan Aru, Ilya Kuzovkin, Arjun Bansal, 還有 Urs K?ster對于此文草稿的點評.

(#譯者注: 當(dāng)然這里還要感謝作者Tambet Matiisen)

外鏈

• David Silver’s lecture about deep reinforcement learning
• Slightly awkward but accessible illustration of Q-learning
• UC Berkley’s course on deep reinforcement learning
• David Silver’s reinforcement learning course
• Nando de Freitas’ course on machine learning (two lectures about reinforcement learning in the end)
• Andrej Karpathy’s course on convolutional neural networks