[RL Notes] 线性方法

1. 线性方法

  我们可以在强化学习中使用任意类型的函数进行函数逼近,使用线性函数是最重要的特殊情况之一。线性函数易于理解,便于记性数学计算,而且通过结合领域知识构造合适的特征,可以快速地学习并达到较高的准确度。

  这里的“线性”指的是近似函数 $\hat{v}(\cdot, \boldsymbol{\mathrm{w}})$ 是权重向量 $\boldsymbol{\mathrm{w}}$ 的线性函数,对于每一个状态 $s$,存在一个和 $\boldsymbol{\mathrm{w}}$ 同维度的实向量 $\boldsymbol{\mathrm{x}} \doteq (x_1(s), x_2(s), \cdots, x_d(s))^\mathsf{T}$,线性近似的状态价值函数为 $\boldsymbol{\mathrm{w}}$ 和 $\boldsymbol{\mathrm{x}}(s)$ 的内积

\begin{equation}
\hat{v}(s, \boldsymbol{\mathrm{w}}) \doteq \boldsymbol{\mathrm{w}}^\mathsf{T} \boldsymbol{\mathrm{x}}(s) \doteq \sum_{i=1}^d w_i x_i(s) \tag{1}
\end{equation}

此时称近似价值函数是依据权重线性的,或者简称为线性的。

  由式 $(1)$ 可得近似价值函数关于 $\boldsymbol{\mathrm{w}}$ 的梯度为

\begin{equation}
\nabla \hat{v}(s, \boldsymbol{\mathrm{w}}) = \boldsymbol{\mathrm{x}}(s) \tag{2}
\end{equation}

回顾通用 SGD 更新公式

\begin{equation}
\boldsymbol{\mathrm{w}}_{t+1} \doteq \boldsymbol{\mathrm{w}}_t + \alpha \Big[U_t – \hat{v}(S_t, \boldsymbol{\mathrm{w}}_t)\Big] \nabla \hat{v}(S_t, \boldsymbol{\mathrm{w}}_t) \tag{3}
\end{equation}

将式 $(2)$ 代入式 $(3)$,可以得到一个非常简单的线性函数的更新公式

\begin{equation}
\boldsymbol{\mathrm{w}}_{t+1} \doteq \boldsymbol{\mathrm{w}}_t + \alpha \Big[U_t – \hat{v}(S_t, \boldsymbol{\mathrm{w}}_t)\Big] \boldsymbol{\mathrm{x}}(S_t) \tag{4}
\end{equation}

2. 线性 TD

  对于单步 TD 的方法,其目标定义为

\begin{equation}
U_{t} \doteq R_{t+1} + \gamma \hat{v}(S_{t+1}, \boldsymbol{\mathrm{w}}_t) \tag{5}
\end{equation}

此时的更新为

\begin{align}
\boldsymbol{\mathrm{w}}_{t+1} &\doteq \boldsymbol{\mathrm{w}}_t + \alpha \Big[R_{t+1} + \gamma \hat{v}(S_{t+1}, \boldsymbol{\mathrm{w}}_t) – \hat{v}(S_t, \boldsymbol{\mathrm{w}}_t)\Big] \boldsymbol{\mathrm{x}}(S_t) \tag{6}
\end{align}

  类似于线性价值函数逼近是表格型价值函数的泛化,线性 TD 也是表格型 TD 的泛化,只需构造特征 $\boldsymbol{\mathrm{x}}(s_i)$ 为状态 $s_i$ 的指示函数

\begin{equation}
\boldsymbol{\mathrm{x}}(s_i) = \begin{bmatrix}0 & 0 & \cdots & 1 & 0 & \cdots & 0\end{bmatrix}^\mathsf{T}
\end{equation}

$\boldsymbol{\mathrm{x(s_i)}}$ 中只有第 $i$ 个元素为 $1$,其余元素为 $0$,此时有 $\hat{v}(S_i, \boldsymbol{\mathrm{w}}) = w_i$。

3. TD 的目标

  回到式 $(6)$,将 $\boldsymbol{\mathrm{x}}(S_t)$ 简写为 $\boldsymbol{\mathrm{x}}_t$,并将式 $(1)$ 代入式 $(6)$,得到

\begin{align}
\boldsymbol{\mathrm{w}}_{t+1} &\doteq \boldsymbol{\mathrm{w}}_t + \alpha \Big[R_{t+1} + \gamma \hat{v}(S_{t+1}, \boldsymbol{\mathrm{w}}_t) – \hat{v}(S_t, \boldsymbol{\mathrm{w}}_t)\Big] \boldsymbol{\mathrm{x}}_t \\
&= \boldsymbol{\mathrm{w}}_t + \alpha \Big[R_{t+1} + \gamma \boldsymbol{\mathrm{w}}_t^\mathsf{T} \boldsymbol{\mathrm{x}}_{t+1} – \boldsymbol{\mathrm{w}}_t^\mathsf{T} \boldsymbol{\mathrm{x}}_t \Big] \boldsymbol{\mathrm{x}}_t \\
&= \boldsymbol{\mathrm{w}}_t + \alpha \Big[R_{t+1}\boldsymbol{\mathrm{x}}_t – \boldsymbol{\mathrm{x}}_t(\boldsymbol{\mathrm{x}}_t – \gamma \boldsymbol{\mathrm{x}}_{t+1})^\mathsf{T} \boldsymbol{\mathrm{w}}_t \Big] \tag{7}
\end{align}

将式 $(7)$ 中等号两边同减去 $\boldsymbol{\mathrm{w}}_t$,可得更新的期望为

\begin{equation}
\mathbb{E}[\Delta \boldsymbol{\mathrm{w}}_t] = \alpha \mathbb{E} \Big[R_{t+1}\boldsymbol{\mathrm{x}}_t – \boldsymbol{\mathrm{x}}_t(\boldsymbol{\mathrm{x}}_t – \gamma \boldsymbol{\mathrm{x}}_{t+1})^\mathsf{T} \boldsymbol{\mathrm{w}}_t \Big] = \alpha (\boldsymbol{\mathrm{b}} – \boldsymbol{\mathrm{A}} \boldsymbol{\mathrm{w}}_t) \tag{8}
\end{equation}

其中

\begin{equation}
\boldsymbol{\mathrm{b}} \doteq \mathbb{E}[R_{t+1} \boldsymbol{\mathrm{x}}_t] \\
\boldsymbol{\mathrm{A}} \doteq \mathbb{E}[\boldsymbol{\mathrm{x}}_t (\boldsymbol{\mathrm{x}}_t – \gamma \boldsymbol{\mathrm{x}}_{t+1})^\mathsf{T}]
\end{equation}

  当式 $(8)$ 为零时权重收敛,称令式 $(8)$ 为零的 $\boldsymbol{\mathrm{w}}_t$ 为 TD 的不动点(fixed point),记为 $\boldsymbol{\mathrm{w}}_{\mathrm{TD}}$,有

\begin{equation}
\mathbb{E}[\Delta \boldsymbol{\mathrm{w}}_{\mathrm{TD}}] = \alpha (\boldsymbol{\mathrm{b}} – \boldsymbol{\mathrm{A}} \boldsymbol{\mathrm{w}}_{\mathrm{TD}}) = 0 \tag{9}
\end{equation}

可以解得

\begin{equation}
\boldsymbol{\mathrm{w}}_{\mathrm{TD}} = \boldsymbol{\mathrm{A}}^{-1} \boldsymbol{\mathrm{b}} \tag{10}
\end{equation}

  可以证明,线性 TD 会收敛到不动点 $\boldsymbol{\mathrm{w}}_{\mathrm{TD}}$,$\boldsymbol{\mathrm{w}}_{\mathrm{TD}}$ 最小化了 $(\boldsymbol{\mathrm{b}} – \boldsymbol{\mathrm{A}} \boldsymbol{\mathrm{w}})^\mathsf{T} (\boldsymbol{\mathrm{b}} – \boldsymbol{\mathrm{A}} \boldsymbol{\mathrm{w}})$,称为映射贝尔曼误差(projected Bellman error)。在 TD 不动点处,$\overline{\mathrm{VE}}$ 在可能的最小误差的一个扩展边界内

\begin{equation}
\overline{\mathrm{VE}}(\boldsymbol{\mathrm{w}}_{\mathrm{TD}}) \leq \frac{1}{1 – \gamma} \min_{\boldsymbol{\mathrm{w}}} \overline{\mathrm{VE}}(\boldsymbol{\mathrm{w}}) \tag{11}
\end{equation}

上式说明 TD 法的渐进误差不超过蒙特卡洛法最小误差的 $\frac{1}{1 – \gamma}$ 倍,$\gamma$ 越小则误差越小。如果我们能完美地逼近真实的价值函数,则无论 $\gamma$ 如何取值,式 $(11)$ 的等号成立,因为此时左右两边表示的误差都为 $0$。由于 TD 使用函数逼近进行自举,如果它对下一个状态的预测一直不准,则会导致 TD 一直向着错误的目标更新;反之,如果函数逼近很准确,则对下一个状态的预测也很准确,此时 TD 的误差也会接近最小价值误差。

  实际中的 $\gamma$ 往往接近 $1$,导致式 $(11)$ 不等号右边的扩展因子会相当大。虽然 TD 方法在渐进性能上有很大损失,但其方差比蒙特卡洛方法小得多,因此收敛得更快。具体哪种方法最好取决于近似的问题和性质,以及学习的时间。