１.蒙特卡洛
Monte-Carlo算法：
1.將agent放入環(huán)境的任意狀態(tài)
2.從這個(gè)狀態(tài)開(kāi)始選擇action, 并進(jìn)入下一個(gè)狀態(tài)
3.重復(fù)第二步直到達(dá)到最終狀態(tài)
4.從最終狀態(tài)回溯，計(jì)算每一個(gè)狀態(tài)的G值
5.重復(fù)1-4過(guò)程，然后平均每一次的G值，最后得到的就是V值
關(guān)于G值：
第一步：根據(jù)策略使agent做出動(dòng)作并進(jìn)入下一動(dòng)作，直到到達(dá)最終狀態(tài)，需要記錄每一個(gè)狀態(tài)的轉(zhuǎn)移，得到獎(jiǎng)勵(lì)r
第二步：從最終狀態(tài)回溯，一遍一遍計(jì)算G值。 G 等于上一狀態(tài)的G值（G‘）乘以一定的折扣（gamma）再加上r
回溯求G值
G值就是從某個(gè)狀態(tài)到最終狀態(tài)的獎(jiǎng)勵(lì)總和
G值
當(dāng)我們進(jìn)行多次實(shí)驗(yàn)，會(huì)經(jīng)過(guò)某個(gè)狀態(tài)多次，因此會(huì)有多個(gè)G值，此時(shí)這個(gè)狀態(tài)的G值就是所有可能的G值的平均值，也就是我們的V值
G值平均
以策略π2進(jìn)行g(shù)ame，由于策略改變，經(jīng)過(guò)S的概率會(huì)發(fā)生變化，因此最終狀態(tài)的經(jīng)過(guò)次數(shù)就會(huì)不同
狀態(tài)價(jià)值函數(shù)V(s)描述在策略pi下某個(gè)狀態(tài)s具有的價(jià)值(預(yù)期返還return)
G就是V的更新目標(biāo)，關(guān)于MC的更新：
兩種方法：
平均值
２.G的逐漸逼近法：
逐漸逼近
不難看出，雖然蒙特卡洛算法比動(dòng)態(tài)規(guī)劃的消耗少，并且不需要知道整個(gè)環(huán)境模型，但是每一次游戲都需要從頭執(zhí)行到尾，再進(jìn)行回溯。如果最終狀態(tài)難以達(dá)到，則會(huì)需要很久才會(huì)更新G值。
MC的弊端：1. MC算法相對(duì)動(dòng)態(tài)規(guī)劃，會(huì)有點(diǎn)不那么準(zhǔn)。因?yàn)镸C每一次的路徑都是不一樣的。 2. 如果環(huán)境的狀態(tài)空間非常大，或者最終狀態(tài)只有非常小的概率達(dá)到。那么MC算法將會(huì)很難處理。
因此需要使用時(shí)序差分(TD)算法解決此問(wèn)題。
２.時(shí)序差分(TD)算法
TD是對(duì)MC的改進(jìn)，即agent走到第N步就可以開(kāi)始回溯更新。
TD
可以理解為走一步看一步，好比下山，MC是直接從山頂下山，看看下山的路有多長(zhǎng)，而TD是先走一段，看看是否有路牌指示到下山還有多少距離，如果有，幾句把剛才的路加上路牌指示的到山腳的距離相加即可。
在一開(kāi)始，我們根本沒(méi)有路牌，所以也不知道到底到山腳有多遠(yuǎn)。 但當(dāng)我們走很多次的時(shí)候，路牌系統(tǒng)就能慢慢建立起來(lái)。 例如第一次，只有到了山腳，我才知道山腳前一站離山腳的的真實(shí)距離。于是我更新了山腳前一站的路牌。第二次，我在山腳前一站路就能看到路牌，所以我就可以更新山腳前一站的路牌了…一直到山頂，就這樣一直建立整座山的路牌系統(tǒng)。
關(guān)于TD的更新公式：
TD的更新公式
在TD，我們只不過(guò)把更新目標(biāo)從G，改成r+gamma*V
reference:
1.Deep Reinforcement Learning: A Brief Survey
https://ieeexplore.ieee.org/abstract/document/8103164
2.https://zhuanlan.zhihu.com/p/109217883
3.https://zhuanlan.zhihu.com/p/25580624
4.https://omarsbrain.wordpress.com/2010/01/22/bootstrapping-and-artificial-intelligence/
5.https://blog.csdn.net/qq_42715079/article/details/117782272
