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