[RL Notes] 时序差分学习
在预测问题中，我们的目标是估计价值函数
\begin{equation}
v_\pi(s) \doteq \mathbb{E}[G_t|S_t = s] \tag{1}
\end{equation}
即从给定状态开始能获得的回报。在使用蒙特卡洛方法进行策略评估时，可以通过下式增量地对估计值进行更新
\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$ 为终止状态