南京大學俞揚博士萬字演講全文：強化學習前沿（上）

雷鋒網［AI科技評論］按：本文根據俞揚博士在中國人工智慧學會AIDL第二期人工智慧前沿講習班「機器學習前沿」所作報告《強化學習前沿》編輯整理而來，雷鋒網在未改變原意的基礎上略作了刪減，經俞揚博士指正確認，特此感謝。全文分為上下兩篇，本文為上篇。

俞揚博士、副教授，主要研究領域為人工智慧、機器學習、演化計算。分別於2004年和2011年獲得南京大學計算機科學與技術系學士學位和博士學位。

2011年8月加入南京大學計算機科學與技術系、機器學習與數據挖掘研究所（LAMDA）從事教學與科研工作。曾獲2013年全國優秀博士學位論文獎、2011年中國計算機學會優秀博士學位論文獎。發表論文40餘篇，包括多篇Artificial Intelligence、IJCAI、AAAI、NIPS、KDD等國際一流期刊和會議上，研究成果獲得IDEAL"16、GECCO"11、PAKDD"08最佳論文獎，以及PAKDD』06數據挖掘競賽冠軍等。

任《Frontiers of Computer Science》青年副編輯，任人工智慧領域國際頂級會議IJCAI』15/17高級程序委員、IJCAI"16/17 Publicity Chair、ICDM"16 Publicity Chair、ACML"16 Workshop Chair。指導的學生獲天貓「雙十一」推薦大賽百萬大獎、Google獎學金等。

在此列出俞揚老師講課目錄，以供讀者參考：

• 一、介紹（Introduction）

• 二、馬爾可夫決策過程（Markov Decision Process）

• 三、從馬爾可夫決策過程到強化學習（Policy Search）

• 四、函數估計（Policy Search）

• 五、策略搜索（Policy Search）

• 六、遊戲中的強化學習（Reinforcement Learning in Games）

• 七、強化學習總結

• 八、強化學習資源推薦

以下為俞揚博士的演講正文：

大家好,我會盡量通過直觀的方式簡單的介紹一下強化學習的三個問題。由於水平有限，所以難免會有一些不足或者不到位的地方，請大家指正。

• 第一，強化學習到底是什麼？

• 第二，強化學習有哪幾類演算法？這幾類演算法的思路是什麼？

• 第三，強化學習能用在什麼地方？應用時會遇到什麼限制？

一、介紹（Introduction）從動物的學習過程說起

現在大家都在說人工智慧，雖然可能難以精確的說清楚到底什麼叫做智能，但我們知道擁有智能會有一些聰明的表現。例如像犬等一些動物，我們可能會認為是有一定智能的，我們可以訓練一隻幼犬聽懂飼養員的指令。訓練方法是：飼養員手裡拿著食物，然後說「坐下」，當幼犬做出符合要求的動作時，就把食物給它。反覆進行訓練，大概半小時的時間，它就學會聽見「坐下」的命令就坐下。這個過程就是動物的學習過程，它的智能就表現在它能在一定時間內發現如何適應環境，獲得食物獎賞。

在很早之前，就有許多學者在想能不能讓計算機也做到相同的事情，自動發現如何適應環境，這也就是我們今天說的強化學習。有這麼一種說法，說「強化學習是真正的人工智慧」。我們現在不評價這句話講的合適不合適，至少，強化目的是希望機器能和動物一樣，有較好的適應環境的能力。

• 強化學習名字的由來

這裡先解釋一下強化學習這個名字。為什麼叫強化學習呢？因為這個過程是不斷的重複、不斷強化認知，英文Reinforcement Learning 中的 Reinforcement 更準確的中文翻譯也是「強化」。

• 類比強化學習和動物學習

訓練幼犬的過程有兩個要素：

1. 飼養員需要對幼犬發出指令，比如讓它「坐著」，

2. 飼養員手中有動物非常想要的東西，即獎賞。對狗來說，獎賞就是食物。

對於智能體（Agent，即計算機）來說，我們希望通過類似的方法能夠訓練智能體，我們把其中的要素抽象出來，可以用下面這個圖來表示：

現在智能體處於一個很暗的環境之中，意思是它並不知道這個環境裡面到底是什麼，這也是我們希望計算機通過強化學習能做到的事——把它扔到一個未知的環境裡面，它能夠通過和環境打交道來適應這個環境，學習到做什麼動作才是最好的。

Agent能夠從環境裡面觀測到的東西有兩個：

1. 狀態。它能夠觀測到的環境和它自己的狀態；

2. 獎賞。當它做出一定動作以後，這個環境可能會給它一個獎賞。

它根據觀察到的狀態做出的行動，叫做動作或決策；這個動作放到環境里以後，會在環境里被執行；執行以後，環境會發生變化。

總體來說，如果按照剛才的要素把它刻畫出來，它對應的變數有：動作的集合、狀態的集合，獎賞函數，以及做完一個動作以後，決定環境會發生什麼變化的轉移函數。

對於Agent來說，自身具備的選擇決策的能力，叫做策略。這個策略意思就是，觀測到了環境現在處於什麼狀態，而選擇做出什麼動作出來。這裡的策略和監督學習里的模型其實是一回事。

• 從智能體的視角來看它所處的環境，以及它所做的動作

1. 剛睜開眼睛的時候，它看到的環境是一個初始狀態。

2. 根據這個狀態，智能體做了一個動作。我們把策略寫成π，π會根據當前的狀態選擇一個動作，然後到環境中去具體執行。

3. 執行了以後，這個環境會發生狀態轉移（Transition），變到下一個狀態。同時，也會反饋給智能體一個回報或者獎賞（Reward）。

4. 最後，智能體繼續根據新的狀態來決定它下面做什麼樣的動作。

所以從智能體的視角來看，即看到什麼狀態，然後決定做一個相應的動作並會收到回報，然後又在下一個狀態做一個動作並收到一個回報，這樣一直下去。

所以大家可以很明確地看到：

• 第一，這個智能體不是做一次決策就完成了學習的過程。實際上，它要做的是一個序列的決策。

• 第二，我們怎麼評判智能體策略的好壞呢？一般評判的形式就是，它能拿到的獎賞會有多大。每一步都可能有獎賞，所以評判的形式是把總的獎賞加起來看看它有多大。

長期累積獎賞有好幾種計數法，比如我們可以把總的T步將上全部加起來，或者用折扣（discounted）的方法，可以讓它走無窮多步，但是不是按照原數值加起來，而是要考慮權重，這個權重會因時間的流逝而產生折扣。

• 在算總獎賞的時候，為什麼要考慮權重？

一方面，是因為在數學上比較好處理；另外一方面，是說在很多真實的應用裡邊，我們對未來的價值的估計有可能是折扣的。舉例說明：

如果你今天能夠賺到100塊，或者下個月能夠賺到200塊，在這兩個決策裡面你要選一個，你可能會選擇今天就拿這100塊錢，將來對你來說可能會比較穩妥，下個月發生的事情還不知道會怎麼回事，所以在有的應用裡邊會考慮折扣，但需要在不同的應用中考慮具體的需求。

智能體要做的事，就是找一個能夠帶來最大的長期累積獎賞的策略。

通過設置獎賞，我們可以定義智能體，讓它去做不同的事情。就像剛才訓練這隻幼犬一樣，我們通過給它一個吃的，可以讓它做趴下的動作，也可以讓它做站起來的動作。

尋找最優策略的兩個例子

實際上強化學習的框架只是一個一般的框架，這個框架可以包含很多很多問題在裡面。下面舉兩個例子。

• 第一個例子：尋找最短路徑的問題。

條件如下圖所示，我們要找一條從s到t的最短路徑。這是很簡單的問題，這裡演示把最短路徑變成強化學習的問題去解決，我們可以這樣做：

先定義狀態和動作：

1. 把每個節點當成是一個狀態；

2. 把每個節點上面連著的邊，當作這個狀態下面可以做的動作。

定義好了狀態和動作，我們就要找最短路徑，也就是要找到路徑的權重和加權最小。

通常強化學習是讓獎賞最大化，因此這裡把路徑上的權重先取一個負的值，讓它最大化這個負的值。稍微做一點變化的是，t會指出來一個單獨的繞自己循環的節點。

接下來，就開始找最優策略。我們先假設能夠找到最優的策略。最優的策略是什麼呢？就是從s開始，我們選擇每一步從哪一條邊走出去，能使總的獎賞最大。我們看到這裡有一個100，這是很大的，所以一定能走到t去，除掉100這個意外情況，上圖加粗線所示路徑的獎賞應該是最大的。

對於最優的策略來說，它們對應的就是一個最優的路徑，我們這裡先不管最優的策略怎麼求解。

• 第二個例子：最大化任意函數

我們展示了怎麼用強化學習來解決最短路徑這個問題；除此之外，強化學習還可以包容很多其他問題。

比如，我們要在0、1的N維空間裡面最大化一個函數f。這不是一個容易解決的問題，特別是沒有規定這個f是什麼，換句話說這個f是什麼都可以。

這個問題也可以變成一個強化學習的問題，怎麼變呢？

我設定初始的狀態裡邊是空集；這個時候有兩個動作，往左走是加一個0，往右走是加一個1，0再往左走再加一個0，再往右走再加一個1；走出N層以後最上面這層就是0、1空間裡面所有的組合，對應所有可能的解。

我們還要設定一個獎賞——中間每一層獎賞都是0，只有最後一層的獎賞是F。這就會使得，如果有一個最優的強化學習的策略，能夠找到最優的路徑到達節點，那麼它就能使得這個獎賞最大、F最大。

通過這個例子，我想表達一個觀點——如果我們面對的這個學習問題比較簡單，就沒必要用強化學習。不能因為它自己在市面上比較火，而把以往的一些問題換成用強化學習的方法來解決。

總結一下，強化學習和規劃哪裡不同？

• 第一，強化學習看到的世界一個黑箱子，而對於規劃而言，這個世界卻是很清楚的。比如我們的最短路徑，所有的節點、便點、權重點都是已知的；而對於強化學習，狀態如何轉移、邊的權制是多少、甚至有哪些狀態都需要自己探索、發現。

• 第二，規劃的問題可能就是一個解、一個路徑；而強化學習的解是一個模型。和監督學習一樣，只要輸入任意一個狀態，強化學習都會告訴你應該做什麼決策。因此，除了給出最優路徑上的每一個狀態、每一個節點應該往哪邊走以外，實際上任何一個節點都能告訴我從這個節點到目標去應該怎麼走。

強化學習（RL）和監督學習（SL）的不同

剛才說到強化學習和監督學習有很多相似的地方，比如說模型實際上是一樣的。那它們之間有何差異呢？

• 監督學習總的來說是一個開環的學習。

1. 通常，監督學習任務會從環境中收集一批數據；

2. 接著我們用監督學習演算法從數據中產生模型；

3. 最後就可以用這個模型來做預測了。

• 但是對於強化學習來說，它面對的是一個閉環的學習。

1. 首先，也是從環境中產生數據；

2. 用強化學習的演算法從數據中產生模型；

3. 還要把模型放回到環境中運行，接著又會產生新的數據出來，再重複以上步驟。

因此從大體上看，兩者的主要區別，一個是開環學習，一個是閉環學習。這點不一樣就帶來了很多具體區別：

首先，在監督學習里，數據是分成觀測的特徵值和一個標記。這個標記的含義是，看到這樣一個觀測的值、特徵以後，應該做出什麼樣的預測。

但是在強化學習裡面，這個數據首先是一個序列，做了一個動作以後下面又到了什麼狀態，有一個反饋值，並且有了新的狀態。這個序列裡面雖然有反饋獎賞，但這個獎賞並不能告訴我們應該做什麼樣的動作，而只是對現在的策略有一個評估值，我們把所有獎賞加起來作為當前策略的一個評估，可以得知策略做的有多好，但並不知道應該做什麼樣的動作是最好的，這個也是數據上的兩個差別。

另外，強化學習的演算法和監督學習的演算法也是不一樣的。兩者的模型可能是一樣的。監督學習裡面可以是一個決策樹，也可以是一個神經網路，也可以是一個模型，在強化學習里也是一樣。

總結起來，兩者最核心的區別，在於強化學習需考慮自身對環境的影響。

• 經典應用

由於強化學習做的是序列的預測和序列的學習，所以它以往主要的一個應用領域，是做機器控制，比如說直升機的操控。

在直升機的應用裡面，智能體就是直升機，環境是其飛行空域，狀態可以是直升機的高度、速度、姿態等等，採取的決策是操縱桿指令。我們希望直升機能夠做出我們想要的軌跡，但是又不會掉下來。這些目標可以作為直升機的獎賞，讓它來學習一個策略，以實時控制直升機的運動。

• 更多的應用

有不少真實世界的應用，其背後面臨的問題都符合強化學習的問題設定。比如說股市預測和商品推薦。

1、股市預測

首先這是一個序列決策，要做出很多的決策，每做一個決策動作都要看當前的股市的狀態如何，動作可以是買、賣，和觀望。

那為什麼這個問題是強化學習問題呢？也有很多序列決策有可能並不是強化學習的問題，我們靠什麼判斷序列決策到底是不是強化學習呢？關鍵因素在於：決策放到環境裡面執行以後，是否會改變這個環境。

在股市交易時，成交的那一刻會決定股價是多少，這相當於決策改變了環境。有時可能很少的交易，也會引起其他投資人對股市的預期，從而影響股市的走勢。

2、另一個例子是商品推薦

為什麼推薦問題也是可以看作它是一個強化學習問題呢？推薦系統會在網頁上放置推薦展品，而用戶的購買行為和推薦行為是有關係的。對於推薦的展品，即使比較普通也可以收到很多客戶瀏覽，而優秀的商品如果沒有被推薦出來則可能無人問津。總的來說，決策會影響整個系統。

3、近期的應用

在處理結構化數據時，比如做自然語言處理、把離散結構的知識庫用到學習系統，會面臨一個問題，即我們面對的語言或者知識庫難以融入可微分模型中。一些研究者最近就想出來一些辦法，把一個句子輸出的詞或知識庫裡面的操作，作為強化學習的動作，這樣通過強化學習一些方法的可微分性納入整個可微分學習系統中來。按照深度學習中比較流行的端到端訓練的說法，強化學習的框架納入進來以後，可把整個系統變成端到端的學習。

大家可能聽到了很多詞，包括MDP，Q-Learning 、還有很多演算法的名字，我在報告里就簡單介紹一下強化學習發展的過程，以及裡面會碰到什麼問題。

強化學習的歷史非常悠久，其中，早期的強化學習和它的一個數學模型MDP有很大關係，我先直觀介紹一下MDP。

• 對MDP的直觀介紹

MDP（Markov Decision Process）裡面有三個詞，其中過程「Process」是代表時間變動的變數，馬爾科夫「Markov」說明這個變動是沒有記憶效應的，下一步往哪兒走只取決於當前狀態。馬爾科夫過程可以用圖來描述，這個圖上的每個點就是這一個狀態。這上面有很多邊，表示它可以做的動作。對於每一個狀態來說，出邊的概率和為1。這是從它的狀態和轉移角度來看的。

我們還可以從時間的角度來看。比如說現在在某個狀態，而到下一時刻，它會根據不同的轉移概率轉移到不同的狀態去。隨著時間的變化而轉移到下一個時刻的狀態去，我們把它稱之為水平（horizon）視角。

• 什麼是穩態分布?

大部分馬爾科夫的過程都會有一個穩態分布，意為當時間很長甚至無窮遠的時候，大部分馬爾科夫都會收斂到一個均衡的分布上，不再隨時間變化。

比如說天氣，今天的天氣是出太陽，確定了出太陽、多雲和下雨的轉移概率以後，可能到30天以後它出太陽、下雨還是多雲的概率和今天是不是出太陽已經沒有關係了，它會收斂到一個確定的概率分布上面去。

• 馬爾科夫回報過程（Markov Reward Process）？

馬爾科夫回報過程是當狀態出現轉移的時候，除了用剛才的轉移概率描述以外，還存在一個獎賞。

假設天氣一直是出太陽的狀態，這樣運行下去以後，我能拿到的總回報是多少。這個總的回報可以用一個符號V來表示。根據之前我們的描述，我們可以有不同的計算方式，比如說全部加起來或者打個折再相加。

怎麼算長期回報？我們從初始狀態開始，按照0.2、0.7、0.1分別轉移到不同的狀態之後，按新的概率，把這個狀態以下總的回報值加起來，就得到這個狀態回報的值。相當於這一步展開以後再部加起來。這就變成一個遞歸式，也就是第0步變成第1步要計算的步驟，第1步又變成第2步要算的步驟。

演算法里有一個加速計算的方式，叫動態規劃，是倒過來算的。

可以理解為，首先設置最後一層（第T層）的V值是0，倒過來算T-1層的V層是多少，再倒過來算T-2的......把這個式子重複T次。

這是走T步的，還有走無窮多步的。我們假設站在無窮大的最後一個點上，這個點照樣每個狀態上面的V都是0，然後算無窮大-1步是多少，無窮大-2步是多少，往後退無窮多步。但是演算法無法實現這個過程，實際上用演算法也不需要退無窮多步，因為存在折扣，即退一定步數以後，這個值就會固定不變。

• 如何形成馬爾科夫決策過程？

對於馬爾科夫過程和馬爾科夫決策過程，我們只能觀察它運行下去的結果，而不能對它的運行過程加以干涉。加上一個決策以後就可以干涉了，這就是馬爾科夫決策過程，不同的動作決定了轉移的概率是不一樣的，所以現在我們可以在每個狀態上選擇不同的動作。

再看馬爾科夫決策過程的水平視角，由於每個狀態可能做不同的動作，所以轉移概率也不同。

總的來說， 馬爾科夫決策過程里有一個四元組，即狀態、動作、獎賞、轉移。

這個四元組和強化學習裡面的四元組一樣的，所以早期的強化學習是完全以MDP為數學基礎的，對它來說也是要找一個策略，這個策略就是選擇不同動作會有不同的概率，或者是確定性策略，在一個狀態就輸出一個動作。

• 早期強化學習的策略和其特點

早期的策略是用表格表示的，表格上記錄了每個狀態下的動作，是一個非常簡單的模型。這個模型在強化學習裡面很常用。在監督學習中，早期也用過這種模型，但由於在真實應用裡面很少用得上，所以很快就被淘汰了。

它的特點是表達能力極強，不過前提是動作和狀態都是離散的。為什麼表達能力極強呢？比如說對於確定性策略，每個狀態下面做什麼動作可以直接修改，而不影響到其他狀態的動作，所以它的表達很靈活。早期強化學習的很多理論都是建立在這種表達上，它雖然不實用，但是理論性質很好。

• 如何求解馬爾科夫決策過程上的最優策略？

我們首先希望在馬爾科夫決策過程上計算出給定策略的總回報。

這和前面講的在馬爾科夫回報過程上計算總回報是一樣的，因為一旦給定策略以後，它的轉移分布已經全部確定了。這就退化成一個馬爾科夫回報過程，即給定一個策略以後我們計算回報方式跟前面一樣。稍微不一樣的一點是，它的轉移是按照策略給出的動作的概率進行的。所以寫V的時候，V右上角寫了一個π，這個π就是表示我們當前固定的策略是什麼，給出了不同的策略以後，我們要算的V值的結果是不一樣的。這個V值表示的含義是，從s這個部分出發，走了很久以後看它的回報是多少。

但如果只是計算V值，從中導出策略不是那麼方便，它表達的是總的回報，但我們想知道的是，在每個狀態上做哪個動作比較好。如果只知道V值的話，是無法直接得知當前的狀態上選擇哪個動作好。只能每個動作嘗試一下，走到下一個狀態，看哪個動作導致的下一個狀態的V值最好的，就用哪一個。這樣比較麻煩。

為了避免麻煩，我們常用Q值函數。Q值函數比V函數多了一個動作輸入，它要估計的是在狀態s做了動作a以後，再跟著這個策略π一直做下去，它的回報是多少。有了Q值函，看到狀態s後，把每個a帶進去，看哪個a出來的Q值大，就用哪個a。所以這樣就可以在當前狀態直接決定用哪個動作了。

Q和V是有直接的對應關係的，如果按照策略來選擇動作，平均的Q值就是V值。

計算最優策略

• 最優策略是否存在？

我們考慮最優策略的時候會想，是否會有一個策略在所有狀態上表現都是最好的，還是只能找到在絕大部分時候表現都最好、但在個別狀態上面值要差一點的策略。實際上前者是存在的，這個結論依賴於一個假設，即策略需要用表格來表示。因為用表格來表示的話，它的表達能力足夠強。

最優策略對應的V值就是最優V值，對應的Q值就是最優Q值，怎麼樣求取最優的策略呢？由於這個V和Q之間是有一定關係的，所以我這裡先直接給出兩個等式，一個是通過Q值來算Q值的，一個是通過V值來算V值的。只要把最優Q和V的關係帶到一般Q和V的關係中就直接可得。

• 最優策略的兩種演算法

有這兩個等式以後，就可以來求取最優策略。

• 第一種方法：首先評估給定一個策略以後，這個策略有多好，然後找一個方向來提高這個策略。

這個演算法的意思是，先計算你給出的這個策略的V值，然後用這種等式來更新這個策略，更新完以後又去計算這個V值是多少，又來更新這個策略，這樣就可以保證這個策略最後收斂到最優策略。當然前提是你使用的是這個表格狀態表示，有窮多個的狀態和有窮多個的動作，這個方式對應的等式就是剛才的第一個等式。這個演算法可能效率比較低，因為它需要不斷的評估更新後的策略。這一方法稱為策略迭代。

• 第二種方法：直接通過V值來更新V值，這一方法稱為值迭代。

根據這兩個等式就可以有兩種計算最優策略的方法。在這裡紀念一下提出者Bellman，實際上動態規劃就是他的發明。

• 最優策略的複雜度是多少？

另外，我們看到這樣一個求解最優策略的過程，它的複雜度是多少呢？它的複雜度是狀態數量乘以動作數量 O(|S|*|A|)，這已經是在一個很簡單的MDP上（確定性 MDP），這個複雜度從狀態數量和動作數量上看，好像是一個線性的複雜度，複雜度並不高。前面我們說了強化學習求解最優策略是NP難的問題，那麼這個差別在什麼地方呢？差別就在於，通常在度量一個問題的複雜度時，並不是根據它有多少狀態來度量的，而是用狀態空間的維度來度量。因此Bellman發明了一個詞叫「維度災難」。如果我們用維度來度量的話，這個複雜度就是一個非常高的複雜度，比如說對於圍棋來說，它的維度是19×19，但是它的有效狀態數量超過了10的170次方。

這裡簡單的介紹了一下在MDP、馬爾科夫決策上，怎麼去求得一個策略。但是MDP並不是強化學習，因為它的四元組都已給出，特別是獎賞和轉移。你任給它一個狀態和動作，都可以算出獎賞值；轉移也是，輸入一個狀態、動作以後，它會告訴你轉移出來的狀態是什麼。

本文為俞揚博士《強化學習前沿》的上篇，下篇敬請關注雷鋒網的後續內容。