理解策略梯度算法

DQN存在的问题

在之前的文章“深度强化学习综述(上)”中介绍了深度强化学习的原理,重点是DQN(深度Q网络)。基于值函数的算法是神经网络与时序差分算法如Q学习相结合的产品。其原理非常简单,神经网络的输入是原始的状态信息,如游戏画面,输出是在这种状态下执行各种动作的回报,即价值函数(Q函数)。训练完成之后,神经网络逼近的是最优Q函数

其中s为状态,a为动作。运行时选择在这种状态下最优的动作执行,即Q函数值最大的动作。这种方法的原理如下图所示。

训练时采用了Q学习的思路,用神经网络拟合Q学习中的误差项,使其最小化

其中θ为神经网络的参数。

DQN虽然在某些问题上取得了成功,但存在以下问题:

1. 无法表示随机策略,某些问题的最优策略是随机策略,需要以不同的概率选择不同的动作。而DQN之类的算法在实现时采用了贪心策略,显然无法实现这种按照概率执行各种候选动作的要求。

2.这种方法输出值(各个动作的最优Q函数值)的微小改变会导致某一动作被选中或不选中,这种不连续的变化会影响算法的收敛。这很容易理解,假设一个动作a的Q函数值本来在所有动作中是第2大的,把它增加0.0001,就变成第最大的,那这种微小的变化会导致策略完全改变。因为之前它不是最优动作,现在变成最优动作了。

3.无法表示连续动作。DQN要求动作空间是离散的,且只能是有限个。某些问题中,动作是连续的,例如要控制在x y z方向的速度、加速度,这些值显然是连续的。

策略梯度算法的基本思想

相比之下,策略梯度算法是一种更为直接的方法,它让神经网络直接输出策略函数π(s),即在状态s下应该执行何种动作。对于非确定性策略,输出的是这种状态下执行各种动作的概率值,即如下的条件概率

所谓确定性策略,是只在某种状态下要执行的动作是确定即唯一的,而非确定性动作在每种状态下要执行的动作是随机的,可以按照一定的概率值进行选择。这种做法的原理如下图所示。

此时的神经网络输出层的作用类似于多分类问题的softmax回归,输出的是一个概率分布,只不过这里的概率分布不是用来进行分类,而是执行动作。至于对于连续型的动作空间该怎么处理,我们在后面会解释。

因此,如果构造出了一个目标函数L,其输入是神经网络输出的策略函数

,通过优化此目标函数,即可确定神经网络的参数θ,从而确定策略函数

。这可以通过梯度上升法实现(与梯度下降法相反,向着梯度方向迭代,用于求函数的极大值)。训练时的迭代公式为

这里假设策略函数对参数的梯度

存在,从而保证

。现在问题的核心就是如何构造这种目标函数L,以及如何生成训练样本。对于后者,采用了与DQN类似的思路,即按照当前策略随机地执行动作,并观察其回报值,以生成样本。

对于第一个问题,一个自然的想法是使得按照这种策略执行时的累计回报最大化,即构造出类似V函数和Q函数这样的函数来。下面介绍常用的目标函数。

目标函数的构造

第一种称为平均奖励(average reward)目标函数,用于没有结束状态和起始状态的问题。它定义为各个时刻回报值的均值,是按照策略π执行,时间长度n趋向于+∞时回报均值的极限

其中

为立即回报值,

是状态s的平稳分布,定义为按照策略π执行时该状态出现的概率,

则为在状态s下执行各种动作时得到的立即回报的均值,

为在状态s下执行动作a所得到的立即回报的数学期望

平稳分布是如下的极限

其意义为按照策略π执行,当时间t趋向于+∞时状态s出现的概率。这是随机过程中的一个概念,对于马尔可夫链,如果满足一定的条件,则无论起始状态的概率分布(即处于每种状态的概率)是怎样的,按照状态转移概率进行演化,系统最后会到达平稳分布,在这种情况下,系统处于每种状态的概率是稳定的。接下来定义这种目标函数所对应的价值函数

它是按照策略π执行,在状态s下执行动作a,各个时刻立即回报数学期望的累加值。此函数将用于策略梯度定理的推导。

第二种称为起始状态(start state)形式的目标函数,用于有起始状态和终止状态的问题。定义为从起始状态

开始,执行策略π所得到的累计回报的数学期望

这里使用了折扣因子

。类似的定义这种目标函数所对应的价值函数

此时状态的平稳分布定义为

在确定目标函数之后,问题的关键是如何计算函数对策略参数θ的梯度值。你可能会问:这里有多种形式的目标函数,我们要分别推导它们对策略参数θ的梯度值,然后用梯度上升法更新参数的值。幸运的是,无论哪种形式的目标函数,其对策略参数的梯度值在形式上都是一致的!因此你的担心是多余的。这由策略梯度定理保证。

策略梯度定理

策略梯度定理(policy gradient theorem)指出,无论是平均奖励还是起始状态形式的目标函数,对任意的马尔可夫决策过程,目标函数对策略参数的梯度均为如下形式

根据此定理,目标函数对策略参数θ的梯度可根据策略函数对其参数的的梯度

计算,而不涉及状态概率对策略参数的梯度

。这极大地简化了问题计算的难度。

下面给出策略梯度定理的证明。首先考虑average-reward形式的目标函数,对于

,根据状态价值函数的定义有

上式第2步使用了乘法的求导公式,第3步对

函数进行了一次展开,第4步中

与θ无关,是常数。由于

,即任意状态下执行各种动作的概率之和为1。因此有

从而可以得到

上式两端同乘以

然后对s求和,可以得到

由于

是平稳分布,因此有

由于

,另外上式右端的最后两项抵消。从而可以得到

接下来考虑 start-state形式的目标函数。对于

,根据定义有

上式第2步使用了乘法求导公式,第3步对

函数进行了一步展开。递归地使用上式最后一行的结果,将

展开,可以得到

其中

为按照策略π执行,从状态s经过k步之后进入状态的概率。因此有

上式最后一步利用了

的定义。

一种实现-REINFORCE算法

根据策略梯度定理,目标函数对策略参数的梯度值正比于策略函数梯度的加权和,权重为按照该策略执行时状态的概率分布,因此按照该策略执行时,各状态出现的次数正比于此概率值。替换掉策略梯度计算公式中对s的求和,目标函数的梯度可以写成对概率p(s)的数学期望

因此可以用蒙特卡洛算法近似计算该期望值。接下来用相同的方式替换掉对a的求和。

其中

为单步的回报值。上式第3步成立是因为

。由此可以得到梯度下降的迭代公式

基于此式可以得到REINFORCE算法。该算法每次迭代时先用已经得到的策略执行动作,得到一个片段,然后根据此片段在每个时刻的回报值计算策略参数的梯度值,然后用梯度下降法进行更新。REINFORCE算法流程如下。

为了加快REINFORCE算法的收敛速度,减小偏差,可以在每次迭代时将回报值R减掉一个基准线值b,由此得到带基准线的REINFORCE算法。

对连续动作空间的处理

对于离散型动作空间,神经网络拟合的是一个离散型分布-多项分布,即执行每种动作的概率。下面介绍对连续型动作空的处理。对于连续型动作空间,神经网络拟合的是概率密度函数,假设动作值服从某种概率分布。更具体的,拟合的是概率密度函数的参数。如果连续型动作服从正态分布,则拟合的是其均值与方差。策略函数为

执行策略时,从该正态分布采样出动作值a然后执行。即按照此正态分布生成一个随机数,然后以该随机数的值作为动作去执行,例如作为速度,按照该速度去行驶。策略的参数为

这称为高斯策略。

关于强化学习,深度强化学习的系统性介绍可以阅读《机器学习-原理、算法与应用》,清华大学出版社,雷明著。

参考文献

[1] Richard S Sutton, David A Mcallester, Satinder P Singh, Yishay Mansour. Policy Gradient methods for reinforcement learning with function approximation. neural information processing systems, 2000.

[2] Mnih, Volodymyr, et al. Human-level control through deep reinforcement learning. Nature. 518 (7540): 529-533, 2015.

[3] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou. Playing Atari with Deep Reinforcement Learning. NIPS 2013.

本文分享自微信公众号 - SIGAI(SIGAICN),作者:技术文章

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深度策略梯度算法是真正的策略梯度算法吗?

    深度强化学习是现代机器学习最为人所知的成就,它造就了 AlphaGO 这样广为人知的应用。对很多人来说,该框架展示了机器学习对现实世界的影响力。但是,不像当前的...

    机器之心
  • Policy Gradient - 策略梯度

    在一个包含Actor、Env、Reward Function的强化学习的情景中,Env和Reward Function是你所不能控制的。

    Steve Wang
  • 理解梯度提升算法1-梯度提升算法

    《机器学习与应用》由清华大学出版社出版,是机器学习和深度学习领域又一高质量的入门与提高教材。该书系统、深入地讲述了机器学习与深度学习的主要方法与理论,并紧密结合...

    SIGAI学习与实践平台
  • 「糟糕」的策略梯度

    AI 科技评论按:强化学习(reinforcement learning)是机器学习界近几年的一大研究热点,无需先验知识、在环境中反复摸索尝试获得高反馈(rew...

    AI科技评论
  • 策略梯度入门(上)

    强化学习是机器学习中的一个子领域,其目标是为「代理」(agent)找到一个最优的行为策略以获得最大的奖励。「策略梯度」(policy gradient)是一类解...

    口仆
  • 深度确定性策略梯度DDPG详解

    1.前言2.算法2.1 概念初识2.2 算法相关概念和定义2.2 DDPG实现框架和算法

    CristianoC
  • 增强式学习核心算法:基于策略的梯度下降法

    我们要打造一个Agent,也就是智能机器人,它运作在一个给定环境中。它每次与环境互动时都有给定种选择,同时它可以获得当前环境的状态,Agent如果在有限种选择...

    望月从良
  • PARL源码走读:使用策略梯度算法求解迷宫寻宝问题

    作为一个强化学习小白,本人怀着学习的心态,安装并运行了PARL里的quick-start。不体验不知道,一体验吓一跳,不愧是NeurIPS 2018 冠军团队的...

    大数据文摘
  • PARL源码走读——使用策略梯度算法求解迷宫寻宝问题

    作为一个强化学习小白,本人怀着学习的心态,安装并运行了PARL里的quick-start。不体验不知道,一体验吓一跳,不愧是 NeurIPS 2018 冠军团队...

    用户1386409

扫码关注云+社区

领取腾讯云代金券