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

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