一检激、Monte-Carlo Learning
(一)Monte-Carlo Reinforcement Learning
- MC方法可直接從經(jīng)驗(yàn)中學(xué)習(xí)
- MC是model-free:不了解MDP轉(zhuǎn)換/獎勵
- MC從完整的episode中學(xué)到:no bootstrapping
- MC使用最簡單的想法:value = mean return
- 警告:只能將MC應(yīng)用于episodic MDPs
- All episodes must terminate
(二)Monte-Carlo Policy Evaluation
-
目標(biāo):從policy
規(guī)定的經(jīng)驗(yàn)中學(xué)習(xí)
-
回想一下蓖扑,回報(bào)是總折扣獎勵:
-
回想一下,value function是預(yù)期的回報(bào):
蒙特卡洛策略評估使用經(jīng)驗(yàn)均值回報(bào)而非預(yù)期回報(bào)
(三)First-Visit Monte-Carlo Policy Evaluation
- 評估狀態(tài)s
- 只統(tǒng)計(jì)狀態(tài)s第一次出現(xiàn)在episode中時(shí)的長期回報(bào)
- 增量計(jì)數(shù)器
- 總收益增加
- 價(jià)值由平均回報(bào)估算
- 根據(jù)大數(shù)定律,
as
(四)Every-Visit Monte-Carlo Policy Evaluation
- 評估狀態(tài)s
- 統(tǒng)計(jì)狀態(tài)s每一次出現(xiàn)在episode中時(shí)的長期回報(bào)
- 增量計(jì)數(shù)器
- 總收益增加
- 價(jià)值由平均回報(bào)估算
- 根據(jù)大數(shù)定律商蕴,
as
(五)Incremental Monte-Carlo
1励烦、Incremental Mean
序列的平均值
可以遞增計(jì)算,
是誤差吼过,平均值將會朝著誤差的方向移動更新锐秦。
2、增量蒙特卡洛更新
- 在episode
后逐步更新
- 對于每個具有回報(bào)
的狀態(tài)
- 在非平穩(wěn)問題中盗忱,跟蹤連續(xù)平均值(即忘掉舊episodes.)可能很有用酱床。
我們的環(huán)境一直在變化,很久以前的episodes對于我現(xiàn)在沒有什么用趟佃,可能還會拖累我們的更新扇谣。所以我們將1/N用代替,每次讓值朝著比較新的return的方向更新闲昭,而不需要使用真正的平均值罐寨。
不會直接更新到平均值,平均值可能還沒達(dá)到正確的程度序矩。取一個恒定步長進(jìn)行更新鸯绿。
類似于常見的梯度下降法的更新公式
二、Temporal-Difference Learning
TD方法可直接從經(jīng)驗(yàn)中學(xué)習(xí)
TD是model-free:的:不了解MDP轉(zhuǎn)換/獎勵
-
TD通過自舉(bootsstrapping)從不完整的episodes中學(xué)習(xí)
- 利用估計(jì)來代表episode的剩余部分贮泞。
-
TD將猜測更新為猜測
- 更新最開始的猜想楞慈,得到后來的猜想
(一)MC and TD
- 目標(biāo):從策略
下的經(jīng)驗(yàn)中在線學(xué)習(xí)
- Incremental every-visit Monte-Carlo
- 朝著實(shí)際回報(bào)
的方向更新價(jià)值
- 朝著實(shí)際回報(bào)
- 最簡單的時(shí)序查分算法:TD(0)
- 朝著估計(jì)回報(bào)
的方向更新價(jià)值
-
被稱為TD target
-
被稱為TD error
- 朝著估計(jì)回報(bào)
(二)Driving Home Example
在這個例子中,reward是每一段行程消耗的時(shí)間(Elapsed Time)啃擦。過程不加折扣(),因此每個狀態(tài)的回報(bào)就是從這個狀態(tài)開始直到回家實(shí)際經(jīng)過的總時(shí)間囊蓝。每個狀態(tài)的價(jià)值是剩余時(shí)間的期望值。第二列數(shù)字給出了遇到的每個狀態(tài)的價(jià)值的當(dāng)前估計(jì)值令蛉。
一種描述蒙特卡洛方法的步驟的簡單方法是在時(shí)間軸上畫出行車總耗時(shí)的預(yù)測值(最后一行數(shù)據(jù))聚霜。箭頭表示的是MC方法推薦的對預(yù)測值的改變。這個值正是每個狀態(tài)的價(jià)值的估計(jì)值(預(yù)估的剩余時(shí)間)與實(shí)際值回報(bào)(真是的剩余時(shí)間)之差珠叔。例如蝎宇,當(dāng)你下高速時(shí),你估計(jì)還有15分鐘就能到家祷安。但實(shí)際上你需要23分鐘姥芥。此時(shí)就可以用公式
確定離開高速后的剩余時(shí)間估計(jì)的增量。這時(shí)的誤差是是8分鐘汇鞭。假設(shè)步長參數(shù)是1/2凉唐,根據(jù)這一經(jīng)驗(yàn)庸追,離開高速后的預(yù)估剩余時(shí)間會增加4分鐘。在當(dāng)前這個例子中台囱,這個改變可能過大了淡溯,因?yàn)槎略诳ㄜ嚭竺嬷R偶然運(yùn)氣不好。無論如何簿训,這種更新只能離線進(jìn)行咱娶,即只有到家以后才能進(jìn)行更新,因?yàn)橹挥械郊夷悴胖缹?shí)際的回報(bào)是多少强品。
是否真的需要知曉最終結(jié)果才能開始學(xué)習(xí)呢膘侮,假設(shè)有一天你回家也是預(yù)計(jì)30分鐘到家,到途中碰到了嚴(yán)重的交通擁堵择懂,離開辦公司25分鐘仍然在高速上寸步難行喻喳,這時(shí)你估計(jì)還有25分鐘才能到家,總共50分鐘困曙。是否只有到家后才能增加對初始狀態(tài)的估計(jì)值呢表伦?如果使用蒙特卡洛方法馍刮,答案是肯定的龄毡,因?yàn)槲覀冞€不知道真正的回報(bào)。
但是根據(jù)TD的方法俩檬,我們可以立即學(xué)習(xí)要糊,將初始估計(jì)得30分鐘增加到50分鐘纲熏。事實(shí)上,每一個估計(jì)都會跟著其后繼的估計(jì)一起更新锄俄【志ⅲ回到例子,右圖顯示了根據(jù)TD規(guī)則推薦的總時(shí)間的預(yù)測值的變化奶赠。每個誤差都與預(yù)測值在時(shí)序上的變化(即預(yù)測中的時(shí)序差分)成正比鱼填。
(三)Advantages and Disadvantages of MC vs. TD
-
TD可以在知道最終結(jié)果之前學(xué)習(xí)
- TD可以在每一步之后在線學(xué)習(xí)
- MC必須等到episode結(jié)束才能知道回報(bào)
-
TD可以在沒有最終結(jié)果的情況下學(xué)習(xí)
- TD可以從不完整的序列中學(xué)習(xí)
- MC只能從完整序列中學(xué)習(xí)
- TD在持續(xù)(非終止)環(huán)境中工作
- MC僅適用于episode(終止)環(huán)境
(四)Bias/Variance Trade-Off
- 回報(bào)
是
的無偏估計(jì)。
- 真實(shí)TD target
是
的無偏估計(jì)毅戈。
這里的是真實(shí)的
苹丸。貝爾曼方程得到的,理想狀態(tài)下的苇经。
- TD target
是
的有偏估計(jì)赘理。
這里的是我們目前最符合實(shí)際的猜測。
- TD target的方差比回報(bào)低得多
- 回報(bào)取決于許多隨機(jī)actions扇单,transitions, rewards
- TD target取決于一個action商模,transitions, rewards
(五)Advantages and Disadvantages of MC vs. TD (2)
首先理解一下方差。
蒙特卡洛通過與環(huán)境交互得到序列的回報(bào)信息,然后用這些信息求平均阻桅,就可以得到估計(jì)得價(jià)值函數(shù)凉倚。但是每次采樣得到的回報(bào)差別可能很大,因?yàn)樵谟?jì)算回報(bào)時(shí)每一步都會收到噪聲干擾嫂沉,導(dǎo)致方差很大。
偏差就是你對V有一些估計(jì)扮碧,這可能是錯誤的趟章,并不是真實(shí)值。這不是干擾慎王。
-
MC具有高方差蚓土,零偏差(
在每一步轉(zhuǎn)換都會有噪聲干擾,得到受到干擾的reward赖淤,所以方差比較大)
- 良好的收斂性
- (具有函數(shù)近似)
- 對初始值不太敏感
因?yàn)槲覀儾粡某跏贾颠M(jìn)行自舉蜀漆。開始的地方很重要,但是我會花更長的時(shí)間來調(diào)整你那些錯得很厲害的值咱旱,把他們改成正確的值确丢。但他不做自身循環(huán)。他不使用自己吐限。 - 很容易理解和使用
-
TD方差低鲜侥,有些偏差(因?yàn)橹粫艿揭徊礁蓴_,所有方差較兄畹洹)
- 通常比MC更高效
- TD(0)收斂至
- (但并非總是用近似函數(shù))
TD里的偏差可能是的算法不起作用 - 對初始值更敏感
(六)Random Walk Example
隨著episode的增多描函,開始趨近于真實(shí)的value(那條直線)。
Random Walk: MC vs. TD
從上圖可以看出TD的效果比MC要好狐粱,RMS誤差減小的很快舀寓。
調(diào)整不同的可以達(dá)到更好的效果。
(七)Batch MC and TD
- MC和TD收斂:
,隨著
-
但是對于有限經(jīng)驗(yàn)的批處理解決方案呢肌蜻?
- 例如:重復(fù)采樣episode
- 將MC或TD(0)應(yīng)用于episode
給定近似價(jià)值函數(shù)V互墓,在訪問非終止?fàn)顟B(tài)的每個時(shí)刻t,使用
或
計(jì)算相應(yīng)的增量宋欺,但是價(jià)值函數(shù)僅根據(jù)所有增量的和改變一次轰豆。然后,利用新的值函數(shù)再次處理所有可用的經(jīng)驗(yàn)齿诞,產(chǎn)生新的總增量酸休,依此類推,知道價(jià)值函數(shù)收斂祷杈。我們稱這種方法為批量更新斑司,因?yàn)橹挥性谔幚砹苏挠?xùn)練數(shù)據(jù)后才進(jìn)行更新。
AB Example
兩種狀態(tài)A,B宿刮; 沒有折扣互站; 8個episode的經(jīng)驗(yàn)
求
Certainty Equivalence
-
MC收斂到具有最小均方誤差的解決方案
-
最適合觀察到的收益
- 在AB示例中,
-
-
TD(0)收斂到最大似然馬爾可夫模型的解
- 最適合數(shù)據(jù)的MDP
的解決方案
- 在AB示例中僵缺,
- 最適合數(shù)據(jù)的MDP
(八)Advantages and Disadvantages of MC vs. TD (3)
- TD利用馬爾科夫性質(zhì)
- 通常在馬爾可夫環(huán)境中效率更高
- MC不利用馬爾科夫性質(zhì)
- 通常在非馬爾可夫環(huán)境中更有效
(九)United View
1胡桃、Monte-Carlo Backup
蒙特卡洛所做的基本上是這里一個完整軌跡的取樣,然后使用該樣本來更新價(jià)值函數(shù)磕潮。
2翠胰、Temporal-Difference Backup
時(shí)序差分備份只有一步,我們對環(huán)境和動作進(jìn)行采樣自脯,當(dāng)在下一步結(jié)束時(shí)之景,看看價(jià)值函數(shù),備份該價(jià)值函數(shù)膏潮。得到在一個步驟中發(fā)生的樣本锻狗,不會一直走到盡頭。
3焕参、Dynamic Programming Backup
動態(tài)規(guī)劃也是一步向前搜索轻纪,但我們沒有取樣,我們必須了解動態(tài)龟糕,我們使用這些動態(tài)來計(jì)算這個期望桐磁。做完整的備份來算出期望值。
4讲岁、Bootstrapping and Sampling
- Bootstrapping: 更新涉及估計(jì)
- MC不自舉
- DP自舉
- TD自舉
DP和TD用了貝爾曼方程我擂,對下一步狀態(tài)進(jìn)行估計(jì)。
- Sampling: 期望更新樣本
- MC samples
- DP does not sample缓艳,窮舉考慮每一個可能性
- TD samples
5校摩、United View of Reinforcement Learning
為什么我們假設(shè)一步之后的值比一步之前更準(zhǔn)確?為什么不轉(zhuǎn)移到另一個方向阶淘,替代的算法會得到正確的答案嗎衙吩?
不會得到正確的答案。事實(shí)上溪窒,即使你做了什么事情坤塞,比如讓這些東西相互靠近,然后將TD誤差等均方誤差最小化澈蚌,你找到了錯誤的答案摹芙,你實(shí)際上通過另一種方法得到了錯誤的答案。為什么我們給你直覺宛瞄,直覺是浮禾,如果你采取一個步驟,你在某種意義上總是更準(zhǔn)確一點(diǎn),因?yàn)檫@一步是真實(shí)的一步盈电,涉及到了真實(shí)回報(bào)蝴簇,也是真實(shí)動態(tài)的一步,然后你估計(jì)你結(jié)束之處的價(jià)值函數(shù)匆帚,但是因?yàn)槟阋呀?jīng)包含了一個真正的動態(tài)和真正的回報(bào)熬词,你在某種意義上更準(zhǔn)確,如果你采取足夠的這些步驟吸重,真正的動態(tài)總是帶你接近真理荡澎。
三、TD(
)
(一)n-Step TD
1晤锹、n-Step Prediction
讓TD目標(biāo)展望未來的n步
2、n-Step Return
- 考慮
的n步收益:
-
定義n步收益
-
n步時(shí)序差分學(xué)習(xí)
3彤委、大型隨機(jī)游動示例
當(dāng)n趨近于無窮鞭铆,接近于蒙特卡洛,會得到很高的錯誤率焦影,可能是訓(xùn)練時(shí)間較短车遂。
n=1時(shí),TD(0)表現(xiàn)很好斯辰。
4舶担、平均n步回報(bào)
- 我們可以對不同n取n步收益的平均值
-
例如:平均兩步和四步收益
- 合并來自兩個不同時(shí)間步的信息
-
我們能否有效地結(jié)合所有時(shí)間步驟中的信息?
(二)Forward View of TD(
)
如果彬呻,則整個更新被簡化為只有第一部分的更新衣陶,即單步時(shí)序差分更新;當(dāng)時(shí)闸氮,則整個更新被簡化為最后一部分的更新剪况,即蒙特卡洛更新。
- The
-return
結(jié)合了n步return
- 使用權(quán)重
可以把TD()看作平均n步更新的一種特例蒲跨,這里的平均值包含了所有可能的n步更新译断,每一個按比例
加權(quán),這里
,最后乘上正則項(xiàng)
保證權(quán)值的和為1或悲。產(chǎn)生的結(jié)果為
回報(bào)孙咪。
- Forward-view TD(
)
(三)
Weighting Function
參數(shù)表征了權(quán)值衰減的程度,因此就確定了在更新時(shí)回報(bào)算法往后看多遠(yuǎn)巡语。
-回報(bào)的定義為
在到達(dá)一個終止?fàn)顟B(tài)后翎蹈,所有的后續(xù)n步回報(bào)等于“齐可以將終止?fàn)顟B(tài)之后的計(jì)算項(xiàng)從主要的求和項(xiàng)中獨(dú)立出來杨蛋。
(四)Forward-view
- 向
-return更新值函數(shù)
- 前向視圖通過觀察未來來計(jì)算
- 像MC一樣,只能根據(jù)完整episodes進(jìn)行計(jì)算
(五)Forward-View
Large Random Walk
性能由最開始10個episode中19個狀態(tài)的真實(shí)價(jià)值和估計(jì)價(jià)值的均方根誤差的平均值來衡量逞力,兩種算法的性能相當(dāng)曙寡。在兩種情況下,都是在n-步算法的n和-回報(bào)的取中間值時(shí)獲得最好的性能寇荧。
(六)Backward View
- Forward view提供理論
- Backward view提供了機(jī)制
- 從不完整的序列在線更新每一步
Eligibility Traces(資格跡)
- 信用分配問題:電鈴還是電燈引起電擊举庶?
- 頻率啟發(fā)式:將信用分配給最頻繁的狀態(tài)
- 新近度啟發(fā)式方法:將信用分配給最近的狀態(tài)
- 資格跡結(jié)合了兩種啟發(fā)式方法:
資格跡是是一個和權(quán)值向量同維度的向量。權(quán)值向量是一個長期的記憶揩抡,在整個系統(tǒng)的生命周期中進(jìn)行積累户侥;而資格跡是一個短期記憶,其持續(xù)時(shí)間通常少于一個episode的長度峦嗤。資格跡輔助整個學(xué)習(xí)過程蕊唐,它們唯一的作用是影響權(quán)值向量,而權(quán)值向量則決定了估計(jì)值烁设。
在 中替梨,資格跡向量被初始化為0,然后再每一步累加價(jià)值函數(shù)的梯度装黑,并以
衰減副瀑。 在這里
是折扣系數(shù),而
為衰減率參數(shù)恋谭。資格跡追蹤了對最近的狀態(tài)評估值做出了或正或負(fù)貢獻(xiàn)的權(quán)值向量的分量糠睡。這里的最近由
來定義。
我們回顧了我們訪問的狀態(tài)的時(shí)間疚颊,所以這是一個特定狀態(tài)的資格跡狈孔,豎道是我們訪問的那個時(shí)刻, 基本上每次我們訪問那個狀態(tài)串稀,就增加資格跡除抛,當(dāng)我們不去訪問它時(shí),我們就指數(shù)地減少資格跡母截。
Backward View
- 保持每個狀態(tài)的資格跡
- 更新每個狀態(tài)s的值
- 與TD錯誤
和資格跡
成比例
當(dāng)一個強(qiáng)化學(xué)習(xí)事件出現(xiàn)時(shí)到忽,我們認(rèn)為這些貢獻(xiàn)“痕跡”展示了權(quán)值向量的對應(yīng)分量有多少“資格”可以接受學(xué)習(xí)過程引起的變化。我們關(guān)注的強(qiáng)化學(xué)習(xí)事件是一個又一個時(shí)刻的單步時(shí)序差分誤差清寇。預(yù)測的狀態(tài)價(jià)值函數(shù)的時(shí)序差分誤差為
在中喘漏,權(quán)值向量每一步的更新正比于時(shí)序差分的標(biāo)量誤差和資格跡。
在時(shí)間上往回看华烟,每個時(shí)刻我們計(jì)算當(dāng)時(shí)的時(shí)序查分誤差翩迈,并根據(jù)之前狀態(tài)對當(dāng)前資格跡的貢獻(xiàn)來分配它】梗可以想象在一個狀態(tài)流中负饲,計(jì)算時(shí)序差分誤差堤魁,然后將其傳播給之前訪問的狀態(tài)。當(dāng)時(shí)序差分誤差和跡同時(shí)起作用時(shí)返十,使得式子得到更新妥泉。
(六)Relationship Between Forward and Backward TD
1、
and
- 當(dāng)
洞坑,只有當(dāng)前狀態(tài)被更新盲链。
此時(shí)相當(dāng)于時(shí)序差分。也就是TD(0)迟杂。
- 這完全等同于
更新
TD(0)僅僅讓當(dāng)前時(shí)刻的前導(dǎo)狀態(tài)被當(dāng)前的時(shí)序差分誤差所改變刽沾。對于更大的,更多的之前的狀態(tài)會被改變排拷,越遠(yuǎn)的狀態(tài)改變越少侧漓,這是因?yàn)閷?yīng)的資格跡更小。也可以這樣說监氢,較早的狀態(tài)被分配了較小的信用來“消費(fèi)”TD誤差火架。
2、
and MC
- 當(dāng)
時(shí)忙菠,信用被推遲到了episode結(jié)束。
- 考慮具有離線更新的episodic環(huán)境
- 在episode過程中纺弊,
的總更新與MC的總更新相同
對于前視圖和后視圖牛欢,離線更新的總和是相同的
如果,那么之前狀態(tài)的信用每步僅僅衰減
淆游。這個恰好和蒙特卡洛算法的行為一致傍睹。
3、MC and TD(1)
- 考慮在時(shí)間步k訪問一次s的episode犹菱,
-
自訪問以來的TD(1)資格跡折扣時(shí)間
-
TD(1)更新在線累積誤差
-
到episode結(jié)束時(shí)拾稳,它累計(jì)了總誤差
4、Telescoping in TD(1)
當(dāng)時(shí)腊脱,將將TD誤差縮合為MC誤差
5访得、
和
-
大致等于every-visit蒙特卡洛
- 誤差是在線累計(jì)的,一步接一步
- 如果值函數(shù)僅在episode結(jié)束時(shí)離線更新陕凹,那么悍抑,總更新與MC完全相同
6、Telescoping in
7杜耙、Forwards and Backwards
- 考慮在步驟k中訪問一次s的episode
- 自訪問以來
資格跡折扣時(shí)間搜骡,
- Backward
在線更新累積誤差
- 到episode結(jié)束時(shí),它會累計(jì)
的誤差
- 對于對s的多次訪問佑女,
會累積許多誤差
8记靡、Offline Equivalence of Forward and Backward TD
離線更新
- 更新在episode中累積
- 但在episode結(jié)束批量應(yīng)用
9谈竿、Onine Equivalence of Forward and Backward TD
在線更新
-
更新將在episode內(nèi)的每個步驟在線應(yīng)用
- 前視和后視
略有不同
- 新:精確的在線
實(shí)現(xiàn)了完美的等效性
- 通過使用略有不同的資格跡形式
- Sutton and von Seijen, ICML 2014
10、Summary of Forward and Backward
= 表示episode結(jié)束時(shí)的總更新量相等摸吠。