[RL Note] 时序差分学习

  在预测问题中,我们的目标是估计价值函数

\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 – 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$ 为终止状态