理解策略梯度算法

基于值函数的算法是神经网络与时序差分算法如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然后执行。即按照此正态分布生成一个随机数，然后以该随机数的值作为动作去执行，例如作为速度，按照该速度去行驶。策略的参数为

这称为高斯策略。