[RL Notes] 线性方法

Author: nex3z 2019-11-05

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 方法在渐进性能上有很大损失，但其方差比蒙特卡洛方法小得多，因此收敛得更快。具体哪种方法最好取决于近似的问题和性质，以及学习的时间。