0
| 本文作者： 奕欣 | 2017-05-09 16:49 |
雷鋒網［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）
三、從馬爾可夫決策過程到強化學習（from Markov Decision Process to Reinforce Learning）
四、值函數估計（Value function approximation）
五、策略搜索（Policy Search）
六、游戲中的強化學習（Reinforcement Learning in Games）
七、強化學習總結
八、強化學習資源推薦
以下為俞揚博士的演講正文：
大家好,我會盡量通過直觀的方式簡單的介紹一下強化學習的三個問題。由于水平有限，所以難免會有一些不足或者不到位的地方，請大家指正。
第一，強化學習到底是什么？
第二，強化學習有哪幾類算法？這幾類算法的思路是什么？
第三，強化學習能用在什么地方？應用時會遇到什么限制？
現在大家都在說人工智能，雖然可能難以精確的說清楚到底什么叫做智能，但我們知道擁有智能會有一些聰明的表現。例如像犬等一些動物，我們可能會認為是有一定智能的，我們可以訓練一只幼犬聽懂飼養員的指令。訓練方法是：飼養員手里拿著食物，然后說“坐下”，當幼犬做出符合要求的動作時，就把食物給它。反復進行訓練，大概半小時的時間，它就學會聽見“坐下”的命令就坐下。這個過程就是動物的學習過程，它的智能就表現在它能在一定時間內發現如何適應環境，獲得食物獎賞。
在很早之前，就有許多學者在想能不能讓計算機也做到相同的事情，自動發現如何適應環境，這也就是我們今天說的強化學習。有這么一種說法，說“強化學習是真正的人工智能”。我們現在不評價這句話講的合適不合適，至少，強化目的是希望機器能和動物一樣，有較好的適應環境的能力。
強化學習名字的由來
這里先解釋一下強化學習這個名字。為什么叫強化學習呢？因為這個過程是不斷的重復、不斷強化認知，英文Reinforcement Learning 中的 Reinforcement 更準確的中文翻譯也是“強化”。
類比強化學習和動物學習
訓練幼犬的過程有兩個要素：
飼養員需要對幼犬發出指令，比如讓它“坐著”，
飼養員手中有動物非常想要的東西，即獎賞。對狗來說，獎賞就是食物。
對于智能體（Agent，即計算機）來說，我們希望通過類似的方法能夠訓練智能體，我們把其中的要素抽象出來，可以用下面這個圖來表示：
現在智能體處于一個很暗的環境之中，意思是它并不知道這個環境里面到底是什么，這也是我們希望計算機通過強化學習能做到的事——把它扔到一個未知的環境里面，它能夠通過和環境打交道來適應這個環境，學習到做什么動作才是最好的。
Agent能夠從環境里面觀測到的東西有兩個：
狀態。它能夠觀測到的環境和它自己的狀態；
獎賞。當它做出一定動作以后，這個環境可能會給它一個獎賞。
它根據觀察到的狀態做出的行動，叫做動作或決策；這個動作放到環境里以后，會在環境里被執行；執行以后，環境會發生變化。
總體來說，如果按照剛才的要素把它刻畫出來，它對應的變量有：動作的集合、狀態的集合，獎賞函數，以及做完一個動作以后，決定環境會發生什么變化的轉移函數。
對于Agent來說，自身具備的選擇決策的能力，叫做策略。這個策略意思就是，觀測到了環境現在處于什么狀態，而選擇做出什么動作出來。這里的策略和監督學習里的模型其實是一回事。
從智能體的視角來看它所處的環境，以及它所做的動作
剛睜開眼睛的時候，它看到的環境是一個初始狀態。
根據這個狀態，智能體做了一個動作。我們把策略寫成π，π會根據當前的狀態選擇一個動作，然后到環境中去具體執行。
執行了以后，這個環境會發生狀態轉移（Transition），變到下一個狀態。同時，也會反饋給智能體一個回報或者獎賞（Reward）。
最后，智能體繼續根據新的狀態來決定它下面做什么樣的動作。
所以從智能體的視角來看，即看到什么狀態，然后決定做一個相應的動作并會收到回報，然后又在下一個狀態做一個動作并收到一個回報，這樣一直下去。
所以大家可以很明確地看到：
第一，這個智能體不是做一次決策就完成了學習的過程。實際上，它要做的是一個序列的決策。
第二，我們怎么評判智能體策略的好壞呢？一般評判的形式就是，它能拿到的獎賞會有多大。每一步都可能有獎賞，所以評判的形式是把總的獎賞加起來看看它有多大。
長期累積獎賞有好幾種計數法，比如我們可以把總的T步將上全部加起來，或者用折扣（discounted）的方法，可以讓它走無窮多步，但是不是按照原數值加起來，而是要考慮權重，這個權重會因時間的流逝而產生折扣。
在算總獎賞的時候，為什么要考慮權重？
一方面，是因為在數學上比較好處理；另外一方面，是說在很多真實的應用里邊，我們對未來的價值的估計有可能是折扣的。舉例說明：
如果你今天能夠賺到100塊，或者下個月能夠賺到200塊，在這兩個決策里面你要選一個，你可能會選擇今天就拿這100塊錢，將來對你來說可能會比較穩妥，下個月發生的事情還不知道會怎么回事，所以在有的應用里邊會考慮折扣，但需要在不同的應用中考慮具體的需求。
智能體要做的事，就是找一個能夠帶來最大的長期累積獎賞的策略。
通過設置獎賞，我們可以定義智能體，讓它去做不同的事情。就像剛才訓練這只幼犬一樣，我們通過給它一個吃的，可以讓它做趴下的動作，也可以讓它做站起來的動作。
尋找最優策略的兩個例子
實際上強化學習的框架只是一個一般的框架，這個框架可以包含很多很多問題在里面。下面舉兩個例子。
第一個例子：尋找最短路徑的問題。
條件如下圖所示，我們要找一條從s到t的最短路徑。這是很簡單的問題，這里演示把最短路徑變成強化學習的問題去解決，我們可以這樣做：
先定義狀態和動作：
把每個節點當成是一個狀態；
把每個節點上面連著的邊，當作這個狀態下面可以做的動作。
定義好了狀態和動作，我們就要找最短路徑，也就是要找到路徑的權重和加權最小。
通常強化學習是讓獎賞最大化，因此這里把路徑上的權重先取一個負的值，讓它最大化這個負的值。稍微做一點變化的是，t會指出來一個單獨的繞自己循環的節點。
接下來，就開始找最優策略。我們先假設能夠找到最優的策略。最優的策略是什么呢？就是從s開始，我們選擇每一步從哪一條邊走出去，能使總的獎賞最大。我們看到這里有一個100，這是很大的，所以一定能走到t去，除掉100這個意外情況，上圖加粗線所示路徑的獎賞應該是最大的。
對于最優的策略來說，它們對應的就是一個最優的路徑，我們這里先不管最優的策略怎么求解。
第二個例子：最大化任意函數
我們展示了怎么用強化學習來解決最短路徑這個問題；除此之外，強化學習還可以包容很多其他問題。
比如，我們要在0、1的N維空間里面最大化一個函數f。這不是一個容易解決的問題，特別是沒有規定這個f是什么，換句話說這個f是什么都可以。
這個問題也可以變成一個強化學習的問題，怎么變呢？
我設定初始的狀態里邊是空集；這個時候有兩個動作，往左走是加一個0，往右走是加一個1，0再往左走再加一個0，再往右走再加一個1；走出N層以后最上面這層就是0、1空間里面所有的組合，對應所有可能的解。
我們還要設定一個獎賞——中間每一層獎賞都是0，只有最后一層的獎賞是F。這就會使得，如果有一個最優的強化學習的策略，能夠找到最優的路徑到達節點，那么它就能使得這個獎賞最大、F最大。
通過這個例子，我想表達一個觀點——如果我們面對的這個學習問題比較簡單，就沒必要用強化學習。不能因為它自己在市面上比較火，而把以往的一些問題換成用強化學習的方法來解決。
總結一下，強化學習和規劃哪里不同？
第一，強化學習看到的世界一個黑箱子，而對于規劃而言，這個世界卻是很清楚的。比如我們的最短路徑，所有的節點、便點、權重點都是已知的；而對于強化學習，狀態如何轉移、邊的權制是多少、甚至有哪些狀態都需要自己探索、發現。
第二，規劃的問題可能就是一個解、一個路徑；而強化學習的解是一個模型。和監督學習一樣，只要輸入任意一個狀態，強化學習都會告訴你應該做什么決策。因此，除了給出最優路徑上的每一個狀態、每一個節點應該往哪邊走以外，實際上任何一個節點都能告訴我從這個節點到目標去應該怎么走。
剛才說到強化學習和監督學習有很多相似的地方，比如說模型實際上是一樣的。那它們之間有何差異呢？
監督學習總的來說是一個開環的學習。
通常，監督學習任務會從環境中收集一批數據；
接著我們用監督學習算法從數據中產生模型；
最后就可以用這個模型來做預測了。
但是對于強化學習來說，它面對的是一個閉環的學習。
首先，也是從環境中產生數據；
用強化學習的算法從數據中產生模型；
還要把模型放回到環境中運行，接著又會產生新的數據出來，再重復以上步驟。
因此從大體上看，兩者的主要區別，一個是開環學習，一個是閉環學習。這點不一樣就帶來了很多具體區別：
首先，在監督學習里，數據是分成觀測的特征值和一個標記。這個標記的含義是，看到這樣一個觀測的值、特征以后，應該做出什么樣的預測。
但是在強化學習里面，這個數據首先是一個序列，做了一個動作以后下面又到了什么狀態，有一個反饋值，并且有了新的狀態。這個序列里面雖然有反饋獎賞，但這個獎賞并不能告訴我們應該做什么樣的動作，而只是對現在的策略有一個評估值，我們把所有獎賞加起來作為當前策略的一個評估，可以得知策略做的有多好，但并不知道應該做什么樣的動作是最好的，這個也是數據上的兩個差別。
另外，強化學習的算法和監督學習的算法也是不一樣的。兩者的模型可能是一樣的。監督學習里面可以是一個決策樹，也可以是一個神經網絡，也可以是一個模型，在強化學習里也是一樣。
總結起來，兩者最核心的區別，在于強化學習需考慮自身對環境的影響。
經典應用
由于強化學習做的是序列的預測和序列的學習，所以它以往主要的一個應用領域，是做機器控制，比如說直升機的操控。
在直升機的應用里面，智能體就是直升機，環境是其飛行空域，狀態可以是直升機的高度、速度、姿態等等，采取的決策是操縱桿指令。我們希望直升機能夠做出我們想要的軌跡，但是又不會掉下來。這些目標可以作為直升機的獎賞，讓它來學習一個策略，以實時控制直升機的運動。
更多的應用
有不少真實世界的應用，其背后面臨的問題都符合強化學習的問題設定。比如說股市預測和商品推薦。
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并不是強化學習，因為它的四元組都已給出，特別是獎賞和轉移。你任給它一個狀態和動作，都可以算出獎賞值；轉移也是，輸入一個狀態、動作以后，它會告訴你轉移出來的狀態是什么。
本文為俞揚博士《強化學習前沿》的上篇，下篇敬請關注雷鋒網的后續內容。
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
