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')] \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.2。

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

将上述式子与上一节关于相对策略表现恒等式的式子相比，我们这一次给出了下界和上界，而不只是一个近似。通过优化 $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）

A.1 奖励调整（Reward Shaping）

这里我们证明引理 5.1。

证明：

$$ 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$

A.2 状态分布差异限制（Bounding Difference in State Distributions）

这里我们证明引理 5.2。

证明：

回忆式（3）我们有 $d^{\pi}=(1-\gamma)(I-\gamma P_{\pi})^{-1}\mu$。

定义 $G=(I-\gamma P_{\pi})^{-1}$，$\overline{G}=(I-\gamma P_{\pi'})^{-1}$，$\Delta=P_{\pi'}-P_{\pi}$。我们有：

$$ G^{-1}-\overline{G}^{-1} = (I-\gamma P_{\pi})-(I-\gamma P_{\pi'}) $$

$$ = \gamma (P_{\pi'}-P_{\pi}) $$

$$ = \gamma \Delta， $$

$$ \Rightarrow \overline{G}-G = \overline{G}(G^{-1}-\overline{G}^{-1})G = \gamma \overline{G} \Delta G， $$

$$ d^{\pi'}-d^{\pi} = (1-\gamma)(\overline{G}-G)\mu $$

$$ =(1-\gamma)\gamma\overline{G} \Delta G \mu $$

$$ = \gamma \overline{G} \Delta (1-\gamma) G \mu $$

$$ = \gamma \overline{G} \Delta d^{\pi}， \tag{12} $$

取式（12）的 $l_1$ 范数，根据范数的性质，我们有：

$$ \lVert d^{\pi'}-d^{\pi} \rVert_{1} = \gamma \lVert \overline{G} \Delta d^{\pi} \rVert_{1} \leq \lVert\overline{G}\rVert_{1} \lVert \Delta d^{\pi} \rVert_{1}。 \tag{13} $$

我们首先限制 $\lVert\overline{G}\rVert_{1}$。

$$ \lVert\overline{G}\rVert_{1} = \lVert (I-\gamma P_{\pi'})^{-1} \rVert_{1} = \lVert \sum_{t=0}^{\infty}\gamma^{t} P_{\pi'}^{t} \rVert_{1} \leq \sum_{t=0}^{\infty} \gamma^{t} \lVert P _ {\pi'} \rVert_{1}^{t} = \frac{1}{1-\gamma}。 \tag{14} $$

接下来限制 $\lVert \Delta d^{\pi} \rVert_{1}$。

$$ \lVert \Delta d^{\pi} \rVert_{1} = \sum_{s'} |\sum_{s} \Delta(s'|s)d^{\pi}(s)| $$

$$ \leq \sum_{s',s}|\Delta(s'|s)|d^{\pi}(s) $$

$$ = \sum_{s',s}|\sum_{a} (M(s'|s,a)\pi'(a|s)-M(s'|s,a)\pi(a|s))|d^{\pi}(s) $$

$$ = \sum_{s',s}|\sum_{a} M(s'|s,a)(\pi'(a|s)-\pi(a|s))|d^{\pi}(s) $$

$$ \leq \sum_{s',s,a} M(s'|s,a)|\pi'(a|s)-\pi(a|s)|d^{\pi}(s) $$

$$ = \sum_{s,a}|\pi'(a|s)-\pi(a|s)|d^{\pi}(s) $$

$$ =\sum_{s} d^{\pi}(s) \sum_{a} |\pi'(a|s)-\pi(a|s)| $$

$$ =2 \mathbb{E}_ {s\sim d^{\pi}}[D_{TV}(\pi'||\pi)[s]] \tag{15}。 $$

结合式（13），（14）和（15），我们有：

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

证明完毕。$\diamondsuit$

A.3 回报差异限制（Bounding Difference in Returns）

这里我们证明引理 5.3。

证明：

定义 $\delta_{f}(s,a,s')=R(s,a,s')+\gamma f(s')-f(s)$。

由于

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

我们有：

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

我们先来关注第一项。

令 $\overline{\delta}_ {f}^{\pi'}(s)=\mathbb{E}_ {a\sim\pi'(\cdot|s),s'\sim M(\cdot|s,a)}[\delta_{f}(s,a,s')] \in \mathbb{R}^{|S|}$，那么：

$$ \mathbb{E}_ {s\sim d^{\pi'},a\sim\pi',s'\sim M}[\delta_{f}(s,a,s')] = \langle d^{\pi'}, \overline{\delta}_ {f}^{\pi'}\rangle $$

$$ = \langle d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle + \langle d^{\pi'}-d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle $$

$$ \leq \langle d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle + \lVert d^{\pi'}-d^{\pi} \rVert_{1} \lVert \overline{\delta}_ {f}^{\pi'} \rVert_{\infty} $$

$$ = \langle d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle + \lVert d^{\pi'}-d^{\pi} \rVert_{1} \epsilon_{f}^{\pi'}， \tag{18} $$

这里 $\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)]$；

并且：

$$ \mathbb{E}_ {s\sim d^{\pi'},a\sim\pi',s'\sim M}[\delta_{f}(s,a,s')] = \langle d^{\pi'}, \overline{\delta}_ {f}^{\pi'}\rangle $$

$$ = \langle d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle - \langle d^{\pi}-d^{\pi'}, \overline{\delta}_ {f}^{\pi'} \rangle $$

$$ \geq \langle d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle - \lVert d^{\pi}-d^{\pi'} \rVert_{1} \lVert \overline{\delta}_ {f}^{\pi'} \rVert_{\infty} $$

$$ = \langle d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle - \lVert d^{\pi'}-d^{\pi} \rVert_{1} \epsilon_{f}^{\pi'}， \tag{19} $$

将式（18）代入式（17），我们得到：

$$ (1-\gamma)(V^{\pi'}-V^{\pi}) \leq \langle d^{\pi}, \overline{\delta}_ {f}^{\pi'} \rangle + \lVert d^{\pi'}-d^{\pi} \rVert_{1} \epsilon_{f}^{\pi'} - \mathbb{E}_ {s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)}[\delta_{f}(s,a,s')] $$

$$ = \mathbb{E}_ {s\sim d^{\pi'},a\sim\pi'(\cdot|s),s'\sim M(\cdot|s,a)}[\delta_{f}(s,a,s')] - \mathbb{E}_ {s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)}[\delta_{f}(s,a,s')] + \lVert d^{\pi'}-d^{\pi} \rVert_{1} \epsilon_{f}^{\pi'} $$

$$ = \mathbb{E}_ {s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)}[(\frac{\pi'(a|s)}{\pi(a|s)}-1)\delta_{f}(s,a,s')] + \lVert d^{\pi'}-d^{\pi} \rVert_{1} \epsilon_{f}^{\pi'} \tag{20}。 $$

定义

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

若我们选择 $f=V^{\pi}$，那么：

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

这是因为根据相同策略选择动作的优势为 $0$：

$$ \mathbb{E}_ {s\sim d^{\pi},a\sim\pi(\cdot|s)}[A^{\pi}(s,a)]=0。 $$

根据式（20）我们有：

$$ V^{\pi'}-V^{\pi}\leq \frac{1}{1-\gamma}(L_{\pi}(\pi')+\lVert d^{\pi'}-d^{\pi} \rVert_{1}\epsilon_{f}^{\pi'})。 \tag{21} $$

同理，根据式（17）和式（19）我们能推出下界：

$$ V^{\pi'}-V^{\pi}\geq \frac{1}{1-\gamma}(\mathbb{E}_ {s\sim d^{\pi},a\sim\pi(\cdot|s),s'\sim M(\cdot|s,a)}[(\frac{\pi'(a|s)}{\pi(a|s)}-1)\delta_{f}(s,a,s')] - \lVert d^{\pi'}-d^{\pi} \rVert_{1}\epsilon_{f}^{\pi'}) $$

$$ = \frac{1}{1-\gamma}(L_{\pi}(\pi')-\lVert d^{\pi'}-d^{\pi} \rVert_{1}\epsilon_{f}^{\pi'})。 \tag{22} $$

证明完毕。$\diamondsuit$

A.4 最大优势（Maximum Advantage）

这里我们证明引理 5.4。

证明：

像 [5] 那样，我们称 $(\pi,\pi')$ 为 $\alpha$-coupled 策略对，如果对于任意 $s$ 都有 $P[a\neq\hat{a}|s]\leq\alpha$，这里 $(a,\hat{a})|s$ 为 $(\pi,\pi')$ 定义的联合分布。定义 $\alpha_{\pi,\pi'}$ 使得 $(\pi,\pi')$ 为 $\alpha_{\pi,\pi'}$-coupled 策略对。令 $\overline{A}(s)$ 为在状态 $s$ 时 $A^{\pi}(s,\hat{a})$ 的期望，这里 $\hat{a}$ 遵循策略 $\pi'$：

$$ \overline{A}(s) = \mathbb{E}_{\hat{a}\sim\pi'(\cdot|s)}[A^{\pi}(s,\hat{a})]。 \tag{23} $$

由于 $\mathbb{E}_{a\sim\pi(\cdot|s)}[A^{\pi}(s,a)|s]=0$，我们将式（23）写为：

$$ \overline{A}(s) = \mathbb{E}_{(a,\hat{a})\sim(\pi,\pi')}[A^{\pi}(s,\hat{a})-A^{\pi}(s,a)] $$

$$ = P[a\neq\hat{a}|s] \mathbb{E}_{(a,\hat{a})\sim(\pi,\pi')}[A^{\pi}(s,\hat{a})-A^{\pi}(s,a)|a\neq\hat{a}] $$

$$ \text{+} P[a=hat{a}|s] \mathbb{E}_{(a,\hat{a})\sim(\pi,\pi')}[A^{\pi}(s,\hat{a})-A^{\pi}(s,a)] $$

$$ \leq \alpha_{\pi,\pi'} \mathbb{E}_{(a,\hat{a})\sim(\pi,\pi')}[A^{\pi}(s,\hat{a})-A^{\pi}(s,a)|a\neq\hat{a}] + P[a=\hat{a}|s]\ast 0 $$

$$ \leq 2 \alpha_{\pi,\pi'} \mathop{\max}_{a} |A^{\pi}(s,a)|。 \tag{24} $$

因此，我们有：

$$ \epsilon_{V^{\pi}}^{\pi'} = \mathop{\max}_ {s} |\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)]| $$

$$ \leq \mathop{\max}_ {s} |2\alpha_{\pi,\pi'} \mathop{\max}_{a} |A^{\pi}(s,a)|| $$

$$ \leq 2 \alpha_{\pi,\pi'} \mathop{\max}_{s,a}|A^{\pi}(s,a)|。 \tag{25} $$

假设 $p_{X}$ 和 $p_{Y}$ 为概率分布且满足 $D_{TV}(p_{X}\lVert p_{Y})=\alpha$，那么存在边界为 $p_{X}$ 和 $p_{Y}$ 的联合分布 $(X,Y)$ 且 $X=Y$ 的概率为 $1-\alpha$ [5]。取 $\alpha_{\pi,\pi'}=\mathop{\max}_ {s} D_{TV}(\pi\lVert\pi')$，我们有：

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

证明完毕。$\diamondsuit$