關(guān)于TD-Learning算法的分析

關(guān)于TDLearning算法的分析導(dǎo)讀：人工智能之機(jī)器學(xué)習(xí)主要有三大類(lèi)：1）分類(lèi)；2）回歸；3）聚類(lèi)。今天我們重點(diǎn)探討一下TDLearning算法。TDLearning時(shí)序差分學(xué)習(xí)結(jié)合了動(dòng)態(tài)規(guī)劃DP和蒙特卡洛MC方法，且兼具兩種算法的優(yōu)點(diǎn)，是強(qiáng)化學(xué)習(xí)的核心思想。雖然蒙特卡羅MC方法僅在最終結(jié)果已知時(shí)才調(diào)整其估計(jì)值，但TDLearning時(shí)序差分學(xué)習(xí)調(diào)整預(yù)測(cè)以匹配后，更準(zhǔn)確地預(yù)測(cè)最終結(jié)果之前的未來(lái)預(yù)測(cè)。TDLearning算法概念：TDLearning（Temporal－DifferenceLearning）時(shí)序差分學(xué)習(xí)指的是一類(lèi)無(wú)模型的強(qiáng)化學(xué)習(xí)方法，它是從當(dāng)前價(jià)值函數(shù)估計(jì)的自舉過(guò)程中學(xué)習(xí)的。這些方法從環(huán)境中取樣，如蒙特卡洛方法，并基于當(dāng)前估計(jì)執(zhí)行更新，如動(dòng)態(tài)規(guī)劃方法。TDLearning算法本質(zhì)：TDLearning（Temporal－DifferenceLearning）時(shí)序差分學(xué)習(xí)結(jié)合了動(dòng)態(tài)規(guī)劃和蒙特卡洛方法，是強(qiáng)化學(xué)習(xí)的核心思想。時(shí)序差分不好理解。改為當(dāng)時(shí)差分學(xué)習(xí)比較形象一些，表示通過(guò)當(dāng)前的差分?jǐn)?shù)據(jù)來(lái)學(xué)習(xí)。蒙特卡洛MC方法是模擬（或者經(jīng)歷）一段序列或情節(jié)，在序列或情節(jié)結(jié)束后，根據(jù)序列或情節(jié)上各個(gè)狀態(tài)的價(jià)值，來(lái)估計(jì)狀態(tài)價(jià)值。TDLearning時(shí)序差分學(xué)習(xí)是模擬（或者經(jīng)歷）一段序列或情節(jié)，每行動(dòng)一步（或者幾步），根據(jù)新?tīng)顟B(tài)的價(jià)值，然后估計(jì)執(zhí)行前的狀態(tài)價(jià)值?？梢哉J(rèn)為蒙特卡洛MC方法是最大步數(shù)的TDLearning時(shí)序差分學(xué)習(xí)。TDLearning算法描述：如果可以計(jì)算出策略?xún)r(jià)值（狀態(tài)價(jià)值v（s），或者行動(dòng)價(jià)值q（s，a）），就可以?xún)?yōu)化策略。在蒙特卡洛方法中，計(jì)算策略的價(jià)值，需要完成一個(gè)情節(jié)，通過(guò)情節(jié)的目標(biāo)價(jià)值Gt來(lái)計(jì)算狀態(tài)的價(jià)值。其公式：MC公式：V（St）V（St）＋tt＝［Gt？V（St）］這里：tMC誤差MC學(xué)習(xí)步長(zhǎng)TDLearning公式：V（St）V（St）＋tt＝［Rt＋1＋V（St＋1）？V（St）］這里：tTDLearning誤差TDLearning步長(zhǎng)TDLearning報(bào)酬貼現(xiàn)率TDLearning時(shí)間差分方法的目標(biāo)為Rt＋1＋V（St＋1），若V（St＋1）采用真實(shí)值，則TDLearning時(shí)間差分方法估計(jì)也是無(wú)偏估計(jì)，然而在試驗(yàn)中V（St＋1）用的也是估計(jì)值，因此TDLearning時(shí)間差分方法屬于有偏估計(jì)。然而，跟蒙特卡羅MC方法相比，TDLearning時(shí)間差分方法只用到了一步隨機(jī)狀態(tài)和動(dòng)作，因此TDLearning時(shí)間差分方法目標(biāo)的隨機(jī)性比蒙特卡羅MC方法中的Gt要小，因此其方差也比蒙特卡羅MC方法的方差小。TDLearning分類(lèi)：1）策略狀態(tài)價(jià)值v的時(shí)序差分學(xué)習(xí)方法（單步多步）2）策略行動(dòng)價(jià)值q的on－policy時(shí)序差分學(xué)習(xí)方法：Sarsa（單步多步）3）策略行動(dòng)價(jià)值q的off－policy時(shí)序差分學(xué)習(xí)方法：Q－learning（單步），DoubleQ－learning（單步）4）策略行動(dòng)價(jià)值q的off－policy時(shí)序差分學(xué)習(xí)方法（帶importancesampling）：Sarsa（多步）5）策略行動(dòng)價(jià)值q的off－policy時(shí)序差分學(xué)習(xí)方法（不帶importancesampling）：TreeBackupAlgorithm（多步）6）策略行動(dòng)價(jià)值q的off－policy時(shí)序差分學(xué)習(xí)方法：Q（）（多步）TDLearning算法流程：1）單步TDLearning時(shí)序差分學(xué)習(xí)方法：IniTIalizeV（s）arbitrarily？sS＋Repeat（foreachepisode）：？IniTIalizeS？Repeat（foreachstepofepisode）：？？AacTIongivenbyforS？？TakeacTIonA，observeR，S？？V（S）V（S）＋［R＋V（S）？V（S）］？？SS？UntilSisterminal2）多步TDLearning時(shí)序差分學(xué)習(xí)方法：Input：thepolicytobeevaluatedInitializeV（s）arbitrarily？sSParameters：stepsize（0，1］，apositiveintegernAllstoreandaccessoperations（forStandRt）cantaketheirindexmodnRepeat（foreachepisode）：？InitializeandstoreS0terminal？T？Fort＝0，1，2，？：？？Ift＜Tt＜T，then：？？？Takeanactionaccordingto（˙｜St）？？？ObserveandstorethenextrewardasRt＋1andthenextstateasSt＋1？？？IfSt＋1isterminal，thenTt＋1？？t？n＋1（isthetimewhosestate＇sestimateisbeingupdated）？？If00：？？？Gmin（＋n，T）i＝＋1i？？1Ri？？？if＋nT＋nTthen：GG＋nV（S＋n）（G（n））？？？V（S）V（S）＋［G？V（S）］？Until＝T？1注意：V（S0）是由V（S0），V（S1），，V（Sn）計(jì)算所得；V（S1）是由V（S1），V（S1），，V（Sn＋1）計(jì)算所得。TDLearning理論基礎(chǔ)TDLearning理論基礎(chǔ)如下：1）蒙特卡羅方法2）動(dòng)態(tài)規(guī)劃3）信號(hào)系統(tǒng)TDLearning算法優(yōu)點(diǎn)：1）不需要環(huán)境的模型；2）可以采用在線(xiàn)的、完全增量式的實(shí)現(xiàn)方式；3）不需等到最終的真實(shí)結(jié)果；4）不局限于episodetask；5）可以用于連續(xù)任務(wù)；6）可以保證收斂到v，收斂速度較快。TDLearning算法缺點(diǎn)：1）對(duì)初始值比較敏感；2）并非總是用函數(shù)逼近。TDLearning算法應(yīng)用：從應(yīng)用角度看，TDLearning應(yīng)用領(lǐng)域與應(yīng)用前景都是非常廣闊的，目前主要應(yīng)用于動(dòng)態(tài)系統(tǒng)、機(jī)器人控制及其他需要進(jìn)行系統(tǒng)控制的領(lǐng)域。結(jié)語(yǔ)：TDLearning是結(jié)合了動(dòng)態(tài)規(guī)劃DP和蒙特卡洛MC方法，并兼具兩種算法的優(yōu)點(diǎn)，是強(qiáng)化學(xué)習(xí)的中心。TDLearning不需要環(huán)境的動(dòng)態(tài)模型，直接從經(jīng)驗(yàn)經(jīng)歷中學(xué)習(xí)；也不需要等到最終的結(jié)果才更新模型，它可以基于其他估計(jì)值來(lái)更新估計(jì)值。輸入數(shù)據(jù)可