策略梯度
前面求解最优策略的方法有两种：对于离散的MDP，如果状态和动作集不大，则通过估计动作值函数$q(s,a)$来估计最优策略；如果状态和动作集非常大，则通过寻找一个函数$f(s,a)$来近似动作值函数，比如上一篇博文中的DQN能够处理高维的状态信息，然后输出离散动作的概率分布。
除此之外，可以直接对策略进行参数化建模，不需要值函数信息，David Silver[1]认为这种直接基于策略的方法有如下的优缺点：
我们将带参数的策略近似函数记为$\pi_{\theta}(s, a)$，其中$\theta$用于描述策略近似函数。我们的目标是给定带参数$\theta$的策略$\pi_{\theta}(s, a)$，寻找最佳的参数$\theta^\star$。为此，我们需要一个值来衡量当前策略$\pi_{\theta}(s, a)$的好坏程度。
假设智能体从初始状态$s_0$开始，根据策略$\pi_{\theta}(s, a)$不断与环境交互，得到一个$trajectory \; \tau = \{ s_0, a_0, \ldots, s_T \}$，每个时刻$t$获得的回报值记为$r_t, t=0,1,\ldots,T$，则在策略参数$\theta$描述的策略下该trajectory出现的概率$p(\tau | \theta)$可以表示为：
$$
p(\tau | \theta) = \mu(s_0) \pi(a_0 | s_0, \theta)P(s_1, r_0 | s_0,a_0) \pi(a_1 | s_1,\theta) \cdots \pi(a_{T-1} | s_{T-1},\theta )P(s_T,r_{T-1} | s_{T-1}, a_{T-1})
$$
我们从$\tau$上选择前$t$个时刻的部分trajectory $\tau_t = \{ s_0, a_0, \ldots, s_t \}$来分析，这个子轨迹出现的概率记为$p(\tau_t | \theta)$，最后时刻$t$对应的回报值记为$r_t$，我们通过$r_t$的期望值来衡量策略$\pi_{\theta}(s, a)$在$\tau_t$的质量：
$$
E_{\tau_t} [r_t] = \sum_{\tau_t} p(\tau_t | \theta) r_t
$$
这里的期望是针对子序列$\tau_t$的概率分布取得，上式是一个以$\theta$为参数的函数，对其求梯度得：
$$
\begin{align}
\nabla_{\theta} E_{\tau_t} [r_t] & = \nabla_{\theta} \sum_{\tau_t} p(\tau_t | \theta) r_t \\
& = \sum_{\tau_t} \nabla_{\theta} p(\tau_t | \theta) r_t \\
& = \sum_{\tau_t} p(\tau_t | \theta) { \nabla_{\theta} p(\tau_t | \theta) \over p(\tau_t | \theta) }r_t \\
& = \sum_{\tau_t} p(\tau_t | \theta) \nabla_{\theta} log [ p(\tau_t | \theta) ] r_t \\
& = E_{\tau_t} [\nabla_{\theta} log [ p(\tau_t | \theta) ] r_t]
\end{align}
$$
我们将$ p(\tau_t | \theta)$展开得到：
$$
p(\tau_t | \theta) = \mu(s_0) \pi(a_0 | s_0, \theta)P(s_1, r_0 | s_0,a_0) \pi(a_1 | s_1,\theta) \cdots \pi(a_{t-1} | s_{t-1},\theta )P(s_t,r_{t-1} | s_{t-1}, a_{t-1})
$$
前面加上对数运算后，上式的累乘运算会变为各部分累加运算：
$$
log [ p(\tau_t | \theta) ] = \sum_{i=0}^t log \pi(a_i | s_i, \theta) + \sum_{i=0}^{t-1} log P(s_{i+1}, r_i | s_i,a_i) + log \mu(s_0)
$$
因为参数$\theta$只出现在策略函数$ \pi(a_i | s_i, \theta)$中，因此$log [ p(\tau_t | \theta) ] $中后两项对参数$\theta$的求导为0，因此有：
$$
\begin{align}
\nabla_{\theta} E_{\tau_t} [r_t]
& = E_{\tau_t} [\nabla_{\theta} log [ p(\tau_t | \theta) ] r_t] \\
& = E_{\tau_t} [ r_t \sum_{i=0}^t \nabla_{\theta} log \pi(a_i | s_i, \theta) ]
\end{align}
$$
整体轨迹$\tau$的累积回报值$R(\tau) = \sum_{k=0}^{T-1} \gamma^k r_k$，对应的期望值导数为：
$$
\begin{align}
\nabla_{\theta} E_{\tau} [R(\tau)]
& = E_{\tau} [ R(\tau) \sum_{i=0}^t \nabla_{\theta} log \pi(a_i | s_i, \theta) ] \\
& = E_{\tau} [ \sum_{k=0}^{T-1} \gamma^k r_k \sum_{i=0}^k \nabla_{\theta} log \pi(a_i | s_i, \theta) ] \\
& = E_{\tau} [ \sum_{t=0}^{T-1} \nabla_{\theta} log \pi(a_t | s_t, \theta) \sum_{t'=t}^{T-1} \gamma^{t'-t} r_{t'} ] \tag{*} \\
\end{align}
$$
表达式()是用于实际估计策略梯度的计算方法，但在实际应用中梯度方差较大[1][2]，容易造成策略收敛不稳定，baseline方法可以减小梯度的方差，加上baseline后的计算表达式为：
$$
\begin{align}
\nabla_{\theta} E_{\tau} [R(\tau)]
& = E_{\tau} [ \sum_{t=0}^{T-1} \nabla_{\theta} log \pi(a_t | s_t, \theta) \; ( \sum_{t'=t}^{T-1} \gamma^{t'-t} r_{t'} - b(s_t) ) ]\tag{**} \\
\end{align}
$$
加上$ b(s_t)$无论取什么值都不会对期望的梯度造成影响[2]，目标在于取一个合适的$ b(s_t)$使得尽可能降低期望梯度的方差，[3]认为最佳的$ b(s_t)$应该取每个状态下的状态值函数估计值，即：
$$
b(s_t) \approx V^{\pi_{\theta}}(s_t) = E_{\tau} [ \sum_{t'=t}^{T-1} \gamma^{t'-t} r_{t'} | s_t; a_{t:T-1 {\pi_{\theta}}}]
$$
根据表达式(*)，可以得到最原始的策略梯度算法(如下图所示)，这只是策略梯度计算的其中一种，更多的策略梯度算法请参考[1][4]文献，这些策略梯度算法的不同在于梯度的计算，而具体的梯度类优化可以自行选择，可以参见本人另一篇介绍优化算法的博文，关于策略优化，还包括策略梯度在内的许多其他方法，Pieter Abbeel 在 Berkeley AI Research Lab 上的汇报[8] 是不错的参考资料。
TRPO
上一节所讨论的策略梯度类算法采取统一的策略参数的更新方式：计算出当前参数下的策略梯度，根据梯度上升方向更新策略参数：
$$
\theta \leftarrow \theta + \eta \nabla_{\theta} E_{\tau} [R(\tau)]
$$
其中$\eta$为更新步长。在策略梯度算法中，步长 $\eta$ 的选择十分关键：如果步长选择太短，则策略更新缓慢；如果步长过长，则容易导致更新到一个坏策略，而坏策略下产生的轨迹$\tau$用于下一轮的策略参数更新，这种恶性循环容易导致策略can’t recover and collapse in performance [5]，这一点与有监督学习下不同：此时因为我们所希望capture到的模式隐藏在给定的训练数据下，因此在某一次迭代时步长过长导致模型效果变差后，能够在后面迭代轮次时纠正过来，而在强化学习下，缺乏这种 ground-truth数据，它训练用的轨迹$\tau$产生自上一次迭代更新后的策略$\pi_{\theta}(s, a)$，因此容易出现“一步走错步步错”的情况。
TRPO（Trust Region Policy Optimization）正是为了解决这个步长选择的问题，它通过计算前后两个策略之间KL散度来控制策略更新的速度，对应的目标函数为：
其中$\pi_{old}(a|s)$表示参数更新之前的策略，$\pi(a|s)$表示参数更新之后当前的策略,$A^{\pi_{old}} (s,a)$表示策略$\pi_{old}(a|s)$下各个状态动作对下的优势函数：
$$
A^{\pi_{old}} (s,a) = E_{\pi_{old}} [ r | s, a ] - V_{\pi_{old}}(s)
$$
其中$V_{\pi_{old}}(s)$是状态值函数，$E_{\pi_{old}} [ r | s, a ]$是近似的动作值函数，因此$A^{\pi_{old}} (s,a)$描述的是策略$\pi_{old}(a|s)$下各个状态动作对的期望回报相对于相同状态下的期望回报所具有的优势大小。TRPO具体的算法步骤参照原论文[6]和博客[7]。另外，Deepmind团队在近期一篇关于利用GAIL模型进行复杂环境下鲁棒性策略学习的论文[11]中将TRPO算法用于策略训练
PPO
TRPO 算法相对于一般的策略梯度算法来说能够更加稳定的训练策略，但是它也存在局限性[9]：
… trust region policy optimization (TRPO) is relatively complicated, and is not compatible with architectures that include noise (such as dropout) or parameter sharing (between the policy and value function, or with auxiliary tasks).
为此，OpenAI团队在17年7月底提出了PPO（Proximal Policy Optimization ）系列算法，它跟TRPO相比[9]：
… use multiple epochs of stochastic gradient ascent to perform each policy update … have the stability and reliability of trust-region methods but are much simpler to implement, requiring only few lines of code change to a vanilla policy gradient implementation, applicable in more general settings (for example, when using a joint architecture for the policy and value function), and have better overall performance.
Deepmind团队在近期一篇关于复杂环境下寻找鲁棒性策略的论文[10]中给出了一种PPO算法的算法流程：
可以看到，它首先对加了KL散度惩罚项的目标函数$J_{PPO}(\theta)$利用普通的梯度上升类算法进行策略参数更新，然后通过平方损失下的梯度下降法更新优势函数，最后它通过检查前后两个策略的KL散度值是否超过区间$(\beta_{low} KL_{target}, \beta_{high} KL_{target})$来不断的调整目标函数中的惩罚系数$\lambda$，如果前后策略的KL散度值超过上限值，则减小惩罚系数，否则扩大惩罚系数，注意这里是希望最大化目标函数$J_{PPO}(\theta)$。
参考文献
- Tutorial for Policy Gradient Algorithm by David Silver;
- John Schulman. Optimizing Expectations: From Deep Reinforcement Learning to Stochastic Computation Graphs;
- E. Greensmith, P. L. Bartlett, and J. Baxter. “Variance reduction techniques for gradient estimates in reinforcement learning.” In: The Journal of Machine Learning Research 5 (2004), pp. 1471–1530 ;
- Richard S. Sutton . reinforcement learning an introduction. Second Edition. MIT press 2012 ;
- Turorial on TRPO;
- Trust Region Policy Optimization;
- About how to solve target function of TRPO;
- Pieter Abbel. Deep Reinforcement Learning through Policy Optimization;
- John Schulman etc. Proximal Policy Optimization Algorithms;
- Nicolas Heess etc. Emergence of Locomotion Behaviours in Rich Environments;
- Ziyu Wang etc. Robust Imitation of Diverse Behaviors;