文档维护:Arvin

网页部署:Arvin

近端策略优化(PPO)算法

重要性采样

基于策略的方法可以分为**同策略(on-policy)异策略(off-policy)**方法。在强化学习中,如果要学习的智能体和与环境交互的智能体是相同的,我们称为同策略。如果是不同的,我们称为异策略。

为什么我们会想要考虑异策略?让我们回忆一下策略梯度。策略梯度是同策略的算法,因为在策略梯度中,我们需要一个智能体、一个策略和一个演员。演员去与环境交互搜集数据,搜集很多的轨迹 τ\tau,根据搜集到的数据按照策略梯度的公式更新策略的参数,所以策略梯度是一个同策略的算法。PPO是策略梯度的变形,它是现在 OpenAI 默认的强化学习算法。

Rˉθ=Eτpθ(τ)[R(τ)logpθ(τ)]\nabla \bar{R}_{\theta}=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[R(\tau) \nabla \log p_{\theta}(\tau)\right]

问题在于上式的 Eτpθ(τ)\mathbb{E}_{\tau \sim p_{\theta}(\tau)} 是对策略 πθ\pi_{\theta} 采样的轨迹 τ\tau 求期望。一旦更新了参数,从 θ\theta 变成 θ\theta' ,概率 pθ(τ)p_\theta(\tau) 就不对了,之前采样的数据也不能用了。所以策略梯度是一个会花很多时间来采样数据的算法,其大多数时间都在采样数据。智能体与环境交互以后,接下来就要更新参数。我们只能更新参数一次,然后就要重新采样数据, 才能再次更新参数。这显然是非常花时间的,所以我们想要从同策略变成异策略,这样就可以用另外一个策略πθ\pi_{\theta'}、另外一个演员θ\theta' 与环境交互(θ\theta' 被固定了),用 θ\theta' 采样到的数据去训练 θ\theta。假设我们可以用 θ\theta' 采样到的数据去训练 θ\theta,我们可以多次使用 θ\theta' 采样到的数据,可以多次执行梯度上升(gradient ascent),可以多次更新参数, 都只需要用同一批数据。因为假设 θ\theta 有能力学习另外一个演员 θ\theta' 所采样的数据,所以θ\theta' 只需采样一次,并采样多一点的数据,让 θ\theta 去更新很多次,这样就会比较有效率。

重要性采样:对于一个随机变量,我们通常用概率密度函数来刻画该变量的概率分布特性。具体来说,给定随机变量的一个取值,可以根据概率密度函数来计算该值对应的概率(密度)。反过来,也可以根据概率密度函数提供的概率分布信息来生成随机变量的一个取值,这就是采样。因此,从某种意义上来说,采样是概率密度函数的逆向应用。与根据概率密度函数计算样本点对应的概率值不同,采样过程往往没有那么直接,通常需要根据待采样分布的具体特点来选择合适的采样策略。

假设我们有一个函数 f(x)f(x),要计算从分布 pp 采样 xx,再把 xx 代入 ff ,得到 f(x)f(x)。我们该怎么计算 f(x)f(x) 的期望值呢?假设我们不能对分布 pp 做积分,但可以从分布 pp 采样一些数据 xix^i。把 xix^i 代入 f(x)f(x),取它的平均值,就可以近似 f(x)f(x) 的期望值。

现在有另外一个问题,假设我们不能从分布 pp 采样数据,只能从另外一个分布 qq 采样数据xxqq 可以是任何分布。如果我们从 qq 采样 xix^i,就不能使用下式。因为式下式是假设 xx 都是从 pp 采样出来的。

Exp[f(x)]1Ni=1Nf(xi)\mathbb{E}_{x \sim p}[f(x)] \approx \frac{1}{N} \sum_{i=1}^N f(x^i)

所以我们做一个修正,期望值 Exp[f(x)]\mathbb{E}_{x \sim p}[f(x)] 就是 f(x)p(x)dx\int f(x) p(x) \mathrm{d}x,我们对其做如下的变换:

f(x)p(x)dx=f(x)p(x)q(x)q(x)dx=Exq[f(x)p(x)q(x)] \int f(x) p(x) \mathrm{d}x=\int f(x) \frac{p(x)}{q(x)} q(x) \mathrm{d}x=\mathbb{E}_{x \sim q}[f(x){\frac{p(x)}{q(x)}}]

就可得

Exp[f(x)]=Exq[f(x)p(x)q(x)]\mathbb{E}_{x \sim p}[f(x)]=\mathbb{E}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]

我们就可以写成对 qq 里面所采样出来的 xx 取期望值。我们从 qq 里面采样 xx,再计算 f(x)p(x)q(x)f(x) \frac{p(x)}{q(x)},再取期望值。所以就算我们不能从 pp 里面采样数据,但只要能从 qq 里面采样数据,就可以计算从 pp 采样 xx 代入 ff 以后的期望值。

因为是从 qq 采样数据,所以我们从 qq 采样出来的每一笔数据,都需要乘一个重要性权重(importance weight) p(x)q(x)\frac{p(x)}{q(x)} 来修正这两个分布的差异。q(x)q(x) 可以是任何分布,唯一的限制就是 q(x)q(x) 的概率是 0 的时候,p(x)p(x) 的概率不为 0,不然会没有定义。假设 q(x)q(x) 的概率是 0 的时候,p(x)p(x) 的概率也都是 0,p(x)p(x) 除以 q(x)q(x)是有定义的。所以这个时候我们就可以使用重要性采样,把从 pp 采样换成从 qq 采样。

重要性采样有一些问题。虽然我们可以把 pp 换成任何的 qq。但是在实现上, ppqq 的差距不能太大。差距太大,会有一些问题。比如,虽然式(5.3)成立(式(5.3)左边是 f(x)f(x) 的期望值,它的分布是 pp,式(5.3)右边是 f(x)p(x)q(x)f(x) \frac{p(x)}{q(x)} 的期望值,它的分布是 qq),但如果不是计算期望值,而是计算方差,Varxp[f(x)]\operatorname{Var}_{x \sim p}[f(x)]Varxq[f(x)p(x)q(x)]\operatorname{Var}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right] 是不一样的。两个随机变量的平均值相同,并不代表它们的方差相同。

我们可以将 f(x)f(x)f(x)p(x)q(x)f(x) \frac{p(x)}{q(x)} 代入方差的公式 Var[X]=E[X2](E[X])2\operatorname{Var}[X]=E\left[X^{2}\right]-(E[X])^{2},可得

Varxp[f(x)]=Exp[f(x)2](Exp[f(x)])2 \operatorname{Var}_{x \sim p}[f(x)]=\mathbb{E}_{x \sim p}\left[f(x)^{2}\right]-\left(\mathbb{E}_{x \sim p}[f(x)]\right)^{2}

Varxq[f(x)p(x)q(x)]=Exq[(f(x)p(x)q(x))2](Exq[f(x)p(x)q(x)])2=Exp[f(x)2p(x)q(x)](Exp[f(x)])2 \begin{aligned} \operatorname{Var}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right] &=\mathbb{E}_{x \sim q}\left[\left(f(x) \frac{p(x)}{q(x)}\right)^{2}\right]-\left(\mathbb{E}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right]\right)^{2} \\ &=\mathbb{E}_{x \sim p}\left[f(x)^{2} \frac{p(x)}{q(x)}\right]-\left(\mathbb{E}_{x \sim p}[f(x)]\right)^{2} \end{aligned}

Varxp[f(x)]\operatorname{Var}_{x \sim p}[f(x)]Varxq[f(x)p(x)q(x)]\operatorname{Var}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right] 的差别在于第一项是不同的, Varxq[f(x)p(x)q(x)]\operatorname{Var}_{x \sim q}\left[f(x) \frac{p(x)}{q(x)}\right] 的第一项多乘了p(x)q(x)\frac{p(x)}{q(x)},如果 p(x)q(x)\frac{p(x)}{q(x)} 差距很大,f(x)p(x)q(x)f(x)\frac{p(x)}{q(x)} 的方差就会很大。所以理论上它们的期望值一样,也就是,我们只要对分布pp采样足够多次,对分布qq采样足够多次,得到的结果会是一样的。但是如果我们采样的次数不够多,因为它们的方差差距是很大的,所以我们就有可能得到差别非常大的结果。

现在要做的就是把重要性采样用在异策略的情况中,把同策略训练的算法改成异策略训练的算法。如下式所示,之前我们用策略πθ\pi_{\theta}与环境交互,采样出轨迹τ\tau,计算 R(τ)logpθ(τ)R(\tau) \nabla \log p_{\theta}(\tau)。现在我们不用θ\theta与环境交互,假设有另外一个策略 πθ\pi_{\theta}',它就是另外一个演员,它的工作是做示范(demonstration)。

Rˉθ=Eτpθ(τ)[pθ(τ)pθ(τ)R(τ)logpθ(τ)]\nabla \bar{R}_{\theta}=\mathbb{E}_{\tau \sim p_{\theta^{\prime}(\tau)}}\left[\frac{p_{\theta}(\tau)}{p_{\theta^{\prime}}(\tau)} R(\tau) \nabla \log p_{\theta}(\tau)\right]

和上一章一样,其中R(τ)R(\tau)可以用优势函数Aθ(st,at)A^{\theta}(s_t, a_t)代替:

E(st,at)πθ[pθ(st,at)pθ(st,at)Aθ(st,at)logpθ(atnstn)]\mathbb{E}_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(s_{t}, a_{t}\right)}{p_{\theta^{\prime}}\left(s_{t}, a_{t}\right)} A^{\theta}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta}\left(a_{t}^{n} | s_{t}^{n}\right)\right]

且:

pθ(st,at)=pθ(atst)pθ(st)pθ(st,at)=pθ(atst)pθ(st)\begin{aligned} p_{\theta}\left(s_{t}, a_{t}\right)&=p_{\theta}\left(a_{t}|s_{t}\right) p_{\theta}(s_t) \\ p_{\theta'}\left(s_{t}, a_{t}\right)&=p_{\theta'}\left(a_{t}|s_{t}\right) p_{\theta'}(s_t) \end{aligned}

由于pθ(st)p_{\theta}(s_t)pθ(st)p_{\theta'}(s_t)由环境决定,所以假设两者一样就直接消掉。

E(st,at)πθ[pθ(atst)pθ(atst)Aθ(st,at)logpθ(atnstn)]\mathbb{E}_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} | s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right) \nabla \log p_{\theta}\left(a_{t}^{n} | s_{t}^{n}\right)\right]

近端策略优化

我们通过重要性采样将同策略变为异策略,但是重要性采样有一个问题:如果 pθ(atst)p_{\theta}\left(a_{t} | s_{t}\right)pθ(atst)p_{\theta'}\left(a_{t} | s_{t}\right) 相差太多,即这两个分布相差太多,重要性采样的结果就会不好。

所以我们会添加一个约束,这个约束是θ\thetaθ\theta'输出的动作的KL散度(KL divergence),是用来衡量两个分布的“距离”即相似程度。

JPPOθ(θ)=Jθ(θ)βKL(θ,θ)Jθ(θ)=E(st,at)πθ[pθ(atst)pθ(atst)Aθ(st,at)](5.6)\begin{aligned} &J_{\mathrm{PPO}}^{\theta^{\prime}}(\theta)=J^{\theta^{\prime}}(\theta)-\beta \mathrm{KL}\left(\theta, \theta^{\prime}\right) \\ &J^{\theta^{\prime}}(\theta)=\mathbb{E}_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right] \end{aligned} \tag{5.6}

PPO有一个前身:信任区域策略优化

JTRPOθ(θ)=E(st,at)πθ[pθ(atst)pθ(atst)Aθ(st,at)],KL(θ,θ)<δ\begin{aligned} J_{\mathrm{TRPO}}^{\theta^{\prime}}(\theta)=\mathbb{E}_{\left(s_{t}, a_{t}\right) \sim \pi_{\theta^{\prime}}}\left[\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{\prime}}\left(a_{t} | s_{t}\right)} A^{\theta^{\prime}}\left(s_{t}, a_{t}\right)\right],\mathrm{KL}\left(\theta, \theta^{\prime}\right)<\delta \end{aligned}

TRPO 与 PPO 不一样的地方是约束所在的位置不一样,PPO 直接把约束放到要优化的式子里面,我们就可以用梯度上升的方法去最大化式(5.6)。但 TRPO 是把 KL 散度当作约束,它希望 θ\thetaθ\theta' 的 KL 散度小于 δ\delta。如果我们使用的是基于梯度的优化,有约束是很难处理的。TRPO 是很难处理的,因为它把 KL 散度约束当作一个额外的约束,没有放在目标(objective)里面,所以它很难计算。因此我们一般就使用 PPO,而不使用 TRPO 。PPO 与 TRPO 的性能差不多,但 PPO 在实现上比 TRPO 容易得多。

PPO 算法有两个主要的变种:近端策略优化惩罚(PPO-penalty)近端策略优化裁剪(PPO-clip)

KL散度

参考链接:Kullback-Leibler(KL)散度介绍

Kullback-Leibler散度通常称为KL散度,是一种比较两个概率分布的方法。通常在概率和统计中,我们会用更简单的近似分布来代替观察到的数据或复杂的分布。KL散度可以帮助我们衡量在选择近似值时损失了多少信息。

分布熵

熵是信息论中的概念,主要用来量化数据中有多少信息

H=i=1Np(xi)logp(xi)H=-\sum_{i=1}^{N} p(x_i)\log{p(x_i)}

如果计算中使用log2\log_2,则单位是比特bit;使用log3\log_3,单位为Tet;使用loge\log_e,单位为Nat;使用log10\log_10,单位为Hart;是因为我们的数字电路设计是基于布尔逻辑的,布尔逻辑中只有两种状态,所以一般用比特。

KL散度

KL散度是对熵公式的略微修改。不仅有原来的概率分布pp,还有近似分布qq

DKL(pq)=i=1Np(xi)(logp(xi)logq(xi))D_{KL}(p||q)=\sum_{i=1}^{N}p(x_i)(logp(x_i)-logq(x_i))

即:

DKL(pq)=E[logp(xi)logq(xi)]D_{KL}(p||q)=E[logp(x_i)-logq(x_i)]

更常见的写法为:

DKL(pq)=i=1Np(xi)(logp(xi)q(xi))D_{KL}(p||q)=\sum_{i=1}^{N}p(x_i)(log\frac{p(x_i)}{q(x_i)})

近端策略优化惩罚

我们来看一下 PPO1 算法,即近端策略优化惩罚算法。它先初始化一个策略的参数 θ0\theta^0。在每一个迭代里面,我们用前一个训练的迭代得到的演员的参数 θk\theta^k 与环境交互,采样到大量状态-动作对。根据 θk\theta^k 交互的结果,我们估测Aθk(st,at)A^{\theta^{k}}\left(s_{t}, a_{t}\right)。我们使用 PPO 的优化公式。但与原来的策略梯度不一样,原来的策略梯度只能更新一次参数,更新完以后,我们就要重新采样数据。但是现在不同,我们用 θk\theta^k 与环境交互,采样到这组数据以后,我们可以让 θ\theta 更新很多次,想办法最大化目标函数,如式(5.7)所示。这里面的 θ\theta 更新很多次也没有关系,因为我们已经有重要性采样,所以这些经验,这些状态-动作对是从 θk\theta^k 采样出来的也没有关系。θ\theta 可以更新很多次,它与 θk\theta^k 变得不太一样也没有关系,我们可以照样训练 θ\theta

JPPOθk(θ)=Jθk(θ)βKL(θ,θk)(5.7)J_{\mathrm{PPO}}^{\theta^{k}}(\theta)=J^{\theta^{k}}(\theta)-\beta \mathrm{KL}\left(\theta, \theta^{k}\right) \tag{5.7}

在 PPO 的论文里面还有一个自适应KL散度(adaptive KL divergence)。这里会遇到一个问题就,即β\beta 要设置为多少。这个问题与正则化一样,正则化前面也要乘一个权重,所以 KL 散度前面也要乘一个权重,但 β\beta 要设置为多少呢?我们有一个动态调整 β\beta 的方法。在这个方法里面,我们先设一个可以接受的 KL 散度的最大值。假设优化完式(5.7)以后,KL 散度的值太大,这就代表后面惩罚的项βKL(θ,θk)\beta \mathrm{KL}\left(\theta, \theta^{k}\right) 没有发挥作用,我们就把 β\beta 增大。另外,我们设一个 KL 散度的最小值。如果优化完式(5.7)以后,KL 散度比最小值还要小,就代表后面这一项的效果太强了,我们怕他只优化后一项,使θ\thetaθk\theta^k 一样,这不是我们想要的,所以我们要减小 β\betaβ\beta 是可以动态调整的,因此我们称之为自适应KL惩罚(adaptive KL penalty)。我们可以总结一下自适应KL惩罚:

  • 如果 KL(θ,θk)>KLmax\mathrm{KL}(\theta,\theta^k)>\mathrm{KL}_{\max},增大 β\beta
  • 如果 KL(θ,θk)<KLmin\mathrm{KL}(\theta,\theta^k)<\mathrm{KL}_{\min},减小 β\beta

近端策略优化惩罚可表示为

JPPOθk(θ)=Jθk(θ)βKL(θ,θk)Jθk(θ)(st,at)pθ(atst)pθk(atst)Aθk(st,at)\begin{aligned} &J_{\text{PPO}}^{\theta^{k}}(\theta)=J^{\theta^{k}}(\theta)-\beta \text{KL}\left(\theta, \theta^{k}\right) \\ &J^{\theta^{k}}(\theta) \approx \sum_{\left(s_{t}, a_{t}\right)} \frac{p_{\theta}\left(a_{t} \mid s_{t}\right)}{p_{\theta^{k}}\left(a_{t} \mid s_{t}\right)} A^{\theta^{k}}\left(s_{t}, a_{t}\right) \end{aligned}

近端策略优化裁剪

如果我们觉得计算 KL 散度很复杂,那么还有一个 PPO2算法,PPO2 即近端策略优化裁剪。近端策略优化裁剪的目标函数里面没有 KL 散度,其要最大化的目标函数为

JPPO2θk(θ)(st,at)min(pθ(atst)pθk(atst)Aθk(st,at),clip(pθ(atst)pθk(atst),1ε,1+ε)Aθk(st,at))\begin{aligned} J_{\mathrm{PPO2}}^{\theta^{k}}(\theta) \approx \sum_{\left(s_{t}, a_{t}\right)} \min &\left(\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{k}}\left(a_{t} | s_{t}\right)} A^{\theta^{k}}\left(s_{t}, a_{t}\right),\right.\\ &\left.\operatorname{clip}\left(\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{k}}\left(a_{t} | s_{t}\right)}, 1-\varepsilon, 1+\varepsilon\right) A^{\theta^{k}}\left(s_{t}, a_{t}\right)\right) \end{aligned}

其中,

  • 操作符(operator)min 是在第一项与第二项里面选择比较小的项。
  • 第二项前面有一个裁剪(clip)函数,裁剪函数是指,在括号里面有3项,如果第一项小于第二项,那就输出 1ε1-\varepsilon;第一项如果大于第三项,那就输出 1+ε1+\varepsilon
  • ε\varepsilon 是一个超参数,是我们要调整的,可以设置成 0.1 或 0.2 。

假设设置 ε=0.2\varepsilon=0.2,我们可得

clip(pθ(atst)pθk(atst),0.8,1.2) \operatorname{clip}\left(\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{k}}\left(a_{t} | s_{t}\right)}, 0.8, 1.2\right)

如果 pθ(atst)pθk(atst)\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{k}}\left(a_{t} | s_{t}\right)} 算出来小于 0.8,那就输出 0.8;如果算出来大于 1.2,那就输出1.2。

我们先要理解

clip(pθ(atst)pθk(atst),1ε,1+ε) \operatorname{clip}\left(\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{k}}\left(a_{t} | s_{t}\right)}, 1-\varepsilon, 1+\varepsilon\right)

下图的横轴代表 pθ(atst)pθk(atst)\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{k}}\left(a_{t} | s_{t}\right)},纵轴代表裁剪函数的输出。

  • 如果 pθ(atst)pθk(atst)\frac{p_{\theta}\left(a_{t} | s_{t}\right)}{p_{\theta^{k}}\left(a_{t} | s_{t}\right)} 大于1+ε1+\varepsilon,输出就是 1+ε1+\varepsilon
  • 如果小于 1ε1-\varepsilon,输出就是 1ε1-\varepsilon
  • 如果介于 1+ε1+\varepsilon ~{} 1ε1-\varepsilon,输出等于输入。

8

参考链接:

论文

重要性采样

Kullback-Leibler(KL)散度介绍