强化学习笔记(五)- 函数近似方法

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言,谢谢

引言

  对于有模型的数值迭代算法,无模型的回合更新算法和时序差分更新算法,在每次更新价值函数时都只更新某个状态或状态动作对下的价值估计,这就带来一个问题,如果状态数和动作数巨大的话,甚至无穷大,是不可能做到对这些状态和动作逐一更新的。于是函数近似算法用参数化的模型来近似整个状态价值函数或者动作价值函数,在每次学习时更新函数。

随机梯度下降(Stochastic-Gradient Descent, SGD )

  我们列出梯度下降的公式:

  这里随机梯度下降中“随机”的含义是我们的更新总是基于单个的样本,或者批样本,而这些样本都是随机选择的。
  上式其实有一个问题,那就是很多时候更新的目标 \(v_{\pi}(S_{t})\) 是未知的,更一般的情况是我们用一个近似的值 \(U_t\) 来表示更新目标,它可能是含有噪音的,或者是通过自举得到的 \(v_{\pi}(S_{t})\) 的一个近似值,在这种情况下,表达式就变成了:

\[ \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\left[U_{t}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\tag{2} \]

  如果 \(U_t\) 是无偏的,即 \(\mathbb{E}\left[U_{t} | S_{t}=s\right]=v_{\pi}\left(S_{t}\right)\),那么 \(\mathbf{w}_{t}\) 可以保证收敛到局部最优。
  用MC估计的值函数 \(G_t\) 是无偏的,因此我们就可以得到一个基于 MC 的值预测方法,叫做梯度 MC 算法,SGD 方法还是非常简单容易理解的,它的伪代码如下:

  算法过程很简单,就是根据 MC 方法得到的期望回报 \(G_t\),然后来拟合一个函数 \(\hat{v}\),使得他在每个状态的值都接近 \(G_t\),不断的仿真轨迹,计算 \(G_t\),然后执行随机梯度下降。

半梯度下降(Semi-Gradient Descent)

  但通常来说都是有偏的估计,也就是说如果 \(U_t\) 是通过自举得到的估计,比如 \(n\) 步时序差分的回报 \(G_{t:t+n}\) ,或者是DP目标 \(\sum_{a, s^{\prime}, r} \pi\left(a | S_{t}\right) p\left(s^{\prime}, r | S_{t}, a\right)\left[r+\gamma \hat{v}\left(s^{\prime}, \mathbf{w}_{t}\right)\right]\) 。这些目标是依赖于当前的权重值,既然当前权重值不是最优的,那必然得到的目标也是有偏的。
  除此之外,另外一种看待这个问题的思路是,从表达式 \((1)\) 的求导过程中,如果想要结论成立,那么目标 \(U_t\) 必须是独立于 \(\mathbf{w}_{t}\) 的。但是对于自益的目标,目标也是 \(\mathbf{w}_{t}\) 的函数。这种情况下 \((2)\) 就不再是一个真正的梯度下降。因为它考虑了 \(\mathbf{w}_{t}\) 对于估计 \(\hat{v}\) 的影响,却没有考虑它对于 \(U_{t}\) 的影响。结果就是只考虑了部分的梯度,因此我们称这样的方法为半梯度方法(semi-gradient methods)。它的伪代码如下:

  尽管半梯度方法在收敛特性上没有梯度方法鲁棒,但是对于近似器为线性的情况,这种收敛是有保证的。另外的话,由于采用了自益,就使得半梯度方法能够在线、更快的学习,这带来了很多计算优势。
  半梯度下降的 SARSA 算法:

  半梯度下降的 \(n\) 阶 SARSA 算法:

线性方法

  线性近似还是很容易理解的,以状态价值近似为例,我们可以为每个状态定义多个不同的特征,进而定义近似函数为这些特征的线性组合,即:

\[ \hat{v}(s, \mathbf{w}) \doteq \mathbf{w}^{\top} \mathbf{x}(s) \doteq \sum_{i=1}^{d} w_{i} x_{i}(s) \]

  我们拿时序差分过程来说,阐述一下它的求导过程,对于状态价值函数求导:

\[ \nabla \hat{v}(s, \mathbf{w})=\mathbf{x}(s) \]

  利用 SGD 可得:

\[ \mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\left[U_{t}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right] \mathbf{x}\left(S_{t}\right) \]

  简记 \(\mathbf{x}_t = \mathbf{x}(S_t)\),把 \(U_t\) 通过单步时序差分展开可得:

\[ \begin{aligned} \mathbf{w}_{t+1} & \doteq \mathbf{w}_{t}+\alpha\left(R_{t+1}+\gamma \mathbf{w}_{t}^{\top} \mathbf{x}_{t+1}-\mathbf{w}_{t}^{\top} \mathbf{x}_{t}\right) \mathbf{x}_{t} \\ &=\mathbf{w}_{t}+\alpha\left(R_{t+1} \mathbf{x}_{t}-\mathbf{x}_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right)^{\top} \mathbf{w}_{t}\right) \end{aligned}\]

  当系统达到稳态时,对于每个 \(\mathbf{w}_{t}\),对于下一个 \(\mathbf{w}_{t+1}\) 的期望可以写成:

\[ \mathbb{E}\left[\mathbf{w}_{t+1} | \mathbf{w}_{t}\right]=\mathbf{w}_{t}+\alpha\left(\mathbf{b}-\mathbf{A} \mathbf{w}_{t}\right) \\ \mathbf{b} \doteq \mathbb{E}\left[R_{t+1} \mathbf{x}_{t}\right] \in \mathbb{R}^{d} \quad \\ \quad \mathbf{A} \doteq \mathbb{E}\left[\mathbf{x}_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right)^{\top}\right] \in \mathbb{R}^{d} \times \mathbb{R}^{d} \]

  所以要想达到收敛的话,\(\mathbf{w}_{t}\)\(\mathbf{w}_{t+1}\) 要相等,即:

\[ \begin{aligned} \mathbf{b}-\mathbf{A} \mathbf{w}_{\mathrm{TD}} &=\mathbf{0} \\ \mathbf{b} &=\mathbf{A} \mathbf{w}_{\mathrm{TD}} \\ \mathbf{w}_{\mathrm{TD}} & \doteq \mathbf{A}^{-1} \mathbf{b} \end{aligned} \]

线性最小二乘时序差分更新(Least-Squares TD, LSTD)

  如果我们不想通过迭代求解,也可以直接求解,就是通过最小二乘法,我们还是拿时序差分举例子:

\[ \mathbf{w}_t = \widehat{\mathbf{A}}_{t}^{-1} \widehat{\mathbf{b}}_{t}\\ \widehat{\mathbf{A}}_{t} \doteq \sum_{k=0}^{t-1} \mathbf{x}_{k}\left(\mathbf{x}_{k}-\gamma \mathbf{x}_{k+1}\right)^{\top}+\varepsilon \mathbf{I} \quad \\ \quad \widehat{\mathbf{b}}_{t} \doteq \sum_{k=0}^{t-1} R_{k+1} \mathbf{x}_{k} \]

  其中 \(\varepsilon \mathbf{I}\) 保证了 \(\widehat{\mathbf{A}}_{t}\) 的可逆性,进一步得到 \(\widehat{\mathbf{A}}_{t}^{-1}\)\(\widehat{\mathbf{A}}_{t-1}^{-1}\) 的关系:

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

  LSTD 的伪代码为:

DQN

  深度 Q 学习将深度学习与强化学习相结合,核心就是用一个人工神经网络 \(q(s,a,w)\) 来代替动作价值函数。
  当同时出现异策,自益和函数近似时,无法保证收敛性,会出现训练不稳定或训练困难的问题,针对这些问题,研究者提出了经验回放和目标网络这两种改进。

经验回放(experience repaly)

  经验回放指的就是将经验(历史状态,动作,奖励等)存储起来,再在存储的经验中按一定的规则采样,它可以让经验分布变得更加稳定,提高训练的稳定性。它主要有两个好处:

  • 在训练 Q 网络时,可以消除数据的关联,使得数据更像是独立同分布的,这样可以减少参数更新的方差,更快的收敛。
  • 能够重复使用经验

  它主要包括两个步骤,存储和采样回放,前者是存储轨迹 \((S_t,A_t,S_{t+1},A_{t+1})\),后者是使用某种规则从存储的 \((S_t,A_t,S_{t+1},A_{t+1})\) 中随机取出一条或多条经验。
  从存储的角度可以分为:

  • 集中式回放:agent 在一个环境中运行,把经验统一存储在经验池中
  • 分布式回放:agent 的多份拷贝同时在多个环境中运行,并将经验统一存储在经验池中

  从采样的角度,又可以分为:

  • 均匀回放:等概率从经验集中取经验,并且用取得的经验来更新最优价值函数
  • 优先回放(Prioritized Experience Replay, PER):为经验池里的每个经验指定一个优先级,采样时倾向于选择优先级高的经验,优先级可以通过成比例优先(proportional priority)\(p_i = (\delta_i + \epsilon)^\alpha\) 和基于排序优先(rank-based priority) \(p_i = (\frac{1}{rank_i})^\alpha\) 等方法计算。

  伪代码如下:

目标网络(target network)

  对于自益的 Q 学习,其回报的估计和动作价值都和权重有关,当权重变化时,回报的估计和动作价值都会变化。在学习的过程中,动作价值试图追逐一个变化的回报,也容易出现不稳定。
  目标网络可以解决这个问题,目标网络是在原有的神经网络之外再搭建一份结构完全相同的网络,原有的网络称为评估网络(evaluation network),在学习的过程中,使用目标网络来进行自益得到回报的评估值,作为学习的目标。在权重更新的过程,只更新评估网络的权重,而不是更新目标网络的权重。这样更新权重时针对的目标不会在每次迭代都变化,是一个固定的目标。再完成一定次数的更新后,再将评估网络的权重值付给目标网络,进而进行下一批更新,这样目标网络也能得到更新,更新目标网络的权重时,我们也可以引入学习率采取一个加权平均的做法 \(\mathbf{w}_{target} \leftarrow (1-\alpha_{target})\mathbf{w}_{target} + \alpha_{target}\mathbf{w}\)

Double DQN

  之前说过 Q-learning 会带来最大化偏差,DQN 同样也有这个问题,Double DQN 可以缓解这个问题,每次更新动作价值时用其中一个网络确定动作,用确定的动作和另一个网络来估计回报。
  伪代码如下:

Dueling DQN

  对偶网络定义了一个新的函数,优势函数(Advantage Function),它是动作价值函数和状态价值函数之差:

\[ a(s,a) = q(s,a) -v(s) \]

  它仍然使用 \(q(\mathbf{w})\) 值来估计动作价值,只不过此时 \(q(\mathbf{w})\) 值是状态价值估计和优势函数估计的和:

\[ q(s,a;\mathbf{w}) = v(s;\mathbf{w}) + a(s,a;\mathbf{w}) \]

  同一个 \(q(\mathbf{w})\) 值可能存在无穷多种分解为 \(v(\mathbf{w})\)\(a(\mathbf{w})\),例如一个 \(q(s,a;\mathbf{w})\) 可以分解成某个 \(v(s;\mathbf{w})\)\(a(s,a;\mathbf{w})\),也可以分解成 \(v(s;\mathbf{w}) + a(s,a;\mathbf{w}) - c(s)\)\(c(s)\) 是任意一个只和状态 \(s\) 有关的函数。我们可以通过增加一个优势函数导出的量,使得等效的优势函数满足固定的特征,使得分解唯一,常用两种方法:

  • 优势函数的最大值,令 \(q(s,a;\mathbf{w}) = v(s;\mathbf{w}) + a(s,a;\mathbf{w}) - \max_{a \in A} a(s,a;\mathbf{w})\),使得等效优势函数 \(a^{\prime}(s,a;\mathbf{w}) =a(s,a;\mathbf{w})- \max_{a \in A} a(s,a;\mathbf{w})\) 满足 \(\max_{a \in A} a^{\prime}(s,a;\mathbf{w}) = 0\)
  • 优势函数的平均值,令 \(q(s,a;\mathbf{w}) = v(s;\mathbf{w}) + a(s,a;\mathbf{w}) - \frac{1}{\mathbf{|A|}}\sum_{a \in A} a(s,a;\mathbf{w})\) 使得等效优势函数 \(a^{\prime}(s,a;\mathbf{w}) = a(s,a;\mathbf{w}) - \frac{1}{\mathbf{|A|}}\sum_{a \in A} a(s,a;\mathbf{w})\) 满足 \(\sum_{a \in A} a^{\prime}(s,a;\mathbf{w}) = 0\)

  那么为什么要提出优势函数呢,论文给出的解释是在游戏中,存在很多状态,不管你采用什么样的动作,对下一步的状态转变是没什么影响的。这些情况下计算动作的价值函数的意义没有状态函数的价值意义大。例如状态很好,状态价值很大,那么不管动作好坏,对于 Q 值的影响不是特别大。所以这个时候,为了制定策略,最好是把动作的作用给提取出来,去除状态对于决策的影响。这个也是可以看做是减去了 baseline,减少了训练模型的方差,使模型的泛化性能更好,更加稳定。提取出了优势函数之后,对于动作之间的即使细微的差别也更容易发现,并且通过对偶这种方法,从实验中可以发现,它可以使得网络更快收敛。

总结

  本文主要记录了函数近似的一些方法,基于回报的随机梯度下降,基于自益目标的半梯度下降,还有函数近似的两种主要方法,线性近似和人工神经网络,前者主要利用了最小二乘法,后者主要是 DQN,包括 nature DQN,Double DQN 和 Dueling DQN,还有采样回放和目标网络一些概念。

Refer

相关内容


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 随机梯度下降(Stochastic-Gradient Descent, SGD )
  3. 3. 半梯度下降(Semi-Gradient Descent)
  4. 4. 线性方法
    1. 4.1. 线性最小二乘时序差分更新(Least-Squares TD, LSTD)
  5. 5. DQN
    1. 5.1. 经验回放(experience repaly)
    2. 5.2. 目标网络(target network)
    3. 5.3. Double DQN
    4. 5.4. Dueling DQN
  6. 6. 总结
  7. 7. Refer
  8. 8. 相关内容
您是第 位小伙伴 | 本站总访问量 | 已经写了 670.5k 字啦

载入天数...载入时分秒...