雷鋒網(公衆号：雷鋒網)按：本期地平線資深算法工程師、增強學習專家穆黎森将為大家帶來增強學習簡介（一），本講内容主要涉及增強學習基本概念及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中非常基礎的一個公式。因為對于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的機率。
回顧一下之前舉的q
learning的例子。最早的q-learning使用一個表格來表示q函數：對于每一個state, action對，儲存一個對應的q值。q
learning的過程就是疊代修改這個表格的過程。可以發現，當state數量非常多，或者不再可枚舉、次元非常高的情況下，表格就不适用了；需要用更經濟的model來模拟這個表格。
深度神經網絡（deep
neural
network），在計算機視覺領域已經被證明是一個非常強大的函數拟合工具，可以用來表達非常複雜的視覺處理函數，來處理高維的圖像輸入。基于dnn的方法已經成為計算機視覺中很多問題的最好的解決方法。是以，是否能将更強的工具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都達到了人類的操作水準。
未完待續
（下一講内容敬請關注《大牛講堂》專欄）
本文作者：大牛講堂