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)]。
$$

上述表达式需要根据 $\pi'$ 的轨迹，然而我们还没有 $\pi'$，这就导致无法进行优化。我们再一次使用可能性来规避这个问题。

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

$$
= \frac{1}{1-\gamma} \mathbb{E}_ {s\sim d^{\pi'},a\sim\pi'}[A^{\pi}(s,a)]
$$

$$
= \frac{1}{1-\gamma} \mathbb{E}_ {s\sim d^{\pi'},a\sim\pi} [\frac{\pi'(a|s)}{\pi(a|s)}A^{\pi}(s,a)]
$$

$$
\approx \frac{1}{1-\gamma} \mathbb{E}_ {s\sim d^{\pi},a\sim\pi} [\frac{\pi'(a|s)}{\pi(a|s)}A^{\pi}(s,a)]
$$

$$
= \frac{1}{1-\gamma} L_{\pi}(\pi')。
$$

我们称 $L_{\pi}(\pi')$ 为替代目标。一个关键问题是什么时候我们可以做出上述近似。显然，当 $\pi=\pi'$ 时，近似变成了相等。然而这并不是有用的，因为我们希望将当前的策略 $\pi$ 改进为更好的策略 $\pi'$。在下面的信任区域策略优化（TRPO）的推导中，我们给出做出近似的界。

## 5. 信任区域策略优化（Trust Region Policy Optimization）

TRPO [3] 的关键思想是定义一个限制策略更新的信任区域。这个约束在策略空间中而不是在参数空间中，并且称为算法的新步长。通过这种方式，我们可以大致确保策略更新后的新策略比旧策略表现得更好。

### 5.1 问题设定（Problem Setup）

考虑一个有限状态和动作的 MDP，$\cal{M}=(S,A,M,R,\gamma)$，这里 $M$ 为状态转移函数。在这一节中，我们假设 $|S|$ 和 $|A|$ 都是有限的，并且假设 $0<\gamma<1$。尽管推导是基于有限状态和动作的，但算法对连续状态和动作同样有效。我们定义

$$
d^{\pi}(s) = (1-\gamma)\sum_{t=0)}^{\infty}\gamma^{t}M(s_t=s|\pi)
\tag{1}
$$

为始于状态 $s$，遵循策略 $\pi$ 与转移函数 $M$ 的衰减状态访问分布，并且定义

$$
V^{\pi} = \frac{1}{1-\gamma} \mathbb{E}_{s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)} [R(s,a,s')]
<\span id="eq2">\tag{2}</span>
$$

为遵循 $\pi$ 与 $M$ 的期望衰减奖励和。注意这里的 $V^{\pi}$ 与前面提到的 $J(\theta)$ 定义相同。

令 $\rho_{\pi}^{t}\in\mathbb{R}^{|S|}$，$\rho_{\pi}^{t}(s)=M(s_t=s|\pi)$，这是遵循 $\pi$ 与 $M$ 时，在时间步 $t$ 时状态为 $s$ 的概率。

令 $P_{\pi}\in\mathbb{R}^{|S|\times|S|}$，这里 $P_{\pi}(s'|s)=\sum_a M(s'|s,a)\pi(a|s)$，这是遵循 $\pi$ 与 $M$ 时，在状态 $s$ 用一步转移到状态 $s'$ 的概率。

令 $\mu$ 为起始状态分布。我们有：

$$
d^{\pi} = (1-\gamma) \sum_{t=0}^{\infty}\gamma^{t}M(s_t=s|\pi)
$$

$$
= (1-\gamma) \sum_{t=0}^{\infty}\gamma^{t} P_{\pi}\mu
$$

$$
= (1-\gamma) (I-\gamma P_{\pi})^{-1}\mu，
\tag{3}
$$

第二个等号是因为 $\rho_{\pi}^{t}=P_{\pi}\rho_{\pi}^{t-1}$，第三个等号可以由几何级数推导得到。

我们的证明的目的是给出 $V^{\pi'}-V^{\pi}$ 的下界。我们从一个关于奖励调整的引理开始证明。

<span id="lemma51">**引理 5.1**</span> 对于任意函数 $f:S\mapsto\mathbb{E}$ 和任意策略 $\pi$，我们有：

$$
(1-\gamma) \mathbb{E}_{s\sim\mu}[f(s)] + \mathbb{E} _{s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)} [\gamma f(s')] - \mathbb{E} _{s\sim d^{\pi}}[f(s)] = 0。
\tag{4}
$$

这一引理的证明可以参见 [4] 以及[附录 A.1](#lemma51p)。

我们可以将这一项添加到[式（2）](#eq2)的右侧：

$$
V^{\pi}(s) = \frac{1}{1-\gamma} (\mathbb{E}_ {s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)} [R(s,a,s')+\gamma f(s')-f(s)]) + \mathbb{E}_{s\sim\mu}[f(s)]。
\tag{5}
$$

这可以被看作奖励调整的一种形式，改变函数是状态的函数而不是动作的函数。注意如果我们令 $f(s)=V^{\pi}(s)$，那么我们就得到了优势函数。

### 5.2 状态分布差异限制（Bounding Difference in State Distributions）

在更新 $\pi\to\pi'$ 时，我们有不同的衰减状态访问分布 $d^{\pi}$ 和 $d^{\pi'}$，现在我们来限制它们之间的差异。

<span id="lemma52">**引理 5.2**</span>

$$
\lVert d^{\pi'}-d^{\pi} \rVert_1 \leq \frac{2\gamma}{1-\gamma} (\mathbb{E}_ {s\sim d^{\pi}} [D_{TV}(\pi'\lVert \pi)[s]])
$$

这一引理的证明可以参见 [4] 以及[附录 A.2](#lemma52p)。

### 5.3 回报差异限制（Bounding Difference in Returns）

现在我们来限制 $V^{\pi'}-V^{\pi}$。

**引理 5.3** 定义如下项：

$$
L_{\pi}(\pi') = \mathbb{E}_{s\sim d^{\pi},a\sim\pi(\cdot|s)} [\frac{\pi'(a|s)}{\pi(a|s)} A^{\pi}(s,a)]，
$$

$$
\epsilon_f^{\pi'} = \mathop{\max}_ {s} |\mathbb{E}_{a\sim\pi'(\cdot|s),s'\sim M(\cdot|s,a)} [R(s,a,s')+\gamma f(s') - f(s)]|，
$$

我们有如下上界

$$
V^{\pi'}-V^{\pi} \leq \frac{1}{1-\gamma}(L_{\pi}(\pi') + \lVert d^{\pi'}-d^{\pi} \rVert_1 \epsilon_f^{\pi'})
\tag{6}
$$

和如下下界

$$
V^{\pi'}-V^{\pi} \geq \frac{1}{1-\gamma}(L_{\pi}(\pi') - \lVert d^{\pi'}-d^{\pi} \rVert_1 \epsilon_f^{\pi'})。
\tag{7}
$$

这一引理的证明可以参见 [4] 以及附录 A.3。

注意，$\lVert d^{\pi'}-d^{\pi} \rVert_1$ 的上界已经由[引理 5.2](#lemma52) 给出，因此可以代入式（6）和式（7）。

### 5.4 最大优势限制（Bounding Maximum Advantage）

现在我们考虑这一项：

$$
\epsilon_f^{\pi'} = \mathop{\max}_ {s} |\mathbb{E}_{a\sim\pi'(\cdot|s),s'\sim M(\cdot|s,a)} [R(s,a,s')+\gamma f(s') - f(s)]|。
\tag{8}
$$

令 $f(s)=V^{\pi}(s)$，即 $f(s)$ 为遵循策略 $\pi$ 的状态 $s$ 的值函数。因此，我们有

$$
\epsilon_{V^{\pi}}^{\pi'} = \mathop{\max}_ s |\mathbb{E}_{a\sim\pi'(\cdot|s)}[A^{\pi}(s,a)]|。
\tag{9}
$$

这使得我们可以做出如下表述：

**引理 5.4**

$$
\epsilon_{V^{\pi}}^{\pi'} \leq 2\mathop{\max}_ s D_{TV}(\pi\lVert \pi') \mathop{\max}_{s,a}|A^{\pi}(s,a)|。
$$

这一引理的证明可以参见 [5] 以及附录 A.4。

### 5.5 信任区域策略优化（TRPO）

回忆一下，令 $f=V^{\pi}$，我们有

$$
\frac{1}{1-\gamma} L_{\pi}(\pi') - \frac{4\epsilon\gamma}{(1-\gamma)^2}\alpha^2 \leq V^{\pi'}-V^{\pi} \leq \frac{1}{1-\gamma} L_{\pi}(\pi') + \frac{4\epsilon\gamma}{(1-\gamma)^2}\alpha^2，
\tag{10}
$$

这里

$$
L_{\pi}(\pi') = \mathbb{E}_{s\sim d^{\pi},a\sim\pi(\cdot|s)} [\frac{\pi'(a|s)}{\pi(a|s)} A^{\pi}(s,a)]，
$$

$$
\epsilon = \mathop{\max}_{s,a} |A^{\pi}(s,a)|，
$$

$$
\alpha = \mathop{\max}_ s D_{TV}(\pi\lVert \pi')。
$$

将上述式子与上一节关于相对策略表现恒等式的式子相比，我们这一次给出了下界和上界，而不只是一个近似。通过优化 $V^{\pi'}-V^{\pi}$ 的下界，我们得到了一个保证策略改进的优化问题。具体来说，我们要解决以下优化问题：

$$
\mathop{\max}_ {\pi'} L_{\pi}(\pi') - \frac{4\epsilon\gamma}{(1-\gamma)^2}\alpha^2。
$$

不幸的是，解决这个优化问题会导致非常小的步长。在 [5] 中，在实现实用的算法时，作者将该优化问题转化为一个有约束优化问题来增大步长。具体来说，优化问题变为如下形式：

$$
\mathop{\max}_ {\pi'} L_{\pi}(\pi')
$$

$$
\text{s.t.} \quad \alpha^2 \leq \delta，
$$

这里 $\delta$ 为超参数。

由于存在大量的状态，$alpha$ 的最大约束无法求解。因此在 [5] 中，作者使用了仅考虑平均 KL 散度的启发式近似。这样近似是有用的，因为我们可以用样本来近似期望而无法用样本来近似最大值。因此我们有：

$$
\mathop{\max}_ {\pi'} L_{\pi}(\pi')
$$

$$
\text{s.t.} \quad \overline{D}_{KL}(\pi,\pi') \leq \delta，
$$

这里 $\overline{D}_ {KL}(\pi,\pi') = \mathbb{E}_ {s\sim d^{\pi}}[D_{TV}(\pi\lVert \pi')[s]]$。

## 6. 练习

**练习 6.1** 在课程幻灯片中，目标函数为 $J(\theta)=V^{\pi_{\theta}}(s_{start})$。对于这个目标函数，我们做了什么假设？

**解答** 我们假设只有 $s_{start}$ 这一个起始状态。一般来说，可能有多个起始状态，这种情况下我们应该使用开始状态分布（$\mu$）的期望。因此，更一般的目标函数为 $J(\theta) = \mathbb{E}_ {start\sim \mu}[V^{\pi_{\theta}}(s_{start})]$。

**练习 6.2** 在有限时间步的设定下，我们讨论了一个可能的目标函数 $J(\theta)=\mathbb{E}_ {(s,a)\sim P_{\theta}(s,a)} [r(s,a)]$。课程幻灯片中，我们讨论了两个目标函数，我们可以使用平均价值 $J_{avV}(\theta)=\sum_{s} d^{\pi_{\theta}}(s) V^{\pi_{\theta}}(s)$，也可以使用每时间步的平均奖励 $J_{avR}(\theta) = \sum_{s} d^{\pi_{\theta}}(s) \sum_{a} \pi_{\theta}(a|s)r(s,a)$。$J(\theta)$ 与 $J_{avV}(\theta)$ 或 $J_{avR}(\theta)$ 是等价的吗？

**解答** $J(\theta)$ 与每时间步的平均奖励等价。由 $P_{\theta}(s,a)$ 引出的 $(s,a)$ 的期望可以扩展为由状态分布 $d^{\pi_{\theta}}(s)$ 引出的 $s$ 的期望与由策略 $\pi_{\theta}(a|s)$ 引出的 $a$ 的期望。

**练习 6.3** 使用有限差异来估计策略梯度的主要优点是什么？

**解答** 这种方法适用于任何策略，即使策略不可导也可以。

**练习 6.4** 在策略梯度中，对数求导技巧的意义是什么？

**解答** 对数求导技巧使得梯度估计不依赖于动态模型，一般来说，动态模型是未知的。

**练习 6.5** 在证明以状态为变量的基准函数无偏的推导中，我们利用了 $\mathbb{E}_ {a_{t}}[\nabla_{\theta} \log\pi_{\theta}(a_{t}|s_{t})]=0$ 这一事实。如何证明这个期望为 $0$？

**解答**

$$
\mathbb{E}_ {a_{t}}[\nabla_{\theta} \log\pi_{\theta}(a_t|s_t)] = \int_{a} \pi_{\theta}(a_t|s_t) 
\frac{\nabla_{\theta}\pi_{\theta}(a_t|s_t)}{\pi_{\theta}(a_t|s_t)} \text{d}a
$$

$$
= \nabla_{\theta} \int_{a} \pi_{\theta}(a_t|s_t) \text{d}a = \nabla_{\theta}1 = 0。
$$

**练习 6.6** 为什么我们不能直接进行下列优化？

$$
\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)]。
$$

**解答** 我们希望找到 $\pi'$，但为了达到这一目标，我们需要用 $\pi'$ 执行 rollout，这一过程过于缓慢。我们需要使用重要性采样。

**练习 6.7** 这里是对离散动作空间使用自动微分来执行最大似然估计的伪代码。

$\text{logits = policy.predictions(states)}$

$\text{negative_likelihoods = tf.nn.softmax_cross_entropy_with_logits(}$

$\quad\quad\text{labels=actions, logits=logits)}$

$\text{loss = tf.reduce_mean(negative_likelihoods)}$

$\text{gradients = loss.gradients(loss, variables)}$

假设我们执行了 $N$ 个片段（episode），每个时间步都为 $T$，并且有 $d_a$ 个不同的动作和 $d_s$ 个状态维度，那么 $\text{actions}$ 和 $\text{states}$ 的形状是什么？

还已知 $\text{q_values}$ 的一个张量，这个张量的形状是什么？

已知 $\text{q_values}$，应该如何修改上述伪代码以执行策略梯度训练？

**解答** $\text{actions}$ 的形状为 $(N\ast T,d_{a})$，$\text{states}$ 的形状为 $(N\ast T,d_{s})$，$\text{q_values}$ 的形状为 $(N\ast T,1)$。

$\text{logits = policy.predictions(states)}$

$\text{negative_likelihoods = tf.nn.softmax_cross_entropy_with_logits(}$

$\quad\quad\text{labels=actions, logits=logits)}$

$\color{red}{\text{weighted_negative_likelihoods = tf.multiply(negative_likelihoods, q_values)}}$

$\text{loss = tf.reduce_mean(} \color{red}{\text{weighted_negative_likelihoods}})$

$\text{gradients = loss.gradients(loss, variables)}$

因此，策略梯度可以被视为一种加权的最大似然估计，这里的权重为在状态 $s$ 执行动作 $a$ 的期望衰减回报，这个期望衰减回报值越高，权重就越大，梯度就越大，因此更新也就越大。

## 参考文献

1. http://rail.eecs.berkeley.edu/deeprlcourse/static/slides/lec-5.pdf.

2. http://rail.eecs.berkeley.edu/deeprlcourse/static/slides/lec-9.pdf.

3. C. Wu et al, "Variance reduction for policy gradient with action-dependent factorized baselines," *ICLR*, 2018.

4. J. Achiam, D. Held, A. Tamar, and P. Abbeel, "Constrained policy optimization," *ICML*, 2017.

5. J. Schulman et al, "Trust region policy optimization," *ICML*, 2015.

## A TRPO 证明（TRPO Proofs）

### <span id="lemma51p">A.1 奖励调整（Reward Shaping）</span>

这里我们证明[引理 5.1](#lemma51)。

证明：

$$
d^{\pi} = (1-\gamma)(I-\gamma P_{\pi})^{-1}\mu，
$$

$$
(1-\gamma)(I-\gamma P_{\pi}) d^{\pi} = (1-\gamma)\mu，
$$

与 $f(s)$ 取点乘，我们得到：

$$
\mathbb{E}_ {s\sim d^{\pi}}[f(s)] - \mathbb{E}_ {s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)}[\gamma f(s')] = (1-\gamma)\mathbb{E}_{s\sim\mu}[f(s)]。
\tag{11}
$$

证明完毕。$\diamondsuit$

### <span id="lemma52p">A.2 状态分布差异限制（Bounding Difference in State Distributions）</span>

这里我们证明[引理 5.2](#lemma52)。