2.3 策略搜索算法
策略搜索算法（Policy Search）广泛用于解决具有连续状态、动作空间的复杂决策强化学习任务，特别是大规模环境中具有连续状态及动作空间的决策控制问题[16]。在解决强化学习问题时，策略搜索是将策略参数化，利用参数化的线性函数或者非线性函数表示策略，寻找最优的策略参数，使得强化学习的目标，即回报的期望最大。
本节我们将对策略搜索进行建模，介绍经典的策略搜索算法，如传统策略梯度算法[17]，自然策略梯度方法[18]以及期望最大化（Expectation Maximization，EM）的策略搜索方法[19]，综述深度强化学习领域中关于策略搜索算法的研究进展，最后总结基于值函数的策略学习算法与策略搜索算法的优缺点。
2.3.1 策略搜索算法建模
策略搜索算法直接利用现有样本数据对策略进行学习，其主要思想是将策略 π表示为参数为 θ 的函数，即 π（a| s，θ）。策略搜索算法的目的就是找到可以使得期望回报值最大化的最优参数。
智能体与环境交互得到路径 h后，便可计算路径的回报，将其表示为：
其中， γ 是折扣因子，通常0≤γ ＜1，折扣因子 γ 决定了回报的时间尺度，瞬时奖励乘以折扣因子，这样意味着当下的奖励比未来反馈的奖励更重要。接近1的折扣因子更关注长期的累积奖励，而接近0的折扣因子优先考虑短期奖励，更关注短期目标。由于环境的动态性及不确定性，每条路径不是确定的，它的回报是一个随机变量，因此无法通过一条路径的回报衡量与描述它的好坏，但是其期望是一个确定值。因此，我们用回报的期望来衡量一个策略。回报的期望可表示为策略参数 θ的函数：
J (θ)=∫p(h|θ)R(h)dh
这里路径 h发生的概率密度取决于策略，根据马尔可夫随机性质，可将其表示为：
回报的期望 J（θ）最大化所对应的参数为最优策略参数θ*：
下面，介绍寻找最优策略参数的经典策略搜索算法：传统策略梯度算法（REINFORCE 算法）[17]、自然策略梯度方法[18]以及期望最大化的策略搜索方法[19]。
2.3.2 传统策略梯度算法（REINFORCE算法）
寻找最优策略参数的最简单、最常用的方式是梯度上升法，在强化学习领域我们将其称为传统策略梯度算法，即 REINFORCE算法[17]，它直接通过梯度上升更新策略参数 θ：
θ ← θ+ ε∇θJ(θ)
其中 ε为学习率，它是一个非常小的正数。因此，REINFORCE 算法的关键是如何计算策略梯度 ∇θJ（θ）。
我们对回报的期望求导可得：
这里使用了log函数求导：∇θp（h|θ）= p（h|θ）∇θlog p（h|θ）。然而，路径的概率密度函数p（h|θ）未知，因此，无法得到策略梯度 ∇θJ（θ）的解析解。我们可以利用经验平均估算，即利用当前策略采样得到 N 条路径，然后用这 N 条路径的经验平均估计策略梯度，即：
其中，
为采样的第 n 条路径样本。由此可以看出，策略梯度的计算最终转换为动作策略的梯度值。
通常，为了更好地进行探索，我们选择随机策略。高斯策略模型是最常用的一种策略模型，假设此处的策略参数为θ=（μ，σ），其中 μ为均值向量， σ为标准差，高斯策略模型可表示为：
其中 φ（s）为基函数向量。在高斯策略模型下，可以很容易求得动作策略梯度的解析解：
到此为止，我们就可以通过梯度上升法计算策略梯度，改进策略参数，直到收敛为止。但是，该方法的问题是当估计策略梯度的样本数不足时，上述策略梯度的方差较大，容易导致收敛速度较慢及不稳定的问题。
2.3.3 自然策略梯度方法（Natural Policy Gradient）
传统策略梯度算法使用欧氏距离来更新参数的方向，这意味着所有参数的维度对所得到的策略均具有较大影响。在更新策略时，使用传统策略梯度算法的一个主要原因是可以通过小幅度调整参数来稳定地改变策略。然而，对策略参数的小幅度调整可能会造成策略的大幅度改变。为了能够使策略更新过程相对稳定，就需要分布π （at|s t，θ）保持相对稳定，在每次更新后分布不会产生较大变化，这就是自然策略梯度方法的核心思想[18]。
每次迭代后对参数θ 进行更新，策略π（at|st，θ）自然也随之改变。策略分布在更新前后存在一定的差异。在自然策略梯度方法中使用 Kullback Leibler （KL）散度来测量当前策略下的路径分布与更新的策略下路径分布之间的距离。KL 散度是两个随机分布距离的度量，记为 DKL（ p|| q），它衡量两个分布p和q的相似程度。Fisher 信息矩阵可以用来近似计算当前策略下的路径分布p（h|θ）和更新θ 至θ+Δθ后策略下的路径分布 p（h|θ+Δθ）之间的距离（Δθ为一个非常小的数），我们将 Fisher信息矩阵用 Fθ来表示：
KL( p(h|θ)|| p(h|θ+Δθ)) ≈ ΔθT FθΔθ
Fθ=∫p(h|θ)∇θlogp(h|θ)∇θlogp(h|θ)T dh
与传统策略梯度算法更新 ∇θJ（θ）类似，自然策略梯度方法也更新策略参数，使得策略更新前后的路径分布之间的 KL散度不大于 ε：
KL( p(h|θ)|| p(h|θ+Δθ))≤ ε
其中 ε是很小的数，趋于0。也就是说自然梯度策略方法可以保证策略参数得到最大程度改变的同时，策略更新前后的路径分布只发生微小的变化，从而保证策略更新过程相对稳定。我们可以将自然梯度下降表示为如下优化问题：
以上目标函数的解析解为：
，其中
表示 Fisher信息矩阵的逆，∇θJ（θ）为传统的策略梯度。同样地，我们可以利用经验平均来估计Fisher信息矩阵，其经验值可表示为
其中，
为采集的第 n条路径样本。
由于 Fisher 信息矩阵总是正定矩阵，自然梯度围绕传统梯度的旋转角度始终小于90°。因此，自然策略梯度方法的收敛同传统策略梯度算法一样具有保证。
与传统策略梯度算法相比，自然策略梯度方法能够很好地避免过早进入到停滞期，以及在目标函数变化极大的情况下出现参数更新步长过大的现象。因此，在实际应用中自然策略梯度方法的学习过程往往比其他方法收敛得更快[20]。
为对比自然策略梯度方法与传统策略梯度算法的不同，我们使用高斯策略模型，并预先设定最优策略参数为θ*=（μ*，σ*）=（-0.912，0）。自然策略梯度方法与传统策略梯度算法的参数更新过程如图2-6所示。图中轮廓线及箭头分别表示期望回报和梯度方向。通过观察可见，传统策略梯度算法中参数 σ变化很快，使之过早停止探索，最终导致只能找到局部最优。而自然策略梯度方法能够缓慢地更新参数 σ和 μ，最终快速找到最优解。此外，在目标函数曲线变化平缓区域，传统策略梯度算法难以沿着正确的方向更新参数，而自然策略梯度方法不存在这样的问题。
图2-6 传统策略梯度算法与自然策略梯度方法的策略参数更新路径比较
自然策略梯度方法与传统策略梯度算法相比，确实能更稳定、更快速地更新策略参数。然而，由于 Fisher 信息矩阵的逆难解，使得自然策略梯度方法难以在实际应用中得以应用[21]。
2.3.4 期望最大化的策略搜索方法
基于梯度的策略更新方法需要人为指定超参数和学习率，学习率的设定往往需要丰富的先验知识。如果学习率设定不当，常常会导致参数更新不稳定或收敛速度很慢[22]。对于以上问题，可以用期望最大化（Expectation Maximization，EM）的策略搜索方法解决[23]。期望最大化的策略搜索方法的主要思想是在无法观测的隐变量的概率模型中寻找参数最大似然估计或最大后验估计。期望最大化的策略搜索方法就是用于估计具有隐变量模型的最大似然解的迭代过程。
基于高斯策略模型与期望最大化求解方法相结合的策略搜索方法，我们称为回报加权回归（Reward Weighted Regression，RWR），RWR的基本思想是通过最大化期望回报的下界来迭代更新策略参数[19]。
下面对 RWR 进行简要说明。令θl为当前策略参数，其中 l为迭代次数。首先给出对数期望回报的下界，即强化学习中目标函数的对数，并将其定义为Ql （）θ：
期望最大化的策略搜索方法通过最大化下界 Ql （）θ 迭代更新参数θ，用公式可表示为：
由于在当前策略参数θl下，log J （θl）= Ql （θl），下界函数Ql （）θ与原函数在θl处重合。因此，通过最大化下界得到的更新参数能保证参数更新方向沿着期望回报单调增加方向进行，即
J(θl+1)≥J(θl)
因此，期望最大化的策略搜索方法能够保证最终结果一定收敛于局部最大期望回报 log J （θ）。为了得到Q l （θ）的最大值，可以对Q l （θ）关于θ求导，然后置0：
求解上式，便可得到最优解。现在，我们使用策略参数为θ=（μ，σ）的高斯策略模型，其中 μ为均值向量， σ为标准差。该策略模型表示为：
其中，φ（s）是 l维基函数向量。
对高斯策略模型的对数中的策略参数求导，可得解析解：
假设高斯策略模型的参数θ=（μ，σ）更新后为θl+1=（μl+1，σl+1） T，将式（2-3）代入式（2-2），便可得到更新后的参数：
由于上式中的 p（h|θ）未知，要想更新策略参数，就需要对数据进行采样，用经验估计值逼近目标函数值。假设我们收集到 N 条路径样本
，利用采样样本得到的经验估计值为：
通过对上述过程不断迭代求解，直到参数更新收敛，便为 RW R 的求解过程。
2.3.5 基于策略的深度强化学习方法
在深度强化学习领域中，Lillicrap 等人将 DQN 方法中的经验回放机制和目标网络应用在策略搜索方法中，提出深度策略梯度方法（Deep Deterministic Policy Gradient，DDPG）增加算法的稳定性和鲁棒性[24]。另外，DDPG不仅能处理具有连续动作空间的强化学习任务，而且由于该方法与深度学习结合，使得其能够高效地应用到大规模复杂决策问题中。然而，该方法需要对网络模型进行大规模的训练才能收敛而且交互环境中存在的环境噪声一定程度上也会影响策略性能。
在梯度更新时，策略梯度方法很难确定每步的更新步长，步长太小时容易使算法陷入局部最优且收敛速度慢，步长过大时会导致最终找不到最优策略。针对此问题，Schulman 提出信赖域策略优化方法（Trust Region Policy Optimization，TRPO）[25]，引入 KL 散度（Kullback-Leibler Divergence）定义的信赖域约束强制限定新旧策略之间的差异来选取合适的步长，保证策略优化过程总是朝着不变坏的方向进行，从而避免因步长偏大或偏小导致的问题[26]。然而，TRPO将 KL约束独立出来的方法会导致计算过程复杂性提高。
针对 TRPO 难以计算的问题，OpenAI 改进了 TRPO 的目标函数，提出近端策略优化算法（Proximal Policy Optimization，PPO）[27]。该算法直接使用上下界常量对策略更新幅度进行裁剪，此方法能够降低计算复杂度，另外，由于传统策略梯度算法每更新一次参数都需要进行重新采样，参数更新慢，即要训练学习具有自主能力的智能体和与环境进行交互的智能体是同一个智能体，是一种 on-policy 的策略搜索方法；与之对应的是 off-policy 策略搜索方法，即要训练的智能体和与环境进行交互的智能体不是同一个智能体。PPO 解决了参数更新效率低的问题，是一种 off-policy 的策略搜索方法，还可以在一次采样后多次更新策略参数，从而提高了样本利用率。
综上，本节介绍了强化学习领域中经典的策略搜索算法。基于上述内容，我们总结策略搜索算法的优缺点。
（1）策略搜索算法是对策略进行参数化表示，与基于值函数的策略学习算法中对值函数进行参数化表示相比，策略参数化更简单，更容易收敛。
（2）利用基于值函数的策略学习算法求解最优策略时，策略改善需要求解arg maxa Q（，）s a，当动作空间极大或为连续动作空间时，无法进行求解。
（3）策略搜索算法通常采用随机策略，因此可以将探索更好地融入到策略的学习过程中。
与基于值函数的策略学习算法相比较，策略搜索算法同时也存在一些不足，如：
（1）策略搜索算法容易陷入局部最小值；
（2）策略评价的样本不充足时，策略搜索算法会导致方差较大，最终影响收敛。