干貨 | 算法工程師入門第二期——穆黎森講增強學習（一）

本文作者：大牛講堂

編輯：劉芳平

2017-07-19 11:38

導語：地平線大牛講堂算法工程師入門第二期來啦！本期地平線資深算法工程師、增強學習專家穆黎森將為大家帶來增強學習簡介（一）

雷鋒網(公眾號：雷鋒網)按：本期地平線資深算法工程師、增強學習專家穆黎森將為大家帶來增強學習簡介（一），本講內容主要涉及增強學習基本概念及Deep Q Learning的相關內容。

傳送門：干貨 | 算法工程師入門第二期——穆黎森講增強學習（二）

今天我很榮幸有機會在這里，跟大家分享增強學習（Reinforcement Learning，RL）這個話題。這次分享，我希望能達到三方面的目的：

第一，希望沒有相關背景的同學能夠對RL有一定的了解，所以我會介紹一些基礎的概念。

第二，希望對有機器學習算法背景的同學，如果對增強學習感興趣的話，能了解到RL近期的一些進展。

第三，對我而言也是對于相關知識的整理。

這次分享主要包括以下三個環節：

• 關于增強學習的一些基本概念；

• Deep Q Learning。DQN這個工作成功地把深度學習應用在了RL領域，所以會單獨介紹一下；

• 在Deep Q Learning之后，近期的一些進展。

基礎概念

機器學習

首先，什么是增強學習，它和監督學習有什么不同？

他們都有學習這個詞，那什么是機器學習呢？根據Tom M. Mitchell的表述：為了完成某個任務（Task）的計算機程序，如果隨著某種形式的經驗（Experience）的增加，在某個表現度量（Performance measure）的衡量下，表現越來越好，我們就可以說，這是一個機器學習的程序。

所以這里，機器學習的三個特征元素：T:Task, E: Experience, P: Performance measure。先舉一個反例。

假設現在需要完成的任務是，根據下班的時刻，預測回家花在路上的時間。我們知道，高峰期會堵車，回家時間會長一些；如果加班到晚上，路上會更通暢一些。這時候，我寫了一個程序來完成這個任務：f(t)=1.0 – 0.5 * (t-18) / 6

t 為時刻，取值[18,24]；返回值表示小時數。很明顯，只要輸入確定，這個程序（算法）的輸出就確定了；所以，是不具有學習的能力的。究其原因，是算法中沒有任何可以改變的部分。所以，我可以寫另外一個程序：f(t)=a – b * (t-18) / 6

其中，a,b是兩個變量，如果我們的算法能讓f(t)在執行了多次預測后，不斷調整a,b的值，使之結果結果越來越接近真實的值，那么，這個算法是具有學習的能力的。 所以，通常機器學習的算法程序，其中需要有一部分是可以隨著Experience而自動調整的。這些可改變的部分，通常屬于算法模型（Model）的一部分。

這里引入模型（Model）的概念。對于比較復雜的任務，完美完成這個任務的真實的函數我們通常不知道，既不知道他的參數，甚至也不知道他的結構。那我們就對這個函數的結構做一個假設，叫做模型（Model），比如說我們假設它是一個用神經網絡（neural network）可以去解決的問題，然后用這個模型來逼近我們想要的真實函數。這個Model里通常會有很多的參數，也就是可以改變的自由度。這些自由度就組成了一個空間，我們需要做的就是在這個空間里面去尋找，到底哪一個參數組合能讓這個Model最接近我們想要的真實函數。

在很多機器學習的算法中，學習的過程，就是尋找模型的最優參數的過程。

監督學習

我們來看第一個任務的例子，圖像分類（Image Classification）。我們知道，如果有標注好的數據集，就可以用監督學習的方法來完成這個任務。那么在這里，機器學習的三個元素：

• T: Task 是把每張圖片標注一個合適的label；

• E: Experience是很多已經標注好的圖像的數據集；

• P: Performance Measure 就是標注的準確度，比如Precision、Recall這些CV領域的衡量標準。
  

監督學習怎么解決這個問題呢？首先，建立一個模型（Model），model的輸入是圖像，輸出是圖像的分類標簽。然后，對于標注好的圖像，用另外一個函數去衡量model的輸出與正確的輸出之前的差距，這個函數通常被叫做損失函數（loss function）。于是，改進model的表現的問題，就轉化成了一個優化問題：通過改變model的參數，讓loss function值越來越接近極小值。優化問題（optimization）又是一個比較大的話題，就可以用各種各樣的數值方法去求解。從優化問題的角度來講，監督學習的特點就是loss function由model輸出和正確輸出之間的差別直接構造而來。

增強學習

我們來看第二個任務的例子，玩游戲。這個任務的目標是得到盡量高的分數。在這個任務里，通常不再有“標注好的數據”以供使用：在第一個局面下，應該往左；在第四個局面下，應該往右，等等。這種情況下，我們可以用增強學習的方法來完成這個任務。機器學習的三個元素：

• T: Task是游戲結束時，得到盡量高的分數；

• E: Experience 是不斷的嘗試玩這個游戲；

• P: Performance measure 就是最后獲取的分數。

可以看到上述兩個例子之間的區別。相似的問題還有很多：

例如下圍棋，或者很多棋牌類游戲到最后一刻決定輸贏的時候，我才知道我是贏（得分+1），還是輸（得分-1），但是中間也許并不是每時每刻都有一個直接的信號告訴我應該下在哪里；

例如駕駛，成功到達了目標，中間有沒有發生事故或者違反交通規則，就算成功完成了這個任務（+1），中間也許并不是每時每刻都有一個專家來指導當前應該怎么前進；

例如機器人控制， 機械臂成功抓取到物體就算完成（+1），但是事先并不知道每個時間點，每種情況下，機械臂的每一個電機應該輸入的電壓是多少。

根據剛才的例子，我們提煉出增強學習的一般過程中，所涉及到的模塊：

Agent，包括了我們需要學習的model，他是通過輸入的狀態（State）輸出一個行為（Action），通過這個action和環境（Environment）去交互，收集到獎勵（Reward）；學習的目標是需要去最大化累積的回饋。

可以看到，在一般性的定義下：

• T: Task就是為了執行某個任務，在某個特定環境下得到一個最優或者說比較優的策略。

• E: Experience就是我不斷地去和環境交互，所得到的交互結果，單次的交互我們把它叫做Transition，連續的交互序列也叫做Trajectory。一條完整的trajectory是從初始狀態出發，到結束狀態（如果有的話）為止。無結束狀態的任務，trajectory可以無限延續；有結束狀態的任務也被稱為Episodic task。?

• P: Performance Measure： 在RL里，通常使用的Performance Measure叫做Discounted Future Reward。

Discounted Future Reward

Discounted Future Reward 定義如下：

也就是最后一行。我們希望Agent能給出一個策略（Policy）：在某個state下，輸出action，使得收到的Discounted Future Reward 最大化。

通常γ會選取一個小于1大于0的值。如果取0的話，相當于策略只用考慮當前一步能收集到的獎勵而不顧及長期回報；如果取1的話，則不好處理持續（無限長）的決策序列問題。

Policy, Value, Transition Model

增強學習中，比較重要的幾個概念：

• Policy 就是我們的算法追求的目標，可以看做一個函數，在輸入state的時候，能夠返回此時應該執行的action或者action的概率分布。?

• Value，價值函數，表示在輸入state，action的時候，能夠返回在 state下，執行這個action能得到的Discounted future reward的（期望）值。

• Transition model是說環境本身的結構與特性：當在state執行action的時候，系統會進入的下一個state，也包括可能收到的reward。

所以很顯然，以上三者互相關聯。如果能得到一個好的Policy function的話，那算法的目的已經達到了。 如果能得到一個好的Value function的話，那么就可以在這個state下，選取value值高的那個action， 自然也是一個較好的策略。如果能的到一個好的transition model的話，一方面，有可能可以通過這個transition model直接推演出最佳的策略；另一方面，也可以用來指導policy function或者value function 的學習過程。

所以，增強學習的方法，大體可以分為三類：

• Value-based RL，值方法。顯式地構造一個model 來表示值函數Q，找到最優策略對應的Q 函數，自然就找到了最優策略。

• Policy-based RL，策略方法。顯式地構造一個model來表示策略函數,然后去尋找能最大化discounted future reward的。

• Model-based RL，基于環境模型的方法。先得到關于environment transition的model，然后再根據這個model去尋求最佳的策略。

以上三種方法并不是一個嚴格的劃分，很多RL算法同時具有一種以上的特性。

Bellman Equation

根據以上R（Discounted Future Reward），Q的定義，我們可以得到Bellman Equation：

Bellman Equation 是RL中非?；A的一個公式。因為對于Value Based method 來說，Bellman Equation 給出了一個迭代改進Q函數的方法：

而對于Policy Based Method 來說， 通常需要通過采樣的方式對Q值進行估計；在各種各樣的估計方法中，Bellman Equation也扮演了重要的角色。

Value Based Method

這里給出一個值方法的算法的例子：Q learning

Policy Based Method

這里給出策略方法的一個例子：policy gradient

所謂策略梯度，是指當策略函數可微的時候，通過找到一個合適的loss function來使得策略函數的模型可以用基于梯度的優化方法來迭代改進。關于loss function的構造有很多種形式，上面的例子是比較基礎的形式，這里就不展開了，不過其基本的效果是，讓策略函數傾向于輸出“更好的”action：對于隨機策略來說，即意味著增大能獲得更大的期望Q值的action的概率。

Deep Q Learning

回顧一下之前舉的Q learning的例子。最早的Q-learning使用一個表格來表示Q函數：對于每一個state, action對，保存一個對應的Q值。Q learning的過程就是迭代修改這個表格的過程?？梢园l現，當state數量非常多，或者不再可枚舉、維度非常高的情況下，表格就不適用了；需要用更經濟的model來模擬這個表格。

深度神經網絡（Deep Neural Network），在計算機視覺領域已經被證明是一個非常強大的函數擬合工具，可以用來表達非常復雜的視覺處理函數，來處理高維的圖像輸入?；贒NN的方法已經成為計算機視覺中很多問題的最好的解決方法。所以，是否能將更強的工具DNN，引入RL領域，來解決更困難的問題呢？

Deep Q learning 這個工作就是將DNN/CNN引入RL來作為Q函數的model。

DNN的loss function 定義如下：

這個loss function也是由Bellman equation得出，其中

也被稱為Temporal Difference，TD。可以看出，這也是一個迭代的過程：通過當前的Q函數的輸出和環境中收集到的獎勵r，來得到新的修正后的Q值。

新的挑戰

但是，神經網絡的引入，也引發了新的問題。

第一個問題是神經網絡的計算代價較大，所以對函數的形式從上圖左邊所示調整為右邊，一次計算就能得出這個state下所有action的Q值。

第二個問題是，在RL中，agent和environment交互所得到的transition序列的數據不是獨立同分布的；而對于神經網絡的訓練來說，訓練數據采樣的獨立同分布是非常有必要的。所以，這里引入了一個replay memory的機制，將transition保存到一定大小的replay memory中，然后從中重新采樣。這樣，樣本之間的相關性就小很多了。

第三個問題是，由于新的Q值是由原來的Q值計算而來，更新后的神經網絡又用來計算新一輪的Q值，對于神經網絡來說，相當于不斷擬合一個移動的目標值，可能會產生一種正反饋效應，讓訓練的過程變得發散。解決這個問題的手段是，增加一個目標網絡target用來計算新的Q值，讓這個目標網絡隔一段時間更新成當前的網絡參數，所以，target網絡在兩次更新之間保持不變，網絡擬合目標的移動問題也得到了緩解。

在DQN這個工作中，使用了卷積神經網絡（CNN）來處理圖像的輸入，最后輸出游戲的動作指令；成功地實現了僅根據觀察游戲的屏幕輸出和獎勵來學會玩游戲的過程。

這里，相鄰的4幀被合并到一起，作為一個state，這樣，神經網絡有機會從多幀抽取信息，比如屏幕上物體的運動速度。

可以看到，在不少游戲上，DQN都達到了人類的操作水平。

總結

以上是生活随笔為你收集整理的干货 | 算法工程师入门第二期——穆黎森讲增强学习（一） 本文作者：大牛讲堂编辑：刘芳平2017-07-19 11:38 导语：地平线大牛讲堂算法工程师入门第二期来啦！本期地平线资深算法工程师、增的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。