畢業(yè)設計--基于強化學習的gambler策略研究與評價

1、<p>　　本科畢業(yè)設計(論文)</p><p>　學院(部)計算機科學與技術(shù)學院</p><p>　題目基于強化學習的Gambler策略研究與評價</p><p>　年級專業(yè)軟件工程（嵌入式）</p><p>　班級學號</p><p>　姓名</p><p>　指導教師職稱<

2、/p><p>　論文提交日期</p><p><b>　　目 錄</b></p><p><b>　　摘 要1</b></p><p>　　ABSTRACT2</p><p>　　第一章 前 言 3</p><p><b>　

3、　1.1背景概述3</b></p><p>　　1.2 強化學習的應用3</p><p>　　1.3論文結(jié)構(gòu)安排4</p><p>　　第二章 強化學習5</p><p>　　2.1強化學習的原理和模型5</p><p>　　2.2強化學習系統(tǒng)的主要組成要素6</p><

4、;p>　　2.3馬爾可夫決策過程 (MDP)7</p><p>　　2.4強化學習的基本算法8</p><p>　　2.4.1 動態(tài)規(guī)劃(Dynamic Programming, DP)8</p><p>　　2.4.2 蒙特卡羅算法 (Monte Carlo method, MC)9</p><p>　　2.5強化學習中

5、有待解決的問題9</p><p>　　2.6本章小結(jié)9</p><p>　　第三章 動態(tài)規(guī)劃分析10</p><p>　　3.1動態(tài)規(guī)劃的適用條件10</p><p>　　3.1.1最優(yōu)化原理10</p><p>　　3.1.2無后向性10</p><p>　　3.1.3子問題的

6、重疊性10</p><p>　　3.2算法流程11</p><p>　　3.2.1策略評估11</p><p>　　3.2.2策略改進11</p><p>　　3.3尋找最優(yōu)策略12</p><p>　　3.3.1策略迭代12</p><p>　　3.3.2值迭代12</

7、p><p>　　3.4動態(tài)規(guī)劃的效率13</p><p>　　3.5本章小結(jié)13</p><p>　　第四章 實驗平臺分析與實現(xiàn)14</p><p>　　4.1實驗平臺描述14</p><p>　　4.1.1系統(tǒng)概述14</p><p>　　4.1.2系統(tǒng)運行環(huán)境14</p&

8、gt;<p>　　4.2Gambler問題仿真14</p><p>　　4.3實驗平臺概要設計15</p><p>　　4.3.1底層框架模型15</p><p>　　4.3.2 Gambler問題模型17</p><p>　　4.3.3界面設計17</p><p>　　4.4實驗平臺的詳

9、細設計19</p><p>　　4.4.1類和接口19</p><p>　　4.4.2核心算法示例22</p><p>　　4.5本章小結(jié)25</p><p>　　第五章 實驗結(jié)果分析26</p><p>　　5.1實驗結(jié)果26</p><p>　　5.2Gambler仿真結(jié)果

10、分析27</p><p>　　5.2.1Gambler 在不同P值下的策略27</p><p>　　5.2.2策略分析與評價27</p><p>　　5.2.3計算誤差對策略的影響28</p><p>　　5.3本章小結(jié)29</p><p>　　第六章 總結(jié)與展望30</p><p&g

11、t;　　6.1課題總結(jié)30</p><p>　　6.2進一步的研究與展望30</p><p><b>　　參考文獻32</b></p><p><b>　　致 謝34</b></p><p><b>　　摘 要 </b></p><p>

12、;　　強化學習是一種重要的機器學習方法。強化學習通過感知環(huán)境狀態(tài)信息來學習動態(tài)系統(tǒng)的最優(yōu)策略，通過試錯法不斷地與環(huán)境進行交互來改善自己的行為，并具有對環(huán)境的先驗知識要求低的優(yōu)點，是一種可以應用到實時環(huán)境中的在線學習方式。因此在智能控制，機器學習等領(lǐng)域中強化學習得到了廣泛研究。</p><p>　　強化學習的任務就是學習從狀態(tài)空間到動作空間的映射。環(huán)境對不同動作做出的評價性反饋信號決定了強化學習系統(tǒng)的動作選擇策略。

13、如果一個動作得到了最多的獎勵，則該動作就會被采取。</p><p>　　本文的特點是在強化學習理論研究的基礎上，以Gambler問題為仿真實驗平臺，對強化學習中的動態(tài)規(guī)劃算法進行實現(xiàn)，并對不同P值下的實驗結(jié)果進行分析。</p><p>　　關(guān)鍵詞：強化學習，機器學習，動態(tài)規(guī)劃，Gambler </p><p><b>　　ABSTRACT</b>

14、;</p><p>　　Reinforcement learning is an important machine learning method. It could learn the optimal policy of the dynamic system through environment state observation and improve its behavior through trial

15、 and error with the environment. Reinforcement learning has the quality of low requirement for a priori knowledge and is also a kind of online learning method for the real-time environment, which is extensively explored

16、in the field of intelligent control and machine learning.</p><p>　　The aim of reinforcement learning is to learn the mapping from the state space to the action space. The selection policy of actions in the r

17、einforcement learning system is determined by the evaluative feedback signal which is made by environment on different actions. If one action leading to the largest reward, it will be taken. </p><p>　　The fe

18、ature of this paper is that based on the basic theories and methods of reinforcement learning, this paper applies the Gambler problem simulation experiment to implement the dynamic programming algorithms and analyses the

19、 results according to different P value thereafter.</p><p>　　Key Words: Reinforcement Learning, Machine Learning, Dynamic Programming, Gambler</p><p>　　Author: Tianlin Li</p><p>　　

20、Supervisor: Quan Liu</p><p><b>　　第一章 前 言</b></p><p><b>　　背景概述</b></p><p>　　學習是人類獲取知識的主要形式，也是人類具有智能的顯著標志，是人類提高智能水平的基本途徑。建造具有類似人的智能機器是智能控制、人工智能研究的一個核心問題。要使機

21、器具有一定智能，一種方式是靠人事先編程來建立知識庫和推理機制，這具有明顯的局限性。我們希望智能機具有向環(huán)境學習的能力，即自動獲取知識、積累經(jīng)驗、不斷更新和擴充知識，改善知識性能。一個學習系統(tǒng)是具有這樣一種能力的系統(tǒng)，它通過與控制對象和環(huán)境的閉環(huán)交互作用，根據(jù)過去獲得的經(jīng)驗信息，逐步改進系統(tǒng)自身的未來性能[1]。</p><p>　　在機器學習范疇，根據(jù)反饋的不同，學習技術(shù)可以分為監(jiān)督學習(Supervised l

22、earning)、非監(jiān)督學習(Unsupervised learning) 和強化學習(Reinforcement learning)三大類。監(jiān)督學習也稱有導師的學習，這種學習方式需要外界存在一個“教師”，它可以對給定一組輸入提供應有的輸出結(jié)果，這種已知的輸入-輸出數(shù)據(jù)稱為訓練樣本集，學習的目的是減少系統(tǒng)產(chǎn)生的實際輸出和預期輸出之間的誤差，所產(chǎn)生的誤差反饋給系統(tǒng)來指導學習。非監(jiān)督學習又稱無導師學習，它是指系統(tǒng)不存在外部教師指導的情形下構(gòu)

23、建其內(nèi)部表征。</p><p>　　研究者發(fā)現(xiàn)，生物進化過程中為適應環(huán)境而進行的學習有兩個特點：一個是人從來不是靜止的被動的等待而是主動的對環(huán)境作試探；二是環(huán)境對試探動作產(chǎn)生的反饋是評價性的，生物根據(jù)環(huán)境的評價來調(diào)整以后的行為，是一種從環(huán)境狀態(tài)到行為映射的學習，具有以上特點的學習就是強化學習(或稱再勵學習，評價學習，簡記為RL)[2]。強化學習是一種以環(huán)境反饋作為輸入的、特殊的、適應環(huán)境的機器學習方法。該方法不同

24、與監(jiān)督學習技術(shù)那樣通過正例、反例來告知采取何種行為，而是通過試錯(trial-and-error)的方法來發(fā)現(xiàn)最優(yōu)行為策略[3]。</p><p>　　強化學習的概念是由Minsky在20世紀60年代最先提出的，從80年代末開始，隨著對強化學習的數(shù)學基礎研究取得突破性進展后，對強化學習的研究和應用也日益開展起來，成為目前機器學習領(lǐng)域的研究熱點之一。</p><p><b>　　強

25、化學習的應用</b></p><p>　　現(xiàn)在，強化學習已經(jīng)成為制造業(yè)過程控制、作業(yè)調(diào)度、路徑規(guī)劃、WEB信息搜索、企業(yè)供應鏈、電子商務等領(lǐng)域，對目標行為優(yōu)化的一種重要技術(shù)[4]。例如，目前將強化學習理論與企業(yè)分銷系統(tǒng)相結(jié)合，目的是將多個制造商與一個零售商組成的分銷系統(tǒng)，他們以各自的利潤最大化為目標。制造商給零售商提供獎金激勵，零售商提供對應于獎金激勵的服務水平，制造商需要進行為零售商提供多大獎金激勵

26、的決策，利用強化學習的啟發(fā)式學習算法來優(yōu)化制造商應提供的最優(yōu)獎金激勵。</p><p>　　在調(diào)度管理中，強化學習體現(xiàn)出了很大的經(jīng)濟價值。Crites和Barto將強化學習算法用于一個4個電梯、10層樓的系統(tǒng)中[5]。每一個電梯都有各自的位置、方向、速度和一系列表示乘客要離開的位置狀態(tài)。這個系統(tǒng)的狀態(tài)集合超過1022個，用傳統(tǒng)方法很難管理，因此他們用反傳算法訓練表示Q函數(shù)的神經(jīng)網(wǎng)絡，與其它算法相比較，強化學習更加

27、優(yōu)越。另外強化學習在蜂窩電話系統(tǒng)中動態(tài)信道分配和Job shop規(guī)劃問題上都有應用。</p><p>　　在游戲比賽中，強化學習理論也被廣泛地應用。最早應用的例子是Samuel的下棋程序，近來，Tesauro把瞬時差分法應用于Backgamon，這就是著名的TD-Gammon。Backgammon大約有1020個狀態(tài)[6]，Tesauro 采用三層BP神經(jīng)網(wǎng)絡把棋盤上的棋子位置與棋手獲勝率聯(lián)系起來，通過訓練取得在

28、40盤比賽中僅負1盤的戰(zhàn)績。</p><p>　　強化學習在多移動機器人系統(tǒng)中的應用研究正日益受到關(guān)注。Turcher Balch提出Clay控制結(jié)構(gòu)應用于機器人足球賽，不同于基于行為控制結(jié)構(gòu)的強化學習，他將強化學習與motor schemas 有機結(jié)合，使得系統(tǒng)既具有強化學習的自適應能力，又有motor schemas的實時性能。Mataric 利用改進的Q學習算法實現(xiàn)四個機器人執(zhí)行foraging任務，事先利

29、用領(lǐng)域知識將狀態(tài)空間到動作空間的映射轉(zhuǎn)化為條件行為來壓縮狀態(tài)空間的規(guī)模，加速學習[7]。</p><p><b>　　論文結(jié)構(gòu)安排</b></p><p>　　本文以強化學習理論為基礎，在Gambler仿真平臺中實現(xiàn)了動態(tài)規(guī)劃算法，并對實驗結(jié)果進行了深入分析。論文結(jié)構(gòu)安排如下：</p><p>　　第一章，前言。該章介紹了強化學習的背景及其應用

30、。</p><p>　　第二章，強化學習。該章介紹了強化學習的基本原理和模型，強化學習系統(tǒng)的主要組成要素以及馬爾可夫決策過程 (MDP)，然后介紹了強化學習的基本算法，包括動態(tài)規(guī)劃，蒙特卡羅算法，最后提出了強化學習過程中有待解決的問題。</p><p>　　第三章，動態(tài)規(guī)劃分析。該章重點介紹了動態(tài)規(guī)劃理論，包括動態(tài)規(guī)劃的適用條件，算法流程以及尋找最優(yōu)策略的兩種迭代方式，最后分析了動態(tài)規(guī)劃的

31、效率。</p><p>　　第四章，實驗平臺分析與實現(xiàn)。該章詳細分析了實驗平臺的概要設計和詳細設計。</p><p>　　第五章，實驗結(jié)果分析。該章分析了仿真平臺的實驗結(jié)果，對Gambler在不同P值下的策略進行了深入比較和分析。</p><p>　　第六章，總結(jié)與展望。該章對本文的研究工作進行了總結(jié)，對強化學習課題的前景做了進一步的展望。</p>&

32、lt;p><b>　　第二章 強化學習</b></p><p>　　強化學習技術(shù)是從控制理論、統(tǒng)計學、心理學等相關(guān)學科發(fā)展而來，最早可以追溯到巴普洛夫的條件反射實驗[8]。強化學習要解決的是這樣一個問題：一個能夠感知環(huán)境的自治Agent，怎樣通過學習選擇能夠達到其目標的最優(yōu)動作[9]。當Agent在環(huán)境中做出每個動作時，施教者會提供獎勵或懲罰信息，以表示結(jié)果狀態(tài)正確與否。例如，在訓練A

33、gent進行棋類對弈時，施教者可在游戲勝利時給出正回報，而在游戲失敗時，給出負回報，其他的時候給出零回報。</p><p>　　強化學習的原理和模型</p><p>　　強化學習的基本原理為：如果Agent的某個行為策略導致環(huán)境正的獎勵，那么Agent產(chǎn)生這個行為策略的趨勢將會加強；如果Agent的某個行為策略導致環(huán)境負的獎勵，那么Agent產(chǎn)生這個行為策略的趨勢將會減弱，最終消亡。由于強

34、化學習不像監(jiān)督學習那樣有教師信號，它僅有一個強化信號來判斷動作的好壞，所以它的學習過程必定是漫長的。</p><p>　　強化學習把學習看作試探過程，基本模型如圖2.l所示。在強化學習中，Agent選擇一個動作a作用于環(huán)境，環(huán)境接收該動作后發(fā)生變化，同時產(chǎn)生一個強化信號(獎或罰)反饋給Agent，Agent再根據(jù)強化信號和環(huán)境的當前狀態(tài)S再選擇下一個動作，選擇的原則是使受到正的報酬的概率增大[10]。選擇的動作不

35、僅影響立即回報值而且還影響下一時刻的狀態(tài)及最終回報值。強化學習的目的就是尋找一個最優(yōu)策略，使得Agent在運行中所獲得的累計回報值最大[11]。</p><p>　　圖2.1 強化學習的基本結(jié)構(gòu)</p><p>　　Agent與環(huán)境進行交互是，在每一時刻循環(huán)發(fā)生如下事件序列：</p><p>　　Agent感知當前的環(huán)境狀態(tài)；</p><p>

36、;　　針對當前的狀態(tài)和強化值，Agent選擇一動作執(zhí)行；</p><p>　　當Agent所選擇的動作作用于環(huán)境時，環(huán)境發(fā)生變化，即環(huán)境狀態(tài)轉(zhuǎn)移至新狀態(tài)并給出獎賞(強化信號r)；</p><p>　　獎賞(強化信號r)反饋給Agent。</p><p>　　強化學習系統(tǒng)的主要組成要素</p><p>　　圖2.2 強化學習的四個要素</

37、p><p>　　如圖2.2所示，除了Agent和環(huán)境，一個強化學習系統(tǒng)還有四個主要的組成要素：策略(policy)、狀態(tài)值函數(shù)(value function)、瞬時獎懲函數(shù)(reward function)和環(huán)境的模型(model)。</p><p>　　Agent的任務是產(chǎn)生控制動作，動作的選定則是根據(jù)策略得到的，所以說策略是狀態(tài)到動作的映射：。策略是強化學習的核心，因為策略直接決定了Age

38、nt的動作，即告訴Agent選擇什么動作，策略的好壞最終決定了Agent的行動和整體性能，策略具有隨機性。</p><p>　　瞬時獎懲函數(shù)是在與環(huán)境交互的過程中，獲取的獎勵信號，該函數(shù)反應了Agent所面臨的任務的性質(zhì)，同時，它也可以作為Agent修改策略的基礎。獎賞信號R是對所產(chǎn)生動作的好壞作一種評價，獎賞信號通常是一個標量信號，例如用一個正數(shù)表示獎，而用負數(shù)表示罰，一般來說正數(shù)越大表示獎的越多，負數(shù)越小表示

39、罰的越多。強化學習的目的就是使Agent最終得到的總的獎賞值達到最大。瞬時獎懲函數(shù)往往是確定的、客觀的，為策略的選擇提供依據(jù)，即告訴Agent選擇什么動作是好的。</p><p>　　如果說瞬時獎懲函數(shù)是對一個狀態(tài)(或狀態(tài)-動作對)的即時評價，那么狀態(tài)值函數(shù)就是從長遠的角度來考慮一個狀態(tài)(或狀態(tài)-動作對)的好壞。值函數(shù)又稱為評價函數(shù)。狀態(tài)st的值，是指Agent在狀態(tài)st根據(jù)策略π執(zhí)行動作at及采取后續(xù)策略所得到

40、的積累獎賞的期望，記為。</p><p>　　環(huán)境的模型是某些強化學習系統(tǒng)的另一個元素，并不是所有的強化學習系統(tǒng)都需要建立環(huán)境的模型。</p><p>　　圖2.2中給出了這四種要素之間的關(guān)系。它們自底向上地構(gòu)成了強化學習的學習結(jié)構(gòu)。首先，系統(tǒng)所面臨的環(huán)境由環(huán)境模型定義，模型是學習環(huán)境的基礎。但是由于模型中函數(shù)和函數(shù)未知，只能使用瞬時獎懲選擇策略。又因為考慮到環(huán)境模型的不確定性和目標的長遠

41、性，所以產(chǎn)生了介于策略和瞬時獎懲之間的狀態(tài)值函數(shù)。即：</p><p><b>　　(2.1)</b></p><p>　　這里 是一個參數(shù)， ，稱為折扣率。</p><p><b>　　(2.2)</b></p><p>　　根據(jù)Bellman最優(yōu)策略公式，在最優(yōu)策略下，其值函數(shù)的定義如下：<

42、;/p><p><b>　　(2.3)</b></p><p>　　馬爾可夫決策過程 (MDP)</p><p>　　在理想狀況下，往往希望一個狀態(tài)能夠簡練地抽象總結(jié)過去的感覺，然而這種方式又能保留所有相關(guān)信息。正常的來說，這比只要求即時感覺要求得更多，但是比要求全部的過去感知歷史要少得多。一個成功保留所有相關(guān)信息的狀態(tài)信號稱為馬爾可夫的，或者說具

43、有馬爾可夫性質(zhì)。比如，一個棋子的位置——當前的在棋盤上所有棋子的結(jié)構(gòu)——將作為一個馬爾可夫狀態(tài)，因為它匯集了所有關(guān)于引導它完成位置序列的重要的東西。雖然關(guān)于這個序列的很多信息丟失了，但是所有有關(guān)于這個游戲的最重要的東西被保留下來了。</p><p>　　對于所有在過去事件中的，，和所有的可能值：來說，如果狀態(tài)信號有馬爾可夫特性，那么環(huán)境在的響應只取決于在時刻的狀態(tài)和動作的表示，在此情況下，環(huán)境和任務是一體的，都稱

44、為具有馬爾可夫性質(zhì)，環(huán)境的動態(tài)量可以定義為：</p><p><b>　　(2.4)</b></p><p>　　滿足馬爾可夫性質(zhì)的強化學習任務被稱為是馬爾可夫決策過程或者MDP。很多強化學習問題基于的一個關(guān)鍵假設就是Agent與環(huán)境之間的交互可以被看成一個馬爾可夫決策過程(MDP)，因此強化學習的研究主要集中于對Markov的問題處理。</p><

45、;p>　　Markov決策過程的模型可以用一個四元組表示：為可能的狀態(tài)集合，為可能的動作集合，是狀態(tài)轉(zhuǎn)移函數(shù)；是獎賞函數(shù)[1]。在每一個時間步，環(huán)境處于狀態(tài)集合中的某狀態(tài)，Agent選擇動作集合中的一個動作，收到即時獎賞，并轉(zhuǎn)移至下一狀態(tài)。狀態(tài)轉(zhuǎn)移函數(shù)表示在狀態(tài)執(zhí)行動作轉(zhuǎn)移到狀態(tài)的概率可以用表示。狀態(tài)轉(zhuǎn)移函數(shù)和獎賞函數(shù)都是隨機的。Agent目標就是尋求一個最優(yōu)控制策略，使值函數(shù)最大[12]。</p><p>

46、;<b>　　強化學習的基本算法</b></p><p>　　大多數(shù)關(guān)于強化學習的方法研究都是建立在MDP理論框架之上的，通過MDP建模，強化學習問題一般可采用迭代技術(shù)更新值函數(shù)的估計值來獲得最優(yōu)策略。當前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率和獎賞值只取決于當前狀態(tài)和選擇的動作，而與歷史狀態(tài)和歷史動作無關(guān)。根據(jù)在學習過程中Agent是否需要學習MDP知識，強化學習可以分為模型無關(guān)法(model-free

47、)和基于模型法(model-base)。動態(tài)規(guī)劃屬于基于模型法，而蒙特卡羅算法則屬于模型無關(guān)法。</p><p>　　2.4.1 動態(tài)規(guī)劃(Dynamic Programming, DP)</p><p>　　動態(tài)規(guī)劃方法是利用值函數(shù)來搜索好的策略方法，適用于解決大規(guī)模問題，設環(huán)境是一個有限馬爾可夫集，對任意策略，如果環(huán)境的動態(tài)信息完全知道，如：策略和，已經(jīng)知道，為了減少計算量，我們常用值

48、迭代法來近似求出,,……，其更新公式為：</p><p><b>　　(2.5)</b></p><p>　　常規(guī)的動態(tài)規(guī)劃方法主要有以下三種方法:第一種是值函數(shù)迭代法，其本質(zhì)是有限時段的動態(tài)規(guī)劃算法在無限時段上的推廣，是一種逐次逼近算法，該算法與強化學習有著密切的聯(lián)系；第二種是策略迭代，這是一種基于Bellman最優(yōu)方程的算法；第三種是改進的策略迭代法，綜合了前面兩

49、種算法，也稱為一般化策略迭代法，是許多強化學習算法的基本思想的來源之一[13]。</p><p>　　動態(tài)規(guī)劃算法的局限性是明顯的，它容易出現(xiàn)“維數(shù)災”和“建模災”問題。其計算量會使狀態(tài)變量的數(shù)量呈指數(shù)增長；它要求事先知道系統(tǒng)的確切模型信息，如和的值，而在實際的大規(guī)模隨機問題中，系統(tǒng)的確切模型信息通常是難以獲得且不易計算的。</p><p>　　2.4.2 蒙特卡羅算法 (Monte Ca

50、rlo method, MC)</p><p>　　蒙特卡羅算法是一種無模型 (model-free) 的學習方法，不需要系統(tǒng)模型——狀態(tài)轉(zhuǎn)移函數(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ù)。由于

51、從起始狀態(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ù)。</p><p>　　與動態(tài)規(guī)劃方法相比，MC法直接同環(huán)境交互獲得經(jīng)驗來優(yōu)化動作行為，不需建立一

52、個環(huán)境的動態(tài)信息模型，該算法中一些狀態(tài)集的值函數(shù)的計算不依賴于其它狀態(tài)集的值函數(shù)，所以我們可以在那些能夠精確描述環(huán)境信息的狀態(tài)子集中計算所獲得的平均獎賞值。另外，它對馬爾可夫性要求不是很嚴。</p><p>　　強化學習中有待解決的問題</p><p>　　在任一階段，Agent都要面對如何在探索與利用之間取舍的問題。利用已知的動作可保證得到一定的獎賞，然而對一定的狀態(tài)而言，探索新動作可能

53、產(chǎn)生更高的獎賞，但過多的探索又會降低系統(tǒng)的性能。</p><p>　　傳統(tǒng)的強化學習算法是基于環(huán)境的，是一個馬爾可夫決策假設。系統(tǒng)的將來狀態(tài)依賴于當前的環(huán)境狀態(tài)，和以前的環(huán)境狀態(tài)無關(guān)，在真實世界的大多數(shù)情況中，實際系統(tǒng)非常復雜，Agent不能夠精確感知環(huán)境的所有狀態(tài)，因此算法收斂性的假設在實際環(huán)境中得不到滿足。</p><p>　　強化學習算法通過搜索狀態(tài)空間和優(yōu)化值函數(shù)得到好的策略，當系

54、統(tǒng)變得復雜時，需要大量的參數(shù)來刻畫它，這樣會引起狀態(tài)空間到動作空間映像的組合爆炸，給搜索帶來了繁重的任務，進而影響行動決策的優(yōu)化問題。</p><p><b>　　本章小結(jié)</b></p><p>　　本章先介紹了強化學習的原理和模型，然后介紹了強化學習系統(tǒng)的一些重要組成元素以及馬爾可夫決策過程。此外本章還介紹了當前強化學習中的一些重要算法：動態(tài)規(guī)劃、Monte Ca

55、rlo算法，最后提出了一些強化學習中有待解決的問題。</p><p>　　第三章 動態(tài)規(guī)劃分析</p><p>　　動態(tài)規(guī)劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學方法。20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問

56、題時，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃是建立在嚴格的數(shù)學基礎之上的，它需要一個完整、精確的環(huán)境模型。動態(tài)規(guī)劃涉及到一系列算法，這些算法能用于在給定完美的馬爾可夫決策過程環(huán)境模型情況下計算最優(yōu)化問題。</p><p><b>　　動態(tài)規(guī)劃的適用條件</b&g

57、t;</p><p>　　任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。</p><p><b>　　最優(yōu)化原理</b></p><p>　　最優(yōu)化原理可以這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余

58、下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)化原理是動態(tài)規(guī)劃的基礎，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。</p><p><b>　　無后向性</b></p><p>　　將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響

59、它未來的決策，而只能通過當前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性。</p><p><b>　　子問題的重疊性</b></p><p>　　動態(tài)規(guī)劃算法的根本目的是解決冗余。其實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復雜度要大于其他算法。設原問題的規(guī)模為n，當子問題

60、樹中的子問題總數(shù)是n的超多項式函數(shù)，而不同的子問題數(shù)只是n的多項式函數(shù)時，動態(tài)規(guī)劃顯得特別有意義，此時動態(tài)規(guī)劃法具有線性時間復雜性。所以能夠用動態(tài)規(guī)劃解決的問題還有一個顯著特征：子問題的重疊性。這個性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其他算法比較就不具備優(yōu)勢。</p><p><b>　　算法流程</b></p><p>　　一般來

61、說，強化學習和動態(tài)規(guī)劃的關(guān)鍵思想就是用值函數(shù)去組織和構(gòu)造好的策略，一旦我們找到符合Bellman最優(yōu)方程的最優(yōu)值函數(shù)，和，就能很容易地得到最優(yōu)策略。事實上，動態(tài)規(guī)劃算法是由Bellman方程轉(zhuǎn)化而來，也就是修正Bellman等式的規(guī)則以提高所期望的值函數(shù)的近似值。</p><p>　　在實際應用中往往按以下幾個步驟進行：</p><p>　　分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。</p

62、><p><b>　　遞歸地定義最優(yōu)值。</b></p><p>　　以自底向上或自頂向下的方法計算出最優(yōu)值。</p><p>　　根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。</p><p><b>　　策略評估</b></p><p>　　策略評估 (policy evalu

63、ation) 是指，對于任意策略，考慮如何計算狀態(tài)值函數(shù)。對于任意, </p><p><b>　　(3.1)</b></p><p>　　這里是指在策略下，狀態(tài)執(zhí)行動作的概率。在實際計算中，可以通過迭代方法來計算V值?？紤]一個逼近值函數(shù)序列：映射到的V。當存在且時，序列通常收斂于，這個算法被稱為迭代策略評估。</p><p>　　為了產(chǎn)生每一

64、個連續(xù)的近似值，從到，對于每一個狀態(tài)，迭代策略評估都采取相同的操作：在被評估策略下，沿著所有可能的一步轉(zhuǎn)換，用的后續(xù)狀態(tài)的舊值與期望的立即獎賞計算得到的新值來替換的舊值。這個操作稱為全更新。迭代策略評估的每一次迭代，一旦產(chǎn)生了一個新的近似值函數(shù)，就要更新每一個狀態(tài)值。在實現(xiàn)方面，另一個關(guān)注點是算法的終止。一種典型的迭代算法的終止條件是，在每執(zhí)行一次掃描過后，去檢查的值，并且當這個值足夠小的時候停止執(zhí)行。</p><p

65、><b>　　策略改進</b></p><p>　　對策略計算值函數(shù)的一個原因就是有助于發(fā)現(xiàn)更好的策略。假如對于任一策略確定一個值函數(shù),對于某些狀態(tài)應該如何判斷是否應該改變策略來選擇動作()。最關(guān)鍵的評判標準就是計算是大于還是小于。如果大于的話，在狀態(tài)下選擇動作，然后再遵循策略，要優(yōu)于一直遵循策略。并且最好在以后每次遇到狀態(tài)的時候都采用動作，事實上，這一新的策略在全局上還是優(yōu)于舊策略的

66、。在這一特殊情況下所做的操作就稱為策略改進原理。的計算公式為：</p><p><b>　　(3.2)</b></p><p>　　通過對原始策略的值函數(shù)使用或近似使用貪心算法，改進原始策略來制定新的策略的過程，就被稱作是策略改進。</p><p><b>　　尋找最優(yōu)策略</b></p><p>

67、　　動態(tài)規(guī)劃思想設計的算法從整體上看基本是按照遞推關(guān)系式來進行迭代算得最優(yōu)解。有兩種迭代方式：策略迭代和值迭代。</p><p><b>　　策略迭代</b></p><p>　　一個策略在利用被改進而產(chǎn)生一個新的更好的策略后，計算，然后再次改進生成更好的策略。每一個策略必須保證在前一個策略上嚴格的改進。因為一個有窮的馬爾可夫決策過程(MDP)僅有有限數(shù)量的策略，這個

68、過程在有限次的迭代后最終收斂于最優(yōu)策略和最優(yōu)值函數(shù)。尋找最優(yōu)策略的方法稱為策略迭代。對于每一次策略評估和其自身的迭代計算都開始于前一次策略的值函數(shù)，這使得策略評估的收斂速度有很大的提高。策略迭代經(jīng)常在很少量的幾步迭代后就收斂至最優(yōu)策略。</p><p><b>　　值迭代</b></p><p>　　策略迭代的一大缺點就是它的每一次迭代都需要進行策略評估，而對于整個狀

69、態(tài)集，該策略評估要對狀態(tài)集多次掃描，不斷地進行自身迭代計算。事實上，通過值迭代可以中斷策略評估的執(zhí)行，而且不影響最終策略迭代的收斂效果。值迭代將策略改進和終止策略評估的步驟結(jié)合了起來，在第一輪掃描 (每個狀態(tài)的一次更新) 過后，策略評估就停止了，公式如下：</p><p><b>　　(3.3)</b></p><p>　　在每一遍的值迭代過程中，都有效地將一遍策略評

70、估和一遍策略改進相結(jié)合，通過在兩遍策略改進之間插入多遍策略評估，從而加快了收斂至最優(yōu)策略的速度。其終止方法是通過計算值函數(shù)在一次掃描后的變化量，如果非常小則停止程序的運行。圖4.1就給出了關(guān)于這種帶結(jié)束條件的完整的算法。</p><p><b>　　圖4.1值迭代</b></p><p><b>　　動態(tài)規(guī)劃的效率</b></p>

71、<p>　　DP對于解決大型的問題來說可能并不太實際，但是與其它一些解決MDP算法相比較，它還是相當有效的。如果不考慮一些技術(shù)上的細節(jié)，那么利用動態(tài)規(guī)劃算法去尋找最優(yōu)策略所花費的(最長)時間是一個關(guān)于狀態(tài)數(shù)和動作數(shù)的多項式。假設n和m表示狀態(tài)和動作的數(shù)量，這就意味著動態(tài)規(guī)劃算法將進行一系列操作步驟必將小于多項式所計算的結(jié)果。即使(確定的)策略的總數(shù)量是，動態(tài)規(guī)劃算法也可以確保在由多項式所得出的時間范圍內(nèi)得到最優(yōu)策略。從這個意義

72、上來說，動態(tài)規(guī)劃算法在尋找最優(yōu)策略的速度上要遠快于其他直接尋找的算法，因為那些直接尋找的算法需要盡力檢驗每一個策略以比較確定是否為最優(yōu)策略。線性規(guī)劃算法也可以用來解決馬爾可夫決策過程的問題，甚至在一些情況下，它的最差收斂保證要優(yōu)于動態(tài)規(guī)劃算法的。但是在狀態(tài)的數(shù)量很小的時候，與動態(tài)規(guī)劃算法比較時，線性規(guī)劃算法就顯的很不實際，比如當狀態(tài)的數(shù)量只有100的時候。而對于那些大型的問題，只有動態(tài)規(guī)劃算法才是可行的。</p><

73、p>　　實際上，利用現(xiàn)今的計算機，動態(tài)規(guī)劃可以用來解決狀態(tài)數(shù)量達到百萬級的馬爾可夫決策過程的問題。策略迭代和值迭代現(xiàn)如今都被廣泛使用，也不能說兩者之間到底是哪一個比較好。實際上，這些算法的收斂速度都是要快于它們理論上的最差運行時間，尤其是當它們一開始就有的比較好的初始值函數(shù)或者策略。</p><p><b>　　本章小結(jié)</b></p><p>　　本章先介紹了

74、動態(tài)規(guī)劃的適用條件，然后說明動態(tài)規(guī)劃的算法流程并且介紹了策略評估和策略改進。其次本章還介紹了兩種尋找最優(yōu)策略的迭代方法以及動態(tài)規(guī)劃的效率。</p><p>　　第四章 實驗平臺分析與實現(xiàn)</p><p>　　基于強化學習理論，采用動態(tài)規(guī)劃算法，以Gambler問題為實驗平臺，對上述理論進行仿真實現(xiàn)。本章重在討論仿真平臺的實現(xiàn)過程，詳細介紹底層框架及核心算法。</p><

75、p><b>　　實驗平臺描述</b></p><p><b>　　系統(tǒng)概述</b></p><p>　　Gambler問題是強化學習過程中比較經(jīng)典的問題，本次實驗重在借助Gambler問題，結(jié)合強化學習的理論和算法，在Visual Studio 2008環(huán)境下實現(xiàn)機器學習，最終能夠給出Gambler問題中的最優(yōu)策略。在該實驗平臺上，用戶可以

76、設定賭徒贏的概率，程序運行過程中，我們可以看到機器學習過程中所產(chǎn)生的V值以及最優(yōu)策略的變化情況。</p><p><b>　　系統(tǒng)運行環(huán)境</b></p><p><b>　　硬件系統(tǒng)</b></p><p>　　處理器：Intel Pentium 166 MX 或者更高</p><p><b

77、>　　內(nèi)存：128M以上</b></p><p><b>　　硬盤空間：2G以上</b></p><p>　　顯卡：SVGA顯卡適配器</p><p><b>　　軟件系統(tǒng)</b></p><p>　　操作系統(tǒng)：Windows 98/ME/2000/XP</p>&l

78、t;p>　　實驗環(huán)境：Visual Studio 2008</p><p>　　Gambler問題仿真</p><p>　　一個賭徒利用硬幣投擲的正反面結(jié)果來賭博。假如投擲結(jié)果是硬幣的正面朝上，那么他將贏得他所壓在這一局的相同錢，如果是反面朝上，那么他將輸?shù)羲馁€金。當這個賭徒贏滿100美元或者他輸?shù)羲械腻X時，賭博結(jié)束。每一輪投擲，賭徒必須取出他資金的一部分作為賭金，賭金必須是整

79、數(shù)。</p><p>　　在該實驗平臺上，能夠有用戶定義硬幣正面朝上的概率P，并且能夠暫停迭代來查看當前的V值及最優(yōu)策略。程序運行結(jié)束后，能夠在系統(tǒng)界面上看到最終的V值及最優(yōu)策略的曲線圖。</p><p>　　Gambler問題可以被描述為情節(jié)式無折扣的（可以理解為）有限MDP模型。狀態(tài)就是賭徒所擁有的資金，，動作就是下賭注，。每一輪只有當賭徒最后贏滿100美元時，反饋值為+1，否則，反饋

80、值為0。狀態(tài)值函數(shù)給出每輪能夠贏得賭博的概率。策略就是如何決定每輪取出多少錢去賭博。最優(yōu)策略就是使取得最后勝利的概率最大化。</p><p><b>　　實驗平臺概要設計</b></p><p>　　本實驗平臺是由兩部分構(gòu)成，一部分是底層框架，該框架的設計初衷是能夠適用任何強化學習問題，因此它是由許多抽象類和接口構(gòu)成，另一部分是具體強化學習問題的模型，它是通過對具體問

81、題建模并且繼承底層框架的抽象類而獲得的。</p><p><b>　　底層框架模型</b></p><p>　　在底層框架中，最重要的是IAgent, IEnvironment, IStrategy這三個抽象類及其子類。IAgnet是環(huán)境(Environment) 和策略(Strategy)模塊交互的橋梁。IEnvironment 主要包括Action和State，用

82、來獲得環(huán)境中的動作以及狀態(tài)。IStrategy是采用的算法，包含進行學習的函數(shù)。在本實驗平臺中，由于環(huán)境模型是確定的，并未使用到IAgent，因此以下將具體說明環(huán)境，算法及值存儲的相關(guān)部分。</p><p><b>　　環(huán)境的結(jié)構(gòu)</b></p><p>　　圖4.1 環(huán)境的結(jié)構(gòu)</p><p>　　如圖4.1所示，最終的CAbstractEn

83、vironmentModel類即是在具體問題中環(huán)境類所要繼承的父類。該類同時繼承IEnvironmentModel和CAbstractEnvironment主要包括一下方法：判斷是否到達最終狀態(tài)；獲取當前狀態(tài)的所有動作值；給定一對狀態(tài)和動作后獲得后繼狀態(tài)，獲得立即獎賞值；初始化狀態(tài)；獲得所有狀態(tài)；以文本形式返回所有的屬性。</p><p>　　IGraphics是一個畫圖的接口，使用該接口可以將環(huán)境中的信息及時返

84、回到系統(tǒng)的圖形界面中。在Gambler問題的具體實現(xiàn)中，并沒有通過這個類來畫圖。</p><p>　　IEnvironmentModel是基于模型的環(huán)境類，繼承IEnvironment。在這個類中有兩個抽象的方法：一個是獲得轉(zhuǎn)移概率的函數(shù)，另一個是獲得所有后繼狀態(tài)的函數(shù)。</p><p><b>　　算法的結(jié)構(gòu)</b></p><p>　　圖4

85、.2 算法的結(jié)構(gòu)</p><p>　　IStrategy是算法的接口，最主要的功能是在給定一個狀態(tài)后，獲取它的最優(yōu)動作或者最優(yōu)動作列表。IModelFreeStrategy繼承IStrategy，主要用于無模型的算法，如TD算法，MC算法，Q算法，包含以下方法：從所有動作中選擇一個動作，從它的經(jīng)驗中進行學習。IModelBasedStrategy也繼承于IStrategy，主要用于已知模型的算法，如DP算法，包含

86、以下方法：進行策略評估，進行機器學習。IStateValueLearner和IActionValueLearner都是返回狀態(tài)的V值的類。因此，由圖4.2可以得知，如果實際問題是用基于模型的算法解決的，則調(diào)用CVISelector類，如果是用無模型的算法解決，則調(diào)用CMCOnPolicySelector類。</p><p><b>　　存儲的結(jié)構(gòu)</b></p><p&g

87、t;　　在機器學習的過程中，需要不斷地使用到當前狀態(tài)的值 (V值或Q值)，在底層框架中使用IVStore和IQStore來存取，并且如果在讀取時發(fā)現(xiàn)還沒值存入，則會調(diào)用IDefaultValueChooser來返回一個默認值。值可以是一個常數(shù)或是一個區(qū)間。CConstantValueChooser和CIntervalValueChooser都繼承于IDefaultValueChooser結(jié)構(gòu)如圖4.3所示。</p><

88、;p><b>　　圖4.3存儲的結(jié)構(gòu)</b></p><p>　　Gambler問題模型</p><p>　　Gambler問題是通過基于模型的DP算法來解決的，根據(jù)上述的底層框架可以得知，在Gambler這個具體問題中，根據(jù)實際的建模分析，需要創(chuàng)建狀態(tài)，動作和環(huán)境的三個類，這三個類分別繼承于CAbstractState，IAction和CAbstractEnv

89、ironmentModel。</p><p>　　狀態(tài)類——Stake</p><p>　　賭徒當前手中的賭金即是一個狀態(tài)。在該類中能夠?qū)顟B(tài)進行復制，判斷兩個狀態(tài)是否相等，獲取當前賭金的金額。</p><p><b>　　動作類——Bet</b></p><p>　　賭徒的動作用他的下注金額來表示。在該類中能夠?qū)幼鬟M

90、行復制，判斷兩個動作是否一樣，獲取下注的金額。</p><p>　　環(huán)境類——Gambler</p><p>　　由于Gambler問題是基于模型的，所以環(huán)境類知道當前狀態(tài)下的所有情況。在環(huán)境類中定義了硬幣正面朝上的概率P及最終狀態(tài)。在該類中能夠判斷是否到達最終狀態(tài)，獲得立即獎賞，在給定狀態(tài)和動作的情況下獲得所有的后續(xù)狀態(tài)，在給定狀態(tài)的情況下獲得所有的動作，獲得所有的狀態(tài)，獲得轉(zhuǎn)移概率，設

91、定P值，獲取P值。</p><p><b>　　界面設計</b></p><p>　　界面設計應遵循簡潔美觀，方便易用的基本原則。</p><p>　　程序界面主要由兩部分組成：左邊的圖形顯示區(qū)和右邊的具體信息顯示區(qū)。右邊的區(qū)域能夠自由的展開或者隱藏。點擊暫停按鈕可以暫停迭代過程。整個頁面布局使用CLR來實現(xiàn)，具體效果圖如4.4，4.5所示：&

92、lt;/p><p>　　圖4.4 系統(tǒng)界面(1)</p><p>　　圖4.4 系統(tǒng)界面(2)</p><p><b>　　實驗平臺的詳細設計</b></p><p>　　基于上述的底層框架和具體問題模型，本系統(tǒng)在Visual Studio 2008開發(fā)環(huán)境上采用CLR實現(xiàn)了具體的功能。在具體實現(xiàn)的過程中，程序中加入了一些額

93、外的代碼，這些代碼能夠?qū)栴}中的各個屬性(例如V值，狀態(tài)值，動作值)輸出到XML文件保存。下面將以代碼的形式分析一些重要的類和接口。</p><p><b>　　類和接口</b></p><p><b>　　IAction</b></p><p>　　在Gambler問題中，Bet類繼承IAction，并且添加了一個Get

94、Action()的方法。</p><p><b>　　IState</b></p><p>　　CAbstractState繼承IState，定義了一些公共行為。Stake類繼承CAbstractState，在此基礎上添加了GetValue()方法來獲得當前狀態(tài)下的賭金數(shù)額。</p><p>　　IEnvironment</p>

95、<p>　　IEnvironmentModel繼承自IEnvironment，在此基礎上添加了獲取轉(zhuǎn)移概率的方法和獲取所有后繼狀態(tài)的方法。如圖4.1所示，CAbstracatEnvironmentModel同時繼承IEnvironmentModel和CAbstractEnvironment。在Gambler問題中，環(huán)境類Gambler繼承CAbstracatEnvironmentModel，并對這些虛函數(shù)進行重載。</p

96、><p><b>　　IVStore</b></p><p>　　IModelBasedStrategy</p><p><b>　　核心算法示例</b></p><p>　　(1)Evaluation方法</p><p>　　在Gambler問題中，最核心的部分在于CVISel

97、ector類的具體實現(xiàn)。在CVISelector類中，調(diào)用Evaluation方法進行策略評估，調(diào)用Learn方法進行完整的學習。由于采用的是基于值迭代的動態(tài)規(guī)劃算法，所以在Learn方法中調(diào)用了Evaluation方法，具體原理參見3.3.2 值迭代。Evaluation方法代碼如下所示：</p><p>　　(2)Evaluation方法在界面程序中的應用</p><p>　　在具體實

98、現(xiàn)的過程中，由于每迭代一次都需要更新界面中的最優(yōu)策略圖及V值圖，并且在迭代過程中用戶也可能需要隨時暫停，因此并沒有直接使用Learn方法來進行機器學習，而是在界面的backgroundWorker1_DoWork()事件中，按照Learn方法的思想，調(diào)用Ealuation方法，并在每次迭代中更新界面中的圖。核心代碼如下所示：</p><p>　　(3)GetAllBestActions方法</p>

99、<p>　　還有一個關(guān)鍵點就是最優(yōu)策略的獲取。在實際問題中，一個狀態(tài)的最優(yōu)動作是通過計算這個狀態(tài)下所有可以選擇動作的，值最大所對應的動作即是最優(yōu)策略，因此不排除在同一狀態(tài)下幾個最優(yōu)策略，因此應該采用ActionList來存儲所有的最優(yōu)動作值。具體代碼如下：</p><p><b>　　本章小結(jié)</b></p><p>　　本章首先對實驗平臺進行的介紹，說明了

100、所要展示的系統(tǒng)以及該系統(tǒng)運行的環(huán)境。其次，對Gambler問題進行的具體的描述。然后詳細分析了實驗平臺的概要設計和實現(xiàn)細節(jié)，在分析過程中介紹了各類之間的關(guān)系，并且以代碼的形式說明了核心算法。實驗平臺實現(xiàn)了強化學習中的DP算法在Gambler問題中的具體運用，下一章將對實驗結(jié)果進行分析。</p><p>　　第五章 實驗結(jié)果分析</p><p><b>　　實驗結(jié)果</b&g

101、t;</p><p>　　在本實驗平臺中，所有最優(yōu)動作即V值最大的所有點，都在最優(yōu)策略圖上顯示了出來，因此在同一狀態(tài)下可能有兩個或三個最優(yōu)動作，這與書上的最優(yōu)策略圖略有區(qū)別。在P=0.4 的默認條件下，最優(yōu)策略圖及V值圖如下圖5.1，圖5.2所示。</p><p><b>　　圖5.1最優(yōu)策略圖</b></p><p><b>　　圖

102、5.2 V值圖</b></p><p>　　當程序運行結(jié)束后，程序中所涉及到的各種數(shù)據(jù)，狀態(tài)和動作的屬性，以及對環(huán)境的描述都會存儲到項目所在文件夾的Test.xml文件中，用于以后的數(shù)據(jù)分析。</p><p>　　Gambler仿真結(jié)果分析</p><p>　　針對Gambler這個具體問題，以下將對它的實驗結(jié)果進行分析。</p><

103、p>　　Gambler 在不同P值下的策略</p><p>　　當P<0.5時，取P為0.4，最優(yōu)策略圖如圖5.1所示</p><p>　　當P=0.5時，最優(yōu)策略圖如圖5.3所示</p><p>　　圖5.3 P=0.5時的最優(yōu)策略圖</p><p>　　當P>0.5時，取P為0.6，最優(yōu)策略圖如圖5.4所示</p&

104、gt;<p>　　圖5.4 P=0.6時的最優(yōu)策略圖</p><p><b>　　策略分析與評價</b></p><p>　　由以上三張圖可以看出，當P值不同時策略圖有很大的變化。策略圖的得出是每個狀態(tài)的最優(yōu)動作，最優(yōu)動作的計算在4.4.2核心算法示例中有具體的代碼說明，程序通過P值和每個狀態(tài)的V值求得最優(yōu)動作，策略圖是根據(jù)計算結(jié)果求解出來的。從圖上可以

105、看出，當P=0.5時，幾乎所有的可用動作都可以用作最優(yōu)策略，這是因為此時賭徒的輸贏類似于隨機概率。但是當P>0.5時，所有的最優(yōu)動作變?yōu)?，這與P<0.5時出現(xiàn)有規(guī)律的變化完全不同。一般人都會認為在贏的概率大的情況下應該多壓一些賭金，能夠迅速取勝，但是經(jīng)過機器學習后，卻得出以每次只壓1美元這種最慢的速度來進行操作，下面將從概率論的角度解釋其原因。</p><p>　　以賭徒手中有2美元為例。當P=0.

106、4時，根據(jù)最優(yōu)策略圖5.1，此時的最優(yōu)策略為2，下一狀態(tài)變?yōu)?的概率是0.4。如果采用圖5.4的做法，每次只壓1美元，如圖5.5所示，</p><p>　　是從2美元變成4美元的具體過程，最終獲得4美元的概率是：。同理，當P=0.6時，根據(jù)圖5.4應采用每次只壓1美元的策略，則變成4美元的概率是：</p><p>　　圖5.5 從2美元變成4美元的過程</p><p&g

107、t;　　從現(xiàn)實角度分析，當P>0.5時，只有增加參與的次數(shù)，才能使實際贏的概率更大。</p><p>　　計算誤差對策略的影響</p><p>　　在本實驗平臺中，最終算出的數(shù)據(jù)并不是與理論值完全一致的，理論上，當P=0.4時，最優(yōu)策略圖應如圖5.6所示，可以很明顯的表示出最優(yōu)策略的趨勢。通過比較圖5.6和圖5.1，發(fā)現(xiàn)在圖5.1中存在一些突變的點，比如當16，17，18這三個狀態(tài)點

108、，根據(jù)理論，采取的最優(yōu)策略應該是9，8，7，但是在圖5.1中卻是16，17，18。通過跟蹤程序中的數(shù)據(jù)，發(fā)現(xiàn)本實驗平臺計算出來的V值在小數(shù)點后14位至16位與理論值存在誤差，就是由于這樣細微的差別導致了最終數(shù)據(jù)存在一些突變的值。這也是本次畢業(yè)設計存在欠缺的方面，但是總體來說，整個實驗平臺的設計思路和實現(xiàn)方式都是正確的。</p><p>　　圖5.6 當P=0.4時理論上的最優(yōu)策略圖</p><

109、p><b>　　本章小結(jié)</b></p><p>　　本章對Gambler問題的實驗結(jié)果進行了分析，比較了不同P值下的最優(yōu)策略，并且解釋了當P>0.5時出現(xiàn)所有最優(yōu)策略都是1的原因。最后提出了V值計算誤差對策略的影響。</p><p><b>　　第六章 總結(jié)與展望</b></p><p><b>　

110、　課題總結(jié)</b></p><p>　　本論文論述的是強化學習理論的仿真實現(xiàn)，課題基于強化學習開展的動態(tài)規(guī)劃算法和Gambler具體問題的研究。論文中著重研究和討論了基于值迭代的動態(tài)規(guī)劃算法以及在Gambler問題上的應用。</p><p>　　本設計能夠很好地展現(xiàn)強化學習的思想，系統(tǒng)結(jié)構(gòu)較合理，具有如下的特點：</p><p>　　普遍、通用、操作簡單

111、</p><p>　　界面簡潔、清晰，操作簡單，用戶可以自行設計參數(shù)(P值)來執(zhí)行強化學習算法，窗口可以進行伸縮。在程序運行的同時，每一次迭代對策略的改進以直觀的圖形展示給用戶。為了更好地進行分析，在界面上還可以看到每次迭代所產(chǎn)生的V值。</p><p>　　系統(tǒng)結(jié)構(gòu)開放，便于擴充</p><p>　　本實驗平臺的底層框架是抽象的，可以運用到其他問題的求解中，本畢業(yè)

112、設計小組的同學也都是使用同一的底層框架，目的在于便于以后強化學習問題的擴充，提供更好的公共接口。</p><p>　　使用XML文檔存儲數(shù)據(jù)</p><p>　　當程序運行結(jié)束后，程序中所有的數(shù)據(jù)，例如V值，以及環(huán)境中涉及到的各種狀態(tài)，屬性都會存儲到XML文檔中，用于以后的數(shù)據(jù)分析。</p><p><b>　　進一步的研究與展望</b><