Skip to content

强化学习导论(九)- 在线策略的近似预测

前面八章讲的算法在使用旧的 Q(S) 时都是在对 Q 函数进行查表操作:采用数据表存储每个 state 的 value ,然后用各种各样的算法来更新这个 Q 表,直到收敛。在更新的过程中也能渐渐确定出对应的最优策略。

本章在 Q 函数的处理上,不再使用查表法,而是使用『函数近似』的方法,他和『查表法』的区别在于:

  1. 不再使用数据表来存储各个对应关系,而是直接用函数来表示这个关系。
  2. 使用『监督学习』,通过更新参数的方式来使函数收敛。

其优点在于,内存空间占用得到了较大优化(这是因为参数的个数通常远小于状态数量),同时,训练出来的函数其泛用性更佳。

9.1 Value-function Approximation

这一章开始,用参数化的形式表示 value function ,写作 \hat{v}(s,\mathbf{w}) ,其中 \mathbf{w} 为训练出来的特征权重。

value function 的更新可以简单表示为映射 s \mapsto u ,其中 s 表示用于更新的 state,u 表示被更新的 update target 。

  • MC: S_t\mapsto G_t
  • TD(0): S_t\mapsto R_{t+1}+\gamma \hat{v}(S_{t+1},\mathbf{w}_t)
  • n-step TD: S_t\mapsto G_{t:t+n}
  • DP: s\mapsto \mathbb{E}_\pi[R_{t+1}+\gamma\hat{v}(S_{t+1},\mathbf{w}_t)|S_t=s]

我们将这样的过程看作 input-output 样本,便能使用各种各样的『监督学习』方法来做训练,最终得到近似的 value function 。

9.2 The Prediction Objective (MSVE)

在监督学习中,我们需要设定一个目标函数来不断优化,这里我们考虑 value function 的『均方误差』:

\mathrm{MSVE}(\mathbf{w})\doteq \sum_{s\in\mathcal S}\mu(s)\left[v_\pi(s)-\hat{v}(s,\mathbf{w})\right]^2

其中 \mu(s)\geq 0, \sum_s\mu(s)=1 为 on-policy distribution ,是状态访问次数的分布,表示了我们对于各个状态的关注程度。

对于离散型的片段式任务,\mu 的定义为

\begin{aligned} \eta(s)&=h(s)+\sum_{\bar{s}}\eta(\bar{s})\sum_a\pi(a|\bar{s})p(s|\bar{s},a), \forall s \in \mathcal S\\ \mu(s)&=\frac{\eta(s)}{\sum_{s'}\eta(s')}, \forall s \in \mathcal S \end{aligned}

其中 h(s) 表示状态 s 被选为初始状态的概率。

我们的目的就是要找到这个误差函数的极小值,得到极值点 \mathbf{w}^* ,进而得以确定近似 value function \hat{v}(s,\mathbf{w}^*)

9.3 Stochastic-gradient and Semi-gradient Methods

考虑采用随机梯度(SGD)的方法来完成上一节的目标,更新式为

\begin{aligned} \mathbf{w}_{t+1}&\doteq \mathbf{w}_t-\frac{1}{2}\alpha\nabla[v_\pi(S_t)-\hat{v}(S_t,\mathbf{w}_t)]^2\\ &=\mathbf{w}_t+\alpha[v_\pi(S_t)-\hat{v}(S_t,\mathbf{w}_t)]\nabla\hat{v}(S_t,\mathbf{w}_t) \end{aligned}

其中的 v_\pi(S_t) 也可以是一个估计值 U_t ,此时,若满足下列条件,可以确保收敛

  • U_tv_\pi(S_t) 的无偏估计,即有 \mathbb{E}(U_t)=v_\pi(S_t)
  • \sum_{n=1}^\infty \alpha_n = \infty , \sum_{n=1}^\infty\alpha_n^2<\infty

以 MC 为例,其算法伪代码如下

一些用到了自助法(bootstrapping)的估计,如

  • n-step TD : G_{t:t+n}=R_{t+1}+\cdots+\gamma^{n-1}R_{t+n}+\gamma^n\hat{v}(S_{t+n},\mathbf{w}_t)
  • DP : \sum_{a,s',r}\pi(a|S_t)p(s',r|S_t,a)[r+\gamma \hat{v}(s',\mathbf{w}_t)]

这些估计值都与权向量 \mathbf{w} 相关,被其偏置(biased),这类 target 代入梯度更新式后,只能得到部分梯度的下降,而非真正的梯度下降,故称其为『半梯度法(semi-gradient methods)』

半梯度法与普通的梯度下降形式一致,区别仅在于 target 的选取,即训练样本的 output 是否是 input 的无偏估计。

半梯度法虽然收敛性不如真正的梯度下降法,但他有如下优点:

  1. 半梯度法在线性模型下仍能确保收敛。
  2. 在可收敛的前提下,半梯度法收敛速度很快。
  3. 半梯度法可用于连续型任务,无需等待一个完整的 episode 结束。

下面给出一个使用半梯度法的示例:

9.4 Linear Methods

在线性近似的方法中,将 value function 看作 \mathbf{w} 的线性函数,此时为权重与特征的内积

\hat{v}(s,\mathbf{w})\doteq\mathbf{w}^T\mathbf{x}(s)\doteq \sum_{i=1}^dw_ix_i(s)

代入更新式即为

\mathbf{w}_{t+1}\doteq\mathbf{w}_t+\alpha[U_t-\hat{v}(S_t,\mathbf{w}_t)]\mathbf{x}(S_t)

上一节的半梯度 TD(0) 算法能够在线性函数逼近中收敛,迭代式为

\begin{aligned} \mathbf{w}_{t+1}&\doteq\mathbf{w}_t+\alpha(R_{t+1}+\gamma\mathbf{w}_t^T\mathbf{x}_{t+1}-\mathbf{w}_t^T\mathbf{x}_t)\mathbf{x}_t\\ &=\mathbf{w}_t+\alpha(R_{t+1}\mathbf{x}_t-\mathbf{x}_t(\mathbf{x}_t-\gamma\mathbf{x}_{t+1})^T\mathbf{w}_t) \end{aligned}

也可写作

\mathbb{E}[\mathbf{w}_{t+1}|\mathbf{w}_t]=\mathbf{w}_t+\alpha(\mathbf{b}-\mathbf{Aw}_t)

其中

\begin{cases} \mathbf{b}\doteq\mathbb{E}[R_{t+1}\mathbf{x}]\in \mathbb{R}^d\\ \mathbf{A}\doteq\mathbb{E}[\mathbf{x}_t(\mathbf{x}_t-\gamma\mathbf{x}_{t+1})^T]\in \mathbb{R}^d\times\mathbb{R}^d \end{cases}

当收敛时,有

\begin{aligned} &\mathbf{b}-\mathbf{Aw}_{TD}=\mathbf{0}\\ \Rightarrow&\mathbf{b}=\mathbf{Aw}_{TD}\\ \Rightarrow&\mathbf{w}_{TD}=\mathbf{A}^{-1}\mathbf{b} \end{aligned}

这个值称为『TD 不动点』,根据一些定理可以证明确实能够收敛于此点。线性半梯度 TD(0) 算法的收敛值就是这个不动点,他有一个性质:

\mathrm{MSVE}(\mathbf{w}_{TD})\leq\frac{1}{1-\gamma}\min_\mathbf{w}\mathrm{MSVE}(\mathbf{w})

即 TD(0) 法得到的误差不超过 MC 法的 \dfrac{1}{1-\gamma} 倍。

9.5 Feature Construction for Linear Methods

线性方法的局限在于,我们所考虑到的特征之间是彼此独立的,即没有考虑到两个特征间的联系。但对一些特征,需要考虑他们之间的联系,接下来讨论几种具体的方法。

9.5.1 Polynomials

一个例子,若直接用 \mathbf{x}(s)=(s_1,s_2)^T 表示状态特征,就不能体现这两个维度特征的交互,此时可以考虑 \mathbf{x}(s)=(1,s_1,s_2,s_1s_2)^T 则能够克服这一问题。

对于这种多项式形式的特征,更一般的构造方法是:

x_i(s)=\prod_{j=1}^ks_j^{c_{i,j}}

其中 c_{i,j}\in\{0,1,\ldots,n\}x_i(s) 构成向量 \mathbf{x}(s)

9.5.2 Fourier Basis

傅里叶方法考虑使用 \sin, \cos 函数来作为基函数,如果将 T 设为原来的两倍,便能在半周期 [0,\dfrac{T}{2}] 内,只用 \cos 或只用 \sin 作基函数,但 \sin 函数的线性组合往往是奇函数,容易在原点处不连续,所以一般考虑用 \cos 作为基函数。

适用傅里叶基来构造特征向量:

x_i(s)=\cos(\pi c^i\cdot s)

其中

c^i=(c_1^i, \cdots, c_k^i)^T , c_j^i \in \{0, \cdots, N\} , j = 1, \cdots, k , i = 0, \cdots ,(N+1)^k

效果:

9.5.3 Coarse Coding

下面讲一种特征编码方法——粗编码(Coarse Coding)。

状态 s 所在的圆的特征值记为 1 ,其他记为 0 ,这样便在各个圆上定义了一个 0-1 的二维特征,表示状态 s 是否处于这个圆中。称这样定义出来的特征编码为『粗编码(coarse coding)』。

在线性梯度下降逼近法中,每个圆对应的是会被影响到的参数(\mathbf{w} 中的一个分量),这样编码,便能优先更新与状态 s 相关性高(图中体现为几个相邻近的圆)的特征对应的参数。

这样的编码需要事先构造好这些圆,不同的形状大小也有着不同的泛化特性。

9.5.4 Tile Coding

上面的粗编码定义抽象,实际中很难在程序中定义出图中各个圆所描述出的位置和大小关系。一种解决方案就是使用形式简单的网格来对特征进行编码。

编码方式以下面一个示例为例:

事先定义好四个用于分割的 4\times 4 大方格(其实是由同一个大方格平移得到),每个大方格中白点所在的方格记为 1 ,其他记为 0(图例中具体而言,表示在总共有 64 个特征分量,只有 4 个分量记为 1 ,其他全为 0 ),这样便定义出了一种特征编码,称为『片编码(tile coding)』。

不同的平移方式能编出不同形式的编码,如下图所示

片编码的优势在于,因为使用对空间的划分作为网格,对每个状态 s 而言,其活跃的特征分量数是固定的(网格数决定),实际应用中便于实现。

不同的网格形状还能决定不同的泛化特点,表达出各种各样的特征。

9.5.5 Radial Basis Functions

径向基函数(RBF)』是对粗编码的一种拓展,相对于 0-1 特征,RBF 特征可以是 0 到 1 之间的任意数字。经典的 RBF 特征 x_i 作为一个高斯形式的反馈,只依赖状态 s 与设定的中心状态 c_i 间的距离,以及特征的相对宽度 \sigma_i

x_i(s)\doteq \exp\left(-\frac{||s-c_i||^2}{2\sigma_i^2}\right)

理论上使用 RBF 特征可以使近似函数更平滑,但实际上实用性较差。

9.6 Nonlinear Function Approximation: Artificial Neural Networks

参数 \mathbf{w} 也可使用人工神经网络(ANN)来训练。

这一节简单介绍了神经网络中的一些概念。

9.7 Least-Squares TD

9.4 节中讲过线性函数逼近的 TD(0) 算法

\mathbb{E}[\mathbf{w}_{t+1}|\mathbf{w}_t]=\mathbf{w}_t+\alpha(\mathbf{b}-\mathbf{Aw}_t)

会收敛于 TD 不动点 \mathbf{w}_{TD}=\mathbf{A}^{-1}\mathbf{b} ,其中

\begin{cases} \mathbf{b}\doteq\mathbb{E}[R_{t+1}\mathbf{x}]\in \mathbb{R}^d\\ \mathbf{A}\doteq\mathbb{E}[\mathbf{x}_t(\mathbf{x}_t-\gamma\mathbf{x}_{t+1})^T]\in \mathbb{R}^d\times\mathbb{R}^d \end{cases}

其实也可以不做迭代,而是每步都直接算出这个不动点,就是本节的 LSTD 算法:

w_{t+1}\doteq\widehat{\mathbf{A}}_t^{-1}\widehat{\mathbf{b}}_t

其中

\begin{cases} \widehat{\mathbf{b}}_t\doteq \sum_{k=0}^{t-1}R_{t+1}\mathbf{x}\\ \widehat{\mathbf{A}}_t\doteq\sum_{k=0}^{t-1}\mathbf{x}_t(\mathbf{x}_t-\gamma\mathbf{x}_{t+1})^T+\varepsilon\mathbf{I} \end{cases}

\varepsilon 为一个较小的正数,\varepsilon \mathbf{I} 确保 \widehat{\mathbf{A}} 可逆。

\widehat{\mathbf{A}}_t^{-1} 的计算可以写作增量式

\begin{aligned} \widehat{\mathbf{A}}_t^{-1}&=\left(\widehat{\mathbf{A}}_{t-1}+\mathbf{x}_t(\mathbf{x}_t-\gamma \mathbf{x}_{t+1})^T\right)^{-1}\\ &=\widehat{\mathbf{A}}_{t-1}^{-1}-\frac{\widehat{\mathbf{A}}_{t-1}^{-1}\mathbf{x}_t(\mathbf{x}_t-\gamma \mathbf{x}_{t+1})^T\widehat{\mathbf{A}}_{t-1}^{-1}}{1+\mathbf{x}_t(\mathbf{x}_t-\gamma \mathbf{x}_{t+1})^T\widehat{\mathbf{A}}_{t-1}^{-1}\mathbf{x}_t} \end{aligned}

此算法复杂度为 O(d^2) ,比直接做求逆运算(复杂度 O(d^3))要快。

LSTD 比普通的迭代法(复杂度 O(d))计算量更大,但是他的优势在于对数据的利用效率更高。

此外,LSTD 无需设置步长参数 \alpha ,取而代之地是只需设置一个较小的 \varepsilon 即可,省去了调参的环节。但是没有步长 \alpha 意味着这个算法缺乏『遗忘性』,很多时候强化学习方法都需要引入遗忘机制,因此 LSTD 一般都是与这类遗忘机制结合使用。

9.8 Memory based Function Approximation

这一节简单介绍基于记忆的非参数估计方法。将样本保存于内存中,当有查询需求的时候,取出一组样本用于计算状态的估计值,也称这种方法为 lazy learning 。

这一节主要关注 local-learning ,如

  • nearest neighbor :找到内存中和 s 最近的状态,然后直接将其值作为 s 的估计值。
  • weighted neighbor :将 s 周围的几个状态做加权平均后作为估计值。
  • locally weighted regression :利用距离定义一个加权意义下的误差(类似 9.1 式),然后根据这个误差做回归得到拟合曲面,在这个曲面上求值来作为 s 的估计值。

作为非参数方法,其优点有

  • 精确度随数据量提升而增加,无需担心收敛问题。
  • 能很自然地关注样本受邻近状态的影响,而无需像参数化方法做一些人工调整。
  • 能够解决『维度灾难』。这是因为他只需要正比于 n 的空间来存样本,但参数化方法则需要指数级的空间来存储参数,这在复杂的高维问题有着明显的差异。

9.9 Kernel-based Function Approximation

kernel regression 其实仍为 memory-based methods:

\hat{v}(s,D) = \sum_{s^\prime \in D} k(s,s^\prime)g(s^\prime)
  • D 表示保存的样本
  • g(s') 表示在保存样本中,s' 的 target

线性参数回归也可看作核方法,使用的是线性核函数:

k(s,s^\prime) = \mathbf{x}(s)^T\mathbf{x}(s^\prime)

核技巧:仅使用存储的训练数据,在高维特征空间中有效地工作。

9.10 Looking Deeper at On-policy Learning: Interest and Emphasis

前面讲的算法对于各状态都是同等重视程度,事实上有些状态应该更加重视,这里引入两个新概念:

  • interest I_t :表示在 t 时刻对当前状态的关注程度,如果希望这次估值能够更准确,则 I_t 应尽量为 1,否则若不关注,则应接近 0 。而前面提到过的分布 \mu 就可以利用 I_t 来对样本加权后求得。
  • emphasis M_tM_t 用于强化或弱化这一次的学习。

下面是一个例子:

\mathbf{w}_{t+n} \doteq \mathbf{w}_{t+n-1}+\alpha M_t[G_{t:t+n}-\hat{v}(S-t,\mathbf{w}_{t+n-1})]\nabla \hat v(S_t, \mathbf{w}_{t+n-1})

其中

M_t = I_t+\gamma^n M_{t-n}, \qquad 0 \leq t < T