时序差分法求解

时序差分法简介

时序差分法与蒙特卡洛法相似，都是不基于模型的强化学习问题求解方法。时序差分法使用不完整的状态序列近似求出给定状态的收获。回顾贝尔曼方程：

\[ v_{\pi}(s) = \mathbb{E}_{\pi}(R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t=s) \]

这说明可以使用\(R_{t+1} + \gamma v(S_{t+1})\)近似的代替收获\(G_t\),一般把\(R_{t+1} + \gamma v(S_{t+1})\)称为TD目标值，\(R_{t+1} + \gamma V(S_{t+1}) -V(S_t)\)称为TD误差。这样我们只需要两个连续状态与对应的奖励就可以求解强化学习问题了。

时序差分法求解预测问题

时序差分问题的表达式为：

\[ G(t) = R_{t+1} + \gamma V(S_{t+1}) \]

在计算时从不完整序列的尾部开始计算，直到计算到首部。

其迭代的式子系数稍有不同，回顾蒙特卡洛法的迭代式子为：

\[ V(S_t) = V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t) ) \]

而在时序差分法中由于没有完整的序列，因此没有对应的次数，因此迭代式子改为：

\[ V(S_t) = V(S_t) + \alpha(G_t - V(S_t) ) \]

\[ Q(S_t, A_t) = Q(S_t, A_t) +\alpha(G_t - Q(S_t, A_t) ) \]

时序差分的特点

1. 时序差分法在知道结果之前就可以学习，也可以在没有结果时学习，还可以在持续进行的环境中学习，而蒙特卡罗法则要等到最后结果才能学习，时序差分法可以更快速灵活的更新状态的价值估计。
2. 时序差分法在更新状态价值时使用的是TD 目标值，即基于即时奖励和下一状态的预估价值来替代当前状态在状态序列结束时可能得到的收获，是当前状态价值的有偏估计，而蒙特卡罗法则使用实际的收获来更新状态价值，是某一策略下状态价值的无偏估计，这一点蒙特卡罗法占优。
3. 虽然时序差分法得到的价值是有偏估计，但是其方差却比蒙特卡罗法得到的方差要低，且对初始值敏感，通常比蒙特卡罗法更加高效。

n步时序差分

基础的时序差分法使用\( R_{t+1} + \gamma v(S_{t+1}) \)近似的代替收获\( G_t \)。这是只考虑到的那个钱状态以及后续一个状态的情况。当然我们也可以考虑后续两个状态：

\[ G_t^{(2)} = R_{t+1} + \gamma R_{t+2} + \gamma^2V(S_{t+2}) \]

从此可以归纳出n步时序差分法的收获\(G_t^{(n)}\)为：

\[ G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1} R_{t+n} + \gamma^nV(S_{t+n}) \]

当n为无穷时，时序差分法变为蒙特卡洛法。

时序差分的控制问题求解

时序差分的控制问题求解可以分为两种方法，分别为离线控制法以及在线控制法。在线控制法最常见的算法为SARSA算法，而离线控制法最常见的算法为Q-Learning算法。