[RL Notes] 时序差分学习——一个例子
1. 问题
使用《强化学习》（第二版）例 6.1 中开车回家的例子，在下班开车回家的路途中，不断地记录路上消耗的时间和估计到家的时间：
- 18:00 – 离开办公室的时间记为时刻 0，估计 30 分钟后到家。
- 18:05 – 5 分钟后到达车旁，发现开始下雨，估计路上会花更多时间，于是估计还要花 35 分钟到家（算上已经花费的 5 分钟，估计到家花费的总时间为 40 分钟）。
- 18:20 – 开了 15 分钟下了高速，高速比往常顺畅，比预期少花了 5 分钟，于是将估计总时间减少到 35 分钟，估计剩余时间为 15 分钟。
- 18:30 – 又开了 10 分钟，被堵在一辆缓慢的卡车后面，道路狭窄无法超车，估计到家要多花些时间，于是将估计总时间增加到 40 分钟，估计剩余时间为 10 分钟。
- 18:40 – 又堵了 10 分钟终于抵达了居住的街道，估计还要花 3 分钟才能到家，于是将估计总时间增加到 43 分钟，估计剩余时间为 3 分钟。
- 18:43 – 终于到家。
将上述过程记录如表 1 所示。
表 1
| 状态 | 消耗的总时间（分钟） | 估计剩余时间 | 估计总时间 |
|---|---|---|---|
| 离开办公室 | 0 | 30 | 30 |
| 到车旁，开始下雨 | 5 | 35 | 40 |
| 下高速 | 20 | 15 | 35 |
| 在路上被堵在卡车后面 | 30 | 10 | 40 |
| 开到居住的街道 | 40 | 3 | 43 |
| 到家 | 43 | 0 | 43 |
定义每个状态的收益为该步骤消耗的时间，过程不加折扣（$\gamma = 1$），则每个状态的回报就是从这个状态开始到回家实际消耗的总时间。
下面分别使用蒙特卡洛方法和时序差分方法对状态价值进行更新。
2. 蒙特卡洛方法
蒙特卡洛方法使用下式对状态价值进行更新。
\begin{equation}
V(S_t) \leftarrow V(S_t) + \alpha [G_t – V(S_t)] \tag{1}
\end{equation}
本例中取 $\alpha = 1$。蒙特卡洛方法使用 $G_t$ 更新估计值，$G_t$ 只有在一幕结束时才能获得。也就是说，必须要等到家后才能更新对各个状态的估计。
将各个时刻 $t$ 下个状态 $S_t$、回报 $G_t$（从 $S_t$ 开始到回家实际消耗的总时间）和状态价值的估计 $V(S_t)$（即表 1 中的估计剩余时间）列出如表 2 所示。
表 2
| $t$ | $S_t$ | $G_t$ | $V(S_t)$ |
|---|---|---|---|
| 0 | 离开办公室 | 43 | 30 |
| 1 | 到车旁，开始下雨 | 38 | 35 |
| 2 | 下高速 | 23 | 15 |
| 3 | 在路上堵在卡车后面 | 13 | 10 |
| 4 | 开到居住的街道 | 3 | 3 |
| 5 | 到家 | 0 | 0 |
如表 2 所示，$G_0$ 表示从离开办公室到抵达家中所消耗的时间，故有
\begin{equation}
G_0 = 5 + 15 + 10 + 10 + 3 = 43
\end{equation}
由式 $(1)$，更新 $V(S_0)$ 为
\begin{equation}
V(S_0) \leftarrow V(S_0) + \alpha [G_0 – V(S_0)] = 30 + (43 – 30) = 43 \\
\end{equation}
类似地，计算其他状态的更新如下
\begin{align}
V(S_1) &\leftarrow V(S_1) + \alpha [G_1 – V(S_1)] = 35 + (38 – 35) = 38 \\
V(S_2) &\leftarrow V(S_2) + \alpha [G_2 – V(S_2)] = 15 + (23 – 15) = 23 \\
V(S_3) &\leftarrow V(S_3) + \alpha [G_3 – V(S_3)] = 10 + (13 – 10) = 13 \\
V(S_4) &\leftarrow V(S_4) + \alpha [G_4 – V(S_4)] = 3 + (3 – 3) = 3
\end{align}
3. 时序差分
实际上，我们并不需要等到家后再更新对各个状态的估计。
时序差分使用下式对状态价值进行更新。
\begin{equation}
V(S_t) \leftarrow V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) – V(S_t)] \tag{2}
\end{equation}
本例中取 $\alpha = 1$，$\gamma = 1$。
将各个时刻 $t$ 下个状态 $S_t$、收益 $R_t$（该步骤消耗的时间）和状态价值的估计 $V(S_t)$（即表 1 中的估计剩余时间）列出如表 3 所示。注意表 3 中并没有 $G_t$。
表 3
| $t$ | $S_t$ | $R_t$ | $V(S_t)$ |
|---|---|---|---|
| 0 | 离开办公室 | 0 | 30 |
| 1 | 到车旁，开始下雨 | 5 | 35 |
| 2 | 下高速 | 15 | 15 |
| 3 | 在路上堵在卡车后面 | 10 | 10 |
| 4 | 开到居住的街道 | 10 | 3 |
| 5 | 到家 | 3 | 0 |
由式 $(2)$，在到达状态 $S_1$ 后，即可更新 $S_0$ 的估计，此时
\begin{equation}
V(0) \leftarrow V(S_0) + \alpha [R_1 + \gamma V(S_1) – V(S_0)] = 30 + (5 + 35 – 30) = 40
\end{equation}
这在直观上也容易理解：从离开办公室（$S_0$）到抵达车旁（$S_1$）花了 $5$ 分钟（$R_1$），发现下雨，估计到家还要花费 $35$ 分钟（$V(S_1)$）。再次回到 $S_0$，由于掌握了 $S_1$ 的信息，此时应该估计到家的时间为 $5 + 35 = 40$ 分钟，更新估计值 $V(S_t)$ 为 $30 + (40 – 30) = 40$ 分钟。
类似地，计算其他状态的更新如下
\begin{align}
V(S_1) &\leftarrow V(S_1) + \alpha [R_2 + \gamma V(S_2) – V(S_1)] = 35 + (15 + 15 – 35) = 30 \\
V(S_2) &\leftarrow V(S_2) + \alpha [R_3 + \gamma V(S_3) – V(S_2)] = 15 + (10 + 10 – 15) = 20 \\
V(S_3) &\leftarrow V(S_3) + \alpha [R_4 + \gamma V(S_4) – V(S_3)] = 10 + (10 + 3 – 10) = 13 \\
V(S_4) &\leftarrow V(S_4) + \alpha [R_5 + \gamma V(S_5) – V(S_4)] = 3 + (3 + 0 – 3) = 3
\end{align}
可见时序差分方法的更新只需要下一个状态，而不需要等到一幕结束。