[RL Notes] 时序差分学习——一个例子

Author: nex3z 2019-10-27

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}$$

可见时序差分方法的更新只需要下一个状态，而不需要等到一幕结束。