理解強化學習知識之基礎知識及MDP

01-29

由於我對RL的期望挺大，很看好它的前景，故之後應該會寫下一個系列的強化學習文章，標題是理解強化學習知識之XX，也就是說，我寫下的是我覺得有必要知道比較重要並容易忽略的知識。也許不會所有強化學習的知識都非常全面的寫，但希望可以對大家有所幫助，同時鞏固我自己的知識！

強化學習是什麼？和監督學習，無監督學習是什麼關係？
強化學習的主要應用是什麼？在其他如NLP的應用呢？
模仿學習是什麼？和強化學習聯繫？
強化學習的整體運行流程是什麼樣的呢？
強化學習的分類
什麼是馬爾可夫(Markov)性？什麼是MP?什麼是MRP？
動態規劃是什麼？為什麼可以利用動態規劃來解決MDP？

強化學習是什麼？和監督學習，無監督學習是什麼關係？

強化學習是什麼：是多學科多領域交叉的一個產物，它的本質就是解決「decision making」問題，即學會自動進行決策。

在計算機科學領域體現為機器學習演算法。
在工程領域體現在決定操作動作的順序來得到最好的結果。
在神經科學領域體現在理解人類大腦如何做出決策，主要的研究是獎勵機制。

在心理學領域，研究動物如何做出決策，動物的行為是由什麼導致的。
在經濟學領域體現在博弈論的研究。
.......

它是什麼可以是如圖所示：

以上所有的問題最終都歸結為一個問題，人為什麼能夠並且如何做出最優決策。是怎麼樣找到最優決策的

然後，它和監督學習，無監督學習是什麼關係？

機器學習包括：監督學習、無監督學習、強化學習，故強化學習是機器學習的一個分支，和監督，無監督是並列關係。

無監督學習和強化學習的區別應該容易知道，下面說說監督學習和強化學習的區別，從強化學習的特點出發：

強化學習沒有監督數據、只有獎勵信號
獎勵信號不一定是實時的，而很可能是延後的，有時甚至延後很多。且時間（序列）是一個重要因素。
強化學習面對的輸入(狀態)總是在變化且不獨立，輸入不像監督學習是獨立同分布的。而每當演算法做出一個行為，它影響了下一次決策的輸入，我認為這點是最重要的區別。

強化學習的主要應用是什麼？在其他領域如NLP的應用呢？

首先強化學習現有具有非常廣泛的應用：直升機特技飛行、經典遊戲、投資管理、發電站控制、讓機器人模仿人類行走等等。

強化學習現有在nlp的應用：文本序列生成，對話策略決策，用戶目標模擬等等。

強化學習現有在cv的應用：強化學習的Attention方法在圖像的應用，強化學習潤色照片等等

然後我認為強化學習在nlp或cv領域是有很大前景的！為什麼？

比如強化學習是天然可以在NLP上應用的：

在離散空間的文本生成和序列決策，RL有先天的對應，也就是說，通過agent在離散策略空間的搜索生成下一個詞或者序列，結合reward的反饋，是可以很好的work的。
先舉個例子，在goal oriented的對話系統的，關鍵步驟就是決策下一輪對話agent該幹什麼（提問？確認？結束？），那就可以利用RL的方法來決策。而RL的本質無非就是結合環境的觀測加上reward的引導做出下一步的決策。
最後是RL的優勢：可以克服其他目標函數如MLE的缺陷，可以模擬大量樣本，或者藉助先前經驗進行學習（如DQN）等等。

cv的話我不是很了解，但也有一些應用RL的論文，只要轉為狀態到決策問題，應該都是可以做的。

模仿學習是什麼？和強化學習有什麼區別和聯繫？

模仿學習：是指從示教者提供的範例中學習，一般提供人類專家的決策數據 $left{ tau_1,tau_2,ldots,tau_m right}$ ，每個決策包含狀態和動作序列 $tau_i = <s_1^i,a_1^i,s_2^i,a_2^i,ldots,s_{n_ni+1}^i>$ ，將所有「狀態-動作對」抽取出來構造新的集合 $mathcal{D}=left{ (s_1,a_1),(s_2,a_2),(s_3,a_3),ldots right}$ 。然後把狀態作為特徵（feature），動作作為標記（label）進行分類（對於離散動作）或回歸（對於連續動作）的學習從而得到最優策略模型。

舉個CS249（是門好課）的例子，如果我們想讓機器學會開車，一個很直接的想法是觀察人類行為，並且模仿人類，在相應觀測下做出人類所做行為。將這個想法實現起來也很簡單，只需要收集該任務的一些觀測（路面的畫面），以及每個觀測人類會做出的反應（轉動方向盤），然後像監督學習一樣訓練一個神經網路，以觀測為輸入，人類行為為標籤，其中行為是離散時是分類任務，連續時是回歸任務：

然而這簡單的監督學習理論上並不可行，一個直觀的原因是由於現實的隨機性或者複雜性，使得機器所採用的動作和人類的動作有偏差或者動作所產生的結果有偏差，這樣在有偏差的下一狀態，機器還會做出有偏差的動作，使得之後狀態的偏差積累，導致機器遇到監督學習時沒有碰到過的狀態，那機器就完全不知道該怎麼做了,也就是如下圖所示：

當然若我們希望希望 $p_{data}(o_t)=p_{pi_{theta}}(o_t)$ 來解決學習時和實際操作時的 $o_t$ 的分布不同，我們可以用很多方法比如DAgger演算法。但即使用了一些方法，模仿學習始終有這些問題：

需要人類提供的大量數據（尤其是深度學習，需要大量樣本）。
人類對一些任務也做的不太好，對於一些複雜任務，人類能做出的動作有限。
我們希望機器能自動學習，即能不斷地在錯誤中自我完善，而不需要人類的指導。

也就是說，直接用模仿學習來解決實際問題很多時候可能比強化學習弱，但是在有些方面比如解決多步決策（sequential decision）中，因學習器不能頻繁地得到獎勵，且這種基於累積獎賞及學習方式存在非常巨大的搜索空間，傳統的強化學習不能很好的解決問題。而我們先通過模仿學習學得初始策略模型，然後在通過強化學習改進模型，獲得更好的策略，就可以較好地解決多步決策問題。更多關於模仿學習的的知識，比如逆強化學習什麼的，之後我也可能會寫，這裡先推薦一篇文章吧，有興趣可以了解。

強化學習的運行流程

圖來自網上

如上圖。對於agent：我們構造出一個agent(圖中的大腦部分)，agent能夠執行某個策略動作（action），例如決定機器人朝哪個方向走，圍棋棋子下在哪個位置。agent能夠接收當前環境(圖中的地球部分)的一個observation。注意，這裡的假設observation是完全的，例如當前對圍棋盤上的已下棋的觀測。agent還能接收當它執行某個action後的reward，即在第t步agent的工作流程是執行一個動作 $A_t$ ，獲得該動作之後的環境觀測狀況 $O_t$ ，以及獲得這個動作的反饋獎賞 $R_t$ 。

對於環境：環境environment(圖中的地球部分)則是agent交互的對象，它是一個行為不可控制的對象，agent一開始不知道環境會對不同action做出什麼樣的反應，而環境會通過observation告訴agent當前的環境狀態，同時環境能夠根據可能的最終結果反饋給agent一個reward。例如圍棋棋面就是一個環境，它可以根據當前的棋面狀況估計一下黑白雙方輸贏的比例。因而在第t步，environment的工作流程是接收一個 $A_t$ ，對這個動作做出反應之後傳遞環境狀況和評估的reward給agent。reward獎賞 $R_t$ ，是一個反饋標量值，它表明了在第t步agent做出的決策有多好或者有多不好，而整個強化學習優化的目標就是最大化累積reward。

強化學習的分類

分類要好好多說下，因為強化學習中的演算法很多，從不同的角度歸類的方式也很多，搞清楚什麼什麼演算法是一類的，有助於我們的記憶和理解。首先如圖：

圖來自網上

強化學習演算法可分為策略優化方法和動態規劃優化兩大類。其中策略優化方法又分為進化演算法和策略梯度方法；動態規劃方法分為策略迭代演算法和值迭代演算法。策略迭代演算法和值迭代演算法可以利用廣義策略迭代方法進行統一描述。

根據轉移概率是否已知和某個動作帶來的獎勵可以分為基於模型的強化學習演算法和無模型的強化學習演算法。

需要注意的是值迭代和策略迭代是基於模型的（base model）的，也就是基於模型的，而蒙特卡洛樹搜索或者其他base model是兩個不一樣的base model的，前者是實實在在的了解環境，在對環境有所了解的基礎上（體現在知道等）建模。而後者是用「想像力對環境進行建模」，也就是多出了一個虛擬環境。

上面一圖算是一個總結，注意根據model是否free分和以值函數和策略優化分是兩回事，他們是有交叉的。

同時，強化學習演算法根據策略是否是隨機的，分為確定性策略強化學習和隨機性策略強化學習。另外，強化學習演算法中的回報函數十分關鍵，根據回報函數是否已知，可以分為強化學習和逆向強化學習。逆向強化學習是根據專家實例將回報函數學出來。

什麼是馬爾可夫(Markov)性？什麼是MP?什麼是MRP？

馬爾可夫性：所謂馬爾科夫性是指系統的下一個狀態 $s_{t+1}$ 僅與當前狀態 $s_t$ 有關，而與以前的狀態無關。用公式表示的話，則為：狀態 $s_t$ 是馬爾科夫的，當且僅當 $[ Pleft[s_{t+1}|s_tright]=Pleft[s_{t+1}|s_1,cdots ,s_tright] ]$ 。

換句話說，當前狀態 $s_t$ 其實是蘊含了所有相關的歷史信息 $s_1,cdots ,s_t$ ，一旦當前狀態已知，歷史信息將會被拋棄。簡單來說，未來只和當前有關，當我們需要去決策未來時，只需要在當下的基礎上去估計，因為當下已經包含之前的所有歷史。

注意：馬爾可夫性描述的是每個狀態的性質，但真正有用的是如何描述一個狀態序列。數學中用來描述隨機變數序列的學科叫隨機過程。所謂隨機過程就是指隨機變數序列。若隨機變數序列中的每個狀態都是馬爾可夫的則稱此隨機過程為馬爾可夫隨機過程。下面說下各種馬爾可夫隨機過程

馬爾可夫鏈/過程(Markov Chain/Process)，是具有馬爾可夫(markov)性質的隨機狀態 $s_1,s_2,…$ 序列。由[S,P]組成。其中S表示狀態，P表示狀態轉移概率。

下面舉例下David Silver公開課中的例子

如下圖1圓圈內是狀態，箭頭上的值是狀態之間的轉移概率。class指上第幾堂課，facebook指看facebook網頁，可以看成上網玩耍，pub指去酒吧，pass指通過考試，sleep指睡覺。例如處於class1有0.5的概率轉移到class2，或者0.5的概率轉移到facebook。

從給定的條件中，可以產生非常多的隨機序列，例如C1 C2 C3 Pass Sleep或者C1 FB FB C1 C2 C3 Pub C1 FB FB FB C1 C2 C3 Pub C2 Sleep等。這些隨機狀態的序列就是馬爾可夫鏈/過程。

馬爾可夫獎賞過程(Markov Reward Process)，即馬爾可夫過程加上價值估計(value judgement)，即判斷一個像上面一個特定的隨機序列有多少累積reward，也就是計算出v(s)。它由[S,P,R,γ]組成，R表示估計價值，或者叫即刻價值(immediate reward)，它由當前的狀態決定。然後複習下必要概念: $G_t$ 是t時刻之後未來執行一組action能夠獲得的reward，因未來具有不確定性，故加入一個γ∈[0,1]，其中：

我們知道，一個馬爾科夫獎勵過程中某一狀態的價值函數為從該狀態開始的馬爾可夫鏈收穫的期望：

$v(s) = E [ G_{t} | S_{t} = s ]$ ，也就是說，v(s)是可以用一系列馬爾可夫過程然後計算其收穫期望得到的，但這裡的系列"需要太多"，接近無窮才能夠得到其期望的值，這樣算是不科學的，故下面就經過推導，使得v(s) 通過已給定R和γ就可以算出，只是算的方式有很多不同對應不同的方法。

先繼續舉出David Silver公開課中的例子，示意圖如下。

可以看出比圖1多了紅色部分即R，但是R的取值只決定了immediate reward，在實際過程中肯定是需要考慮到後面步驟的reward才能確定當前的選擇是否正確。而實際上v(s)由兩部分組成，一個是immediate reward，一個是後續狀態產生的discounted reward。由

這個推導過程相對簡單，僅在導出最後一行時，將 $G_{t+1}$ 變成了 $v(S_{t+1})$ 。其理由是收穫的期望等於收穫的期望的期望。先說說貝爾曼（Bellman）方程：指是用動態規劃（Dynamic Programming）解決這些數學最佳化方法能夠達到最佳化的必要條件。此方程把「決策問題在特定時間怎麼的值」以「來自初始選擇的報酬比從初始選擇衍生的決策問題的值」的形式表示。下式是針對MRP的Bellman方程：

通過方程可以看出 $v(s)$ 由兩部分組成，一是該狀態的即時獎勵期望，即時獎勵期望等於即時獎勵，因為根據即時獎勵的定義，它與下一個狀態無關；另一個是下一時刻狀態的價值期望，可以根據下一時刻狀態的概率分布得到其期望。如果用s』表示s狀態下一時刻任一可能的狀態，那麼Bellman方程可以寫成：

那麼每一個狀態下能得到的狀態值函數取值或者說累積reward如下所示，即原來寫著class、sleep狀態的地方替換成了數字(這裡假設γ=1γ=1)。可以從sleep狀態出發，推導出每個狀態的狀態值函數取值，如右上角紅色公式所示。最右的-23與-13，列出二元一次方程組即可求出。

將Bellman方程表達成矩陣形式，變成了 $v=ER+γPv$ ，是個線性等式，直接求解得到 $v=(I?γP)^{-1}R$ 。而這樣求解的話計算複雜度是 $O(n^3)$ ，所以一般通過動態規劃、蒙特卡洛估計與Temporal-Difference learning這些迭代的方式求解。

馬爾可夫決策過程(Markov Decision Process)：它是擁有決策能力的馬爾可夫獎賞過程，馬爾可夫決策過程的組成包括 $M = <S, A, P, R, gamma>$ 和一個策略π，同時，相對的狀態序列 $S_{1},S_{2},...$ 是一個馬爾科夫過程 $<S, P^{pi}>$ ；樣，狀態和獎勵序列 $S_{1}, R_{2}, S_{2}, R_{3}, S_{3}, ...$ 是一個馬爾科夫獎勵過程 $<S, P^{pi}, R^{pi}, gamma>$ 。

與之前MP和MRP不同的是，MDP擁有兩個值函數，分別是狀態價值函數 $v_pi(s)$ 表示在遵循當前策略π時，個體（agent）處在狀態s時的價值大小，和行為價值函數 $q_{pi}(s,a)$ 。表示在遵循當前策略π時，個體（agent）在當前狀態執行行為a的價值大小，根據這兩個值函數的定義，它們之間的關係表示為

上面的式子表明在遵循策略π時，狀態s的價值體現為在該狀態下遵循某一策略而採取所有可能行為的價值按行為發生概率的乘積求和。
下面的式子表明某一個狀態下採取一個行為的價值，可以分為兩部分：其一是離開這個狀態的價值，其二是所有進入新的狀態的價值於其轉移概率乘積的和。

而將兩個式子互相代入，可以得到如下的Bellman期望方程：

還是原來的例子，一個MDP的例子，箭頭上的單詞表示action，與MRP不同的是，這裡給出的immediate reward是同時在某個狀態s和某個動作a條件下，所以圖中R不是只取決於s，而是取決於s和a。右上角的等式表達出了這一個狀態的狀態值函數求解過程。

然後由於策略是 $pi(a|s)$ 是可以改變的，因此兩個值函數的取值不像MRP一樣是固定的，而是能從不同的取值中找到一個最大值即最優值函數。而我們的目的是為了得到最優策略，這裡先提一下相關必要定理：

（1）所有的最優策略有相同的最優價值函數，也就是找到最優值函數，也就能對應找到最好策略。
（2）存在至少一個最優策略，比任何其他策略更好，而且所有的最優策略具有相同的行為價值函數。

上面提出MDP有兩個值函數，對應的，最優值函數表示為 $v_*(s)$ 指在從所有策略產生的狀態價值函數中，選取使狀態s價值最大的函數，公式表示為： $v_{*} = max_{pi} v_{pi}(s)$ ；最優行為價值函數 $q_{*}(s,a)$ 指的是從所有策略產生的行為價值函數中，選取是狀態行為對 $<s,a>$ 價值最大的函數，公式表示為 $q_{*}(s,a) = max_{pi} q_{pi}(s,a)$ 。

如果知道了 $q_{*}(s,a)$ 那麼也就知道了在每一步選擇過程中應該選擇什麼樣的動作。也就是說MDP需要解決的問題並不是每一步到底會獲得多少累積reward，而是找到一個最優的解決方案。同時兩個最優值函數同樣存在著一定關係，如下所示：

同樣的，第一個式子說明一個狀態的最優價值等於從該狀態出發採取的所有行為產生的行為價值中最大的那個行為價值：
第二個式子說明在某個狀態s下，採取某個行為的最優價值由2部分組成，一部分是離開狀態 s 的即刻獎勵，另一部分則是所有能到達的狀態 s』的最優狀態價值按出現概率求和。

同非最優方程類似，有以下Bellman優化方程：

最後，注意Bellman最優方程是非線性的，沒有固定的解決方案，通過一些迭代方法來解決：價值迭代、策略迭代、Q學習、Sarsa等。後面會講。

動態規劃是什麼？為什麼可以利用動態規劃來解決MDP？

動態規劃演算法的基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，而最後一個子問題就是初始問題的解。簡單來說，動態規劃演算法是通過拆分問題，定義問題狀態和狀態之間的關係，使得問題能夠以遞推（或者說分治）的方式去解決。

舉一個動態規劃中簡單又經典的例子：

給定一個數列，長度為N，求這個數列的最長上升（遞增）子數列（LIS）的長度.比如5，3，4，8，6，7為例。答案是這個數列的最長遞增子數列是 3,4,6,7，長度為4.

但是怎麼求，可能比較短的數列是比較好求的，（一眼就可以看出），但是當數列很長之後，問題也就變得複雜了，下面我們用動態規劃的思想去求解：

我們先重新定義問題：定一個數列，長度為N，設 $F_{k}$ 為：以數列中第k項結尾的最長遞增子序列的長度.求 $F_{1}..F_{N}$ 中的最大值.按照這樣的定義方式，然後再用遞推的方式求解，如下所示：

前1個數的LIS長度d(1)=1(序列：5)
前2個數的LIS長度d(2)=1(序列：3或者5)，這個依賴前1個數的解
前3個數的LIS長度d(3)=2(序列：3，4)，這個依賴前2個數的解

前4個數的LIS長度d(4)=3(序列：3，4，8；) ，這個依賴前3個數的解
....
最後得答案前6個數的最長遞增子數列是 3,4,6,7，長度為4.

注意：這個例子的求解中重新定義問題的方式有很多種，上面只是其中一種，而動態規劃的核心也如何拆分和重新定義問題，然後用遞推（或者說分治）的方式去解決。

怎麼利用動態規劃來解決MDP？首先，從上文可以總結出利用動態規劃可以解決的問題需要滿足兩個條件：（1）整個優化問題可以分解為多個子優化問題，並且解決了所有子問題後表示原問題也已經解決（2）子優化問題的解可以被存儲和重複利用。

然後，對應我們之前講的MDP，我們先定義兩個概念：

預測：表示給定一個MDP $<S, A, P, R, gamma>$ 和策略 $pi$ ，或者給定一個MRP $<S, P^{pi}, R^{pi}, gamma>$ ，要求輸出基於當前策略π的價值函數 $V_{pi}$ 。對應的，就是解決計算MDP中Bellman期望方程

控制：表示給定一個MDP $<S, A, P, R, gamma>$ ，要求確定最優價值函數 $V_{*}$ 和最優策略 $pi_{*}$ ，對應的，就是解決計算MDP中Bellman優化方程找到最佳策略。

對於預測，不使用直接求解的方式，因為複雜度太高或不能直接求解，我們發現是可以把整個問題分成每一次對整體的環境遵循一次給定策略執行來更新 $V_{pi}$ 的。也就是說，整個預測的問題可以分解成多個子問題，符合條件（1），然後我們可以把上一次執行策略後得到的值函數的值儲存並作為已知條件給下一次執行策略的計算值函數。這個符合上面的條件（2）。也就是說，對於預測，我們是可以用動態規劃解決的。

具體來說，對於 $v_{k}(S)$ ，我們可以使用如下公式進行迭代，也就是對應動態規劃中的後一個子問題求解用到前一個子問題的解的公式。

$v_{k+1}(s) = sum_{a in A}pi(a|s)(R^a_s + gamma sum_{s in S}P^a_{ss}v_k(s))$

對於控制，同預測一樣，也是在動態規劃的基礎上，分為兩種方式，分別為策略迭代：尋找最優策略問題則先在給定或隨機策略下計算狀態價值函數，根據狀態函數貪婪更新策略，多次反覆找到最優策略；價值迭代：單純使用價值迭代，全程沒有策略參與也可以獲得最優策略，但需要知道狀態轉移矩陣，即狀態s在行為a後到達的所有後續狀態及概率。而具體公式如下：

價值迭代：

策略迭代：

其中的 $V^π$ ：

以上是利用動態規劃的思想來解決基於模型的強化學習，也就是說 $P,R,gamma$ 是已知的，但通常實際情況中，更多的是無模型的，也就是不清楚做出了某個action之後會變到哪一個state也不知道這個action好還是不好， $P,R,gamma$ 都是未知的，那無模型的怎麼解決呢？敬請期待下期！