人工智能之TD Learning算法

　　人工智能機器學(xué)習(xí)有關(guān)算法內(nèi)容，請參見公眾號“科技優(yōu)化生活”之前相關(guān)文章。人工智能之機器學(xué)習(xí)主要有三大類：1)分類;2)回歸;3)聚類。今天我們重點探討一下TD Learning算法。 ^_^

　　TD Learning時序差分學(xué)習(xí)結(jié)合了動態(tài)規(guī)劃DP和蒙特卡洛MC(請參見人工智能(31))方法，且兼具兩種算法的優(yōu)點，是強化學(xué)習(xí)的核心思想。

　　雖然蒙特卡羅MC方法僅在最終結(jié)果已知時才調(diào)整其估計值，但TD Learning時序差分學(xué)習(xí)調(diào)整預(yù)測以匹配后，更準確地預(yù)測最終結(jié)果之前的未來預(yù)測。

　　TD Learning算法概念：

　　TD Learning(Temporal-Difference Learning) 時序差分學(xué)習(xí)指的是一類無模型的強化學(xué)習(xí)方法，它是從當前價值函數(shù)估計的自舉過程中學(xué)習(xí)的。這些方法從環(huán)境中取樣，如蒙特卡洛方法，并基于當前估計執(zhí)行更新，如動態(tài)規(guī)劃方法。

　　TD Learning算法本質(zhì)：

　　TD Learning(Temporal-DifferenceLearning)時序差分學(xué)習(xí)結(jié)合了動態(tài)規(guī)劃和蒙特卡洛方法，是強化學(xué)習(xí)的核心思想。

　　時序差分不好理解。改為當時差分學(xué)習(xí)比較形象一些，表示通過當前的差分數(shù)據(jù)來學(xué)習(xí)。

　　蒙特卡洛MC方法是模擬(或者經(jīng)歷)一段序列或情節(jié)，在序列或情節(jié)結(jié)束后，根據(jù)序列或情節(jié)上各個狀態(tài)的價值，來估計狀態(tài)價值。TD Learning時序差分學(xué)習(xí)是模擬(或者經(jīng)歷)一段序列或情節(jié)，每行動一步(或者幾步)，根據(jù)新狀態(tài)的價值，然后估計執(zhí)行前的狀態(tài)價值。可以認為蒙特卡洛MC方法是最大步數(shù)的TD Learning時序差分學(xué)習(xí)。

　　TD Learning算法描述：

　　如果可以計算出策略價值(π狀態(tài)價值vπ(s)，或者行動價值qπ(s，a))，就可以優(yōu)化策略。

　　在蒙特卡洛方法中，計算策略的價值，需要完成一個情節(jié)，通過情節(jié)的目標價值Gt來計算狀態(tài)的價值。其公式：

　　MC公式：

　　V(St)←V(St)+αδt

　　δt=[Gt?V(St)]

　　這里：

　　δt – MC誤差

　　α – MC學(xué)習(xí)步長

　　TD Learning公式：

　　V(St)←V(St)+αδt

　　δt=[Rt+1+γV(St+1)?V(St)]

　　這里：

　　δt – TD Learning誤差

　　α – TD Learning步長

　　γ – TD Learning報酬貼現(xiàn)率

　　TD Learning時間差分方法的目標為Rt+1+γ V(St+1)，若V(St+1) 采用真實值，則TD Learning時間差分方法估計也是無偏估計，然而在試驗中V(St+1) 用的也是估計值，因此TD Learning時間差分方法屬于有偏估計。然而，跟蒙特卡羅MC方法相比，TD Learning時間差分方法只用到了一步隨機狀態(tài)和動作，因此TD Learning時間差分方法目標的隨機性比蒙特卡羅MC方法中的Gt 要小，因此其方差也比蒙特卡羅MC方法的方差小。

　　TD Learning分類：

　　1)策略狀態(tài)價值vπ的時序差分學(xué)習(xí)方法(單步多步)

　　2)策略行動價值qπ的on-policy時序差分學(xué)習(xí)方法： Sarsa(單步多步)

　　3)策略行動價值qπ的off-policy時序差分學(xué)習(xí)方法： Q-learning(單步)，Double Q-learning(單步)

　　4)策略行動價值qπ的off-policy時序差分學(xué)習(xí)方法(帶importance sampling)： Sarsa(多步)

　　5)策略行動價值qπ的off-policy時序差分學(xué)習(xí)方法(不帶importance sampling)： Tree Backup Algorithm(多步)

　　6)策略行動價值qπ的off-policy時序差分學(xué)習(xí)方法： Q(σ)(多步)

　　TD Learning算法流程：

　　1)單步TD Learning時序差分學(xué)習(xí)方法：

　　InitializeV(s) arbitrarily ?s∈S+

　　Repeat(for each episode)：

　　?Initialize S

　　?Repeat (for each step of episode)：

　　?? A←actiongiven by π for S

　　??Take action A， observe R，S′

　　??V(S)←V(S)+α[R+γV(S′)?V(S)]

　　?? S←S′

　　?Until S is terminal

　　2)多步TD Learning時序差分學(xué)習(xí)方法：

　　Input：the policy π to be evaluated

　　InitializeV(s) arbitrarily ?s∈S

　　Parameters：step size α∈(0，1]， a positive integer n

　　Allstore and access operations (for St and Rt) can take their index mod n

　　Repeat(for each episode)：

　　?Initialize and store S0≠terminal

　　? T←∞

　　? Fort=0，1，2，?：

　　?? Ift<tt<t， p="" then：

　　???Take an action according to π( ˙|St)

　　???Observe and store the next reward as Rt+1 and the next state as St+1

　　???If St+1 is terminal， then T←t+1

　　?? τ←t?n+1(τ is the time whose state's estimate is being updated)

　　?? Ifτ≥0τ≥0：

　　??? G←∑min(τ+n，T)i=τ+1γi?τ?1Ri

　　???if τ+n≤Tτ+n≤T then： G←G+γnV(Sτ+n)(G(n)τ)

　　???V(Sτ)←V(Sτ)+α[G?V(Sτ)]

　　?Until τ=T?1

　　注意：V(S0)是由V(S0)，V(S1)，…，V(Sn)計算所得;V(S1)是由V(S1)，V(S1)，…，V(Sn+1)計算所得。

　　TD Learning理論基礎(chǔ)：

　　TD Learning理論基礎(chǔ)如下：

　　1)蒙特卡羅方法

　　2)動態(tài)規(guī)劃

　　3)信號系統(tǒng)

　　TD Learning算法優(yōu)點：

　　1)不需要環(huán)境的模型;

　　2)可以采用在線的、完全增量式的實現(xiàn)方式;

　　3)不需等到最終的真實結(jié)果;

　　4)不局限于episode task;

　　5)可以用于連續(xù)任務(wù);

　　6)可以保證收斂到 vπ，收斂速度較快。

　　TD Learning算法缺點：

　　1) 對初始值比較敏感;

　　2) 并非總是用函數(shù)逼近。

　　TD Learning算法應(yīng)用：

　　從應(yīng)用角度看，TD Learning應(yīng)用領(lǐng)域與應(yīng)用前景都是非常廣闊的，目前主要應(yīng)用于動態(tài)系統(tǒng)、機器人控制及其他需要進行系統(tǒng)控制的領(lǐng)域。

　　結(jié)語：

　　TD Learning是結(jié)合了動態(tài)規(guī)劃DP和蒙特卡洛MC方法，并兼具兩種算法的優(yōu)點，是強化學(xué)習(xí)的中心。TD Learning不需要環(huán)境的動態(tài)模型，直接從經(jīng)驗經(jīng)歷中學(xué)習(xí);也不需要等到最終的結(jié)果才更新模型，它可以基于其他估計值來更新估計值。輸入數(shù)據(jù)可以刺激模型并且使模型做出反應(yīng)。反饋不僅從監(jiān)督學(xué)習(xí)的學(xué)習(xí)過程中得到，還從環(huán)境中的獎勵或懲罰中得到。TD Learning算法已經(jīng)被廣泛應(yīng)用于動態(tài)系統(tǒng)、機器人控制及其他需要進行系統(tǒng)控制的領(lǐng)域。