文/ Tambet Matiisen 譯/趙屹華，劉翔宇
原作者Tambet Matiisen在文章結尾列出了對本文內容給出意見和建議的讀者，以及深入了解這些技術的在線文檔和視頻連結，受篇幅所限，譯文不再贅述。感謝Tambet Matiisen授權《程式設計師》翻譯和刊載。
原文連結：http://neuro.cs.ut.ee/demystifyingdeep-reinforcement-learning/
本文為《程式設計師》文章，未經允許不得轉載，更多精彩文章請訂閱2016年《程式設計師》
儘管監督式和非監督式學習的深度模型已經廣泛被技術社區所採用，深度強化學習仍舊顯得有些神秘。這篇文章將試圖揭秘這項技術，並解釋其背後的邏輯。受眾讀者主要是有機器學習或者神經網絡背景，卻還沒來得及深入鑽研強化學習技術的朋友。
文章大綱如下：
強化學習面臨的主要挑戰是什麼？我們將會在此討論credit assignment問題和探索-利用的取捨。
如何用數學表達式表示強化學習過程？我們將定義馬爾科夫決策過程，並用它來解釋強化學習過程。
該如何構建長期策略？我們定義了「未來回報折扣（discounted future reword）」概念，它構成了下一節算法的基礎。
如何預測和估計未來回報？我們將會定義並且解釋簡單的基於表的Q-learning算法。
如果狀態空間過大了怎麼辦？我們演示了如何用一個（深度）神經網絡模型來替換Q-table算法。
在真正使用它之前我們還需要做些什麼？我們將會討論經驗重播技術，用神經網絡來穩定學習過程。
都完成了嗎？最後，我們會考慮一些針對探索-利用問題的簡單解決方案。
強化學習我們以Breakout（打磚塊）遊戲為例。在遊戲中，玩家將操控屏幕底部的一塊滑板，讓球反彈後撞擊屏幕上部的磚塊，直到所有磚塊都破碎。每當球擊中了磚塊，磚塊會消失，玩家的得分會增加——玩家得到了獎勵回報。
假設你想訓練一個神經網絡模型來玩這款遊戲。網絡的輸入將是屏幕圖像，輸出結果是三種動作：向左、向右和撞擊（接住球）。我們可以把它當做一個分類問題——對每一幀屏幕圖像，你是需要左移、右移還是撞擊。聽起來很直白嗎？沒錯，接著你需要，大量的訓練樣本數據。當然，你可以用專家級玩家的遊戲視頻作為訓練數據，但這不是我們的學習方式。我們不需要外人千百次地告訴我們每一幀圖像該選擇哪一種操作動作。我們只需要偶爾得到一些正反饋信息，剩下的一切事情我們自己就能搞定。
這就是強化學習試圖去解決的任務。強化學習介於監督式學習和非監督式學習之間。監督式學習的每個訓練樣本都有一個標籤，非監督式學習的訓練樣本沒有標籤，強化學習的訓練樣本有稀疏並且時間滯後的標籤——即獎勵回報。模型僅基於這些獎勵回報從環境中學習正確的行為。
儘管概念非常直觀，在實際操作中卻充滿了挑戰。舉個例子，當你在「打磚塊」遊戲中擊中了磚塊並且得到了獎勵回報，這個回報往往與最近的幾次動作（移動滑板）並沒有關聯。調整滑板位置、撞擊球使其反彈，所有這些複雜工作在得到回報之前早已完成了。這被稱為credit assignment問題——也就是說，是由於之前的哪些行為才取得的回報，它們的貢獻程度是什麼。
當你用某一種策略取得了一定的回報之後，你是打算繼續做下去，還是嘗試一些可能獲得更大回報的方法呢？在上面的「打磚塊」遊戲中，一種簡單的策略就是移到屏幕的左邊界等著。球飛向左側的情況總是比右側更多些，所以你在遊戲結束前總是能很容易地得到大概10分。你對這個成績已經感到滿意了，還是想得到更多？這就是所謂的探索-利用困境——是應該利用好已知有效的方法，還是要發掘其它可能更好的方法。
強化學習是我們（或者所有的動物）如何學習的一種重要模型。來自父母的獎勵、在學習取得的成績、工作的薪水——這些都是回報的形式。Credit assignment問題和探索-利用困境在我們每天的工作和感情生活中都會遇到。因此研究這個問題是十分重要的，遊戲組成了一隻嘗試各種新方法的絕妙沙盒。
馬爾科夫決策過程接下來，問題轉化為如何將強化學習問題公式化，使得人能夠理解？最常見的一種方法就是將其用馬爾科夫決策過程展示。
假設你是一位代理者（agent），位於某個環境（environment）中（比如「打磚塊」遊戲）。這個環境又處在某個特定狀態（state）下（比如滑板的位置、球的位置和方向、剩餘的磚塊等等）。代理者能在環境中執行特定的動作（actions）（比如左移或者右移滑塊）。這些動作有時會帶來一次回報（reward）（比如得分增加）。每次動作都會轉換環境進入到新的狀態，代理者又可以執行另一個動作，周而復始。你選擇動作的依據可以稱為策略（policy）。通常來說環境是隨機的，也就是說下一個狀態將會隨機出現（比如，某一次你沒接住球，新發射的球隨機出現在某個方向上）。
狀態和動作的集合，以及相鄰兩次轉換的規則，構成了馬爾科夫決策過程。每一輪過程（如一局遊戲）是一系列有限的狀態、動作和回報：
s₀,a₀,r₁,s₁,a₁,r₂,s₂,…,sn-1,an-1,rn,sn這裡si表示狀態，ai表示動作，ri+1表示執行動作後得到的回報。本輪過程的結束狀態為sn（比如「遊戲結束」畫面）。馬爾科夫決策過程依賴於馬爾科夫假設，下一個狀態si+1的概率僅取決於當前狀態si和當前動作ai，與之前的動作和狀態無關。
未來回報折扣為了取得長期良好的表現，我們不僅需要考慮即刻的回報，還有未來將會取得的回報。我們將要如何處理呢？
假定有一次馬爾科夫決策過程，我們很容易計算出一輪中取得的所有回報（total reward）：
基於此，時間t之後的所有未來回報（total future reward）可以表示為：
但由於我們的環境是隨機的，不能保證下次進行同樣的動作時候可以得到同樣的回報。我們越深入未來，越可能出現分歧。出於這個原因，通常使用未來回報折扣來代替：
其中γ是介於0到1之間的折扣因子——回報越是深入未來，γ值越小。很容易看出，在t時刻的未來回報折扣可以用t+1時刻同樣的事情來表示：
Rt=rt+yrt+1+y2rt+2…+yn-trn如果我們令折扣因子γ=0，那麼這種策略將是目光短淺的，我們只依賴於即刻回報。如果我們希望保持即刻回報與未來回報之間的平衡，應該將折扣因子γ設為與0.9近似的值。如果的環境是恆定的，相同的動作總是能夠得到同樣的回報，那麼我們可以把折扣因子設為1。
對於一個agent良好的策略是，總是選擇能夠使未來回報（折扣）最大化的動作。
Q學習（Q-learning）在Q學習中，我們定義一個函數Q(s, a)，表示在狀態s下進行a動作時最大的未來回報折扣，並以此繼續優化。
Q（st,at）=max Rt+1Q(s, a)可以理解為「在狀態s下進行a操作之後，遊戲結束時最有可能的得分」。它之所以稱為Q函數，是因為表示的是在某一狀態下執行某一操作時候的「質量」。
這聽起來可能令人費解。只知道當前的狀態和動作，不知道後來的動作和回報，我們如何估計最後的分數呢？其實我們不能。只不過作為一個理論構想，我們假設存在這麼一個函數。只要閉上眼睛，嘴裡默念五遍：「Q(s, a)存在，Q(s, a)存在……」感受到了嗎？
如果你存有疑慮，那麼想想有這麼一個函數會帶來什麼。假設你在某個狀態下不知道是否執行a動作還是b動作。你想選擇結束時有最高得分的那個動作。一旦你使用了神奇的Q函數，那麼答案就相當簡單——選擇Q值最高的那個動作。
π(s)=ar gmaxa Q(s,a)其中π表示策略，我們在每個狀態下如何選擇動作。
好了，那麼我們如何得到Q函數呢？現在我們只來關注一個轉換< s, a, r, s』>。與上一節的未來回報折扣一樣，可以用下一個狀態s』的Q值來表示s狀態下執行a動作時的Q值。
Q(s,a)=r+ymaxa＇,Q(s＇,a＇)這被稱為貝爾曼方程。如果你仔細思考，會發現這很合乎邏輯——對於當前狀態和動作的最大未來回報是即刻回報加上下一個狀態的最大未來回報。
Q學習的主要思想是，我們可以使用貝爾曼方程迭代逼近Q函數。在最簡單的情況下，Q函數用一個表來實現，狀態作為行，動作作為列。Q學習算法的要點很簡單，如下：
initialize Q[numstates,numactions]arbitrarilyobserve initial state srepeatselect and carry out an action aobserve reward r and new state sQ[s,a] = Q[s,a] + α(r + γmaxaQ[ss = suntil terminated
算法中的α表示的是學習率，它控制著考慮多少之前Q值和新計算的Q值之間的不同。特別地，當α=1時，那麼取消兩個Q[s, a]，剩下的與貝爾曼方程就是一樣的了。
我們用來更新Q[s, a]的maxa 『Q[s』,a』]只是一個近似值，而且在學習的早期可能完全是錯誤的。但是，隨著每次迭代，這個近似值會越來越準確，這已經得到證明了，如果我們執行這種更新足夠多的話，那麼Q函數會收斂並代表真正的Q值。
深度Q網絡打磚塊遊戲的環境狀態可以由球拍位置，球的位置和方向，以及是否有磚塊來定義。這種直觀的表示是一個遊戲特有的。我們可以用更為通用的方式來表示所有遊戲嗎？很明顯可以選擇屏幕像素——它們包含了所有關於遊戲狀況的相關信息，除了球的速度和方向。兩個連續的屏幕也包含這些信息。
如果我們把在DeepMind論文中提到的相同預處理方式運用於遊戲屏幕上——取最後四個屏幕圖像，大小調整為84×84，然後用256級灰度轉換成灰度圖像——我們會得到25684x84x4≈ 1067970種可能的遊戲狀態。這意味著假想Q表中有1067970行——比宇宙已知的原子數還要多！有人可能會說，許多像素組合（因此狀態也是）永遠不會出現——我們完全可以用一張稀疏表來表示已訪問的狀態。即便如此，大多數狀態很少被訪問，Q表收斂就要等到天荒地老了。理想情況下，我們會對從未見過的狀態猜測它的Q值。
此時深度學習就有用武之地了。神經網絡非常適合對高度結構化的數據進行特徵提取。我們可以用神經網絡來表示Q函數，狀態（四個遊戲屏幕）和動作作為輸入，並輸出對應的Q值。或者，可以只將遊戲屏幕作為輸入，並對每個可能的動作輸出Q值。這種方法的優點是，如果想要更新Q值或是選擇有最高Q值的動作，只需要在網絡中進行簡單的一步，就能夠立刻得到對於所有動作的所有Q值。
DeepMind使用的網絡架構如下：
這是一個經典的卷積神經網絡，有三個卷積層，之後是兩個全連接層。對於熟悉物體識別網絡的人，可能會注意到這裡沒有池化層。但如果仔細想想，池化層保證了轉換不變性——網絡對圖像中物體的位置不敏感。這對類似於ImageNet的分類任務來說意義非凡，但是對於遊戲來說，球的位置對於確定潛在回報至關重要，我們不希望丟棄這個信息！
網絡的輸入是4個84×84的灰度遊戲屏幕圖像。網絡的輸出是每個可能動作（Atari中的18個）的Q值。Q值可以是任何實數，這樣就可以使用回歸，通過簡單的平方誤差損失進行優化。
給定一個轉換< s, a, r, s』>，之前算法中Q表的更新法則需要替換成：
1、對於當前狀態s進行前饋操作，得到所有動作的預測Q值。
2、對於下一個狀態s』進行前饋操作，並計算所有網絡輸出的最大值maxa』 Q(s』, a』)。
3、將針對某個動作的Q值設定為r+γmaxa』 Q(s』,a』)（使用步驟2中計算出的最大值）。對於其他的動作，將Q值設定為步驟1中的Q值，對於這些輸出把誤差設為0。
4、使用反向傳播更新權值。
現在，我們已經知道了如何使用Q學習來估計每個狀態下未來回報，以及使用卷積神經網絡來逼近Q函數。但事實證明，使用非線性函數的Q值近似不是那麼穩定。讓它收斂有很多種方法。這也相當耗時，使用一塊GPU大概要花一個星期。
最重要的訣竅是經驗重播。在遊戲中，所有的經驗< s, a, r, s』>被存儲在重播內存中。在訓練網絡時，從重播內存中隨機使用小批次，代替多數最近的轉換。這打破了後續訓練樣本的相似性，這可能會導致網絡陷入局部最小中。經驗重播使得訓練任務與常規的監督式學習非常相像，簡化了算法的調試和測試。可以從人類玩家中獲取所有的經驗來訓練網絡。
探索 - 利用（Exploration-Exploitation）Q學習試圖解決credit assignment問題——它及時將回報傳播，直到達到關鍵決策點，這個點就是得到回報的實際原因。但是我們還沒踏入探索-利用困境……
首先觀察到的是，當Q表或是Q網絡被隨機初始化，那麼它的預測最初也是隨機的。如果我們選擇具有最高Q值的動作，這個動作將是隨機的，agent將執行粗「探索」。當Q函數慢慢收斂，它返回更為連續的Q值，探索量也隨之減少。有人就會這說，Q學習結合了探索作為算法的一部分。但是這種探索是「貪婪」的，它由它碰到的第一個有效策略決定。
解決上述問題的一個簡單而有效的方式是使用ε貪婪探索——有ε的概率選擇隨機動作，否則「貪婪」選擇Q值最高的動作。在他們的系統中，DeepMind實際上讓ε隨著時間從1降低至0.1——在開始的時候系統完全進行隨機移動來最大限度地探索狀態空間，然後它會降低到一個固定的探索率。
深度Q學習算法下面是使用經驗重播的深度Q學習算法：
initialize replay memory Dinitialize action-value function Q withrandom weightsobserve initial state srepeatselect an action awith probability ε select arandom actionotherwise select a =argmaxa』Q(s,a,)carry out action aobserve reward r and new state s,store experience <s, a, r, s』> inreplay memory Dsample random transitions <ss, aa,rr, ss,> from replay memory Dcalculate target for each minibatchtransitionif ss, is terminal state then tt= rrotherwise tt = rr +γmaxa』Q(ss,, aa,)train the Q network using (tt -Q(ss, aa))^2 as losss = suntil terminated
DeepMind使用了很多訣竅來讓它起作用——比如目標網絡（target network）、誤差剪裁（error clipping）、回報剪裁（reward clipping）等，但這些都不在本文討論範圍。
這個算法最驚人的部分是，它可以學習任何東西。試想一下——因為我們的Q函數隨機初始化，它最開始輸出的全是垃圾。我們使用這些垃圾（下一個狀態的最大Q值）作為網絡的目標，偶爾加入微小的回報。這聽起來很瘋狂，它怎麼可能學習到任何有意義的東西？事實是，它就是可以。
CCAI 2016中國人工智慧大會（http://ccai.caai.cn/）將於8月26-27日在京舉行，AAAI主席，多位院士，MIT、微軟、大疆、百度、阿里、滴滴專家領銜全球技術領袖和產業先鋒打造國內人工智慧前沿平臺，7+重磅大主題報告，4大專題論壇，1000+高質量參會嘉賓，探討人機互動、機器學習、模式識別學術前沿及產業實戰。門票限時八折優惠中（http://huiyi.csdn.net/activity/product/goods_list?project_id=3023）。