基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法及應(yīng)用研究分析 數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)

目錄第一章緒論 11.1 研究背景及意義 11.2 研究現(xiàn)狀 21.3 論文的主要工作及組織結(jié)構(gòu) 3第二章背景知識介紹 52.1馬爾科夫決策過程 52.2基于模型的動態(tài)規(guī)劃方法 62.3基于蒙特卡羅方法的理論 62.4基于時間差分的強(qiáng)化學(xué)習(xí)方法 72.4.1SARSA學(xué)習(xí) 82.4.2Q-learning方法 9第三章Q-learning及其改進(jìn)算法研究 103.1Q-learning算法 103.1.1Q-learning簡介 103.1.2Q-learning算法收斂性討論 123.1.3Q-learning算法分析 143.1.4單一估計器造成高估的證明 163.2DoubleQ-learning方法 163.2.1DoubleQ-learning的提出 163.2.2算法分析 173.3WeightedQ-learning 193.3.1簡介 203.3.2算法分析 203.3.3誤差估計 223.4WeightedDoubleQ-learning方法 23第四章相關(guān)試驗(yàn)與結(jié)果 254.1實(shí)驗(yàn)設(shè)計 254.2結(jié)果分析 28第五章總結(jié)與展望 295.1全文總結(jié) 295.2后續(xù)工作與展望 29參考文獻(xiàn) 31致謝 33摘要Q-learning是一種流行的無模型的強(qiáng)化學(xué)習(xí)方法。學(xué)習(xí)者通過不斷地與環(huán)境互動獲得新知識，并反過來改進(jìn)自己的行動策略，最終得到在馬爾科夫決策過程中以最佳方式行事的能力。然而，Q-learning對動作值函數(shù)的估計會有一個正偏差，這使得Q-learning在一些隨機(jī)環(huán)境中的表現(xiàn)不及預(yù)期中的那么好。為了解決這種偏差，在此基礎(chǔ)上提出了DoubleQ-learning方法。DoubleQ-learning方法的革新之處在于使用了雙估計器方法，這種方法有時會低估而不是高估最大期望值。已有的工作表明，在許多順序決策場景中，DoubleQ-learning方法在性能上優(yōu)于Q-learning，但仍無法避免絕對偏差。于是，本文接著介紹了WeightedQ-learning，它基于樣本均值的加權(quán)平均來估計最大期望值，可以有效避免估計的偏差。本文研究分析了Q-learning以及其變種DoubleQ-learning在估計最大期望值時產(chǎn)生誤差的內(nèi)在原因，并證明了WeightedQ-learning的確能有效避免這種誤差。在理論分析的基礎(chǔ)上，設(shè)計了“格子世界”的仿真實(shí)驗(yàn)以觀察集幾種算法在生產(chǎn)環(huán)境中的表現(xiàn)情況，并將實(shí)驗(yàn)結(jié)果和理論結(jié)果相互驗(yàn)證。為了觀察幾種算法Q值在迭代過程中的變化，本文可視化了“格子世界”的實(shí)驗(yàn)結(jié)果，以顏色深淺來表示每個格子Q值的大小，更加直觀易懂。本文最后對于強(qiáng)化學(xué)習(xí)未來的發(fā)展前景提出了自己的設(shè)想和展望。關(guān)鍵詞：馬爾科夫決策過程；最大期望值估計；基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法；Q-learningAbstractQ-learningisapopularreinforcementlearningmethod.Agentcontinuouslyacquirenewknowledgebyinteractingwiththeenvironmentand,inturn,improvetheirowntacticsofaction,andultimatelygaintheabilitytoactinthebestwayintheMarkovdecisionprocess.However,Q-learninghasapositivebiasintheestimationoftheactionvaluefunction,whichmakesQ-learningperformlesswellthanexpectedinsomerandomenvironments.Inordertosolvethiskindofdeviation,aDoubleQ-learningmethodisproposedonthisbasis.TheinnovationoftheDoubleQ-learningmethodistheuseofthedoubleestimatormethod,whichsometimesunderestimatesratherthanoverestimatesthemaximumexpectation.ExistingworkhasshownthattheDoubleQ-learningmethodoutperformsQ-learninginmanysequentialdecisionscenarios,butitstillcannotavoidabsolutedeviations.Therefore,thispaperthenintroducesWeightedQ-learning,whichestimatesthemaximumexpectedvaluebasedontheweightedaverageofthesamplemeans,whichcaneffectivelyavoidthebiasoftheestimation.Inthispaper,theinternalcausesofQ-learninganditsvariantDoubleQ-learninginestimatingthemaximumexpectedvaluearestudiedandanalyzed.ItisprovedthatWeightedQ-learningcaneffectivelyavoidthiskindoferror.Basedonthetheoreticalanalysis,asimulationexperimentof"LatticeWorld"wasdesignedtoobservetheperformanceofseveralalgorithmsintheproductionenvironment,andtheexperimentalresultsandtheoreticalresultsweremutuallyverified.InordertoobservethechangesoftheQvalues??ofseveralalgorithmsintheiterativeprocess,thispapervisualizestheexperimentalresultsofthe“LatticeWorld”.TheQvalueofeachgridisexpressedintermsofcolordepth,whichismoreintuitiveandeasiertounderstand.Intheend,thispaperputsforwarditsownideasandprospectsforstrengtheningthefuturedevelopmentoflearning.Keywords:Markovdecisionprocess;Reinforcementlearningmethodbasedonvaluefunction;Q-learning第一章緒論研究背景及意義對人類來說，學(xué)習(xí)的本質(zhì)是什么呢？當(dāng)我們思考這個問題的時候，我們首先應(yīng)該想到的是我們是通過與環(huán)境的不斷互動來進(jìn)行學(xué)習(xí)的。一個嬰兒天生便會揮舞手臂，自己玩耍，正因?yàn)槲覀兩鷣肀闾幱谂c環(huán)境的不斷互動與聯(lián)系中。隨著嬰兒漸漸長大，一些聯(lián)系便會在腦海中逐漸根深蒂固，比如好好學(xué)習(xí)就會有糖吃，上課遲到就會被罰站等，于是我們便“學(xué)”會了。在我們的生活中，這種與環(huán)境的交互無疑是我們的主要知識來源。無論我們是學(xué)習(xí)駕駛汽車還是舉行對話，我們都非常清楚我們的環(huán)境如何回應(yīng)我們的行為，并且我們試圖通過改變自我的行為來影響環(huán)境的反饋。從與環(huán)境交互的過程中學(xué)習(xí)是幾乎所有的機(jī)器學(xué)習(xí)方法理論的基礎(chǔ)。根據(jù)與環(huán)境交互的不同，機(jī)器學(xué)習(xí)可以分為監(jiān)督學(xué)習(xí)（SupervisedLearning）、非監(jiān)督學(xué)習(xí)（UnsupervisedLearning）和強(qiáng)化學(xué)習(xí)（ReinforcementLearning）3類ADDINEN.CITE<EndNote><Cite><Author>高陽</Author><Year>2004</Year><RecNum>14</RecNum><DisplayText><styleface="superscript">[1]</style></DisplayText><record><rec-number>14</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525928409">14</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author><styleface="normal"font="default"charset="134"size="100%">高陽</style></author><author><styleface="normal"font="default"charset="134"size="100%">陳世福</style></author><author><styleface="normal"font="default"charset="134"size="100%">陸鑫</style></author></authors></contributors><titles><title><styleface="normal"font="default"charset="134"size="100%">強(qiáng)化學(xué)習(xí)研究綜述</style></title></titles><dates><year>2004</year></dates><work-type>J</work-type><urls></urls></record></Cite></EndNote>[1]。在監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)中，數(shù)據(jù)是靜態(tài)的不需要與環(huán)境進(jìn)行交互，比如圖像識別，只要給足夠的差異樣本，將數(shù)據(jù)輸入到深度網(wǎng)絡(luò)中進(jìn)行訓(xùn)練即可。而強(qiáng)化學(xué)習(xí)主要的工作是如何在與環(huán)境不斷地交互中建立一個狀態(tài)到動作的映射，從而達(dá)到最大化回報的目的。強(qiáng)化學(xué)習(xí)的學(xué)習(xí)過程是個動態(tài)的，不斷交互的過程，所需要的數(shù)據(jù)也是通過與環(huán)境不斷地交互產(chǎn)生的。所以，與監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)相比，強(qiáng)化學(xué)習(xí)涉及到的對象更多，比如動作，環(huán)境，狀態(tài)轉(zhuǎn)移概率和回報函數(shù)等。另外，深度學(xué)習(xí)如圖像識別和語音識別解決的是感知的問題，強(qiáng)化學(xué)習(xí)解決的是決策的問題。人工智能的終極目的是通過感知進(jìn)行智能決策。所以，將近年發(fā)展起來的深度學(xué)習(xí)技術(shù)與強(qiáng)化學(xué)習(xí)算法結(jié)合而產(chǎn)生的深度強(qiáng)化學(xué)習(xí)算法是人類實(shí)現(xiàn)人工智能終極目的的一個很有前景的方法。在許多機(jī)器學(xué)習(xí)問題中，收集到每個隨機(jī)變量的樣本值后，我們常常需要估計這些變量的最大期望值（MEV）ADDINEN.CITE<EndNote><Cite><Author>Bellman</Author><Year>2013</Year><RecNum>6</RecNum><DisplayText><styleface="superscript">[2]</style></DisplayText><record><rec-number>6</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525784357">6</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Bellman,Richard</author></authors></contributors><titles><title>Dynamicprogramming</title></titles><dates><year>2013</year></dates><publisher>CourierCorporation</publisher><isbn>0486317196</isbn><work-type>J</work-type><urls></urls></record></Cite></EndNote>[2]。例如，在強(qiáng)化學(xué)習(xí)中，我們可以通過在每個狀態(tài)下都采取達(dá)到最大預(yù)期累積獎勵的行動來找到最佳策略。在一個狀態(tài)中，動作的最優(yōu)值依賴于其所能達(dá)到的最大期望值。由于學(xué)習(xí)過程中的誤差是通過狀態(tài)-行為對來傳播的，所以在估計最大期望值時，所采用的估計器的表現(xiàn)將會影響學(xué)習(xí)速度ADDINEN.CITE<EndNote><Cite><Author>Hasselt</Author><Year>2010</Year><RecNum>1</RecNum><DisplayText><styleface="superscript">[3]</style></DisplayText><record><rec-number>1</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525783859">1</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Hasselt,HadoV</author></authors></contributors><titles><title>DoubleQ-learning</title><secondary-title>AdvancesinNeuralInformationProcessingSystems</secondary-title></titles><pages>2613-2621</pages><dates><year>2010</year></dates><work-type>M</work-type><urls></urls></record></Cite></EndNote>[3]。最常見的估計器是最大估計量(MaximumEstimator,ME)，它涉及到使用最大樣本均值來估計最大期望值。在使用單一估計器時，令μ={μ1,μ2?μN(yùn)}是一組無偏估計量，使得對于所有i，有Eμi=E{Xi}。假定D=∪i=1NDi是一組樣本，其中Di是至少包含變量Xi一個樣本的子集，并且Di中元素滿足為了避免使用單一估計器產(chǎn)生的最大化偏差，Hasselt提出了雙估計器方法ADDINEN.CITE<EndNote><Cite><Author>Hasselt</Author><Year>2010</Year><RecNum>1</RecNum><DisplayText><styleface="superscript">[3]</style></DisplayText><record><rec-number>1</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525783859">1</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Hasselt,HadoV</author></authors></contributors><titles><title>DoubleQ-learning</title><secondary-title>AdvancesinNeuralInformationProcessingSystems</secondary-title></titles><pages>2613-2621</pages><dates><year>2010</year></dates><work-type>M</work-type><urls></urls></record></Cite></EndNote>[3]。其中關(guān)鍵在于將樣本D分成兩個不相交的子集DU和DV。設(shè)μU={μ1U,μ2U?μN(yùn)U}和μV={μ1V,μ2V,?μN(yùn)V}是兩組無偏估計量，本文探究的重點(diǎn)——基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法已被證明能找到全局最優(yōu)策略，它在一些諸如掃地機(jī)器人尋路，格子游戲等小規(guī)模強(qiáng)化學(xué)習(xí)問題中有著非常好的性能，但仍存在如上述對最大期望值估計不準(zhǔn)確的問題，本文將一一探究這些方法，并做仿真實(shí)驗(yàn)?zāi)M算法效果。研究現(xiàn)狀早期的強(qiáng)化學(xué)習(xí)的發(fā)展主要包括兩條主線，一個是涉及動物心理學(xué)的“試錯學(xué)習(xí)”，另一個設(shè)計最優(yōu)控制問題以及使用值函數(shù)和動態(tài)規(guī)劃的解決方案。20世紀(jì)50年代后期，理查德·貝爾曼等人提出了“最優(yōu)控制”理論，使用動態(tài)系統(tǒng)狀態(tài)和值函數(shù)的概念來定義一個函數(shù)方程，現(xiàn)在我們常稱之為貝爾曼方程。貝爾曼還引入了稱為馬爾科夫決策過程（MDPs）的最優(yōu)控制問題的離散版本，RonaldHovvard設(shè)計了MDP的策略迭代方法。所有這些，都為現(xiàn)代強(qiáng)化學(xué)習(xí)理論奠定了基礎(chǔ)。1988年，RichardSutton提出時間差分算法(Temporal-Difference,TD)，時間查分方法是另一種無模型強(qiáng)化學(xué)習(xí)方法，也可以視作強(qiáng)化學(xué)習(xí)的第三條發(fā)展主線，主要用于解決時間信都分配問題。這里所謂的時間差分是指在不同時刻下，對某一變量的觀察值的差。1989年，ChrisWatkins等人提出了Q-learning算法，并將動態(tài)規(guī)劃和時間差分思想與Q-learning很好地結(jié)合起來，并證明了Q-learning的收斂性，指出了只要所有狀態(tài)對的訪問概率大于0，算法就會收斂ADDINEN.CITE<EndNote><Cite><Author>Sutton</Author><Year>2009</Year><RecNum>13</RecNum><DisplayText><styleface="superscript">[4]</style></DisplayText><record><rec-number>13</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525928052">13</key></foreign-keys><ref-typename="ConferenceProceedings">10</ref-type><contributors><authors><author>Sutton,RichardS</author><author>Maei,HamidReza</author><author>Precup,Doina</author><author>Bhatnagar,Shalabh</author><author>Silver,David</author><author>Szepesvári,Csaba</author><author>Wiewiora,Eric</author></authors></contributors><titles><title>Fastgradient-descentmethodsfortemporal-differencelearningwithlinearfunctionapproximation</title><secondary-title>Proceedingsofthe26thAnnualInternationalConferenceonMachineLearning</secondary-title></titles><pages>993-1000</pages><dates><year>2009</year></dates><publisher>ACM</publisher><isbn>1605585165</isbn><urls></urls></record></Cite></EndNote>[4]。Mahadevan等人在原有的Q-learning算法的基礎(chǔ)上提出了基于平均獎上函數(shù)（R-Learning）的方法，并與Q-learning算法進(jìn)行對比，證明了在很多平均強(qiáng)化學(xué)習(xí)算法的性能優(yōu)于Q-learning算法。1994年，Rummery和Niranjan提出了提出SARSA算法。SARSA是一種模型相關(guān)算法，它在TD方法的基礎(chǔ)上擴(kuò)展到了控制學(xué)習(xí)中，也被稱為改進(jìn)的Q-learning方法。近幾年，強(qiáng)化學(xué)習(xí)發(fā)展迅速，在理論和算法方面取得了長足的進(jìn)步。Sutton引入了值函數(shù)來改進(jìn)時間差分算法，使之能更好的適用于時間信用分配問題。Watkins等提出了Q-learning方法借助CMAC實(shí)現(xiàn)Q值的逼近ADDINEN.CITE<EndNote><Cite><Author>Watkins</Author><Year>1992</Year><RecNum>2</RecNum><DisplayText><styleface="superscript">[5]</style></DisplayText><record><rec-number>2</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525783901">2</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Watkins,ChristopherJCH</author><author>Dayan,Peter</author></authors></contributors><titles><title>Q-learning</title><secondary-title>Machinelearning</secondary-title></titles><periodical><full-title>Machinelearning</full-title></periodical><pages>279-292</pages><volume>8</volume><number>3-4</number><dates><year>1992</year></dates><isbn>0885-6125</isbn><work-type>C</work-type><urls></urls></record></Cite></EndNote>[5]。AlessandroNuara提出了WeightedQ-learning方法試圖解決Q-learning估計最大期望值不準(zhǔn)確的問題，在此基礎(chǔ)上章宗長等提出了WeightedDoubleQ-learning以追求更準(zhǔn)確的估計值。論文的主要工作及組織結(jié)構(gòu)本文主要研究了幾種基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法，提出了自己的想法和見解，并做仿真實(shí)驗(yàn)探究了他們之間的區(qū)別。主要工作和文章結(jié)構(gòu)如下：第一章：緒論。主要介紹了強(qiáng)化學(xué)習(xí)的一些發(fā)展歷史，以及Q-learning方法在近幾年的研究現(xiàn)狀。說明了本文的行文邏輯和組織結(jié)構(gòu)。第二章：背景知識。本章介紹了在研究值函數(shù)強(qiáng)化學(xué)習(xí)算法之前需要了解的基礎(chǔ)知識，主要包括馬爾科夫決策過程、蒙特卡羅方法、時間差分方法等。第三章：深入研究Q-learning方法，并給出詳細(xì)證明，指出Q-learning所面臨的困境并且分析成因。以此為基礎(chǔ)，介紹了DoubleQ-learning，WeightedQ-learning等幾種改進(jìn)算法，并同Q-learning在算法和性能上作對比。第四章：相關(guān)實(shí)驗(yàn)。將上一章所論述的集中算法在“格子世界”中實(shí)現(xiàn)，并可視化幾種算法在迭代過程中Q值的變化過程。第五章：總結(jié)與展望。對本論文的研究內(nèi)容做出總結(jié)，并對強(qiáng)化學(xué)習(xí)、值函數(shù)方法未來的發(fā)展前景提出自己的設(shè)想。

第二章背景知識介紹2.1馬爾科夫決策過程總的來說，馬爾科夫決策過程，簡稱MDP，是近幾十年間無數(shù)學(xué)者通過不斷的努力和探索提出的一套可以解決大部分強(qiáng)化學(xué)習(xí)問題的框架。所謂馬爾科夫性是指系統(tǒng)的下一個狀態(tài)st+1僅與當(dāng)前狀態(tài)st有關(guān)，與之前的狀態(tài)無關(guān)。用數(shù)學(xué)的話講就是：狀態(tài)sP由此可以看到，如果當(dāng)前狀態(tài)st是馬爾科夫的，那么它包含了所有相關(guān)的歷史信息s1,s2···,st，那就意味著一旦當(dāng)前狀態(tài)已知，歷史信息將會被拋棄。如果對于一個隨機(jī)變量序列M，它的每個狀態(tài)m1,m2···,mn都是馬爾科夫的，則稱此隨機(jī)過程為馬爾科夫隨機(jī)過程ADDINEN.CITE<EndNote><Cite><Author>鄧鑫洋</Author><Year>2012</Year><RecNum>15</RecNum><DisplayText><styleface="superscript">[6]</style></DisplayText><record><rec-number>15</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525928549">15</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author><styleface="normal"font="default"charset="134"size="100%">鄧鑫洋</style></author><author><styleface="normal"font="default"charset="134"size="100%">鄧勇</style></author><author><styleface="normal"font="default"charset="134"size="100%">章雅娟</style></author><author><styleface="normal"font="default"charset="134"size="100%">馬爾可夫決策過程是基于馬爾可夫過程理論的隨機(jī)動態(tài)系統(tǒng)的決策過程，它可以用元(S,A,P,R,γ)來描述，其中：:有限的狀態(tài)集；:為有限的動作集；P:狀態(tài)轉(zhuǎn)移概率；:回報函數(shù)；:折扣因子，用于計算累計回報，。與馬爾科夫過程不同的是，馬爾科夫決策過程的狀態(tài)轉(zhuǎn)移概率是包含動作的，可用如下公式表示：P由式（2-2）不難發(fā)現(xiàn)，系統(tǒng)的下個狀態(tài)不僅和當(dāng)前的狀態(tài)有關(guān)，也和當(dāng)前采取的動作有關(guān)。但是在某個狀態(tài)下采取哪個行動只和當(dāng)前的s和a有關(guān)，而不用考慮之前的狀態(tài)和動作。強(qiáng)化學(xué)習(xí)的目標(biāo)是給定一個馬爾可夫決策過程，尋找最優(yōu)策略。所謂策略是狀態(tài)到動作的映射，策略常用符號π來表示，它是指給定狀態(tài)s時，動作及上的一個分布，即π以上公式的含義是：策略π在每個狀態(tài)s指定一個動作概率。如果給出的策略π是確定性的，那么策略π在每個狀態(tài)s指定一個確定的動作。2.2基于模型的動態(tài)規(guī)劃方法廣義上講，強(qiáng)化學(xué)習(xí)是一個序貫決策問題，目標(biāo)是找到最優(yōu)策略π使得累計回報的期望最大。所謂策略是狀態(tài)到動作的映射π:s→α，用τ表示從狀態(tài)s到最終狀態(tài)的一個序列τ:st,st+1···，sT，這是累計回報max強(qiáng)化學(xué)習(xí)的最終目標(biāo)就是找到最優(yōu)策略為π*:s→u根據(jù)貝爾曼最優(yōu)性原理，對于一個給定的策略π，狀態(tài)值函數(shù)和狀態(tài)-行為值函數(shù)的計算公式為：vq式（2.5）表示，在狀態(tài)s處的值函數(shù)等于采用策略π時，所有狀態(tài)-行為值函數(shù)的總和。式（2.6）表示在狀態(tài)s采用動作a的狀態(tài)值函數(shù)等于回報加上后續(xù)狀態(tài)值函數(shù)。2.3基于蒙特卡羅方法的理論在上一節(jié)中，式（2.5）、（2.6）在計算狀態(tài)s處的值函數(shù)時利用了模型Pss'a，而在無模型強(qiáng)化學(xué)習(xí)中，模型Pss'a是未知的，這時我們可以采用蒙特卡羅的方法計算該期望。蒙特卡羅思想最初起源于概率論和數(shù)理統(tǒng)計，在計算值函數(shù)時，蒙特卡羅方法能利用經(jīng)驗(yàn)平均代替隨機(jī)變量的期望，用隨即大量實(shí)驗(yàn)來模擬真實(shí)值。所謂“經(jīng)驗(yàn)平均”，是指當(dāng)我們評估智能體的當(dāng)前策略π時，我們可以利用策略π產(chǎn)生很多次實(shí)驗(yàn)G經(jīng)過很多次這樣的實(shí)驗(yàn)，會產(chǎn)生多幕數(shù)據(jù)，然后對這些數(shù)據(jù)的回報求平均值。在使用蒙特卡羅方法估計真實(shí)值時，充分評估策略值函數(shù)的前提是每個狀態(tài)都能至少被訪問一次，因此，在MC方法中必須采用一定的方法使每個狀態(tài)都能被訪問到。方法之一是探索性初始化，該方法能保證每個狀態(tài)都有一定的幾率作為初始狀態(tài)。探索性初始化蒙特卡羅方法偽代碼為：2.4基于時間差分的強(qiáng)化學(xué)習(xí)方法時間差分(Temporal-Difference,TD)方法是另外一種無模型的強(qiáng)化學(xué)習(xí)方法。與蒙特卡羅方法和動態(tài)規(guī)劃的方法相比，TD方法的區(qū)別主要在值函數(shù)的估計上。式（2.5）、（2.6）說明了在使用動態(tài)規(guī)劃方法計算值函數(shù)時用到了當(dāng)前狀態(tài)s的所有后繼狀態(tài)s'處的值函數(shù)，這是一種典型的自舉算法。應(yīng)當(dāng)注意的是，此處后繼的狀態(tài)是由模型公式p(s',r|St,無模型時，我們同樣可以采用蒙特卡羅的方法利用經(jīng)驗(yàn)平均來估計當(dāng)前狀態(tài)的值函數(shù)。此處的經(jīng)驗(yàn)指一次實(shí)驗(yàn)，而一次實(shí)驗(yàn)要等到中止?fàn)顟B(tài)出現(xiàn)才結(jié)束。式（2.7）中的Gt是狀態(tài)S時間差分方法結(jié)合了蒙特卡羅的采樣方法和動態(tài)規(guī)劃的自舉方法，將值函數(shù)的公式更新為：V其中a為學(xué)習(xí)速率，Rt+1+γV(St+1)被稱為TD目標(biāo)，與式（2.6）中的Gt對應(yīng)，兩者不同之處在于TD目標(biāo)利用了自舉2.4.1SARSA學(xué)習(xí)Rummery和Niranjan在1994年在Q-learning的基礎(chǔ)上提出了一種在線策略算法，期初被稱之為改進(jìn)的Q-learning算法，后稱SARSA學(xué)習(xí)算法ADDINEN.CITE<EndNote><Cite><Author>Rummery</Author><Year>1994</Year><RecNum>12</RecNum><DisplayText><styleface="superscript">[7]</style></DisplayText><record><rec-number>12</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525831717">12</key></foreign-keys><ref-typename="Book">6</ref-type><contributors><authors><author>Rummery,GavinA</author><author>Niranjan,Mahesan</author></authors></contributors><titles><title>On-lineQ-learningusingconnectionistsystems</title></titles><volume>37</volume><dates><year>1994</year></dates><publisher>UniversityofCambridge,DepartmentofEngineering</publisher><urls></urls></record></Cite></EndNote>[7]。SARSA迭代過程中使用的是真實(shí)的Q值，在狀態(tài)s時根據(jù)貪婪策略選擇一個動作a，得到回報r和下一個狀態(tài)s'，然后繼續(xù)根據(jù)貪婪策略選擇st作為下一個行動，直至所有的Q(s,a)收斂。同策略SARSA強(qiáng)化學(xué)習(xí)算法中，行動策略和評估的策略都是?-greedy策略。?-greedy策略是強(qiáng)化學(xué)習(xí)最基本最常用的隨機(jī)策略，其含義是選取是的動作值函數(shù)最大的動作的概率為1-?+?As，而其他動作的概率為等概率，都為?As。?-greedy策略平衡了利用(exploitation)2.4.2Q-learning方法與SARSA方法不同，Q-learning是一種異策略的強(qiáng)化學(xué)習(xí)方法。所謂異策略是指產(chǎn)生數(shù)據(jù)的策略與評估和改善的策略不是同一個策略。我們使用π表示用來評估和改善的策略，使用μ來表示產(chǎn)生樣本數(shù)據(jù)的策略。用于異策略的目標(biāo)策略π和行動策略μ并非任意選擇的，而是必須滿足一定的條件，這個條件是覆蓋性條件，即行動策略產(chǎn)生的行為覆蓋包含目標(biāo)策略產(chǎn)生的行為。異策略可以保證充分的探索性。例如用來評估和改善的策略π是貪婪策略，用于產(chǎn)生數(shù)據(jù)的探索性策略μ為探索性策略，如?-soft策略。在Q-learning中，評估和改善的策略是Q比較Q-learning算法和SARSA算法不難發(fā)現(xiàn)，他們一個顯著的不同點(diǎn)在于在更新值函數(shù)時Q-learning使用了貪心算法尋找maxaQ(st+1,a)。Q-learning行動策略采用的是第三章Q-learning及其改進(jìn)算法研究3.1Q-learning算法3.1.1Q-learning簡介Q-learning是由Watkins在時間差分的基礎(chǔ)上提出的借助狀態(tài)-動作對值函數(shù)Q（s,a）來進(jìn)行值函數(shù)迭代的一種模型無關(guān)的強(qiáng)化學(xué)習(xí)算法，又稱為離策略TD學(xué)習(xí)（off-policyTD）{Bellman,1954#7}。Q-learning同樣可以視作是一種異策略蒙特卡羅方法，每次行動使用貪婪策略作為評估策略評估Q值函數(shù)，使用貪心策略作為行動函數(shù)產(chǎn)生樣本數(shù)據(jù)，通過探索行為序列，它能使學(xué)習(xí)者在馬爾科夫域中采取最佳的動作，而不需要構(gòu)建域的映射。Q-learning的學(xué)習(xí)過程同時間差分方法類似：學(xué)習(xí)者在某個特定的狀態(tài)下嘗試某個動作，并根據(jù)其產(chǎn)生的直接回報或懲罰以及下一個狀態(tài)的估計價值來評估當(dāng)前狀態(tài)的價值。學(xué)習(xí)者的主要目標(biāo)是尋找到一個最優(yōu)策略，所謂最優(yōu)策略是指根據(jù)該策略所采取的一系列動作能帶來最大的期望獎賞。并且我們認(rèn)為，立即獲取的獎賞要大于延期獲取的獎賞，所以在計算某個狀態(tài)的值函數(shù)時加入了折扣因子γ（0<γ<1)，來對延遲獎賞做修正。學(xué)習(xí)者在狀態(tài)x處能獲得一個立即回報Rxπx，同時也應(yīng)該加上從狀態(tài)x出發(fā)，所有可能達(dá)到的下一個狀態(tài)y的期望回報乘以折扣因子γV式(3.2)，在計算狀態(tài)x的價值時都需要用到下一個狀態(tài)y的價值，然而狀態(tài)y的價值也是未知的，需要用在下一個狀態(tài)計算。所以，這是一種典型的Bootstrapping(自舉)算法，但仍然能夠求解。Q學(xué)習(xí)者面臨的主要問題就是在未知這些值的情況下決定一個最優(yōu)策略π*。動態(tài)規(guī)劃思想提供了一些計算V*和π*的方法，就是假定Rxa和Pxya是已知的，然后在此基礎(chǔ)上回推V*。由于Q-learning在確定最優(yōu)策略時采用這種step-by-step的方式，對于一個策略π，我們將Q值函數(shù)定義為：Q式(3.2)說明，狀態(tài)x的Q值是在狀態(tài)x下采取動作a后獲取的立即獎賞加上之后策略π決定的一系列動作帶來的延遲獎賞。為方便起見我們進(jìn)一步定義為Q*x,a=Qπ*s,a,?x,a。如果采取在Q-learning中，學(xué)習(xí)者需要不斷地經(jīng)歷狀態(tài)到?jīng)Q策，決策再到新的狀態(tài)這樣一種不斷迭代過程。在第n步中，學(xué)習(xí)者需要做的動作依次為：觀察當(dāng)前狀態(tài)xn觀察隨后的狀態(tài)yn，并獲得立即獎賞r接著根據(jù)以下因素使用學(xué)習(xí)因子an來修正Qn-1（3.3）其中：V是學(xué)習(xí)者認(rèn)為在狀態(tài)y下能做出的最好的決策。當(dāng)然，在學(xué)習(xí)的早些階段，Q值并不能準(zhǔn)確的反映他們隱含定義的策略，即式(3.4)中的最大化價值的行為。假定對所有的狀態(tài)和動作最初的Q值是給定的，為Q0(x,a)。這樣我們便可以建立查找表(look-uptable)來儲存Qn(建立Q-table并給每個狀態(tài)賦初始值后，Agent開始根據(jù)Q-table采取動作，并且根據(jù)環(huán)境的反饋反過來對Q-table里的Q值做修正，使能獲得較高獎賞的動作會有更高的概率被執(zhí)行，而相應(yīng)獲得較低獎賞甚至懲罰的動作更不容易被執(zhí)行，經(jīng)過不斷地迭代與修正，Agent采取的動作集最終會收斂至最優(yōu)動作集。Q-learning的每次數(shù)據(jù)更新過程如圖所示：Q-learning的每次數(shù)據(jù)更新過程如圖所示：圖中S代表Agent所經(jīng)歷的狀態(tài)，下標(biāo)代表狀態(tài)的序號。比如Sn代表第n個狀態(tài)。如圖所示，在第一次迭代中，計算S0的值需要用到S1的數(shù)據(jù)，S1不難看出，Q-learning在迭代過程中采用這種step-by-step的方式，每次只傳遞一個數(shù)據(jù)，導(dǎo)致在學(xué)習(xí)效率不高且很難收斂。但Q-learning仍有可取之處，比如它算法容易理解，易于擴(kuò)展，又是一種無模型的強(qiáng)化學(xué)習(xí)方法，所以Q-learning仍不失為一種優(yōu)秀的強(qiáng)化學(xué)習(xí)方法。3.1.2Q-learning算法收斂性討論在證明Q-learning算法之前，為了計算方便，我們合并式(3.3)、(3.4)得到：Q式(3-6)更清楚的表明，對于狀態(tài)st處的Q值時需要用到它上一個狀態(tài)st-1處的Q值。要想得到收斂的Q值就要求maxaQst+1,a是穩(wěn)定的，同理s注意：以下證明過程當(dāng)且僅當(dāng)應(yīng)滿足以下前提時成立學(xué)習(xí)環(huán)境滿足具有MDP性；使用查找表來表示Q函數(shù)；使用的折扣因子γ滿足,0≤γ≤1；自由化問題的解可以被儲存和重復(fù)利用；采用恰當(dāng)?shù)牟介L；在以上證明過程中，我們用到了遞推法，即用下一個狀態(tài)Q值去計算當(dāng)前狀態(tài)的Q值，所以各個狀態(tài)之間的收斂時間不是相等的，狀態(tài)st+1要先于狀態(tài)st收斂。隨著Agent在環(huán)境中迭代次數(shù)的增加，Q-learning的查找表也會趨于穩(wěn)定，最終收斂于最優(yōu)值。Q-table是Q學(xué)習(xí)的精髓所在，收斂的Q-table可以說就是最優(yōu)策略π*的一種體現(xiàn)，他給出了每個狀態(tài)-行為對的Q值。根據(jù)Q3.1.3Q-learning算法分析在上一節(jié)，我們證明了Q-learning使用式(3.5)來進(jìn)行迭代求解值函數(shù)的方法是能夠保證收斂于最優(yōu)值函數(shù)Q*的。下面我們開始對Q-learning的算法進(jìn)行分析。一般的，異策略Q-learning算法為：此算法中Q-learning的更新是：Q在式（3-8）中，Qtst,at給出在時間t時，處于狀態(tài)s下采取動作a的值；獎賞rt決定于一個固定的獎勵分配規(guī)則R:S×A×S→R，其中Erts,a,s'=st,at,st+1=Rsas'；下一個狀態(tài)st+1有固定狀態(tài)轉(zhuǎn)移概率矩陣P:S×A×S→0,1，?式(3.8)中的折扣因子γ可做兩種解釋。首先，它可以被看作是要解決的問題的一個屬性，相比以后的獎賞更看重與當(dāng)前的獎賞。其次，在非場景任務(wù)中，折扣因子確保每個動作值都是有限的。隨著經(jīng)驗(yàn)數(shù)量的上升，Q-learning的收斂時間呈指數(shù)級增長，但這取決于學(xué)習(xí)率，選擇適當(dāng)?shù)膶W(xué)習(xí)率仍可在多項(xiàng)式時間內(nèi)收斂。為了解決這類問題，產(chǎn)生了許多衍生算法，如時延Q學(xué)習(xí)(DelayedQ-learning)，階段Q學(xué)習(xí)(PhasedQ-learning)，和擬合Q迭代(FittedQ-iteration)等。與原始算法相比，這些衍生算法的提出主要為了加快收斂速度。Q-learning已經(jīng)被用于尋找許多問題的解決方案，但又一個重要的問題似乎被忽略掉了：Q-learning在使用最大值作為最大期望值的近似值會產(chǎn)生正偏差，導(dǎo)致動作值的高估，使Q-learning的性能遭受較大的損失。下面，我們來分析這種情況產(chǎn)生的原因?？紤]一組M個隨機(jī)變量X={X1,X2,?XM}，在許多情況下，我們對它的最大期望值maxiEXi感興趣(比如在計算Q值時)ADDINEN.CITE<EndNote><Cite><Author>D’Eramo</Author><Year>2016</Year><RecNum>3</RecNum><DisplayText><styleface="superscript">[9]</style></DisplayText><record><rec-number>3</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525784003">3</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>D’Eramo,Carlo</author><author>Restelli,Marcello</author><author>Nuara,Alessandro</author></authors></contributors><titles><title>Estimatingmaximumexpectedvaluethroughgaussianapproximation</title><secondary-title>InternationalConferenceonMachineLearning</secondary-title></titles><pages>1032-1040</pages><dates><year>2016</year></dates><work-type>O</work-type><urls></urls></record></Cite></EndNote>[9]。通常在不知道X中變量的分布函數(shù)的形式或參數(shù)時，最大期望值是不可能完全確定的，這就需要通過為所有i構(gòu)建E{Xi}的近似值來估計最大期望值E其中μi是變量Xi的估計量。由于每一個樣本s∈S都是E{Xfi表示變量Xi的概率密度函數(shù)(PDFsFi(x)表示變量X在使用上述方法進(jìn)行估計時，一個顯而易見的方法是使用最大估計量的值：max為了與下一節(jié)介紹的DoubleQ-leaning區(qū)分開來，我們稱該方法為單一估計量(TheSingleEstimator)。Q-learning使用此方法通過最大化該狀態(tài)下的估計動作值來估計下一個狀態(tài)的值。最大估計量maxiμi服從概率密度函數(shù)fmaxμ，而fmaxμ依賴于估計量fiFmaxiE的一個無偏估計，這可以由下式給出：E然而該式中的max運(yùn)算符和期望運(yùn)算符與maxiEXi相比是反著的。這使得最大估計量maxiμi(S)是maxiEXi3.1.4單一估計器造成高估的證明在證明之前先闡述一條證明過程中用到的重要引理。引理1：令X={X1,X2?XM}為一組隨機(jī)變量，μ={μ1,μ2?M記Max(S)為產(chǎn)生最大期望估計值的估計器Max那么，對于所有j∈E此外，當(dāng)且僅當(dāng)Pj?證明：假定j∈M,μj是任意期望值最大的估計量E=≥=根據(jù)Max的定義，有Emaxiμi>Eμ3.2DoubleQ-learning方法3.2.1DoubleQ-learning的提出前文已經(jīng)有過論述，在一些隨機(jī)環(huán)境中強(qiáng)化學(xué)習(xí)算法Q-learning性能很差。這種糟糕的表現(xiàn)是由于對動作值函數(shù)的高估造成的。而這種高估則是源于Q-learning使用最大動作值函數(shù)作為最大期望值函數(shù)的近似值而引入的正偏差。為了解決這種正的偏差，我們希望找到一種方法能避免在估計最大期望值函數(shù)值時造成的高估。于是，Hasselt提出了雙估計器方法來避免單一估計器產(chǎn)生的最大化偏差，其中一個換檢點(diǎn)是將樣本集D分成兩部分不相交的子集DU和DV，3.2.2算法分析使用單一估計方法導(dǎo)致的高估可能會對使用此方法的算法（比如Q-learning）產(chǎn)生很大的負(fù)面影響。為了避免這種高估，DoubleQ-learning在估計最大期望值maxiEXi時使用雙估計器可見，DoubleQ-learning使用雙估計器來進(jìn)行估計，算法中存儲兩個Q函數(shù)，QU和QV。每個Q函數(shù)在更新下一個狀態(tài)的值時，都使用了來自另一個Q函數(shù)的值。算法第7行中的動作a*是使得值函數(shù)QU最大的動作。然而，這里我們并沒有使用Q-learning的做法使用QUs',a*=maxaQU(s',a)首先將樣本集合S分成兩個子集SU和SV，且滿足S=SU∪SV，SU∩SV=?。設(shè)μU={μ1U,μ2U?μMa是μU(S)中最大的估計集合。由于μV是一組獨(dú)立的無偏估計量，對于所有j，有EμjV=E{Xμ若存在多個能使μU取極值的變量，假設(shè)從這些變量中隨機(jī)取一個。那么我們可以使用μa*V作為maxmax隨著樣本容量的增加，估計量的方差會減小。極限條件下，對于所有i，滿足：μ且使式（3.9）收斂到正確的結(jié)果。如果概率密度函數(shù)是連續(xù)的，對于所有j，概率P(j=a*)等于所有i≠j給出較低估計的概率。因此μiP其中fiU和FiU分別是μiUj而若是概率密度函數(shù)是離散的，應(yīng)考慮兩個或更多估計量相等的概率，相應(yīng)的積分應(yīng)該用他們的總和代替，這部分工作就比較容易。比較式（3.9）和（3.11），不同點(diǎn)在于雙估計量使用EμjV來代替x。相較于單估計量方法的高估，使用雙估計量的方法實(shí)際上產(chǎn)生了負(fù)偏差，造成了對期望值的低估。由于概率P(j=a*引理1：令X={X1,X2?XM}十一組隨機(jī)變量，令μA={μ1A,μ2A?μMA}和μB={證明：若假設(shè)a*∈M，則Eμa*B=E{XE≤當(dāng)且僅當(dāng)Pa*?M>0是，3.3WeightedQ-learning對于一組隨機(jī)變量最大期望值的估計問題，前文已經(jīng)給出了兩種方法——使用單一估計器進(jìn)行估計的Q-learning和使用雙估計器進(jìn)行估計的DoubleQ-learning方法。我們已經(jīng)證明，這兩種估計量都不是無偏估計量，單一估計器會產(chǎn)生正偏差，而雙估計器會產(chǎn)生負(fù)偏差。下面，我們基于樣本均值的加權(quán)平均值提出了一個新的MKV的估計量，其中權(quán)重使用高斯近似值對樣本均值的分布來進(jìn)行計算。下面，我們將通過嚴(yán)格的數(shù)學(xué)證明來推導(dǎo)偏差的上界和估計量的方差，并通過在不同順序?qū)W習(xí)問題上測試性能，比較所提出的估計量和其他強(qiáng)化學(xué)習(xí)方法。3.3.1簡介前文講過，為了解決Q-learning使用ME方法高估了最大期望值的問題，Hasselt提出了雙估計器方法(DE)，它包含一個交叉驗(yàn)證方法，其中總體樣本集S被分為SA和SB。DE方法估計的結(jié)果來自于兩次估計的平均值。對于第一次估計，樣本集SA用于確定哪個是具有最大均值的變量，而樣本集SB被用于估計該變量的值。不幸的是，DE方法使用的估計量仍不是無偏估計量，它的估計結(jié)果存在一個負(fù)偏差，這在許多著名的實(shí)驗(yàn)中都已經(jīng)得到了驗(yàn)證ADDINEN.CITE<EndNote><Cite><Author>Littman</Author><Year>2015</Year><RecNum>9</RecNum><DisplayText><styleface="superscript">[11]</style></DisplayText><record><rec-number>9</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525784617">9</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Littman,MichaelL</author></authors></contributors><titles><title>Reinforcementlearningimprovesbehaviourfromevaluativefeedback</title><secondary-title>Nature</secondary-title></titles><periodical><full-title>Nature</full-title></periodical><pages>445</pages><volume>521</volume><number>7553</number><dates><year>2015</year></dates><isbn>1476-4687</isbn><work-type>J</work-type><urls></urls></record></Cite></EndNote>[11]。并且，對于許多常見的分布(比如高斯分布，二項(xiàng)分布，和Beta分布)，根本不存在最大期望值的無偏估計量ADDINEN.CITE<EndNote><Cite><Author>Blumenthal</Author><Year>1968</Year><RecNum>17</RecNum><DisplayText><styleface="superscript">[12]</style></DisplayText><record><rec-number>17</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525932816">17</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Blumenthal,Saul</author><author>Cohen,Arthur</author></authors></contributors><titles><title>Estimationofthelargeroftwonormalmeans</title><secondary-title>JournaloftheAmericanStatisticalAssociation</secondary-title></titles><periodical><full-title>JournaloftheAmericanStatisticalAssociation</full-title></periodical><pages>861-876</pages><volume>63</volume><number>323</number><dates><year>1968</year></dates><isbn>0162-1459</isbn><work-type>M</work-type><urls></urls></record></Cite></EndNote>[12]，這使得DE方法在某些場景中無法使用。本節(jié)，將介紹另外一種估計最大期望值的估計器——加權(quán)估計其（WE）來估計最大期望值。加權(quán)估計器涉及到樣本均值的加權(quán)平均，其中權(quán)重是通過估計每個變量具有最大期望值的概率獲得的。計算這個概率，需要預(yù)先得知樣本均值的分布函數(shù)。而根據(jù)中心極限定理，我們利用樣本均值和樣本方差參數(shù)化的高斯分布就可以近似得到樣本均值的分布。這種加權(quán)機(jī)制在不增加方差的情況下，降低了ME的偏差。3.3.2算法分析我們同樣來考慮對一系列獨(dú)立隨機(jī)變量期望值的估計問題，設(shè)X={X1,X2?fi表示第i個變量的概率密度函數(shù)(PDF)Fi表示第i個變量的累計密度函數(shù)（CDFμi表示均值，σ0.5表示變量X最大期望值μ*(μ由上式可以看出，如果概率密度函數(shù)是未知的，就不能分析出μ*加權(quán)估計方法（WE）與ME和DE方法不同，后兩種方法的輸出變量的樣本平均值被估計為具有最大均值的變量的平均值，而WE方法計算所有樣本均值的加權(quán)平均來估計最大期望值μ*μ理想情況下，每個權(quán)重wiS應(yīng)該等于μi(w如果已知每個μi(S)的概率密度函數(shù)fμ下面我們來說明式(3-15)的推導(dǎo)過程。首先，樣本均值μi(S)是一個隨機(jī)變量，它的期望值是μi，方差是σi2|Si|。然而，樣本的概率密度函數(shù)fiS取決于變量XμiS~N(μi,σi2|Si|)。其次，由中心極限定理，樣本均值μis的分布函數(shù)f于是便可得到式(3-15)。隨著樣本容量趨于無窮大，每個樣本的均值μi收斂至相關(guān)的整體均值μi，并且正態(tài)分布fi的方差趨于0，因此期望值小于μ*(3.3.3誤差估計本節(jié)將從偏差和方差兩個方面分析WeightedQ-learning方法的誤差。對于已介紹過的幾種方法，就偏差方向而言，ME方法是正向偏差，而DE方法是負(fù)向偏差；就絕對偏差而言，ME方法和DE方法并沒有明顯的優(yōu)劣之分ADDINEN.CITE<EndNote><Cite><Author>Bellman</Author><Year>2013</Year><RecNum>6</RecNum><DisplayText><styleface="superscript">[2]</style></DisplayText><record><rec-number>6</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525784357">6</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Bellman,Richard</author></authors></contributors><titles><title>Dynamicprogramming</title></titles><dates><year>2013</year></dates><publisher>CourierCorporation</publisher><isbn>0486317196</isbn><work-type>J</work-type><urls></urls></record></Cite></EndNote>[2]。例如，當(dāng)所有隨機(jī)變量服從同一分布，DE方法是無偏的，但這時使用ME方法就會產(chǎn)生最大的誤差；而當(dāng)最大期望值遠(yuǎn)遠(yuǎn)大于其他變量的期望值時，ME方法的絕對偏差就遠(yuǎn)小于DE方法。ME方差的范圍決定于公式：而對于DE方法（雙變量估計），Hasselt推測其范圍決定于公式：下免得定理將說明WE方法和ME方法的偏差的關(guān)系。定理1：對任意給定的由M個隨機(jī)變量構(gòu)成的集合X，有：這并不意味著WE方法的絕對偏差必然小于ME方法的偏差，因?yàn)閃E的偏差也可能是負(fù)的。為了更好地表征WE方法的偏差，我們把它與DE的方差聯(lián)系起來看。定理2：對任意給定的由M個隨機(jī)變量構(gòu)成的集合X，有：圖3.1同一環(huán)境中兩種方法估計值的偏差圖3.1可視化了在同一環(huán)境中兩種方法估計值的偏差，其中兩組隨機(jī)變量分布情況為，X1~N(μ1,σ12)，X2~N(μ2,σ22)，其中σ12=σ22=10，且假定樣本容量S=100。圖3.1的左子圖證明了之前的理論分析：ME總會產(chǎn)生一個正偏差，而DWE和DE方法總會產(chǎn)生一個負(fù)偏差，且DE方法的絕對偏差大于DWE方法。根據(jù)情況的不同，WE方法的偏差可正可負(fù)，但它總是落在ME和DE的偏差區(qū)間內(nèi)。圖3.1的右子圖顯示了這些方法的絕對偏差，由圖可以看出這些方法并沒有明顯的優(yōu)劣之分。正如前文所說，當(dāng)變量具有相同的均值時，DE3.4WeightedDoubleQ-learning方法對于估計一組隨機(jī)變量的最大期望值，前文講了包括單一估計器，雙估計器，加權(quán)估計器在內(nèi)的三種方法以及它們對應(yīng)的三種強(qiáng)化學(xué)習(xí)算法，下面介紹第四種更為先進(jìn)的方法——WeightedDoubleQ-learning。 由算法可以看出，WeightedDoubleQ-learning方法結(jié)合了Q-learning和DoubleQ-learning方法的特點(diǎn)ADDINEN.CITE<EndNote><Cite><Author>Zhang</Author><Year>2017</Year><RecNum>8</RecNum><DisplayText><styleface="superscript">[13]</style></DisplayText><record><rec-number>8</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525784575">8</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>Zhang,Zongzhang</author><author>Pan,Zhiyuan</author><author>Kochenderfer,MykelJ</author></authors></contributors><titles><title>WeighteddoubleQ-learning</title><secondary-title>Proceedingsofthe26thInternationalJointConferenceonArtificialIntelligence</secondary-title></titles><pages>3455-3461</pages><dates><year>2017</year></dates><publisher>AAAIPress</publisher><isbn>0999241109</isbn><work-type>C</work-type><urls></urls></record></Cite></EndNote>[13]。它們的關(guān)鍵區(qū)別在于算法三使用第8行到第10行代替算法2的第8行，使用第14行到16行代替算法二中的第12行。這些改變，使DoubleQ-learning能使用不同的δ來更新QU和QV，記為：Q其中WeightedDoubleQ-learning方法的提出主要是為了避免常規(guī)Q-learning中固有的對動作值的高估以及DoubleQ-learning學(xué)習(xí)中對動作值的低估偏差。參數(shù)c用于控制單一和雙重估計其的重要性權(quán)重。將來，在Atari視頻游戲中使用價值函數(shù)逼近時，分析WeightedDoubleQ-learning的性能會很有趣ADDINEN.CITE<EndNote><Cite><Author>VanHasselt</Author><Year>2016</Year><RecNum>18</RecNum><DisplayText><styleface="superscript">[14]</style></DisplayText><record><rec-number>18</rec-number><foreign-keys><keyapp="EN"db-id="92e5etrrktd0zjewzzox5d5fsasreszpfwe0"timestamp="1525933328">18</key></foreign-keys><ref-typename="Thesis">32</ref-type><contributors><authors><author>VanHasselt,Hado</author><author>Guez,Arthur</author><author>Silver,David</author></authors></contributors><titles><title>DeepReinforcementLearningwithDoubleQ-Learning</title><secondary-title>AAAI</secondary-title></titles><pages>2094-2100</pages><volume>16</volume><dates><year>2016</year></dates><work-type>C</work-type><urls></urls></record></Cite></EndNote>[14]。第四章相關(guān)試驗(yàn)與結(jié)果在很多應(yīng)用場景中，學(xué)習(xí)者常常被要求在一個平面區(qū)域內(nèi)找到最優(yōu)決策路線，比如自動掃地機(jī)器人的尋路問題，迷宮尋寶游戲等。受此啟發(fā)，本章設(shè)計了“格子世界”的仿真實(shí)驗(yàn)，通過實(shí)證比較WE，ME和DE在連續(xù)決策問題上的表現(xiàn)情況。本章主要分為實(shí)驗(yàn)設(shè)計和結(jié)果分析兩個部分，實(shí)驗(yàn)設(shè)計主要說明代碼邏輯和框架，結(jié)果展示主要做了可視化的工作，使實(shí)證結(jié)果同理論分析互相驗(yàn)證。4.1實(shí)驗(yàn)設(shè)計所謂“格子世界”是指一個n×n的方形網(wǎng)格，它包括n2個狀態(tài)(網(wǎng)格中的每個單元格代表一個狀態(tài))，和四種動作：{東、西、南、北}。在不碰到格子邊界的前提下，在某個狀態(tài)下，每執(zhí)行一個操作就會到達(dá)一個新的狀態(tài)。實(shí)驗(yàn)的初始狀態(tài)s0被設(shè)置在格子的最左上角，中止?fàn)顟B(tài)s圖4.13*3格子世界圖4.23*3格子世界圖4.33*3格子世界圖4.1至圖4.3分別表示在4×4的格子下起始狀態(tài)，中間狀態(tài)和目標(biāo)狀態(tài)的情況。在迭代過程中，如果在某個狀態(tài)采取某個動作到達(dá)終止?fàn)顟B(tài)，則本次迭代結(jié)束，學(xué)習(xí)者以相等的概率隨機(jī)獲得-30或者+40的獎賞。如果采取某個動作到達(dá)任意非終止態(tài)，則以相等的概率隨機(jī)獲得-6或者+4的獎賞。我們設(shè)計這些獎賞數(shù)字的目的在于，使得對于達(dá)到終止?fàn)顟B(tài)的操作給予的期望獎賞為+5，而對于那些中間過程的每一步操作都給予-1的期望獎賞，這也體現(xiàn)了延期的獎賞不如即期獎賞的思想。下圖4.1至圖4.3分別表示在4×4的格子下起始狀態(tài)，中間狀態(tài)和目標(biāo)狀態(tài)的情況。圖4.5Gird類圖圖4.4判定過程對于Gird類結(jié)構(gòu)如圖4.4所示，其成員變量主要包括格子世界的行列數(shù)，狀態(tài)數(shù)，每個狀態(tài)的動作數(shù)量，以及當(dāng)前所處的狀態(tài)。Gird類包括兩個方法，reset()方法功能是將當(dāng)前狀態(tài)置零，action()方法功能是在當(dāng)前狀態(tài)的基礎(chǔ)上采取一個動作，并更新狀態(tài)，若新狀態(tài)為最終狀態(tài)則隨機(jī)獲取一個-30或+40的獎賞，這部分代碼如圖4.5所示。在使用代碼實(shí)現(xiàn)