从TRPO到PPO（理论分析与数学证明）-六虎

本文首发于行者AI

导言

一篇关于强化学习算法的理论推导，或许能够帮助你了解PPO算法背后的原理，然后找到改善PPO算法的创意…

马尔可夫决议计划进程由 $\rho_0, \gamma)$ 六个元素构成。其间 $S$ 是一个有限的情况空间集合， $A$ 是一个有限的动作空间集合。 $\times A \times S \rightarrow \mathbb{R}$ 表明情况转移概率函数，例如 $P (s^{'} ∣ s, a) = 0.6$ 表明的含义便是在情况 $s$ 处执行动作 $a$ 抵达的情况为 $s^{'}$ 的概率为0.6。 $S\rightarrow \mathbb{R}$ 是奖赏函数， $0:S→R\rho_0: S\rightarrow\mathbb{R}$ 是初始情况分布概率函数， $∈(0,1)\gamma\in (0,1)$ 是扣头因子。

让 $\pi$ 表明一个随机战略函数 $:SA→[0,1]\pi: S\times A\rightarrow [0,1]$ ,例如 $(s,a)=0.5\pi(s,a)=0.5$ 表明在情况 $s$ 处挑选动作 $a$ 的概率为0.5。令 $()\eta(\pi)$ 表明根据战略 $\pi$ 的长时间希望扣头奖赏： $()=Es0,a0,…[∑t=0∞tr(st)]\eta(\pi) = \mathbb{E}_{s_0, a_0,\ldots}[\sum\limits_{t=0}^{\infty}\gamma^t r(s_t)]$ , 其间 $s0∼0(s0),at∼(at∣st),st+1∼P(st+1∣st,at)s_0\sim \rho_0(s_0), a_t\sim \pi(a_t|s_t), s_{t+1}\sim P(s_{t+1}|s_t,a_t)$ 。

下面给出情况价值函数、情况动作价值函数、优势函数的界说：

（1）情况动作价值函数：

Q(st,at)=Est+1,at+1,…[∑l=0∞lr(st+l)]Q_\pi(s_t,a_t) = \mathbb{E}_{s_{t+1},a_{t+1},\ldots}[\sum\limits_{l=0}^\infty\gamma^lr(s_{t+l})]

表明的是在情况 $s_t$ 处执行动作 $a_t$ 后取得的长时间希望扣头奖赏。

（2）情况价值函数:

V(st)=Eat,st+1,…[∑l=0∞lr(st+l)]=Eat[Q(st,at)]V_\pi(s_t) = \mathbb{E}_{a_t, s_{t+1},\ldots}[\sum\limits_{l=0}^\infty\gamma^lr(s_{t+l})] = \mathbb{E}_{a_t}[Q_\pi(s_t, a_t)]

表明从情况 $s_t$ 开端取得的长时间希望扣头奖赏。

（3）优势函数：

A(s,a)=Q(s,a)−V(s,a)A_\pi(s, a) = Q_\pi(s,a) – V_\pi(s,a)

表明的是在情况 $s$ 处，动作 $a$ 相关于平均水平的高低。

强化学习的目标便是最大化长时间希望扣头奖赏 $()=Es0,a0,…[∑t=0∞tr(st)]\eta(\pi) = \mathbb{E}_{s_0, a_0,\ldots}[\sum\limits_{t=0}^{\infty}\gamma^t r(s_t)]$ 其间战略函数 $\pi$ 能够看作是带有参数 $\theta$ 的随机战略 $(s,a)=(s,a)\pi(s,a) = \pi_\theta(s,a)$ 。在战略梯度算法(Policy Gradient)中，参数 $\theta$ 的更新公式为 $new=old+∇()\theta_{new} = \theta_{old} + \alpha\nabla_{\theta}\eta(\theta)$ 这样的更新公式容易导致以下问题：假如步长 $\alpha$ 选取不适宜，那么会导致 $new\theta_{new}$ 比 $old\theta_{old}$ 差，当运用 $new\theta_{new}$ 进行采样学习的时分，采取到的样本便是比较差的样本，再持续运用欠好的样本对参数进行更新，得到的是更加欠好的战略，然后导致恶性循环。TRPO算法处理的问题便是：怎么挑选一个适宜的更新战略，或是怎么挑选一个适宜的步长，使得更新往后的战略 $new\pi_{\theta_{new}}$ 必定比更新前的战略 $old\pi_{\theta_{old}}$ 好呢？

1.TRPO的理论剖析

1.1 不同战略的长时间希望扣头奖赏之间的关系

先来看一下根据战略 $\pi$ 的长时间扣头奖赏 $\eta({\pi}) = \mathbb{E}_{s_0,a_0,\ldots}[\sum\limits_{t=0}^{\infty}\gamma^t r(s_t)]$ 关于另一个战略 $~\tilde{\pi}$ ,两个战略之间的长时间扣头奖赏函数 $(~)\eta(\tilde{\pi})$ 与 $()\eta(\pi)$ 之间的关系为： $(~)=()+Es0,a0,…∼~[∑t=0∞tA(st,at)](3.1)\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty \gamma^t A_{\pi}(s_t,a_t)]\ \ \ \ \ \ \ (3.1)$ 其间 $A(st,at)A_\pi(s_t,a_t)$ 为优势函数， $A(st,at)=Q(st,at)−V(st)A_\pi(s_t,a_t) = Q_\pi(s_t,a_t) – V_\pi(s_t)$ 。（证明进程见文章后边附录证明4.1）。

上述公式要留意的点是 $s0,a0,…∼~s_0,a_0,\ldots\sim\tilde{\pi}$ 表明轨道中的情况和动作都是根据战略 $~\tilde{\pi}$ 采样得到的，而 $A(st,at)A_{\pi}(s_t,a_t)$ 表明的是战略 $\pi$ 的优势函数。为了方便公式的书写和后续求导的核算，界说 $(s)=P(s0=s)+P(s1=s)+2P(s2=s)+…\rho_\pi(s) = P(s_0=s) + \gamma P(s_1=s) + \gamma^2 P(s_2=s) + \ldots$ 则公式 $(3.1)$ 能够改写为： $(~)=()+∑s~(s)∑s~(a∣s)A(s,a)(3.2)\eta({\tilde{\pi}}) = \eta({\pi}) + \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_s\tilde{\pi}(a|s)A_\pi(s,a) \ \ \ \ \ \ \ \ (3.2)$ 证明进程见文章后边附录证明4.2。

1.2 代替函数的建立

再来回忆一下咱们在布景中提出的目标：找到一个适宜的步长，使得每一个更新得到的新的战略 $new\pi_{new}$ 要比更新前的战略 $old\pi_{old}$ 好,体现在公式上便是要求 $(new)≥(old)\eta(\pi_{new}) \ge \eta(\pi_{old})$ 。

由于公式 $(3.2)$ 中的 $~\rho_{\tilde{\pi}}$ 对 $~\tilde{\pi}$ 有强烈的依赖性，可是在更新之前咱们还不知道战略 $~\tilde{\pi}$ 的具体形式，所以咱们考虑找到一个 $(~)\eta(\tilde{\pi})$ 的代替函数：

L(~)=()+∑s(s)∑a~(a∣s)A(s,a)(3.3)L_\pi(\tilde{\pi}) = \eta({\pi}) + \sum\limits_s\rho_\pi(s)\sum\limits_a\tilde{\pi}(a|s)A_\pi(s,a) \ \ \ \ \ \ \ (3.3)

这个代替函数的作用是什么呢，能够帮助咱们得到 $\eta$ 函数的哪些性质呢？把战略 $\pi$ 表明为带有参数 $\theta$ 的随机战略 $=\pi=\pi_\theta$ ，给出下面定理： $L0()L_{\pi_{\theta_0}}(\pi_\theta)$ 与 $()\eta(\pi_\theta)$ 在 $0\theta_0$ 处一阶近似，用公式表明为:

{L0(0)=(0)∇L0()∣=0=∇()∣=0\left\{ \begin{aligned} L_{\pi_{\theta_0}}(\pi_{\theta_0})& = \eta(\pi_{\theta_0})\\ \nabla_{\theta}L_{\pi_{\theta_0}}(\pi_\theta)|_{\theta=\theta_0}& = \nabla_\theta\eta(\pi_\theta)|_{\theta=\theta_0}\\ \end{aligned} \right.

证明进程见文章后边附录证明4.3。

上述公式的第二个等式能够告诉咱们：在 $=0\theta = \theta_0$ 邻近， $()=L0()\eta(\pi_\theta) = L_{\pi_{\theta_0}}(\pi_\theta)$ 的曲线的改变趋势相同，由于一阶导数的含义便是曲线的改变趋势。又由于这两个函数在 $=0\theta = \theta_0$ 处的值相等（公式的榜首个等式），所以在 $=0\theta = \theta_0$ 的邻近，能够经过优化 $L0()L_{\pi_{\theta_0}}(\pi_\theta)$ 来到达优化 $()\eta(\pi_\theta)$ 的意图，留意是： $=0\theta = \theta_0$ 的邻近！！！邻近！！！下面给出一个一阶近似的比如：

如图所示：函数 $f (x) = x - 1$ 与函数 $g (x) = l n x$ 在 $x = 1$ 处是一阶近似的，即 $f (1) = g (1)$ , $f^{'} (1) = g^{'} (1)$ ，所以这两个函数的曲线的改变趋势在 $x = 1$ 处是近乎相同的。

用 $old\pi_{old}$ 来表明更新前的战略，界说 $′=argmax′Lold(′)\pi’ = argmax_{\pi’}L_{\pi_{old}}(\pi’)$ 咱们选用一种软更新的方法对战略进行更新，更新公式为 $\pi_{new} = (1-\alpha)\pi_{old} + \alpha\pi’ \ \ \ \ \ \ \ \ (3.4)$ 其间 $new\pi_{new}$ 就表明更新之后的战略， $\alpha$ 为更新步长。

部分读者在阅读到这儿的时分可能会产生以下疑问：为什么不直接把 $′\pi’$ 直接当作更新之后的战略呢？ $Lold(′)≥Lold(old)L_{\pi_{old}}(\pi’)\ge L_{\pi_{old}}(\pi_{old})$ 不是能够推导出 $(′)≥(old)\eta(\pi’)\ge\eta(\pi_{old})$ 吗？

回答：由于这是一种迭代更新方法， $′\pi’$ 只是给出了一个能够优化 $old\pi_{old}$ 的方向，咱们要做的是将 $old\pi_{old}$ 向 $′\pi’$ 的那个方向迭代，而不是直接将 $′\pi’$ 当作更新之后的战略；别的 $Lold(′)≥Lold(old)L_{\pi_{old}}(\pi’)\ge L_{\pi_{old}}(\pi_{old})$ 并不能够直接推导出 $(′)≥(old)\eta(\pi’)\ge\eta(\pi_{old})$ ，由于 $′\pi’$ 并不必定在 $old\pi_{old}$ 的邻近!

1.3 TRPO算法的推出

再来回忆一下咱们开端的意图：找到一个适宜的步长，使得每一个更新得到的新的战略 $new\pi_{new}$ 要比更新前的战略 $old\pi_{old}$ 好。那么运用软更新方法得到的战略 $new\pi_{new}$ 是否比更新前的战略 $old\pi_{old}$ 好呢，换句话说，是否建立 $(new)≥(old)\eta(\pi_{new})\ge \eta(\pi_{old})$ 呢？其实 $′=argmax′Lold(′)\pi’ = argmax_{\pi’}L_{\pi_{old}}(\pi’)$ 给咱们的优化提供了方向，咱们的要害就在于怎么挑选适宜的步长使得更新之后的战略必定是比更新之前的战略好。再考虑一下，其实必定有 $Lold(new)≥Lold(old)L_{\pi_{old}}(\pi_{new}) \ge L_{\pi_{old}}(\pi_{old})$ , 由于 $new\pi_{new}$ 是从 $old\pi_{old}$ 朝着 $′\pi’$ 的方向迭代的,而且 $Lold(′)≥Lold(old)L_{\pi_{old}}(\pi’)\ge L_{\pi_{old}}(\pi_{old})$ 。再回想一下前面咱们说：在 $=old\pi = \pi_{old}$ 邻近， $Lold()≥Lold(old)L_{\pi_{old}}(\pi)\ge L_{\pi_{old}}(\pi_{old})$ 等价于 $()≥(old)\eta(\pi)\ge \eta(\pi_{old})$ , 所以咱们只需要把 $new\pi_{new}$ 束缚在 $old\pi_{old}$ 邻近即可，能够经过放在赏罚项或许束缚上进行束缚。怎么束缚两个战略的差异性呢，能够运用两个战略的KL散度： $DKLmax(old,new)D_{KL}^max(\theta_{old}, \theta_{new})$ ，由于KL散度是用来度量两个概率分布类似度的目标。其实从这个剖析咱们就能够得到最终的TRPO算法了，原论文中给出了严格的数学推导，咱们大约介绍一下思路(能够不看）：

设 $new\pi_{new}$ 是依照更新公式 $(3.4)$ 得到的新战略，从论文[1]中能够得到下面不等式建立：

(new)≥Lold(new)−2(1−)22(3.5)\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new}) – \frac{2\epsilon \gamma}{(1-\gamma)^2}\alpha^2 \ \ \ \ \ \ \ (3.5)

其间 $=maxs∣Ea∼′(a∣s)[A(s,a)]∣\epsilon = max_s|\mathbb{E}_{a\sim \pi'(a|s)}[A_\pi(s,a)]|$ 。

咱们能够令 $=DTVmax(old,new)\alpha = D^{max}_{TV}(\pi_{old}, \pi_{new})$ , 然后建立：

(new)≥Lold(new)−4(1−)22\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new}) – \frac{4\epsilon\gamma}{(1-\gamma)^2}\alpha^2

其间 $=maxs,a∣A(s,a)∣\epsilon = max_{s,a}|A_\pi(s,a)|$ 。再根据不等式： $DTV(p∣∣q)2≤DKL(p∣∣q)D_{TV}(p||q)^2\le D_{KL}(p||q)$ ,令 $DKLmax(,~)=maxsDKL((⋅∣s)∣∣~(⋅∣s))D_{KL}^{max}(\pi, \tilde{\pi}) = max_s D_{KL}(\pi(|s)||\tilde{\pi}(|s))$ 建立：

(~)≥L(~)−CDKLmax(,~)\eta(\tilde{\pi}) \ge L_\pi(\tilde{\pi}) – CD_{KL}^{max}(\pi, \tilde{\pi})

其间 $\frac{4\epsilon\gamma}{(1-\gamma)^2}$ 。

给出下面战略更新算法：

假定咱们根据上面这个算法得出一个战略序列 $0,1,…\pi_0, \pi_1, \ldots$ ，下面证明该战略序列是越来越好的，即 $(0)≤(1)≤…\eta(\pi_0)\le\eta(\pi_1)\le\ldots$ 。

令 $Mi()=Li()−CDKLmax(i,)M_i(\pi) = L_{\pi_i}(\pi) – CD_{KL}^{max}(\pi_i, \pi)$ , 则建立：

(i+1)≥Mi(i+1)\eta(\pi_{i+1})\ge M_i(\pi_{i+1})

(i)=Mi(i)\eta(\pi_i) = M_i(\pi_i)

等式建立是由于当 $~=\tilde{\pi} = \pi$ 时， $DKLmax(,~)=0D_{KL}^{max}(\pi, \tilde{\pi}) = 0$ 。

所以建立： $(i+1)−(i)≥Mi(i+1)−M(i)\eta(\pi_{i+1}) – \eta(\pi_i) \ge M_i(\pi_{i+1}) – M(\pi_i)$

所以在第i次迭代时, $Mi()M_i(\pi)$ 能够作为 $()\eta(\pi)$ 的代替函数，然后得到的战略序列是越来越好的。然后每一个更新往后的战略 $new\pi_{new}$ 都好于更新前的战略 $old\pi_{old}$ 。意图到达。假如这个数学证明没看懂没有关系，能够直接经过之前的言语剖析了解TRPO算法。

为了方便将 $old\pi_{\theta_{old}}$ 写作 $old\theta_{old}$ , 在接下来的剖析中，咱们都考虑带有参数 $\theta$ 的战略 $(a∣s)\pi_\theta(a|s)$ 。经过之前的剖析，然后咱们能够经过优化下面的式子来到达优化 $()\eta(\pi)$ 的意图：

maximize[Lold()−CDKLmax(old,)]maximize_\theta\ \ [L_{\theta_{old}}(\theta) – CD_{KL}^max(\theta_{old}, \theta)]

可是有C作为赏罚系数，会导致每次的 $DKLmax(old,)D_{KL}^max(\theta_{old},\theta)$ 的值特别小，然后导致更新的脚步很小，下降更新速度，所以咱们考虑将赏罚项变为束缚项:

maximizeLold()subjecttoDKLmax(old,)≤\begin{aligned} maximize_\theta&\ \ L_{\theta_{old}}(\theta)\\ subject\ \ to&\ \ D_{KL}^{max}(\theta_{old}, \theta)\le \delta \end{aligned}

用言语了解便是在以 $0\theta_0$ 为球（圆）心，以 $\delta$ 为半径的区域中搜索能够进步 $Lold()L_{\pi_{old}}(\pi)$ （等价于进步 $()\eta(\pi)$ ）的战略 $\pi$ 。这便是TRPO算法。

留意到 $Lold()=(old)+∑sold(s)∑a(a∣s)Aold(s,a)L_{\theta_{old}}(\theta) = \eta(\theta_{old}) + \sum\limits_s\rho_{\theta_{old}}(s)\sum\limits_a\pi_\theta(a|s)A_{\theta_{old}}(s,a)$ , 其间 $(old)\eta(\theta_{old})$ 相关于 $\theta$ 来说是常数，能够去掉，因而上述公式变为

maximize∑sold∑a(a∣s)Aold(s,a)subjecttoDKLmax(old,)≤\begin{aligned} maximize_\theta&\ \ \sum\limits_s\rho_{\theta_{old}}\sum\limits_a\pi_\theta(a|s)A_{\theta_{old}}(s,a)\\ subject\ \ to&\ \ D_{KL}^{max}(\theta_{old}, \theta)\le \delta \end{aligned}

1.4 重要度采样

在最开端推导公式 $(3.1)$ 的时分，咱们当时说了等号右边的 $s, a$ 是根据战略 $~\tilde{\pi}$ 采样的，可是在实在世界中，由于在更新前 $~\tilde{\pi}$ 是不知道的，所以咱们没法根据 $~\tilde{\pi}$ 采样，所以咱们考虑运用重要度采样，假定咱们运用战略 $q (a ∣ s)$ 进行采样，那么咱们的优化函数要有所改变：

∑sold(s)∑a(a∣s)A(s,a)=∑sold(s)∑aq(a∣s)(a∣s)q(a∣s)Aold(s,a)=∑sold(s)Ea∼q[(a∣s)q(a∣s)Aold(s,a)]=Es∼old,a∼q[Aold(s,a)]\begin{aligned} \sum\limits_s\rho_{\theta_{old}}(s)\sum\limits_a\pi(a|s)A_\pi(s,a)&=\sum\limits_s\rho_{\theta_{old}}(s)\sum\limits_aq(a|s)\frac{\pi_\theta(a|s)}{q(a|s)}A_{\theta_{old}}(s,a)\\ &=\sum\limits_s\rho_{\theta_{old}}(s)\mathbb{E}_{a\sim q}[\frac{\pi_\theta(a|s)}{q(a|s)}A_{\theta_{old}}(s,a)]\\ &=\mathbb{E}_{s\sim \rho_{\theta_{old}},a\sim q}[A_{\theta_{old}}(s,a)] \end{aligned}

所以最终TRPO的更新算法变为：

maximizeEs∼old,a∼q[Aold(s,a)]subjecttoDKL(old,)≤\begin{aligned} maximize_\theta&\ \ \mathbb{E}_{s\sim \rho_{\theta_{old}},a\sim q}[A_{\theta_{old}}(s,a)]\\ subject\ \ to&\ \ D_{KL}(\theta_{old}, \theta)\le \delta \end{aligned}

留意：这儿的 $s$ 仍是服从 $old\rho_{\theta_{old}}$ 的概率，即 $old(s)\rho_{\theta_{old}}(s)$ 中的动作 $a$ 的概率仍是根据战略 $old\theta_{old}$ ！！这儿是咱们比较容易了解过错的当地，误以为 $s$ 公式中的 $a$ 是根据采样战略 $q$ 的。而且这儿的采样概率 $q (a ∣ s)$ 能够是恣意的，只用来采样罢了！！后来TRPO算法在做的时分直接将 $old(a∣s)\pi_{\theta_{old}}(a|s)$ 当作采样战略 $q (a ∣ S)$ 。

2. PPO算法的理论剖析

2.1 TRPO算法的局限性

可是采样战略 $q$ 真的能够恣意吗？太恣意会呈现什么问题呢？咱们来看下面这个比如：

如图所示， $p (x)$ 是实在的分布概率， $q (x)$ 是采样时分运用的概率，显然二者的差异很大。设曲线 $p (x), q (x), f (x)$ 交点的横坐标为 $x = 0$ ，所以在采样的时分，咱们大多采到的是 $x > 0$ 的点，由于 $q (x)$ 在正半轴的概率值更大，所以咱们最终得到的 $Ex[f(x)]\mathbb{E}_x[f(x)]$ 的值为正值，可是实在的情况是， $x$ 大多分布在负半轴，实在的 $Ex[f(x)]\mathbb{E}_x[f(x)]$ 应该为负值，这便是由于采样概率和实在概率距离过大导致的误差。

所以咱们还得束缚采样战略 $q (a ∣ s)$ 和更新战略 $(a∣s)\pi(a|s)$ 的类似度，使得他们尽可能的相像，这便是PPO算法要做的工作了。

2.2 PPO算法

榜首种思路：记住咱们在剖析TRPO算法中，运用了KL散度束缚了战略 $(a∣s)\pi_{\theta}(a|s)$ 和战略 $old（a∣s)\pi_{\theta_{old}}（a|s)$ 的类似度，使得他们两个的距离不能太大，所以咱们考虑直接用 $old(a∣s)\pi_{\theta_{old}}(a|s)$ 当作采样战略 $q (a ∣ s)$ ，所以这就同时束缚了采样战略和战略 $(a∣s)\pi_\theta(a|s)$ 的距离，一箭双雕，这就得到了PPO算法：

maximizeEs,a∼old[Aold(s,a)−DKL(old,)]\begin{aligned} maximize_\theta&\ \ \mathbb{E}_{s,a\sim \theta_{old}}[A_{\theta_{old}}(s,a) – \beta D_{KL}(\theta_{old}, \theta)] \end{aligned}

留意到这儿的 $(s)\rho(s)$ 公式中的 $a$ 的概率也是根据战略 $old\theta_{old}$ 的。

2.3 PPO2算法

第二种思路：在优化公式中对 $q (a ∣ s)$ 和 $(a∣s)\pi_{\theta}(a|s)$ 进行束缚，选用了切断函数，当两个函数的比值过大时，用 $1+1+\epsilon$ 切断，当两个函数的比值过小时，选用 $1−1-\epsilon$ 切断。PPO2算法如下：

maximizeEs∼old,a∼q(a∣s)min((a∣s)q(a∣s)Aold(s,a),clip((a∣s)q(a∣s),1−,1+)Aold(a∣s))\begin{aligned} maximize_\theta&\ \ \mathbb{E}_{s\sim \rho_{\theta_{old}},a\sim q(a|s)}min(\frac{\pi_\theta(a|s)}{q(a|s)}A_{\theta_{old}}(s,a), clip(\frac{\pi_\theta(a|s)}{q(a|s)}, 1-\epsilon, 1+\epsilon)A_{\theta_{old}}(a|s)) \end{aligned}

其实这儿的采样战略 $q (a ∣ s)$ 是能够运用恣意采样战略的，可能是为了作用更好，在PPO的论文中，仍然依照TRPO算法的方法，将 $old(a∣s)\pi_{\theta_{old}}(a|s)$ 作为采样战略 $q (a ∣ s)$ :

maximizeEs,a∼oldmin((a∣s)old(a∣s)Aold(s,a),clip((a∣s)old(a∣s),1−,1+)Aold(a∣s))\begin{aligned} maximize_\theta&\ \ \mathbb{E}_{s,a\sim \theta_{old}}min(\frac{\pi_\theta(a|s)}{\pi_{\theta_{old}}(a|s)}A_{\theta_{old}}(s,a), clip(\frac{\pi_\theta(a|s)}{\pi_{\theta_{old}}(a|s)}, 1-\epsilon, 1+\epsilon)A_{\theta_{old}}(a|s)) \end{aligned}

3.参考文献

[1] Kakade,Sham and Langford,John. Approximately optimal approximate reinfocement learning(citeseerx.ist.psu.edu/viewdoc/dow…). In ICML, volume2,pp.267-247,2002.

[2] R.Sutton, D.McAllester, S.Singh, and Y.Mansour. Policy gradient methods for reinforcement learning with function approximation(homes.cs.washington.edu/~todorov/co…). Neural Information Processing Systemsm,13,2000.

[3] J.Schulman, S.Levine, P.Moritz, M.I.Jordan, and P.Abbeel.”Trust region policy optimization”(arxiv.org/abs/1502.05…). In: CoRR, ans/1502.05477(2015).

[4] Proximal Policy Optimization Algorithms](arxiv.org/abs/1707.06…), Schulman et al. 2017

4.附录证明

4.1 证明： $(~)=()+Es0,a0,…∼~[∑t=0∞tA(st,at)]\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)]$

$()=Es0,a0,…[∑t=0∞tr(st)]=E[V(s0)]\eta(\pi) = \mathbb{E}_{s_0, a_0,\ldots}[\sum\limits_{t=0}^{\infty}\gamma^t r(s_t)] = \mathbb{E}[V_\pi(s_0)]$

Es0,a0,…∼~[∑t=0∞tA(st,at)]=Es0,a0,…∼~[∑t=0∞t(Q(st,at)−V(st))]=Es0,a0,…∼~[∑t=0∞t(r(st)+V(st+1)−V(st))]=Es0,a0,…∼~[−V(s0)+∑t=0∞tr(st)]=−Es0[V(s0)]+Es0,a0,…∼~[∑t=0∞tr(st)]=−()+(~)\begin{aligned} \mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)] &=\mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t(Q_\pi(s_t,a_t)-V_\pi (s_t))]\\ &=\mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t(r(s_t)+\gamma V_\pi (s_{t+1})-V_\pi (s_t))]\\ &=\mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[-V_\pi(s_0) + \sum\limits_{t=0}^\infty\gamma^t r(s_t)]\\ &=-\mathbb{E}_{s_0}[V_\pi(s_0)] + \mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t r(s_t)]\\ &=-\eta(\pi) + \eta(\tilde{\pi}) \end{aligned}

4.2 证明： $(~)=()+∑s~(s)∑a~(a∣s)A(s,a)\eta(\tilde{\pi}) =\eta(\pi) + \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_{\pi}(s,a)$

(~)=()+Es0,a0,…∼~[∑t=0∞tA(st,at)]=()+∑t=0∞∑sP(st=s∣~)∑a~(a∣s)tA(s,a)=()+∑s∑t=0∞tP(st=s∣~)∑a~(a∣s)A(s,a)=()+∑s~(s)∑a~(a∣s)A(s,a)\begin{aligned} \eta(\tilde{\pi}) &= \eta(\pi) + \mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty \gamma^t A_{\pi}(s_t,a_t)]\\ &=\eta(\pi) + \sum\limits_{t=0}^\infty\sum\limits_sP(s_t=s|\tilde{\pi})\sum\limits_a\tilde{\pi}(a|s)\gamma^tA_\pi(s,a)\\ &=\eta(\pi) + \sum\limits_s\sum\limits_{t=0}^\infty\gamma^tP(s_t=s|\tilde{\pi})\sum\limits_a\tilde{\pi}(a|s)A_\pi(s,a)\\ &=\eta(\pi) + \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_{\pi}(s,a) \end{aligned}

4.3 证明：

{L0(0)=(0)∇L0()∣=0=∇()∣=0\left\{ \begin{aligned} L_{\pi_{\theta_0}}(\pi_{\theta_0})& = \eta(\pi_{\theta_0})\\ \nabla_{\theta}L_{\pi_{\theta_0}}(\pi_\theta)|_{\theta=\theta_0}& = \nabla_\theta\eta(\pi_\theta)|_{\theta=\theta_0}\\ \end{aligned} \right.

$L(~)=()+∑s(s)∑a~(a∣s)A(s,a)L_\pi(\tilde{\pi}) = \eta(\pi) + \sum\limits_s\rho_\pi(s)\sum\limits_a\tilde{\pi}(a|s)A_\pi(s,a)$ 当 $~=\tilde{\pi} = \pi$ 时： $L()=()+∑s(s)∑a~(a∣s)A(s,a)L_\pi(\pi) = \eta(\pi) + \sum\limits_s\rho_\pi(s)\sum\limits_a\tilde{\pi}(a|s)A_\pi(s,a)$ 关于每一个 $s$ 有

∑a(a∣s)A(s,a)=Ea[A(s,a)]=Ea[Q(s,a)−V(s)]=Ea[Q(s,a)−Ea[Q(s,a)]]=E[Q(s,a)]−Ea[Ea[Q(s,a)]]=E[Q(s,a)]−E[Q(s,a)]=0\begin{aligned} &\sum\limits_a\pi(a|s)A_\pi(s,a)\\ =&\mathbb{E}_a[A_\pi(s,a)]\\ =&\mathbb{E}_a[Q_\pi(s,a) – V_\pi(s)]\\ =&\mathbb{E}_a[Q_\pi(s,a) – \mathbb{E}_a[Q_\pi(s,a)]]\\ =&\mathbb{E}[Q_\pi(s,a)] – \mathbb{E}_a[\mathbb{E}_a[Q_\pi(s,a)]]\\ =&\mathbb{E}[Q_\pi(s,a)] – \mathbb{E}[Q_\pi(s,a)]\\ =& 0 \end{aligned}

上述推导进程中第五行到第六行的推导进程中的 $Ea[Ea[Q(s,a)]]\mathbb{E}_a[\mathbb{E}_a[Q_\pi(s,a)]]$ = $Ea[Q(s,a)]\mathbb{E}_a[Q_\pi(s,a)]$ 是由于希望的希望等于希望,从另一个角度来看这个等式， $Ea[Q(s,a)]\mathbb{E}_a[Q_\pi(s,a)]$ 的结果与a无关，相当于一个常数，所以再对a求希望的话，相当于对常数求希望，等于常数自身。

再证明公式 $(3.4)$ 的第二个等式： $∇L0()∣=0=∇()∣=0\nabla_{\theta}L_{\pi_{\theta_0}}(\pi_\theta)|_{\theta=\theta_0} = \nabla_\theta\eta(\pi_\theta)|_{\theta=\theta_0}$

咱们有: $L0()=(0)+∑s0(s)∑a(a∣s)A0(s,a)L_{\pi_{\theta_0}}(\pi_\theta) = \eta(\pi_{\theta_0}) + \sum\limits_s\rho_{\pi_{\theta_0}}(s)\sum\limits_a\pi_\theta(a|s)A_{\pi_{\theta_0}}(s,a)$ 两头对 $\theta$ 求导（留意任何和 $0\theta_0$ 有关的式子在对 $\theta$ 求导的时分都视为常数）得: $∇L0()=∑s0(s)∑a∇(a∣s)A0(s,a)\nabla_\theta L_{\pi_{\theta_0}}(\pi_\theta) = \sum\limits_s\rho_{\pi_{\theta_0}}(s)\sum\limits_a\nabla_\theta\pi_\theta(a|s)A_{\pi_{\theta_0}}(s,a)$ 然后建立： $∇L0()∣=0=∑s0(s)∑a∇(a∣s)∣=0A0(s,a)\nabla_\theta L_{\pi_{\theta_0}}(\pi_\theta)|\theta = \theta_0 = \sum\limits_s\rho_{\pi_{\theta_0}}(s)\sum\limits_a\nabla_\theta\pi_\theta(a|s)|_{\theta = \theta_0}A_{\pi_{\theta_0}}(s,a)$

由论文[2]可知： $∇()=∑s(s)∑a∇(a∣s)Q(s,a)\nabla_\theta\eta(\pi_\theta) = \sum\limits_s\rho_{\pi_\theta}(s)\sum\limits_a\nabla_\theta\pi_\theta(a|s)Q_{\pi_\theta}(s,a)$

又由于

∑s(s)∑a∇(a∣s)V(s)=∑s(s)V(s)∑a∇(a∣s)=∑s(s)V(s)∇∑a(a∣s)=0\begin{aligned} &\sum\limits_s\rho_{\pi_\theta}(s)\sum\limits_a\nabla_\theta\pi_\theta(a|s)V_{\pi_\theta}(s)\\ =&\sum\limits_s\rho_{\pi_\theta}(s)V_{\pi_\theta}(s)\sum\limits_a\nabla_\theta\pi_\theta(a|s)\\ =&\sum\limits_s\rho_{\pi_\theta}(s)V_{\pi_\theta}(s)\nabla_\theta\sum\limits_a\pi_\theta(a|s)\\ =&0 \end{aligned}

上述推导进程中榜首行到第二行是由于 $V(s)V_{\pi_\theta}(s)$ 与 $a$ 无关，所以能够说到 $∑a\sum\limits_a$ 的前面。第二个式子到第三个式子是由于求和的导数等于导数的求和。第三个式子到第四个式子是由于关于每个 $s$ 来说都建立： $∑a(a∣s)=1\sum\limits_a\pi_\theta(a|s)=1$ ,然后1对 $\theta$ 求导等于0，即 $∇∑a(a∣s)=∇1=0\nabla_\theta\sum\limits_a\pi_\theta(a|s) = \nabla_\theta1 = 0$ 。

所以可得：

∇()=∑s(s)∇(a∣s)Q(s,a)=∑s(s)∇(a∣s)[Q(s,a)−V(s)]=∑s(s)∇(a∣s)A(s,a)\begin{aligned} \nabla_\theta\eta(\pi_\theta)&=\sum\limits_s\rho_{\pi_\theta}(s)\nabla_\theta\pi(a|s)Q_\pi(s,a)\\ &=\sum\limits_s\rho_{\pi_\theta}(s)\nabla_\theta\pi_\theta(a|s)[Q_\pi(s,a) – V_\pi(s)]\\ &=\sum\limits_s\rho_{\pi_\theta}(s)\nabla_\theta\pi_\theta(a|s)A_{\pi_\theta}(s,a) \end{aligned}

然后建立：

∇()∣=0=∑s0(s)∇(a∣s)∣=0A0(s,a)=∇L0()∣=0\begin{aligned} \nabla_\theta\eta(\pi_\theta)|_{\theta = \theta_0}&=\sum\limits_s\rho_{\pi_{\theta_0}}(s)\nabla_{\theta}\pi_\theta(a|s)|_{\theta = \theta_0}A_{\pi_{\theta_0}}(s,a) = \nabla_\theta L_{\pi_{\theta_0}}(\pi_\theta)|_{\theta=\theta_0} \end{aligned}

命题得证。

咱们是行者AI，咱们在“AI＋游戏”中不断前行。

前往公众号【行者AI】，和咱们一起探讨技术问题吧！

从TRPO到PPO（理论分析与数学证明）

导言

1.TRPO的理论剖析

1.1 不同战略的长时间希望扣头奖赏之间的关系

1.2 代替函数的建立

1.3 TRPO算法的推出

1.4 重要度采样

2. PPO算法的理论剖析

2.1 TRPO算法的局限性

2.2 PPO算法

2.3 PPO2算法

3.参考文献

4.附录证明

4.1 证明：(~)=()+Es0,a0,…∼~[∑t=0∞tA(st,at)]\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)](~)=()+Es0​,a0​,…∼~​[t=0∑∞​tA​(st​,at​)]

4.2 证明：(~)=()+∑s~(s)∑a~(a∣s)A(s,a)\eta(\tilde{\pi}) =\eta(\pi) + \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_{\pi}(s,a)(~)=()+s∑​~​(s)a∑​~(a∣s)A​(s,a)

4.3 证明：

相关文章

Android OkHttp使用过程中的一些经验总结

带你可视化理解go内存

通过build configuration配置多环境

Jetpack Compose Material3 组件之 DatePicker（日期选择）

作者信息

4.1 证明： $(~)=()+Es0,a0,…∼~[∑t=0∞tA(st,at)]\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)]$

4.2 证明： $(~)=()+∑s~(s)∑a~(a∣s)A(s,a)\eta(\tilde{\pi}) =\eta(\pi) + \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_{\pi}(s,a)$