本文介绍Policy Gradient，这是这个系列的最后一篇文章。
更多本系列文章请点击强化学习简介系列文章。更多内容请点击深度学习理论与实战：提高篇。
目录
值函数的方法里的策略是隐式的，比如π(a|s)=argmaxaQ(s,a)。而Policy Gradient不同，它直接有一个参数化的策略(比如是一个神经网络)，Policy Gradient通过直接求Reward对策略函数的参数的梯度来不断的找到更好的策略(参数)使得期望的Reward越来越大。这是一种梯度上升(Gradient Ascent)算法，和梯度下降类似，只不过一个是求最大值，一个是求最小值，如果加一个负号，那么就是一样的了。
Reward
假设策略函数(可以是很复杂的神经网络)的参数是θ，我们把策略函数记作πθ(a|s)，它表示在状态s时采取策略a的概率。Reward函数的定义如下：
J(θ)=∑s∈Sdπ(s)Vπ(s)=∑s∈Sdπ(s)∑a∈Aπθ(a|s)Qπ(s,a)上式中，dπ(s)是以πθ为转移概率的马尔科夫链的稳态分布(stationary distribution)。马尔科夫链有一个很好的性质，当跳转次数趋于无穷大的时候，最终它处于某个状态的概率只取决于跳转概率，而与初始状态无关。为了记号的简单，我们把dπθ简记为dπ，Qπθ简记作Qπ。稳态概率的形式化定义为：dπ(s)=lim。当t趋于无穷大的时候，概率P(s_t = s \vert s_0, \pi_\theta)与s_0无关，因此可以记作d^\pi(s)。
我们可以这样来解读J(\theta)：要计算一个策略\pi的Reward，我们可以一直运行(run)这个策略无穷多次，那么最终停在状态s的概率是稳态分布d^\pi(s)，而状态s的价值是V^\pi(s)，因此我们认为最终的Reward就是\sum_{s \in \mathcal{S}} d^\pi(s) V^\pi(s) 。而后面那个等式就是简单的把V^{\pi(s)}展开成Q^{\pi(s)}，这个技巧我们在前面已经见过很多次了。
Policy Gradient定理
计算Reward对参数\theta的梯度\nabla_\theta J(\theta)比较Tricky。因为J(\theta)中的三项d^{\pi(s)}、\pi_\theta(a \vert s)和Q^\pi(s, a)都与参数\theta有关，而且d^{\pi(s)}和Q^\pi(s, a)都是非常间接的受\theta的影响——\theta影响策略\pi_\theta(a \vert s)，而策略(跳转概率)影响稳态分布d^{pi(s)}和值函数Q^\pi(s,a)。
Policy Gradient定理帮我们理清上面复杂的函数依赖关系，给出了简洁的Policy Gradient的计算公式：
\begin{split} \nabla_\theta J(\theta) & = \nabla_\theta \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \pi_\theta(a \vert s) \\ & \propto \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \nabla_\theta \pi_\theta(a \vert s) \end{split}上面的公式非常简洁好记，直接把梯度符号\nabla越过各种求和符合直接放到\pi_\theta(a \vert s)前就行。
Policy Gradient定理的推导
推导数学公式有点多，跳过也不影响理解后续的内容(但是Policy Gradient定理得记住)，但是作者强烈建议读者能拿出纸笔详细的抄写一遍，这会对后续的算法的理解很有帮助。虽然推导过程有些繁琐，但并不复杂，如果有一两步确实不能理解，读者也可以忽略其推导过程暂时”假设”它是对的，也许等读完整个过程之后就能理解它了。
我们先看V^\pi(s)的梯度：
\begin{aligned} & \nabla_\theta V^\pi(s) \\ =& \nabla_\theta \Big(\sum_{a \in \mathcal{A}} \pi_\theta(a \vert s)Q^\pi(s, a) \Big) & \\ =& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\nabla_\theta Q^\pi(s, a)} \Big) & \scriptstyle{\text{; 乘法的导数}} \\ =& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\nabla_\theta \sum_{s', r} P(s',r \vert s,a)(r + V^\pi(s'))} \Big) & \scriptstyle{\text{; 用未来的} Q^\pi \text{ 扩展 }} \\ =& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\sum_{s', r} P(s',r \vert s,a) \nabla_\theta V^\pi(s')} \Big) & \scriptstyle{P(s',r \vert s,a) \text{ 不是 }\theta \text{的函数}}\\ =& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\sum_{s'} P(s' \vert s,a) \nabla_\theta V^\pi(s')} \Big) & \scriptstyle{\text{; 因为 } P(s' \vert s, a) = \sum_r P(s', r \vert s, a)} \end{aligned}因此我们有：
\color{red}{\nabla_\theta V^\pi(s)} = \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \sum_{s'} P(s' \vert s,a) \color{red}{\nabla_\theta V^\pi(s')} \Big)上面的公式是递归定义的，右边的\nabla_\theta V^\pi(s’)又可以用相同的方法展开，后面我们会用到。
我们下面考虑如下的访问序列：
s \xrightarrow[]{a \sim \pi_\theta(.\vert s)} s' \xrightarrow[]{a \sim \pi_\theta(.\vert s')} s'' \xrightarrow[]{a \sim \pi_\theta(.\vert s'')} \dots定义从状态s经过k步跳转到状态x的概率为\rho^\pi(s \to x, k)。这个概率的计算需要递归进行：
当k=0时，\rho^\pi(s \to s, k=0) = 1，除了跳转到自己之外其余的概率都是0
k=1时，\rho^\pi(s \to s’, k=1) = \sum_a \pi_\theta(a \vert s) P(s’ \vert s, a)。
k>1时，\rho^\pi(s \to x, k+1) = \sum_{s’} \rho^\pi(s \to s’, k) \rho^\pi(s’ \to x, 1)。
当k=1时，也就是从状态s调整到s’的概率，我们需要遍历每一个action a，在策略\pi下，我们采取a的概率是\pi(a \vert s)，而我们在状态s下采取a跳到s’的概率是P(s’ \vert s, a)，因此就得到k=1时的计算公式。
而从s通过k+1步跳转到x的概率计算，我们分为两步：第一步是s通过k步跳转到s’；第二步从s’跳转到x。前者的概率是 \rho^\pi(s \to s’, k)，后者的概率是\rho^\pi(s’ \to x, 1)，因此就得到k>1的情况。
接下来我们递归的展开\nabla_\theta V^\pi(s)，为了简单，我们定义\phi(s) = \sum_{a \in \mathcal{A}} \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a)，因为对a求和了，所有右边是只与s有关而与a无关的函数。
下面的推导就是通过不断的展开\nabla_\theta V^\pi(s)：
\begin{aligned} & \color{red}{\nabla_\theta V^\pi(s)} \\ =& \phi(s) + \sum_a \pi_\theta(a \vert s) \sum_{s'} P(s' \vert s,a) \color{red}{\nabla_\theta V^\pi(s')} \\ =& \phi(s) + \sum_{s'} \sum_a \pi_\theta(a \vert s) P(s' \vert s,a) \color{red}{\nabla_\theta V^\pi(s')} \\ =& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \color{red}{\nabla_\theta V^\pi(s')} \\ =& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \color{red}{\nabla_\theta V^\pi(s')} \\ =& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \color{red}{[ \phi(s') + \sum_{s''} \rho^\pi(s' \to s'', 1) \nabla_\theta V^\pi(s'')]} \\ =& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \phi(s') + \sum_{s''} \rho^\pi(s \to s'', 2)\color{red}{\nabla_\theta V^\pi(s'')} \\ =& \phi(s) + \sum_{s'} \rho^\pi(s \to s', 1) \phi(s') + \sum_{s''} \rho^\pi(s \to s'', 2)\phi(s'') + \sum_{s'''} \rho^\pi(s \to s''', 3)\color{red}{\nabla_\theta V^\pi(s''')} \\ =& \dots \scriptstyle{\text{; 重复不断的展开 }\nabla_\theta V^\pi(.)} \\ =& \sum_{x\in\mathcal{S}}\sum_{k=0}^\infty \rho^\pi(s \to x, k) \phi(x) \end{aligned}上面的推导把\nabla_\theta Q^\pi(s, a)去掉了，有了\nabla_\theta V^\pi(s)之后，我们就可以计算\nabla_\theta J(\theta)：
\begin{aligned} \nabla_\theta J(\theta) &= \nabla_\theta V^\pi(s_0) & \scriptstyle{\text{; 稳态分布与初始状态无关，可能随机选择初始状态} s_0} \\ &= \sum_{s}\color{blue}{\sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)} \phi(s) &\scriptstyle{\text{; 令 }\color{blue}{\eta(s) = \sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)}} \\ &= \sum_{s}\eta(s) \phi(s) & \\ &= \Big( {\sum_s \eta(s)} \Big)\sum_{s}\frac{\eta(s)}{\sum_s \eta(s)} \phi(s) & \scriptstyle{\text{; 把 } \eta(s), s\in\mathcal{S} \text{ 归一化成概率分布}}\\ &\propto \sum_s \frac{\eta(s)}{\sum_s \eta(s)} \phi(s) & \scriptstyle{\sum_s \eta(s)\text{ 是一个常量}} \\ &= \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) & \scriptstyle{d^\pi(s) = \frac{\eta(s)}{\sum_s \eta(s)}\text{ 是稳态分布}} \end{aligned}我们可以这样来解读\eta(s) = \sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)：\eta(s)表示这个policy从s_0开始重复不断的执行，”经过”状态s的概率。显然我们可以从s_0零步跳转到s(只能是跳到自己)；s_0一步跳转到s；…。因此把这些概率加起来就是”经过”状态s的概率。
因为马尔科夫链的极限是趋近于稳态分布，用通俗的话说就是时间足够大之后处于状态s的概率与初始状态无关。因此存在某个T，当时刻t>T时，p(s)=d^\pi(s)。因此\sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)可以分为两部分，第一部分是\sum_{k=0}^T，另一部分是sum_{k=T+1}^\infty。前一部分总是一个有限的值，而后一部分是无穷大，因此可以忽略前一部分，而sum_{k=T+1}^\infty \rho^\pi(s_0 \to s, k)的平均值等于d^\pi(s)，而且\sum_sd^\pi(s)=1，因此有d^\pi(s) = \frac{\eta(s)}{\sum_s \eta(s)}。
对于连续的情况\sum_s\eta(s)=1，而对于Episode的情况\sum_s\eta(s)等于Episode的平均长度。上面的梯度可以继续简化：
\begin{aligned} \nabla_\theta J(\theta) &\propto \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \nabla_\theta \pi_\theta(a \vert s) &\\ &= \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} \pi_\theta(a \vert s) Q^\pi(s, a) \frac{\nabla_\theta \pi_\theta(a \vert s)}{\pi_\theta(a \vert s)} &\\ &= \mathbb{E}_\pi [Q^\pi(s, a) \nabla_\theta \ln \pi_\theta(a \vert s)] & \scriptstyle{\text{; 因为 } (\ln x)' = 1/x} \end{aligned}上式中\mathbb{E}_\pi指的是\mathbb{E}_{s \sim d_\pi, a \sim \pi_\theta}。这里有一个公式需要大家熟悉：
\begin{split} \mathbb{E}_{x \sim p(x)} [f(x)]=\sum_x p(x)f(x) & \text{离散情况p(x)是概率分布函数} \\ \mathbb{E}_{x \sim p(x)} [f(x)]=\int p(x)f(x) dx & \text{连续情况p(x)是概率密度函数} \end{split}对照上面的公式，最后一步就比较容易理解了。把Policy Gradient定理写成期望的形式在实现的时候更加方便，因为实现时我们通常会使用采样的方法(不过是MC的全采样还是TD的只采样一个时刻)，期望等价于采样的求和Ef(X) \approx \frac{1}{N} \sum_i f(x_i)。
这个式子是各种Policy Gradient算法的基础，所有的Policy Gradient算法的目的都是为了使得估计的\mathbb{E}_\pi的均值接近真实值同时又尽量保证方差较少。
也就是说，Policy Gradient的目的是为了计算梯度g:=\nabla_\theta\mathbb{E}[\sum_{t=0}^{\infty}r_t]，最终又都可以写出统一的形式：g=\mathbb{E}[\sum_{t=0}^\infty \Psi_t \nabla_\theta log \pi_\theta (a_t|s_t)]。其中log \pi_\theta (a_t|s_t)可以类比\nabla_\theta \ln \pi_\theta(a \vert s)，而\Psi_t 可以有很多种近似方法，比如：
- \sum_{t=0}^{\infty}r_t，这是整个trajectory的reward
- \sum_{t’=t}^{\infty}r_{t’}，这是a_t之后的reward，我们通常假设”因果”关系——a_t不影响t时刻之前的reward。
- \sum_{t’=t}^{\infty}r_{t’} - b(s_t)，减去baseline，使得方差变小但是均值不变
- Q^\pi(s_t,a_t)，这就是上面我们推导的形式
- A^\pi(s_t,a_t)=Q^\pi(s_t,a_t)-V^\pi(s_t)，使用Advantage。
- r_t +\gamma V^\pi(s_{t+1}) -V^\pi(s_t)，TD的\delta。
因为Policy Gradient通常和深度学习结合，因此本章不介绍具体的代码，后面深度强化学习的部分会有Policy Gradient代码介绍。
- 显示Disqus评论(需要科学上网)