兼具動態(tài)規(guī)劃DP和蒙特卡洛MC優(yōu)點的TD Learning算法

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

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

TD Learning算法概念：

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

TD Learning算法本質(zhì)：

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

時序差分不好理解。改為當(dāng)時差分學(xué)習(xí)比較形象一些，表示通過當(dāng)前的差分?jǐn)?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)價值。可以認(rèn)為蒙特卡洛MC方法是最大步數(shù)的TD Learning時序差分學(xué)習(xí)。

TD Learning算法描述：

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

在蒙特卡洛方法中，計算策略的價值，需要完成一個情節(jié)，通過情節(jié)的目標(biāo)價值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時間差分方法的目標(biāo)為Rt＋1＋γ V（St＋1），若V（St＋1） 采用真實值，則TD Learning時間差分方法估計也是無偏估計，然而在試驗中V（St＋1） 用的也是估計值，因此TD Learning時間差分方法屬于有偏估計。然而，跟蒙特卡羅MC方法相比，TD Learning時間差分方法只用到了一步隨機狀態(tài)和動作，因此TD Learning時間差分方法目標(biāo)的隨機性比蒙特卡羅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， 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)域。