概述

時(shí)序差分算法是一種無模型的強(qiáng)化學(xué)習(xí)算法民褂。它繼承了動(dòng)態(tài)規(guī)劃(Dynamic Programming)和蒙特卡羅方法(Monte Carlo Methods)的優(yōu)點(diǎn)，從而對(duì)狀態(tài)值(state value)和策略(optimal policy)進(jìn)行預(yù)測蚓哩。從本質(zhì)上來說规婆，時(shí)序差分算法和動(dòng)態(tài)規(guī)劃一樣泽裳，是一種bootstrapping的算法。同時(shí)增拥，也和蒙特卡羅方法一樣啄巧，是一種無模型的強(qiáng)化學(xué)習(xí)算法，其原理也是基于了試驗(yàn)掌栅。雖然秩仆，時(shí)序差分算法擁有動(dòng)態(tài)規(guī)劃和蒙特卡羅方法的一部分特點(diǎn)，但它們也有不同之處渣玲。以下是它們各自的backup圖：

動(dòng)態(tài)規(guī)劃backup圖

蒙特卡羅方法backup圖

時(shí)序差分算法backup圖

根據(jù)它們的backup圖可以知道逗概，動(dòng)態(tài)規(guī)劃的backup操作是基于當(dāng)前狀態(tài)和下一個(gè)狀態(tài)的reward，蒙特卡羅方法的backup是基于一個(gè)完整的episode的reward忘衍，而時(shí)序差分算法的backup是基于當(dāng)前狀態(tài)和下一個(gè)狀態(tài)的reward逾苫。其中，最基礎(chǔ)的時(shí)序差分算法被稱為TD(0)枚钓。它也有許多拓展铅搓，如n-step TD算法和TD(lambda)算法。

Stationary Environment和Nonstationary Environment的區(qū)別

Stationary Environment即為固定的環(huán)境搀捷，也就是說采取相同的動(dòng)作時(shí)星掰，狀態(tài)和環(huán)境是固定不變的多望。如：垃圾回收機(jī)器人每次充完電之后電都是滿的。而Nonstationary Environment與此相反氢烘，在采取相同的動(dòng)作時(shí)怀偷，狀態(tài)和環(huán)境是不確定的。如：轉(zhuǎn)一下抽獎(jiǎng)轉(zhuǎn)盤播玖，它每次停止的位置都是不一樣的椎工。

TD(0)時(shí)序差分算法

時(shí)序差分算法和蒙特卡羅方法一樣，仍然有兩部分計(jì)算蜀踏。第一部分是時(shí)序差分的預(yù)測(即計(jì)算state value)维蒙，第二部分是時(shí)序差分的控制(TD control)，其目的是為了得到最優(yōu)的策略(optimal policy)果覆。

時(shí)序差分預(yù)測(TD Prediction)

預(yù)測是為了計(jì)算狀態(tài)值(state value)颅痊。在計(jì)算的時(shí)間上，時(shí)序差分比蒙特卡羅方法更快一些局待。其計(jì)算公式分別如下所示：

TD prediction

MC prediction

根據(jù)公式斑响，TD只需要等到跳轉(zhuǎn)到下一個(gè)狀態(tài)時(shí)，便可得知當(dāng)前狀態(tài)的state value燎猛。但是恋捆，蒙特卡羅方法則需要等到整個(gè)試驗(yàn)結(jié)束之后才可以得到當(dāng)前狀態(tài)的state value值照皆。因?yàn)橹乇粒瑫r(shí)序差分算法計(jì)算value值時(shí)，是根據(jù)當(dāng)前狀態(tài)和接下來的狀態(tài)來計(jì)算膜毁，因此是有偏差的昭卓，但方差很小。相反瘟滨，蒙特卡羅方法是無偏差的候醒，但是方差卻很大。

時(shí)序差分和蒙特卡羅方法的學(xué)習(xí)都是通過試驗(yàn)采樣來計(jì)算value值的杂瘸，采樣致使我們無法得到完整的在當(dāng)前狀態(tài)跳到下一個(gè)狀態(tài)的分布倒淫。可以清晰的從上面的backup 圖了解到败玉，只有DP是基于所有的下一個(gè)狀態(tài)的分布敌土。

TD算法和MC算法更新的那一部分被我們成為error(即真實(shí)value和評(píng)估的value的差值)，如下所示：

TD error

MC error

因?yàn)槭歉逻^程运翼，所以其目的就是為了使最終預(yù)測的value值與真實(shí)的value值的誤差盡量小返干，也就是使其error最小化。在預(yù)測的計(jì)算公式中血淌，alpa代表的是步長矩欠，類似于梯度下降里面的步長。為什么不讓error直接變到最小(為零)呢？其原因和我們平常所學(xué)的Gradient Descent概念是一樣的癌淮。因?yàn)樘煞兀覀兪褂玫氖浅闃拥姆椒ǎ]有得到真正的數(shù)據(jù)分布乳蓄，而如果步長很大的話反倒會(huì)使計(jì)算value的收斂速度下降护奈。其TD Prediction的偽代碼如下：

TD Prediction

Batch TD(0)

在對(duì)state value進(jìn)行預(yù)測時(shí)挪凑，我們不僅可以一個(gè)試驗(yàn)一個(gè)試驗(yàn)的更新，同時(shí)，也可以一批一批的進(jìn)行更新拾并。這就是我們所說的batch TD(0)。

例1: 假如我們對(duì)一個(gè)隨機(jī)游走(Random Walk)的游戲進(jìn)行state value的預(yù)測奢讨。我們通過一批(8個(gè))試驗(yàn)得到了狀態(tài)和相應(yīng)的reward蔚鸥，如下所示：

????????????????????????????????A:0, B:0 ? ? ? ?B:1 ? ? ? ? B:1 ? ? ? ?B:1 ? ? ? ?B:1 ? ? ? ?B:1 ? ? ? ?B:0 ? ? ? ?B:1????

我們很容易計(jì)算出B的value值應(yīng)該為四分之三。因?yàn)樵谶@8個(gè)試驗(yàn)中捧弃，B為1的總共有六個(gè)赠叼。而A的value值是多少呢？可能有人會(huì)說是0违霞，因?yàn)橹挥幸淮卧囼?yàn)嘴办，而且A的reward還為零。但其實(shí)答案也是四分之三买鸽。要知道TD計(jì)算A的value值會(huì)根據(jù)下一個(gè)狀態(tài)的reward計(jì)算的涧郊，因?yàn)橹挥幸粋€(gè)A試驗(yàn)，且狀態(tài)被轉(zhuǎn)換到了B狀態(tài)眼五。因此妆艘，TD會(huì)推斷從A到B的概率應(yīng)該是100%，所以通過計(jì)算看幼，A的value值即為0 + 3 / 4 = 3 / 4批旺。

Sarsa: On-policy TD Control

前面在講蒙特卡羅方法時(shí)，我們已經(jīng)說明了on-policy和off-policy的區(qū)別了诵姜，這里就不再重復(fù)汽煮。我們知道一個(gè)episode是由多個(gè)state-action對(duì)所組成的，如圖所示：

one episode

Sarsa則是State->action->reward->State->action(St, At, Rt+1, St+1, At+1)的簡稱棚唆。所以暇赤，其action value的計(jì)算公式為：

Sarsa

其偽代碼如下所示：

Sarsa code

Q-learning: Off-policy Control

Q-learning是一種off-policy的算法，也就是里面有兩個(gè)policy瑟俭。其中翎卓，behavior policy是用來去盡可能的探索。其偽代碼如下所示：

Q-learning code

Expected Sarsa

Expected Sarsa和Q-learning很像摆寄， 其區(qū)別在于Q-learning中behavior policy計(jì)算的是最大值失暴，而Expected Sarsa計(jì)算的則是期望坯门，如圖所示：

backup diagrams

其公式如下所示：

Expected Sarsa公式

Reference

1. Reinforcement Learning An Introduction

2.強(qiáng)化學(xué)習(xí)入門 第四講 時(shí)間差分法（TD方法）?https://zhuanlan.zhihu.com/p/25913410