畢業(yè)設(shè)計(jì)--基于強(qiáng)化學(xué)習(xí)的gambler策略研究與評(píng)價(jià)

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

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 強(qiáng)化學(xué)習(xí)的應(yīng)用3</p><p>　　1.3論文結(jié)構(gòu)安排4</p><p>　　第二章 強(qiáng)化學(xué)習(xí)5</p><p>　　2.1強(qiáng)化學(xué)習(xí)的原理和模型5</p><p>　　2.2強(qiáng)化學(xué)習(xí)系統(tǒng)的主要組成要素6</p><

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

5、有待解決的問題9</p><p>　　2.6本章小結(jié)9</p><p>　　第三章 動(dòng)態(tài)規(guī)劃分析10</p><p>　　3.1動(dòng)態(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策略評(píng)估11</p><p>　　3.2.2策略改進(jìn)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動(dòng)態(tài)規(guī)劃的效率13</p><p>　　3.5本章小結(jié)13</p><p>　　第四章 實(shí)驗(yàn)平臺(tái)分析與實(shí)現(xiàn)14</p><p>　　4.1實(shí)驗(yàn)平臺(tái)描述14</p><p>　　4.1.1系統(tǒng)概述14</p><p>　　4.1.2系統(tǒng)運(yùn)行環(huán)境14</p&

8、gt;<p>　　4.2Gambler問題仿真14</p><p>　　4.3實(shí)驗(yàn)平臺(tái)概要設(shè)計(jì)15</p><p>　　4.3.1底層框架模型15</p><p>　　4.3.2 Gambler問題模型17</p><p>　　4.3.3界面設(shè)計(jì)17</p><p>　　4.4實(shí)驗(yàn)平臺(tái)的詳

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

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

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

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

13、如果一個(gè)動(dòng)作得到了最多的獎(jiǎng)勵(lì)，則該動(dòng)作就會(huì)被采取。</p><p>　　本文的特點(diǎn)是在強(qiáng)化學(xué)習(xí)理論研究的基礎(chǔ)上，以Gambler問題為仿真實(shí)驗(yàn)平臺(tái)，對(duì)強(qiáng)化學(xué)習(xí)中的動(dòng)態(tài)規(guī)劃算法進(jìn)行實(shí)現(xiàn)，并對(duì)不同P值下的實(shí)驗(yàn)結(jié)果進(jìn)行分析。</p><p>　　關(guān)鍵詞：強(qiáng)化學(xué)習(xí)，機(jī)器學(xué)習(xí)，動(dòng)態(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>　　學(xué)習(xí)是人類獲取知識(shí)的主要形式，也是人類具有智能的顯著標(biāo)志，是人類提高智能水平的基本途徑。建造具有類似人的智能機(jī)器是智能控制、人工智能研究的一個(gè)核心問題。要使機(jī)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、性，所以產(chǎn)生了介于策略和瞬時(shí)獎(jiǎng)懲之間的狀態(tài)值函數(shù)。即：</p><p><b>　　(2.1)</b></p><p>　　這里 是一個(gè)參數(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>　　在理想狀況下，往往希望一個(gè)狀態(tài)能夠簡(jiǎn)練地抽象總結(jié)過去的感覺，然而這種方式又能保留所有相關(guān)信息。正常的來說，這比只要求即時(shí)感覺要求得更多，但是比要求全部的過去感知?dú)v史要少得多。一個(gè)成功保留所有相關(guān)信息的狀態(tài)信號(hào)稱為馬爾可夫的，或者說具

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

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

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

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

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

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

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

50、rlo method, MC)</p><p>　　蒙特卡羅算法是一種無模型 (model-free) 的學(xué)習(xí)方法，不需要系統(tǒng)模型——狀態(tài)轉(zhuǎn)移函數(shù)和獎(jiǎng)賞函數(shù)，只需要通過與環(huán)境的交互獲得的實(shí)際或模擬樣本數(shù)據(jù) (狀態(tài)、動(dòng)作、獎(jiǎng)賞值) 序列，從而發(fā)現(xiàn)最優(yōu)策略。MC總是基于平均化取樣回報(bào)來解決強(qiáng)化學(xué)習(xí)問題，它把要解決的問題分解為情節(jié)(episode)。當(dāng)環(huán)境狀態(tài)為終止?fàn)顟B(tài)G時(shí)，將得到的累積回報(bào)賦予開始狀態(tài)S的值函數(shù)。由于

51、從起始狀態(tài)到終止?fàn)顟B(tài)的過程中，S可能不止出現(xiàn)一次，這樣對(duì)S的值函數(shù)的更新，可以有兩種方法:FVMC(First Visit MC)和EVMC(Every Visit MC)。前者將回報(bào)賦予第一次訪問的S,后者將每次訪問S到終止?fàn)顟B(tài)G的回報(bào)平均化以后賦予S的值函數(shù)。兩者雖然在理論上有區(qū)別，但是都可以最終收斂到最優(yōu)值函數(shù)。</p><p>　　與動(dòng)態(tài)規(guī)劃方法相比，MC法直接同環(huán)境交互獲得經(jīng)驗(yàn)來優(yōu)化動(dòng)作行為，不需建立一

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

76、設(shè)定賭徒贏的概率，程序運(yùn)行過程中，我們可以看到機(jī)器學(xué)習(xí)過程中所產(chǎn)生的V值以及最優(yōu)策略的變化情況。</p><p><b>　　系統(tǒng)運(yùn)行環(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>　　實(shí)驗(yàn)環(huán)境：Visual Studio 2008</p><p>　　Gambler問題仿真</p><p>　　一個(gè)賭徒利用硬幣投擲的正反面結(jié)果來賭博。假如投擲結(jié)果是硬幣的正面朝上，那么他將贏得他所壓在這一局的相同錢，如果是反面朝上，那么他將輸?shù)羲馁€金。當(dāng)這個(gè)賭徒贏滿100美元或者他輸?shù)羲械腻X時(shí)，賭博結(jié)束。每一輪投擲，賭徒必須取出他資金的一部分作為賭金，賭金必須是整

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

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

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

82、來獲得環(huán)境中的動(dòng)作以及狀態(tài)。IStrategy是采用的算法，包含進(jìn)行學(xué)習(xí)的函數(shù)。在本實(shí)驗(yàn)平臺(tái)中，由于環(huán)境模型是確定的，并未使用到IAgent，因此以下將具體說明環(huán)境，算法及值存儲(chǔ)的相關(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)境類所要繼承的父類。該類同時(shí)繼承IEnvironmentModel和CAbstractEnvironment主要包括一下方法：判斷是否到達(dá)最終狀態(tài)；獲取當(dāng)前狀態(tài)的所有動(dòng)作值；給定一對(duì)狀態(tài)和動(dòng)作后獲得后繼狀態(tài)，獲得立即獎(jiǎng)賞值；初始化狀態(tài)；獲得所有狀態(tài)；以文本形式返回所有的屬性。</p><p>　　IGraphics是一個(gè)畫圖的接口，使用該接口可以將環(huán)境中的信息及時(shí)返

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

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

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

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

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

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

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

91、定P值，獲取P值。</p><p><b>　　界面設(shè)計(jì)</b></p><p>　　界面設(shè)計(jì)應(yīng)遵循簡(jiǎn)潔美觀，方便易用的基本原則。</p><p>　　程序界面主要由兩部分組成：左邊的圖形顯示區(qū)和右邊的具體信息顯示區(qū)。右邊的區(qū)域能夠自由的展開或者隱藏。點(diǎn)擊暫停按鈕可以暫停迭代過程。整個(gè)頁面布局使用CLR來實(shí)現(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>　　實(shí)驗(yàn)平臺(tái)的詳細(xì)設(shè)計(jì)</b></p><p>　　基于上述的底層框架和具體問題模型，本系統(tǒng)在Visual Studio 2008開發(fā)環(huán)境上采用CLR實(shí)現(xiàn)了具體的功能。在具體實(shí)現(xiàn)的過程中，程序中加入了一些額

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

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

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

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

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

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

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

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

101、t;</p><p>　　在本實(shí)驗(yàn)平臺(tái)中，所有最優(yōu)動(dòng)作即V值最大的所有點(diǎn)，都在最優(yōu)策略圖上顯示了出來，因此在同一狀態(tài)下可能有兩個(gè)或三個(gè)最優(yōu)動(dòng)作，這與書上的最優(yōu)策略圖略有區(qū)別。在P=0.4 的默認(rèn)條件下，最優(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>　　當(dāng)程序運(yùn)行結(jié)束后，程序中所涉及到的各種數(shù)據(jù)，狀態(tài)和動(dòng)作的屬性，以及對(duì)環(huán)境的描述都會(huì)存儲(chǔ)到項(xiàng)目所在文件夾的Test.xml文件中，用于以后的數(shù)據(jù)分析。</p><p>　　Gambler仿真結(jié)果分析</p><p>　　針對(duì)Gambler這個(gè)具體問題，以下將對(duì)它的實(shí)驗(yàn)結(jié)果進(jìn)行分析。</p><

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

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

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

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

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

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

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

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

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

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