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