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 问题设定

考虑一个有限状态和动作的 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')]
\tag{2}
$$

为遵循 $\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}$ 的下界。我们从一个关于奖励改变的引理开始证明。

**引理 5.1** 对于任意函数 $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。

我们可以将这一项添加到式（2）的右侧：

$$
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'}$，现在我们来限制它们之间的差异。

**引理 5.2**

$$
\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.1。

### 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 给出，因此可以代入式（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')。
$$