10.md

# Lecture 10 Advanced Policy Gradient

# 课时10 高级策略梯度 2019.02.11

## 1. 策略梯度的目标（Policy Gradient Objective）

在策略梯度中，我们将策略 $\pi_\theta$ 参数化，并使用环境中的经历直接来优化它。我们首先定义基于当前策略 $\pi_\theta$ 的轨迹的概率为 $\pi_\theta(\tau)$：

$$
\pi_\theta(\tau) = \pi_\theta(s_1,a_1,...,s_T,a_T)=P(s_1)\prod_{t=1}^T \pi_\theta(a_t|s_t)P(s_{t+1}|s_t,a_t)，
$$

这里 $P(s_1)$ 为起始状态为 $s_1$ 的概率，$\pi_\theta(a_t|s_t)$ 为根据当前的策略在状态 $s_t$ 选择动作 $a_t$ 的概率，$P(s_{t+1}|s_t,a_t)$ 为在状态 $s_t$ 选择动作 $a_t$ 时，状态转移到 $s_{t+1}$ 的概率。注意，$\pi_\theta(\tau)$ 为轨迹的概率而 $\pi_\theta(a|s)$ 为给定状态时选择某个动作的概率。

和到目前为止我们讨论过的大多数其他 RL 目标类似，策略梯度的目标是最大化衰减奖励总和。

$$
\theta^* = \mathop{\arg\max}_{\theta} \mathbb{E} _{\tau\sim \pi _{\theta}(\tau)}[\sum_t \gamma^t r (s_t,a_t)]。
$$

我们将目标函数记为 $J(\theta)$，可以用蒙特卡洛方法估计 $J(\theta)$。我们用 $r(\tau)$ 来代表轨迹 $\tau$ 的衰减奖励总和。

$$
J(\theta) = \mathbb{E}_{\tau\sim \pi _{\theta}(\tau)}[\sum_t \gamma^t r (s_t,a_t)] = \int \pi _{\theta} (\tau) r(\tau) \text{d} \tau
$$

$$
 \approx \frac{1}{N}\sum_{i=1}^N \sum_{t=1}^T \gamma^t r(s_{i,t},a_{i,t})，
 $$

$$
\theta^* = \mathop{\arg\max}_\theta J(\theta)。
$$

我们定义 $P_\theta(s,a)$ 为 $(s,a)$ 出现在轨迹中的概率。注意，若时间步无穷大而且状态的平稳分布存在时，我们可以将 $P_\theta(s,a)$ 写为 $P_\theta(s,a)=d^{\pi_{\theta}}(s)\pi_{\theta}(a|s)$，这里 $d^{\pi_{\theta}}(s)$ 为遵照策略 $\pi_{\theta}$ 时的状态的平稳分布。

在无限时间步的情况下，我们有：
$$
\theta^{*} = \mathop{\arg\max}_{\theta}\sum _{t=1}^{\infty} \mathbb{E} _{(s,a) \sim P _{\theta}(s,a)}[\gamma^t r(s,a)]
$$

$$
= \mathop{\arg\max}_{\theta} \frac{1}{1-\gamma}\mathbb{E} _{(s,a) \sim P _{\theta}(s,a)}[r(s,a)]
$$

$$
= \mathop{\arg\max}_{\theta} \mathbb{E} _{(s,a) \sim P _{\theta}(s,a)}[r(s,a)]。
$$

在有限时间步的情况下，我们有：
$$
\theta^{*} = \mathop{\arg\max}_{\theta} \sum _{t=1}^{T} \mathbb{E} _{(s_t,a_t) \sim P _{\theta}(s_t,a_t)}[\gamma^t r(s_t,a_t)]。
$$

我们可以使用基于梯度的方法来完成上述优化，也就是说，我们需要找到 $J(\theta)$ 基于 $\theta$ 的梯度。
$$
\nabla_{theta}J(\theta) = \nabla_{\theta}\int \pi _{\theta} (\tau) r(\tau) \text{d} \tau
$$

$$
= \int \nabla_{\theta} \pi _{\theta} (\tau) r(\tau) \text{d} \tau
$$

$$
= \int \pi_{\theta}(\tau) \frac{\nabla_{theta} \pi_ {\theta} (\tau)}{\pi_{\theta}(\tau)}r(\tau)\text{d}\tau
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[\nabla_{\theta}\log\pi_{\theta}(\tau)r(\tau)]。
$$

通过对数导数技巧，我们将梯度从期望之外转移到了期望之内。这样做的好处就是，我们不再需要对状态转移函数求梯度，正如下面我们将看到的。
$$
\nabla_{theta}J(\theta) = \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[\nabla_{\theta}\log\pi_{\theta}(\tau)r(\tau)]
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[\nabla_{theta} [\log P(s_1)+\sum_{t=1}^{T}(\log\pi_{\theta}(a_t|s_t) + \log P(s_{t+1}|s_t,a_t))]r(\tau)]
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}} [\nabla_{\theta} [\sum_{t=1}^{T}(\log\pi_{\theta}(a_t|s_t))] r(\tau)]
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}} [\sum_{t=1}^{T}(\nabla_{\theta}(\log\pi_{\theta}(a_t|s_t))(\sum_{t=1}^{T}\gamma^t r(s_t,a_t)))]
$$

$$
\approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} (\nabla_{\theta} (\log\pi_{\theta}(a_{i,t}|s_{i,t}))(\sum_{t=1}^{T}\gamma^t r(s_{i,t},a_{i,t})))。
$$

在第三个等式中，不包含 $\theta$ 的项被去掉。最后一步，我们应用了蒙特卡洛估计。

注意，在监督学习的设定下，上述式子与最大似然估计（Maximum Likelihood Estimate，MLE）有很多相似之处，例如，对于监督学习中的 MLE，我们有概率 $J'(\theta)$ 和对数概率 $J(\theta)$：

$$
J'(\theta) = \prod_{i=1}^{N}P(y_i|x_i)，
$$

$$
J(\theta) = \log J'(\theta) = \sum_{i=1}^{N}\log P(y_i|x_i)，
$$

$$
\nabla_{theta}J(\theta) = \sum_{i=1}^{N} \nabla_{\theta}\log P(y_i|x_i)。
$$

与策略梯度推导相比，关键的差别在于奖励的累加。我们甚至可以将 MLE 视为回报都为 1 的策略梯度。尽管这一差异看起来很小，它会使得问题变得更加困难，特别是，将奖励累加会大大增加方差。因此，在一节中，我们将讨论两种减小方差的方法。

## 2. 在策略梯度中减小方差（Reducing Variance in Policy Gradient）

### 2.1 因果关系（Causality）

首先我们注意到在时间 $t'$ 采取动作不会影响到 时间 $t$ 的奖励，对于所有的 $t < t'$ 而言，这就是所谓的因果关系，因为我们现在做的事不会影响到过去。因此，我们可以将奖励的累加 $\sum_{t=1}^{T}\gamma^{t}r(s_{i,t},a_{i,t})$ 改为 $\hat{Q}_ {i,t}=\sum_{t'=t}^{T}\gamma^{t'}r(s_{i,t'},a_{i,t'})$。这里我们用 $\hat{Q}$ 来表示它是 $Q$ 的蒙特卡洛估计。这样做有助于减小方差，因为我们可以有效地减少来自先前奖励的噪声。因此，我们的目标变为：

$$
\nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} (\nabla_{\theta}\log \pi_{\theta}(a_{i,t}|s_{i,t}) (\sum_{t'=t}^{T}\gamma^{t'}r(s_{i,t'},a_{i,t'}))) = \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} (\nabla_{\theta}\log \pi_{\theta}(a_{i,t}|s_{i,t})\hat{Q}_{i,t})。
$$

### 2.1 基准（Baselines）

现在我们来考虑从回报中减去一个基准，也就是说，我们将目标改为如下形式：
$$
\nabla_{\theta}J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} (\nabla_{\theta}\log \pi_{\theta}(a_{i,t}|s_{i,t})((\sum_{t'=t}^{T}\gamma^{t'}r(s_{i,t'},a_{i,t'}))-b))。
$$

首先，减去的常值基准 $b$ 是无偏的：
$$
\mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\nabla_{\theta}\log \pi_{\theta}(\tau) b] = \int \pi_{\theta}(\tau) \nabla_{\theta}\log \pi_{\theta}(\tau) b \text{d} \tau
$$

$$
= \int \pi_{\theta}(\tau) \frac{\nabla_{\theta}\pi_{\theta}(\tau)}{\pi_{\theta}(\tau)} b \text{d} \tau
$$

$$
= \int \nabla_{\theta}\pi_{\theta}(\tau) b \text{d} \tau
$$

$$
= b \nabla_{\theta} \int \pi_{\theta}(\tau) \text{d} \tau
$$

$$
= b \nabla_{\theta} 1 = 0。
$$

最后的等式中，所有轨迹的概率和为 1。在倒数第二个等式中，由于 $b$ 为常值，我们可以将提出至积分外面（例如，$b$ 可以为平均回报，$b = \frac{1}{N}\sum_{i=1}^{N}r(\tau)$）。即使 $b$ 是状态 $s$ 的函数，这一项也是无偏的：
$$
\mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\nabla_{\theta}\log \pi_{\theta}(\tau) b(s_t)]
$$

$$
= \mathbb{E}_ {s_{0:t},a_{0:(t-1)}} [\mathbb{E}_ {s_{(t+1):T},a_{t:(T-1)}} [\nabla_{\theta}\log \pi_{\theta}(a_t|s_t)b(s_t)]]
$$

$$
= \mathbb{E}_ {s_{0:t},a_{0:(t-1)}} [b(s_t) \mathbb{E}_ {s_{(t+1):T},a_{t:(T-1)}}[\nabla_{\theta}\log \pi_{\theta}(a_t|s_t)]]
$$

$$
= \mathbb{E}_ {s_{0:t},a_{0:(t-1)}} [b(s_t) \mathbb{E}_ {a_t}[\nabla_{\theta}\log \pi_{\theta}(a_t|s_t)]]
$$

$$
= \mathbb{E}_ {s_{0:t},a_{0:(t-1)}} [b(s_t) \cdot 0] = 0。
$$

如上所述，如果对策略不做任何假设，那么基准不能是动作的函数，因为上述证明需要提出 $b(s_t)$。如果我们对策略做出一些假设，那么例外情况就出现了，参见 [3] 了解与动作相关的基准的例子。

一个常用的基准是值函数 $V^{\pi_{\theta}}(s)$。因为回报估计了状态-动作值函数 $Q^{\pi_{\theta}}(s,a)$，通过减去这个基准，我们实际上是在计算优势 $A^{\pi_{\theta}}(s,a)=Q^{\pi_{\theta}}(s,a)-V^{\pi_{\theta}}(s)$。在实现方面，这意味着训练一个单独的值函数 $V_{\phi}(s)$。

另一方面，我们可以训练另一个状态-动作值函数 $Q_{\omega}(s,a)$ 来逼近策略梯度，而不是使用环境返回的实际回报来估计 $Q^{\pi_{\theta}}(s,a)$。这一方法被称为 $actor-critic$，这里 $Q_{\omega}$ 为 $critic$。本质上，$critic$ 做策略评估，$actor$ 做策略改进。

那么为了最小化方差，最优的基准是什么？事实上，最优的基准为按梯度平方加权的期望奖励，如下所示。
$$
Var[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2，
$$

$$
\nabla_{\theta}J(\theta) = \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\nabla_{\theta} \log \pi_{\theta}(\tau)(r(\tau)-b)]，
$$

$$
Var = \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[(\nabla_{\theta} \log \pi_{\theta}(\tau)(r(\tau)-b))^2] - (\mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[\nabla_{\theta} \log \pi_{\theta}(\tau)(r(\tau)-b)])^2
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[(\nabla_{\theta} \log \pi_{\theta}(\tau)(r(\tau)-b))^2] - (\mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[\nabla_{\theta} \log \pi_{\theta}(\tau)r(\tau)])^2。
$$

上述等式中，因为我们已经证明 $b$ 在期望中是无偏的，我们可以将 $b$ 去掉。为了最小化方差，我们将方差关于 $b$ 的导数设为 0，第二项与 $b$ 无关，因此只需要对第一项求导：
$$
\frac{{\text d}Var}{{\text d}b} = \frac{{\text d}}{{\text d}b} \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [(\nabla_{\theta} \log \pi_{\theta}(\tau)(r(\tau)-b))^2]
$$

$$
= \frac{{\text d}}{{\text d}b} (\mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[(\nabla_{\theta} \log \pi_{\theta}(\tau))^2 b^2] - 2\mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[(\nabla_{\theta} \log \pi_{\theta}(\tau))^2 r(\tau)b])
$$

$$
= 2\mathbb{E} [(\nabla_{\theta} \log \pi_{\theta}(\tau))^2 b] - 2\mathbb{E} [(\nabla_{\theta} \log \pi_{\theta}(\tau))^2 r(\tau)] = 0，
$$

$$
b = \frac{\mathbb{E} [(\nabla_{\theta} \log \pi_{\theta}(\tau))^2 r(\tau)]}{\mathbb{E} [(\nabla_{\theta} \log \pi_{\theta}(\tau))^2]}。
$$

## 3. 离线策略策略梯度（Off Policy Policy Gradient）

上面的分析中，我们的目标为对基于 $\pi_{\theta}(\tau)$ 的轨迹求期望，这意味着具有上述目标的策略梯度将产生在线策略算法。不论何时改变参数 $\theta$，我们的策略都改变，并且过去的轨迹无法再被使用。而 DQN 为离线策略算法，因为它能够存储并利用过去的经历。这意味着一般情况下，上述策略梯度的样本有效性低于 Q-学习。为了解决这一问题，我们将讨论重要性采样（Importance Sampling）来生成离线策略策略梯度（Off Policy Policy Gradient）算法。具体来说，我们需要做出哪些改变，如果我们想用基于先前策略 $\pi_{\theta}$ 生成的轨迹,而不是基于当前策略 $\pi_{\theta}'$ 生成的轨迹来估计 $J(\theta)$。

$$
\theta^* = \mathop{\arg\max}_{\theta'} J(\theta')
$$

$$
= \mathop{\arg\max}_ {\theta'} \mathbb{E}_ {\tau\sim\pi_{\theta'}(\tau)} [r(\tau)]
$$

$$
= \mathop{\arg\max}_ {\theta'} \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\frac{\pi_{\theta'}(\tau)}{\pi_{\theta}(\tau)} r(\tau)]
$$

$$
= \mathop{\arg\max}_ {\theta'} \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\frac{P(s_1)\prod_{t=1}^{T}\pi_{\theta'}(a_t|s_t)P(s_{t+1}|s_t,a_t)}{P(s_1)\prod_{t=1}^{T}\pi_{\theta}(a_t|s_t)P(s_{t+1}|s_t,a_t)} r(\tau)]
$$

$$
= \mathop{\arg\max}_ {\theta'} \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\frac{\prod_{t=1}^{T}\pi_{\theta'}(a_t|s_t)}{\prod_{t=1}^{T}\pi_{\theta}(a_t|s_t)}]。 （？？？？感觉有问题）
$$

因此，对于旧的参数 $\theta$，我们有：
$$
J(\theta) = \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[r(\tau)]，
$$

对于新的参数 $\theta'$，我们有：
$$
J(\theta') = \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)}[\frac{\pi_{\theta'}(\tau)}{\pi_{\theta}(\tau)} r(\tau)]。
$$

$$
\nabla_{\theta'}J(\theta') = \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\frac{\nabla_{\theta'}\pi_{\theta'}(\tau)}{\pi_{\theta}(\tau)} r(\tau)]
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\frac{\pi_{\theta'}(\tau)}{\pi_{\theta}(\tau)} \nabla_{\theta'}\log\pi_{\theta'}(\tau) r(\tau)]
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [(\prod_{t=1}^{T} \frac{\pi_{\theta'}(a_t|s_t)}{\pi_{\theta}(a_t|s_t)}) (\sum_{t=1}^{T}\nabla_{\theta'}(\log\pi_{\theta'}(a_t|s_t))) (\sum_{t=1}^{T}\gamma^{t}r(s_t,a_t))]
$$

$$
= \mathbb{E}_ {\tau\sim\pi_{\theta}(\tau)} [\sum_{t=1}^{T}(\nabla_{\theta'}(\log\pi_{\theta'}(a_t|s_t)) (\prod_{t'=1}^{t} \frac{\pi_{\theta'}(a_{t'}|s_{t'})}{\pi_{\theta}(a_{t'}|s_{t'})}) (\sum_{t'=t}^{T}\gamma^{t'}r(s_{t'},a_{t'})))]。
$$

最后一个等式中，我们应用了因果关系，前 $k$ 次状态转移只依赖于前 $k$ 个动作而不依赖于将来的动作。

## 4. 相对策略表现恒等式（Relative Policy Performance Identity）

根据目标 $J(\theta)$ 相对于参数 $\theta$ 的梯度直接采取梯度步骤的一个问题是，在参数空间中移动与在策略空间中移动是不同的。这导致了步长的选择问题，小的步长使得学习较为缓慢，而大的步长可能导致策略变差。

在监督学习的情况下，这通常没关系，因为以下更新一般会解决这个问题。然而，在强化学习中，坏的策略将导致在坏的策略下收集下一批数据。因此，执行坏的策略可能会引起无法恢复的性能崩溃。在梯度方向上执行简单的线搜索可能缓解此问题，例如，我们可以为每次更新尝试多个学习率，并选择表现最佳的学习率。然而，这样做属实有点简单，并且在一阶近似（梯度）不好的时候会导致收敛很慢。

下一节将讨论的信任区域策略优化（Trust Region Policy Optimization）算法尝试去解决这个问题。在此之前，我们首先推导一个关于相对策略表现 $J(\pi')-J(\pi)$ 的恒等式，这里我们使用如下符号：$J(\pi')=J(\theta')$，$J(\pi)=J(\theta)$，$\pi'=\pi_{\theta'}$ 与 $\pi=\pi_{\theta}$。

**引理 4.1**

$$
J(\pi')-J(\pi) = \mathbb{E}_ {\tau\sim\pi'}[\sum_{t=0}^{\infty}\gamma^{t} A^{\pi}(s_t,a_t)]。
$$

证明：

$$
\mathbb{E}_ {\tau\sim\pi'} [\sum_{t=0}^{\infty}\gamma^{t} A^{\pi}(s_t,a_t)] = \mathbb{E}_ {\tau\sim\pi'} [\sum_{t=0}^{\infty}\gamma^{t} [r(s_t,a_t)+\gamma V^{\pi}(s_{t+1}) - V^{\pi}(s_t)]]
$$

$$
= \mathbb{E}_ {\tau\sim\pi'} [\sum_{t=0}^{\infty} \gamma^{t}r(s_t,a_t)] + \mathbb{E}_ {\tau\sim\pi'}[\sum_{t=0}^{\infty}\gamma^{t}[\gamma V^{\pi}(s_{t+1}) - V^{\pi}(s_t)]]
$$

$$
= J(\pi') - \mathbb{E}_ {\tau\sim\pi'}[V^{\pi}(s_0)]
$$

$$
J(\pi')-J(\pi)。
$$

证明完毕。$\diamondsuit$

因此，我们有：

$$
\mathop{\max}_ {\pi'} J(\pi') = \mathop{\max}_{\pi'} J(\pi')-J(\pi)
$$

$$
= \mathop{\max}_ {\pi'} \mathbb{E}_ {\tau\sim\pi'}[\sum_{t=0}^{\infty}\gamma^{t} A^{\pi}(s_t,a_t)]。
$$