强化学习导论——Temporal-Difference Lear

毫无疑问TD是强化学习中一个最新奇的算法，它结合了MC和DP的思想

constant a-MC可以表示为

那么简单的TD可以表示为

可以看出TD仅需要一步动作就能更新价值函数

他们的区别在于MC以6.3式为目标，而TD以6.4式为目标

而且蒙特卡洛error可以拆分成很多TD error

TD相对于DP来说不需要知道环境模型，相对于MC来说可以尽可能早的学习，实验发现TD比constant a-MC的收敛要快一些。

如果数据集为

batch TD（0）预测V(A)=3/4，而batch Monte Carlo预测V(A)=0，显然batch TD（0）的预测更符合我们的常理。因为如果给定MDP模型，显然容易得到。batch TD(0)收敛于certainty-equivalence estimate

batch TD（0）和batch Monte Carlo方法找到的估计值之间的一般差异。 batch蒙特卡罗方法总是找到最小化训练集上的均方误差的估计，而batch TD（0）总是找到对于马尔可夫过程的最大似然模型而言非常正确的估计。

对于策略的学习(即预测Q(s, a))

on-policy的方法行为策略和目标策略是一致的

off-policy的行为策略和目标策略不一致，Q-Learning被证明以概率1收敛到q*

他们的区别在于：Although Q-learning actually learns the values of the optimal policy, its on-line performance is worse than that of Sarsa, which learns the roundabout policy.

修改一下策略迭代公式，可以得到基于期望的Sarsa，通常可以减小方差

无论是Q-Learning还是Sarsa都涉及到max操作，这会产生一种过估计的现象，假设有一种情况，所有的q(s,a)都是0，实际上预测是在0上下浮动，max操作便会使得最终的预测结果倾向于更大的值，这就是Double Learning中的过估计问题。

一种解决过估计的方法：过估计产生的原因是使用相同的样本选择最大价值动作和预估其值，Double Learning使用一个额外的策略选择最大价值动作，并且预估当前策略的值。

算法描述如下

实际效果