蒙特卡洛，时序差分Temporal-Difference Lea

１.蒙特卡洛
Monte-Carlo算法：
1.将agent放入环境的任意状态
2.从这个状态开始选择action, 并进入下一个状态
3.重复第二步直到达到最终状态
4.从最终状态回溯，计算每一个状态的G值
5.重复1-4过程，然后平均每一次的G值，最后得到的就是V值

关于G值：
第一步：根据策略使agent做出动作并进入下一动作，直到到达最终状态，需要记录每一个状态的转移，得到奖励r
第二步：从最终状态回溯，一遍一遍计算G值。 G 等于上一状态的G值（G‘）乘以一定的折扣（gamma）再加上r

回溯求G值

G值就是从某个状态到最终状态的奖励总和

G值
当我们进行多次实验，会经过某个状态多次，因此会有多个G值，此时这个状态的G值就是所有可能的G值的平均值，也就是我们的V值
G值平均
以策略π2进行game，由于策略改变，经过S的概率会发生变化，因此最终状态的经过次数就会不同 状态价值函数V(s)描述在策略pi下某个状态s具有的价值(预期返还return)

G就是V的更新目标，关于MC的更新：
两种方法：

１.平均值法： 平均值
２.G的逐渐逼近法： 逐渐逼近
不难看出，虽然蒙特卡洛算法比动态规划的消耗少，并且不需要知道整个环境模型，但是每一次游戏都需要从头执行到尾，再进行回溯。如果最终状态难以达到，则会需要很久才会更新G值。
MC的弊端：1. MC算法相对动态规划，会有点不那么准。因为MC每一次的路径都是不一样的。 2. 如果环境的状态空间非常大，或者最终状态只有非常小的概率达到。那么MC算法将会很难处理。
因此需要使用时序差分(TD)算法解决此问题。

２.时序差分(TD)算法
TD是对MC的改进，即agent走到第N步就可以开始回溯更新。

TD
可以理解为走一步看一步，好比下山，MC是直接从山顶下山，看看下山的路有多长，而TD是先走一段，看看是否有路牌指示到下山还有多少距离，如果有，几句把刚才的路加上路牌指示的到山脚的距离相加即可。
在一开始，我们根本没有路牌，所以也不知道到底到山脚有多远。 但当我们走很多次的时候，路牌系统就能慢慢建立起来。 例如第一次，只有到了山脚，我才知道山脚前一站离山脚的的真实距离。于是我更新了山脚前一站的路牌。第二次，我在山脚前一站路就能看到路牌，所以我就可以更新山脚前一站的路牌了…一直到山顶，就这样一直建立整座山的路牌系统。
关于TD的更新公式：
TD的更新公式
在TD，我们只不过把更新目标从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