首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >理解策略梯度算法

理解策略梯度算法

作者头像
SIGAI学习与实践平台
发布2019-11-28 23:44:43
1K0
发布2019-11-28 23:44:43
举报

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.

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-11-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 SIGAI 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • DQN存在的问题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档