系列论文阅读——Policy Gradient Algorithms and so on(1)

以DQN为代表的绝大多数基于值的方法通过求解最优值函数+选择当前价值最高的动作来实现。策略高梯度算法则从另一个角度展开——将策略参数化为 $\pi_\theta$ ，直接通过优化参数 $\theta$ 来最大化累计回报的期望。

根据马尔可夫性质，一条迹 $\tau$ ,受策略 $\pi_\theta$ 和转移概率影响，它出现概率为
$p(\tau)=p(s_0)\prod_{i=0}^\infty p(s_{i+1}|s_t,a_t)\pi_\theta(a_i|s_i)$
而他的累积回报为
$r(\tau)=\sum_tr(s_t,a_t)$
我们的目标是最大化累计回报的期望：
$\max_\theta E_{\tau \sim p_\theta(\tau)}r(\tau)$

目标函数记为：
$J(\theta) =E_{\tau \sim p_\theta(\tau)} r(\tau)=\int p_{\theta}(\tau) r(\tau) d \tau$
它的梯度是：
$\begin{aligned}\nabla_{\theta} J(\theta) &=\int \nabla_{\theta} p_{\theta}(\tau) r(\tau) d \tau \end{aligned}$
这里计算梯度的一个技巧是利用对数求导公式做一个变换：
$\begin{aligned}\nabla_{\theta} J(\theta) &=\int p_{\theta}(\tau) \frac{\nabla_{\theta} p_{\theta}(\tau) }{ p_{\theta}(\tau)}r(\tau) d \tau \\ &=\int p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau) r(\tau) d \tau\\&=E_{\tau \sim p_\theta(\tau)} \nabla_{\theta}\log p_\theta(\tau)r(\tau)\end{aligned}$
展开 $\nabla_{\theta} \log p_{\theta}(\tau)$ ，其中，只有 $\pi_\theta(a|s)$ 和 $\theta$ 有关，因此，其他都可以去掉
$\begin{aligned} \nabla_{\theta}\log p_\theta(\tau)&= \nabla_{\theta}\log p(s_0) + \sum_{i=0}^\infty \nabla_{\theta}\log p(s_{i+1}|s_t,a_t)+\sum_{i=0}^\infty\nabla_{\theta}\log \pi_\theta(a_i|s_i) \\ &=\sum_{i=0}^\infty\nabla_{\theta}\log \pi_\theta(a_i|s_i) \end{aligned}$
代入目标函数,再将 $r(\tau)$ 展开，并将它放入前面的括号里，同时，我们用 $\pi_\theta$ 表示当前策略下，动作空间的概率分布，用 $\rho_\pi$ (s)表示到达状态s的概率密度：
$\begin{aligned} \nabla_{\theta} J(\theta) &= E_{s\sim \rho_\pi,a \sim \pi_\theta}\left[\sum_{t=0}^T \nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right)\right]\left[\sum_{t'=0}^T r\left(s_{t'}, a_{t'}\right)\right] \\ &=E_{s\sim \rho_\pi,a \sim \pi_\theta}\left[\sum_{t=0}^T \left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right)\sum_{t'=0}^T r\left(s_{t'}, a_{t'}\right)\right]\right] \end{aligned}$

值得注意的是， $t$ 时刻的动作并不会对 $t$ 之前的收益造成影响，因此，我们将 $t'$ 的初始值设为 $t$ ，最后的公式为：
$\begin{aligned} \nabla_{\theta} J(\theta) &=E_{s\sim \rho_\pi,a \sim \pi_\theta}\left[\sum_{t=0}^T \left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right)\sum_{t'=t}^T r\left(s_{t'}, a_{t'}\right)\right]\right] \end{aligned}$
这时，我们就可以通过使用蒙特卡洛方法从实际系统中采样出的轨迹样本，用 $\nabla_{\theta} J(\theta) \approx \frac{1}{N}\sum^N_{i=1}\left[\sum_{t=0}^T \left[\nabla_{\theta} \log \pi_{\theta}\left(a_{i,t} | s_{i,t}\right)\sum_{t'=t}^T r\left(s_{i,t'}, a_{i,t'}\right)\right]\right]$ 对梯度做一个无偏估计，然后利用梯度提升法来更新策略的参数 $θ$ ：
$\theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)$
由于这个算法依赖于采样得到的完整轨迹，因此被称为蒙特卡洛策略梯度(REINFORCE)。算法流程简单粗暴：

1.随机化策略函数参数 $\theta$

2.循环：

a.使用当前策略 $\pi_\theta$ 产生一条完整的迹: $\tau=(s_0,a_0,s_1,a_1,s_2,a_2,s_3......s_T)$

b.对于每个时间步骤t=T,......2,1： # 从后往前计算 $G_t$ 的效率更高

i.估计累计回报 $G_t$

ii.更新参数： $\theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)$

但是这种简单的方法存在两个问题：

1.累计回报的方差大，导致梯度的方差大，使得训练慢且不稳定，结果难以复现。

2.如果将累计回报看成权值的话，策略梯度算法与极大似然估计非常相似，回报有正有负，策略梯度算法降低一些不好的样本出现概率，而增加其他样本出现概率。但在某些强化学习问题中，环境一直给的都是正向的回报。下图是伯克利强化学习课程第4讲中的一个例子，图（a）所示，左边样本的累计回报是个负数，而右边两个是很小的正数，因此，我们会将策略从实线移动到右边的虚线。提高右边出现的概率，降低左侧坏的出现的概率。但是，当我们将所有的回报都加上一个相等的很大的常数,优劣样本之间的回报差并未改变（如图b），此时，策略梯度算法想要增加所有样本出现的概率，只是左侧较劣的样本出现的概率没有右侧提升的幅度高，此时可以看到，策略从实线到虚线，移动的幅度小了，且变得更加平缓，方差随之也增大。

一个最简单的办法是，从累计回报中减去一个常数基准值b，使得好的样本的累计回报是正的，差的是负的。比如，b可以是累计回报的均值：
$b = \frac{1}{N}\sum^N_{i=1}\sum^T_{t=0} r(s_t,a_t)$
梯度公式变为：
$\begin{aligned} \nabla_\theta J(\theta) &=E_{\tau\sim p_{\theta}(\tau)}\left[\nabla_{\theta} log \ p_{\theta}(\tau)\left[ r(\tau) - b\right]\right] \\&= E_{s\sim \rho_{\pi},a\sim \pi_\theta}[\sum_{t=0}^T \bigtriangledown_\theta log\pi_\theta(a_{t}|s_{t})(\sum_{t^\prime=t}^Tr(s_{t^\prime}, a_{t^\prime}) - b)] \\ &\approx \frac{1}{N}\sum_{i=1}^N[\sum_{t=0}^T \bigtriangledown_\theta log\pi_\theta(a_{i,t}|s_{i,t})(\sum_{t^\prime=t}^Tr(s_{i,t^\prime}, a_{i,t^\prime}) - b)] \end{aligned}$

一个简单的证明：
$\begin{aligned} E_{\tau\sim p_{\theta}(\tau)}\left[\nabla_{\theta} log \ p_{\theta}(\tau) b\right]&=\int p_\theta(\tau) \nabla_{\theta}log\ p_{\theta}(\tau) b \ d \tau \\&= b \ \int \nabla_{\theta} p_{\theta}(\tau) d \tau \\ &= b \nabla_{\theta}\int p_{\theta}(\tau) d \tau\\&=b \nabla_\theta 1 \\&= 0 \end{aligned}$
因此我们减去常数b后的估计在期望意义下依旧是无偏的。

其次，是策略梯度的方差，根据公式 $Var[X]=E[X^2]-E[X]^2$ ：
$\begin{aligned} Var(E_{\tau\sim p_{\theta}(\tau)}\left[\nabla_{\theta} log p_{\theta}(\tau)\left[ r(\tau) - b\right]\right]) &= E_{\tau\sim p_{\theta}(\tau)}\left[\nabla_{\theta} log \ p_{\theta}(\tau)\left[ r(\tau) - b\right]\right]^2 - (E_{\tau\sim p_{\theta}(\tau)}\left[\nabla_{\theta} log \ p_{\theta}(\tau)\left[ r(\tau) - b\right]\right])^2\\ &=E_{\tau\sim p_{\theta}(\tau)}\left[\nabla_{\theta} log\ p_{\theta}(\tau)\left[ r(\tau) - b\right]\right]^2-(E_{\tau\sim log\ p_{\theta}(\tau)}\left[\nabla_{\theta} log \ p_{\theta}(\tau)r(\tau)\right])^2 \end{aligned}$
由此可以证明减去了b之后，在保证偏差不变的情况下减小估计梯度

且求导可得最优的b为：
$b^* = \frac{E[(\nabla_{\theta} \log p_{\theta}(\tau))^2r(\tau)]}{E[\nabla_{\theta} \log p_{\theta}(\tau))^2]}$
PS 这里没有用到折扣因子，加了折扣因子后，一样可以证明