David Silver 强化学习 第六讲

价值函数的近似表示

Posted by Pelhans on January 19, 2018

前五讲主要是强化学习的理论内容,往往不能很好的解决实际问题.因此本讲及后三讲都是讲解实践中的强化学习.

简介

总结自叶强的David Silver强化学习公开课中文讲解及实践专栏

在实际应用中,对于状态和行为空间巨大的情况下,我们很难精确的获得v(S)和q(s, a).因此我们不得不寻找近似函数,具体来说可以使用线性组合,神经网络以及其他方法来近似价值函数:

\[v(S) \approx v(S, w)\]

w表示引入的参数.通过函数近似的方式,我们可以直接拟合各种价值函数,本课程讲近似方法分为两大类:递增方法(即时更新)和批方法(收集一批数据后更新).两类方法没明显界限,相互借鉴.到目前为止,在理论中我们使用的都是Table Lookup的方式,即每一个状态或者状态行为对对应一个价值函数.对于实际问题来讲,状态空间太大的话这就不现实了.因此对于大规模问题,我们采用如下思路:

1) 通过函数近似来估计实际的价值函数:

\[v_{*}(s, w) \approx v_{\pi}(s)\] \[q_{*}(s, a ,w) \approx q_{\pi}(s, a)\]

2) 把从已知的状态学习到的函数通用化推广至那些未碰到的状态中.

3) 使用MC或TD学习来更新函数参数.

对于近似函数的选择往往需要考虑针对状态可导和收敛的一些性质.最终我们需要一个适用于非静态,满足i.i.d的数据的训练方法得到近似函数.

递增方法 (Incremental Methods)

线性函数近似-特征向量(Linear Function Approximation - Feature Vectors)

用一个特征向量表示一个状态,每一个状态是由以w表示的不同强度的特征来线性组合得到:

\[x(S) = \left( \begin{aligned} x_{1}(S) & \\ \vdots & \\ x_{1}(S) \end{aligned} \right)\]

若采用线性函数近似价值函数的话,则:

\[v^{*}(S,\textbf{w}) = \textbf{x}(S)^{T}\textbf{w} = \sum\limits_{j=1}^{n}\textbf{x}_{j}(S)\textbf{w}_{j}\]

因此目标函数就可以表示为:

\[J(\textbf{w}) = E_{\pi}[(v_{\pi}(S) - \textbf{x}(S)^{T}\textbf{w})^{2}]\]

对应的参数更新规则为:

\[\nabla_{w}v^{*}(S, \textbf{w}) = \textbf{w}(S)\] \[\triangle\textbf{w} = \alpha(v_{\pi}(S) - v^{*}(S, w))\textbf{x}(S)\]

这样就可以像常见的机器学习算法一样用梯度下降就可以收敛到全局最优解了.

递增-预测算法(Incremental Prediction Algorithms)

上面公式虽然看起来合理,但别忘了是在强化学习中使用,和带标签的监督学习不同,此时我们没有监督学习,因此上式还不能直接使用.那怎么办呢?假如能找到能替代\(v_{\pi}(S)\)的目标值就好了.

对于MC算法,目标值就是收获:

\[\triangle\textbf{w} = \alpha(G_{t} - v^{*}(S_{t}, \textbf{w}))\nabla_{w}v^{*}(S_{t}, \textbf{w})\]

对于TD(0),目标值就是TD目标:

\[\triangle\textbf{w} = \alpha(R_{t+1} + \gamma v^{*}(S_{t+1}, \textbf{w}) - v^{*}(S_{t}, \textbf{w}))\nabla_{w}v^{*}(S_{t}, \textbf{w})\]

对于TD(\(\lambda\)),目标值就是\(\lambda\)收获:

\[\triangle\textbf{w} = \alpha(G_{t}^{\lambda} - v^{*}(S_{t+1}, \textbf{w}))\nabla_{w}v^{*}(S_{t},\textbf{w})\]

MC应用于状态价值函数近似

前面学过,MC的收获\(G_{t}\)是对真实价值\(V_{\pi}(S_{t})\)的有噪声无偏采样.此时的训练数据集可以是:

\[<S_{1}, G_{1}>, <S_{2}, G_{2}> , \ldots, <S_{T}, G_{T}>\]

如果使用线性蒙特卡洛策略迭代,用\(G_{t}\)作为标签数据的话,那么每次参数的修正值则为:

\[\triangle\textbf{w} = \alpha(G_{t} - v^{*}(S_{t}, \textbf{w}))\textbf{x}(S_{t})\]

蒙特卡洛策略迭代即使使用线性函数近似时也是收敛到一个局部最优解.

TD应用于状态价值函数近似

TD目标值是真实价值的有噪声、有偏采样。此时的训练数据集是:

\[<S_{1}, R_{2}+\gamma v^{*}(S_{2},\textbf{w})>,<S_{2}, R_{3}+\gamma v^{*}(S_{3},\textbf{w})>, \ldots,<S_{T-1}, R_{T}>\]

若使用线性TD(0)学习,则讲数据集带入梯度更新公式由:

\[\nabla\textbf{w} = \alpha\delta\textbf{w} (S)\]

线性TD(0)近似收敛至全局最优解。

TD(λ)应用于状态价值函数近似

TD(λ)目标值是真实价值的有噪声、有偏采样。此时的训练数据集是:

\[<S_{1}, G_{1}^{\lambda}>, <S_{2}, G_{2}^{\lambda}>, \ldots, <S_{T-1}, G_{T-1}^{\lambda}>\]

如果使用线性TD(λ)学习,从反向认识看,有:

\[\delta_{t} = R_{t+1} + \gamma v^{*}(S_{t+1}, \textbf{w}) - v^{*}(S_{t}, w)\] \[E_{t} = \gamma\lambda E_{t-1} + \textbf{x}(S_{t})\] \[\triangle\textbf{w} = \alpha\delta_{t}E_{t}\]

对于一个完整的Episode,TD(λ)的前向认识和反向认识对于w的改变是等效的。线性TD(0)近似收敛至全局最优解。

递增-控制算法(Incremental Control Algorithms)

对于控制问题,我们需要能够近似状态行为对的价值函数而不是单针对状态的近似。此时的策略评估也是近似的:

\[q^{*}(S, A, \textbf{w}) \approx q_{\pi}(S, A)\]

而策略的改善则使用\(\epsilon -greedy\)执行。需要注意的是改进死无法最终收敛于最优策略对应的价值函数。

有了行为价值函数近似表示后,采用最小均方差为损失评估:

\[J(\textbf{w}) = E_{\pi}[(q_{\pi}(S, A) - q^{*}(S, A, \textbf{w}))^{2}]\]

若使用随机梯度下降来寻找局部最优解的话,则参数更新公式为:

\[\triangle \textbf{w} = \alpha(q_{\pi}(S, A) - q^{*}(S, A, \textbf{w}))\nabla_{\textbf{w}}q^{*}(S, A, \textbf{w})\]

当使用线性函数近似状态行为价值函数时,线性特征组合的状态行为价值近似函数可以表示为:

\[q^{*}(S, A, \textbf{w}) = \textbf{w}(S, A)^{T}\textbf{w} = \sum\limits_{j=1}^{n}\textbf{x}_{j}(S, A)\textbf{w}_{j}\]

随机梯度下降的参数更新是:

\[\triangle\textbf{w} = \alpha(q_{\pi}(S, A) - q^{*}(S, A, \textbf{w}))\textbf{x}(S, A)\]

类似于预测部分,对于线性控制算法,我们找到真实行为价值的目标值。

对于MC算法,目标值就是收获:

\[\triangle\textbf{w} = \alpha(G_{t} - q^{*}(S_{t}, A_{t}, \textbf{w}))\nabla_{\textbf{w}}q^{*}(S_{t}, A_{t}, \textbf{w})\]

对于TD(0),目标值就是TD目标:

\[\triangle\textbf{w} = \alpha(R_{t+1} + \gamma q^{*}(S_{t+1}, A_{t+1}. \textbf{w}) - q^{*}(S_{t}, A_{t},\textbf{w}))\nabla_{\textbf{w}}q^{*}(S_{t}, A_{t}, \textbf{w})\]

对于后向认识TD(λ),对应的参数更新是:

\[\delta_{t} = R_{t+1} + \gamma q^{*}(S_{t+1}, A_{t+1}, \textbf{w}) - q^{*}(S_{t}, A_{t}, \textbf{w})\] \[E_{t} = \gamma \lambda E_{t-1} + \nabla_{\textbf{w}}q^{*}(S_{t}, A_{t}, \textbf{w})\] \[\triangle\textbf{w} = \alpha\delta_{t}E_{t}\]

收敛性

下图给出预测学习算法的收敛性总结,:

下图给出的是针对控制学习算法的收敛性总结:

批方法(Batch Methods)

批方法是把一段时间的数据集中起来,通过学习使得数能较好地符合这段时期内所有的数据。这里的训练数据集“块”相当于个体的一段经验。具体流程为:

假设存在一个价值函数的近似:

\[v^{*} \approx_{\pi}(s)\]

在一段时期内的经历D:

\[D = {<s_{1}, v_{1}^{\pi}>, <s_{2}, v_{2}^{\pi}>, \ldots , <s_{T}, v_{T}^{\pi}>}\]

若采用最小平方差损失:

\[J(\textbf{w}) = \sum\limits_{t=1}^{T}(v_{t}^{\pi} - v^{*}(s_{t}, \textbf{w}))^{2} = E_{D}[(v^{\pi} - v^{*}(s, \textbf{w}))^{2}]\]

DQN

先前说过TD方法结合非线性的神经网络函数近似可能不会收敛,但DQN(Deep Q-Networks) 使用 经历重现和固定的Q目标值 能做到收敛而且保持很好的鲁棒性。在解释其收敛之前先要介绍DQN算法的要点:

  1. 依据Ɛ-greedy执行策略产生t时刻的行为;

  2. 将大量经历数据(例如百万级的)以 \((s_{t}, a_{t}, r_{t+1}, s_{t+1})\) 存储在内存里,作为D大块;

  3. 从D大块中随机抽取小块(例如64个样本数据)数据 (s, a, r, s’);

  4. 维护两个神经网络DQN1,DQN2,一个网络固定参数专门用来产生目标值,目标值相当于标签数据。另一个网络专门用来评估策略,更新参数。

  5. 优化关于Q网络和Q目标值之间的最小平方差,其中\(w^{fix}\)是批学习过程中固定的参数,\(w_{i}\)则是动态更新的参数: \(L_{i}(w_{i}) = E_{s,a,r,s'\~ D}[(r+ \gamma \max\limits_{a'}Q(s',a',w_{i}^{fix}) - Q(s, a_{i}, w_{i}))^{2}]\)

  6. 用随机梯度下降的方式更新参数。

首先,随机采样打破了状态之间的联系;第二个神经网络会暂时冻结参数,我们从冻结参数的网络而不是从正在更新参数的网络中获取目标值,这样增加了算法的稳定性。经过一次批计算后,把冻结参数的网络换成更新的参数再次冻结产生新一次迭代时要用的目标值。

下图给出分别移除DQN各个部件的表现对比:

可以看出,批方法对结果的影响较大,参数固定的影响相对小一点。