[RL Notes] 时序差分学习
在预测问题中，我们的目标是估计价值函数
vπ(s)≐E[Gt|St=s]
即从给定状态开始能获得的回报。在使用蒙特卡洛方法进行策略评估时，可以通过下式增量地对估计值进行更新
\begin{equation} V(S_t) \leftarrow V(S_t) + \alpha [G_t – V(S_t)] \tag{2} \end{equation}
其中 G_t 是 t 时刻的真实回报，\alpha 是常量步长参数。使用这种增量式的实现，就不必保存回报列表。式 (2) 所示的方法称为常量 \alpha \; MC。注意式 (2) 中的 G_t 需要到一幕结束时才能得到，因此蒙特卡洛方法在一幕运行的期间学不到任何知识，而是需要等到一幕的末尾才能确定对 V(S_t) 的增量。
由折后回报的定义
\begin{equation} G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots = R_{t+1} + \gamma G_{t+1} \tag{3} \end{equation}
在式 (3) 中使用 V(S_{t+1}) 估计 G_{t+1}，则有
\begin{equation} G_t \approx R_{t+1} + \gamma V(S_{t+1}) \tag{4} \end{equation}
将式 (4) 替换式 (2) 中的 G_t，得到
\begin{equation} V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1})- V(S_t)] \tag{5} \end{equation}
注意式 (5) 中已经没有 G_t 了，不必等到一幕结束，而只需等到下一个时刻，就可以更新 V(S_t)。式 (5) 所示的方法是一种时序差分（time difference，TD）方法，称为 TD(0)，或单步 TD。
式 (5) 中的 R_{t+1} + \gamma V(S_{t+1})- V(S_t) 称为 TD 误差，记为
\begin{equation} \delta_t = R_{t+1} + \gamma V(S_{t+1})- V(S_t) \tag{6} \end{equation}
TD 将状态 S_t 的价值向其下一个状态 S_{t+1} 的价值的方向进行更新。
对比式 (2) 和式 (5) 可见，蒙特卡洛方法更新的目标是 G_t，而 TD 更新的目标是 R_{t+1} + \gamma V(S_{t+1})。 对比动态规划迭代策略评估的更新公式
\begin{equation} V(s) \leftarrow \sum\limits_a \pi(a|s) \sum\limits_{s’,r} p(s’, r | s, a) \Big[r + \gamma V(s’) \Big] \tag{7} \end{equation}
和式 (5) 可见，动态规划方法中的 \sum\limits_{s’,r} p(s’, r | s, a)\Big[r + \gamma V(s’) \Big] 一项计算了所有后续状态的期望，而在 TD 中只需要下一个状态，且这“下一个状态”可以直接从环境中获得，而不需要模型。
TD(0) 的完整算法如下所示。
表格型 TD(0) 算法，用于估计 v_\pi
输入：待评估的策略 \pi
算法参数：步长 \alpha \in (0, 1]
对于所有 s \in \mathcal{S}^+，任意初始化 V(s)，其中 V(终止状态)=0
对每幕循环：
初始化 S
对幕中的每一步循环：
A \leftarrow 策略 \pi 在状态 S 下做出的决策动作
V(S) \leftarrow V(S) + \alpha [R + \gamma V(S’)- V(S)]
S \leftarrow S’
直到 S 为终止状态