【文章內容簡介】 和瞬時獎懲之間的狀態(tài)值函數(shù)。即： 21 2 3 10kt t t t t kkR r r r r? ? ??? ? ? ? ??? ? ? ? ? ? () 這里 ? 錯誤 !未找到引用源。 是一個參數(shù)， 錯誤 !未找到引用源。 ，稱為折扣率。 ( ) { }ttV s E R s s? ??? }{0 1ssrE tk ktk ?? ??? ???? }{ 0 21 ssrrE tk ktkt ??? ??? ??? ??? ? ?? ?????? ??? ??? ??39。 10 239。39。 }39。{),( s tk ktkassassa ssrERPas ??? ? ?? ?? 39。 39。39。 )]39。([),( s assassa sVRPas ??? () 根據(jù) Bellman 最優(yōu)策略公式，在最優(yōu)策略 *? 下，其值函數(shù)的定義如下： },)({m a x)( 1*1)(* aasssVrEsV ttttsAa ???? ??? ? ? ?? ? 39。 *39。39。)( )]39。([m a x s assasssAa sVRP ? () 馬爾可夫決策過程 (MDP) 在理想狀況下，往往希望一個狀態(tài)能夠簡練地抽象總結過去的感覺，然而這種方式又能保留所有相關信息。正常的來說，這比只要求即時感覺要求得更多，但是比要求全部的過去感知歷史要少得多。一個成功保留所有相關信息的狀態(tài)信號稱為馬爾可夫的，或者說具有馬爾可夫性質。比如，一個棋子的位置 —— 當前的在棋盤上所有棋子的結構 —— 將作為一個馬爾可夫狀態(tài)，因為它匯集了所有關于引導它完成位置序列的重要的東西。雖然關于這個 序列的很多信息丟失了，但是所有有關于這個游戲的最重要的東西被保留下來了。 對于所有在過去事件中的 39。s ， r ， 和所有的可能值： 1 1 1 0 0, , , , , ... , , ,t t t t ts a r s a r s a?? 來說，如果狀態(tài)信號有馬爾可夫特性，那么環(huán)境在 1t? 的響應只取決于在 t 時刻的狀態(tài)和動作的表示，在此情況下，環(huán)境和任務是一體的，都稱為具有 馬爾可夫性質，環(huán)境的動態(tài)量可以定義為： 1 1 ,P r { 39。, | }t t t ts s r r s a???? () 蘇州大學本科生畢業(yè)設計（論文） 8 滿足馬爾可夫性質的強化學習任務被稱為是馬爾可夫決策過程或者 MDP。很多強化學習問題基于的一個關鍵假設就是 Agent 與環(huán)境之間的交互可以被看成一個馬爾可夫決策過程 (MDP)，因此強化學習的研究主要集中于對 Markov 的問題處理。 Markov 決策過程的模型可以用一個四元組 ? ?RTAS , 表示： S 為可能的狀態(tài)集合， A為可能的動作集合， TAST ??: 是狀態(tài)轉移函數(shù)； RASR ??: 是獎賞函數(shù) [1]。在每一個時間步 k ，環(huán)境處于狀態(tài)集合 S 中的某狀態(tài) kx ， Agent 選擇動作集合 A 中的一個動作 ka ，收到即時獎賞 kr ，并轉移至下一狀態(tài) ky 。狀態(tài)轉移函數(shù) ),( kkk yaxT 表示在狀態(tài) kx 執(zhí)行動作 ka 轉移到狀態(tài) ky 的概率可以用 )( kyx aPkk表示。狀態(tài)轉移函數(shù)和獎賞函數(shù)都是隨機的。Agent 目標就是尋求一個最優(yōu)控 制策略，使值函數(shù)最大 [12]。 強化學習的基本算法 大多數(shù)關于強化學習的方法研究都是建立在 MDP 理論框架之上的，通過 MDP 建模，強化學習問題一般可采用迭代技術更新值函數(shù)的估計值來獲得最優(yōu)策略。當前狀態(tài)向下一狀態(tài)轉移的概率和獎賞值只取決于當前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關。根據(jù)在學習過程中 Agent 是否需要學習 MDP 知識，強化學習可以分為模型無關法(modelfree)和基于模型法 (modelbase)。動態(tài)規(guī)劃屬于基于模型法，而蒙特卡羅算法則屬于模型無關法。 動態(tài)規(guī)劃 (Dynamic Programming, DP) 動態(tài)規(guī)劃方法是利用值函數(shù)來搜索好的策略方法，適用于解決大規(guī)模問題，設環(huán)境是一個有限馬爾可夫集，對任意策略 ? ， 如果環(huán)境的動態(tài)信息完全知道，如：策略 ? 和 39。assR ，39。assP 已經知道，為了減少計算量，我們常用值迭代法來近似求出 0V , 1V , 2V ??，其更新公式為： 1 1 1( ) { ( ) | }k t k t tV s E r V s s s? ?? ? ?? ? ? 39。39。( , ) [ ( 39。) ]aass ss kass a P R V s?????? () 常規(guī)的動態(tài)規(guī)劃方法主要有以下三種方法 :第一種是值函數(shù)迭代法，其本質是有限時段的動態(tài)規(guī)劃算法在無限時段上的推廣，是一種逐次逼近算法，該算法與強化學習有著密切的聯(lián)系；第二種是策略迭代，這是一種基于 Bellman 最優(yōu)方程的算法；第三種是改進的策略迭代法，綜合了前面兩種算法，也稱為一般化策略迭代法，是許多強化學習算法的基本思想的來源之一 [13]。 動態(tài)規(guī)劃算法的局限性是明顯的，它容易出現(xiàn)“維數(shù)災”和“建模災”問題。其計算量會使狀態(tài)變量的數(shù)量呈指數(shù)增長；它要求事先知道系統(tǒng)的確切模型信息，如 39。assR 和 39。assP 的蘇州大學本科生畢業(yè)設計（論文） 9 值，而在實際的大規(guī)模隨機問題中，系統(tǒng)的確切模型信息通常是難以獲得且不易計算的。 蒙特卡羅算法 (Monte Carlo method, MC) 蒙特卡羅算法是一種無模型 (modelfree) 的學習方法，不需要系統(tǒng)模型 —— 狀態(tài)轉移函數(shù)和獎賞函數(shù)，只需要通過與環(huán)境的交互獲得的實際或模擬樣本數(shù)據(jù) (狀態(tài)、動作、獎賞值 ) 序列，從而發(fā)現(xiàn)最優(yōu)策略。 MC 總是基于平均化取樣回報來解決強化學習問題，它把要解決的問題分解為情節(jié) (episode)。當環(huán)境狀態(tài)為終止狀態(tài) G 時，將得到的累積回報賦予開始狀態(tài) S 的值函數(shù)。由于從起始狀態(tài)到終止狀態(tài)的過程中， S 可能不止出現(xiàn)一次，這樣對 S 的值函數(shù)的更新，可以有兩種方法 :FVMC(First Visit MC)和 EVMC(Every Visit MC)。前者將回報賦予第一次訪問的 S,后者將每次訪問 S 到終止狀態(tài) G 的回報平均化以后賦予 S 的值函數(shù)。兩者雖然在理論上有區(qū)別，但是都可以最終收斂到最優(yōu)值函數(shù)。 與動態(tài)規(guī)劃方法相比， MC 法直接同環(huán)境交互獲得經驗來優(yōu)化動作行為，不需建立一個環(huán)境的動態(tài)信息模型，該算法中一些狀態(tài)集的值函數(shù)的計算不依賴于其它狀態(tài)集的值函數(shù)，所以我們可以在那些能夠精確描述環(huán)境信息的狀態(tài)子集中計算所獲得的平均獎賞值。另外，它對馬爾可夫性要求不是很嚴。 強化學習中有待解決的問題 (1) 在任一 階段， Agent 都要面對如何在探索與利用之間取舍的問題。利用已知的動作可保證得到一定的獎賞，然而對一定的狀態(tài)而言，探索新動作可能產生更高的獎賞，但過多的探索又會降低系統(tǒng)的性能。 (2) 傳統(tǒng)的強化學習算法是基于環(huán)境的，是一個馬爾可夫決策假設。系統(tǒng)的將來狀態(tài)依賴于當前的環(huán)境狀態(tài)，和以前的環(huán)境狀態(tài)無關，在真實世界的大多數(shù)情況中，實際系統(tǒng)非常復雜， Agent 不能夠精確感知環(huán)境的所有狀態(tài)，因此算法收斂性的假設在實際環(huán)境中得不到滿足。 (3) 強化學習算法通過搜索狀態(tài)空間和優(yōu)化值函數(shù)得到好的策略，當系統(tǒng)變得復雜時，需要大量的參數(shù)來刻 畫它，這樣會引起狀態(tài)空間到動作空間映像的組合爆炸，給搜索帶來了繁重的任務，進而影響行動決策的優(yōu)化問題。 本章小結 本章先介紹了強化學習的原理和模型，然后介紹了強化學習系統(tǒng)的一些重要組成元素以及馬爾可夫決策過程。此外本章還介紹了當前強化學習中的一些重要算法：動態(tài)規(guī)劃、Monte Carlo 算法，最后提出了一些強化學習中有待解決的問題。 蘇州大學本科生畢業(yè)設計（論文） 10 第三章 動態(tài)規(guī)劃分析 動態(tài)規(guī)劃 (dynamic programming)是運籌學的一個分支，是求解 決策過程 (decision process)最優(yōu)化的數(shù)學方法。 20 世紀 50 年代初美國數(shù)學家 等人在研究 多階段決策過程 (multistep decision process)的優(yōu)化問題時，提出了著名的 最優(yōu)化原理 (principle of optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法 ——動態(tài)規(guī)劃。 動態(tài)規(guī)劃是建立在嚴格的數(shù)學基礎之上的，它需要一個完整、精確的環(huán)境模型。動態(tài)規(guī)劃涉及到一系列算法，這些算法能用于在給定完美的馬爾可夫決策過程環(huán)境模型情況下計算最優(yōu)化問題。 動態(tài)規(guī)劃的適用條件 任何思想方法都有 一定的局限性，超出了特定條件，它就失去了作用。同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。 最優(yōu)化原理 最優(yōu)化原理可以這樣闡述：一個最優(yōu)化策略具有這樣的性質，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結構性質。最優(yōu)化原理是動態(tài)規(guī)劃的基礎，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。 無后向性 將各階段按照一定的次序排列好之后， 對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結。這就是無后向性，又稱為無后效性。 子問題的重疊性 動態(tài)規(guī)劃算法的根本目的是解決冗余。其實質上是一種以空間換時間的技術，它在實現(xiàn)過程中，不得不存儲產生過程中的各種狀態(tài)，所以它的空間復雜度要大于其他算法。設原問題的規(guī)模為 n，當子問題樹中的子問題總數(shù)是 n 的超多項式函數(shù)，而不同的子問題數(shù)只是 n 的多項式函數(shù)時，動態(tài)規(guī)劃顯得特別有意義，此時動態(tài)規(guī)劃法具有線性時間復雜性。所以能夠用 動態(tài)規(guī)劃解決的問題還有一個顯著特征：子問題的重疊性。這個性質并不是動蘇州大學本科生畢業(yè)設計（論文） 11 態(tài)規(guī)劃適用的必要條件，但是如果該性質無法滿足，動態(tài)規(guī)劃算法同其他算法比較就不具備優(yōu)勢。 算法流程 一般來說，強化學習和動態(tài)規(guī)劃的關鍵思想就是用值函數(shù)去組織和構造好的策略，一旦我們找到符合 Bellman 最優(yōu)方程的最優(yōu)值函數(shù)， *V 和 *Q ，就能很容易地得到最優(yōu)策略。事實上，動態(tài)規(guī)劃算法是由 Bellman 方程轉化而來，也就是修正 Bellman 等式的 規(guī)則以提高所期望的值函數(shù)的近似值。 在實際應用中往往按以下幾個步驟進行： (1) 分析最優(yōu)解的性質，并刻畫其結構特征。 (2) 遞歸地定義最優(yōu)值。 (3) 以自底向上或自頂向下的方法計算出最優(yōu)值。 (4) 根據(jù)計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。 策略評估 策略評估 (policy evaluation) 是指， 對于任意策略 ? ， 考慮如何計算狀態(tài)值函數(shù) V? 。對于任意 sS? , 39。39。39。( ) ( , ) [ ( 39。) ]aas s s sasV s s a P R V s???????? () 這里 (, )sa? 是指在策略 ? 下，狀態(tài) s 執(zhí)行動作 a 的概率。在實際計算中，可以通過迭代方法來計算 V 值?？紤]一個逼近值函數(shù)序列： 0 1 2, , ,...,V V V 映射 S? 到 ? 的 V。當 V? 存在且k?? 時，序列 {}KV 通常收斂于 V? ， 這個算法被稱為迭代策略評估。 為了產生每一個連續(xù)的近似值，從 kV 到 1kV? ， 對于 每一個狀態(tài) s ，迭代策略評估都采取相同的操作：在被評估策略下，沿著所有可能的一步轉換，用 s 的后續(xù)狀態(tài)的舊值與期望的立即獎賞計算得到的新值來替換 s 的舊值。這個操作稱為全更新。迭代策略評估的每一次迭代，一旦產生了一個新的近似值函數(shù) 1kV? ，就要更新每一個狀態(tài)值。在實現(xiàn)方面，另一個關注點是算法的終止。一種典型的迭代算 法的終止條件是，在每執(zhí)行一次掃描過后，去檢查 1m a x | ( ) ( ) |s S k kV s V s?? ?的值，并且當這個值足夠小的時候停止執(zhí)行。 策略改進 對策略計算值函數(shù)的一個原因就是有助于發(fā)現(xiàn)更好的策略。假如對于任一策略 ? 確定一個值函數(shù) V? ,對于某些狀態(tài) s 應該如何判斷是否應該改變策略來選擇動作 a ( ()as?? )。最關鍵的評判標準就是計算 ( , )Q sa? 是大于還是小于 ()Vs? 。如果大于的話，在狀態(tài) s 下蘇州大學本科生畢業(yè)設計（論文） 12 選擇動作 a ， 然后再遵循策略 ? ，要優(yōu)于一直遵循策略 ? 。并且最好在以后每次遇到狀態(tài)的時 候都采用動作 a ，事實上，這一新的策