TD-预测

在蒙特卡洛方法中，对于 every-visit 的蒙特卡洛方法，可以给出一个递推的更新公式：

这个式子里面的 必须在一幕结束之后才能计算出来，所以在一幕中学不到任何信息。

而 的定义是：

如果使用 来估算 的话，那么有

带入有

注意到这里的式子里面已经没有东西需要在一个幕结束之后才能算出来，那么就得到了一个只需要一步的时序差分方法，称为 或单步

算法如图所示：

TD-Error

定义 TD-error 为：

那么式 可以写为

蒙特卡洛误差可以被写成 TD-Error 的形式：

Sarsa方法

前面给出了状态价值函数的更新公式，但是在实际做出决策的时候，动作价值函数是更为实用的选择，所以这里给出动作价值函数的更新公式：

这里的公式中同样不含有任何需要一个episode结束才能算出来的东西，所以可以动态更新。

On-policy的时序差分方法

在给定策略 的情况下，可以根据公式 来更新动作价值函数，并且更新 来逼近最优的策略。算法如图：

Q-Learning —— Off-Policy 的时序差分方法

定义更新公式：

Q-Learning已经证明是不依赖初始策略，以概率为1去逼近最优策略的动作价值函数了，其算法如下图所示：

基于期望的Sarsa

基于期望的Sarsa的更新公式改成了

相比于Sarsa，基于期望的版本的更新更为平稳，但是计算更复杂一些。

最大化偏差和Double-Q Learning

在Q-Learning中，因为是取的期望，所以在每一次取最大化的过程中，会存在最大化偏差，导致某些很差的动作被选择的概率降低的速度很慢，那么就可以使用Double-QLearning，把所有情况的价值函数拆成两个部分分别更新来解决这个问题，算法如图：

TODO:弄清楚为什么Double的效果更好