proximal policy optimization (PPO)是策略梯度方法家族的一员，在PPO被提出来之前，它的哥哥(trust region policy optimization)TRPO先被提出，在介绍PPO之前我们先回顾一下TRPO的相关概念。
在TRPO方法中，置信域的概念被应用。假设我们有一个需要优化的函数J( θ \theta θ), 但是直接对这个函数进行优化很难，我们可以假设在一个置信域内能够使用另外的一个函数L( θ ∣ θ n o w \theta|\theta_{now} θ∣θnow)，( θ n o w \theta_{now} θnow为现在参数的值)来替换原函数，从而将原本的优化目标变成新的函数，方便优化的进行。
整个置信域方法的框架可以分为两步
我们可以将置信域的方法应用到策略优化里面。在TRPO里我们要最大化的目标函数J(
θ
\theta
θ)
J
(
θ
)
=
E
S
[
E
A
∼
π
(
⋅
∣
S
;
θ
now
)
[
π
(
A
∣
S
;
θ
)
π
(
A
∣
S
;
θ
now
)
⋅
Q
π
(
S
,
A
)
]
]
J(\boldsymbol{\theta})=\mathbb{E}_{S}\left[\mathbb{E}_{A \sim \pi\left(\cdot \mid S ; \boldsymbol{\theta}_{\text {now }}\right)}\left[\frac{\pi(A \mid S ; \boldsymbol{\theta})}{\pi\left(A \mid S ; \boldsymbol{\theta}_{\text {now }}\right)} \cdot Q_{\pi}(S, A)\right]\right]
J(θ)=ES[EA∼π(⋅∣S;θnow )[π(A∣S;θnow )π(A∣S;θ)⋅Qπ(S,A)]]
在OpenAI的PPO那篇论文中没有用
Q
π
(
S
,
A
)
Q_{\pi}(S, A)
Qπ(S,A)而是用了
A
π
(
s
,
a
)
A_{\pi}(s, a)
Aπ(s,a)来代替，其中
A
π
(
s
,
a
)
=
Q
π
(
s
,
a
)
−
V
π
(
s
)
A_{\pi}(s, a)=Q_{\pi}(s, a)-V_{\pi}(s)
Aπ(s,a)=Qπ(s,a)−Vπ(s)，称作advantage function，用于评估动作的好坏。
可能有些人会对这里的目标函数有些疑惑，后续会讲解这个是怎么来的。
第一步，做近似(
u
t
=
r
t
+
γ
⋅
r
t
+
1
+
γ
2
⋅
r
t
+
2
+
⋯
+
γ
n
−
t
⋅
r
n
u_{t}=r_{t}+\gamma \cdot r_{t+1}+\gamma^{2} \cdot r_{t+2}+\cdots+\gamma^{n-t} \cdot r_{n}
ut=rt+γ⋅rt+1+γ2⋅rt+2+⋯+γn−t⋅rn)
L
~
(
θ
∣
θ
now
)
=
1
n
∑
t
=
1
n
π
(
a
t
∣
s
t
;
θ
)
π
(
a
t
∣
s
t
;
θ
now
)
⋅
u
t
\tilde{L}\left(\boldsymbol{\theta} \mid \boldsymbol{\theta}_{\text {now }}\right)=\frac{1}{n} \sum_{t=1}^{n} \frac{\pi\left(a_{t} \mid s_{t} ; \boldsymbol{\theta}\right)}{\pi\left(a_{t} \mid s_{t} ; \boldsymbol{\theta}_{\text {now }}\right)} \cdot u_{t}
L~(θ∣θnow )=n1t=1∑nπ(at∣st;θnow )π(at∣st;θ)⋅ut
第二步，最大化
θ
new
=
argmax
θ
L
~
(
θ
∣
θ
now
)
;
s.t.
∥
θ
−
θ
now
∥
2
≤
Δ
\theta_{\text {new }}=\underset{\theta}{\operatorname{argmax}} \tilde{L}\left(\theta \mid \theta_{\text {now }}\right) ; \quad \text { s.t. }\left\|\theta-\theta_{\text {now }}\right\|_{2} \leq \Delta
θnew =θargmaxL~(θ∣θnow ); s.t. ∥θ−θnow ∥2≤Δ
在第二步中，我们需要求解一个带约束优化问题，而带约束优化问题的求解往往比较复杂，用梯度方法求解可能不太方便。PPO的提出则解决了这个问题
在PPO的求解里面，将原本的约束优化变成了无约束优化，方便了算法的制定。将原本的优化问题变成了下面的形式
maximize
θ
E
^
t
[
π
θ
(
a
t
∣
s
t
)
π
θ
o
l
d
(
a
t
∣
s
t
)
A
^
t
−
β
KL
[
π
θ
o
l
d
(
⋅
∣
s
t
)
,
π
θ
(
⋅
∣
s
t
)
]
]
\underset{\theta}{\operatorname{maximize}} \hat{\mathbb{E}}_{t}\left[\frac{\pi_{\theta}\left(a_{t} \mid s_{t}\right)}{\pi_{\theta_{\mathrm{old}}}\left(a_{t} \mid s_{t}\right)} \hat{A}_{t}-\beta \operatorname{KL}\left[\pi_{\theta_{\mathrm{old}}}\left(\cdot \mid s_{t}\right), \pi_{\theta}\left(\cdot \mid s_{t}\right)\right]\right]
θmaximizeE^t[πθold(at∣st)πθ(at∣st)A^t−βKL[πθold(⋅∣st),πθ(⋅∣st)]]
将原本的约束项取消，变成了有点类似于惩罚项，加到了目标函数的后面。目的是让更新的策略和旧的策略相差不要过大。没有了约束项能够更加方便地使用梯度方法来求解。同时在PPO的目标函数中也出现了
π
θ
(
a
t
∣
s
t
)
π
θ
o
l
d
(
a
t
∣
s
t
)
\frac{\pi_{\theta}\left(a_{t} \mid s_{t}\right)}{\pi_{\theta_{\mathrm{old}}}\left(a_{t} \mid s_{t}\right)}
πθold(at∣st)πθ(at∣st)
这个和重要性采样有着关系。PPO是一个 on policy的算法，而相比于off policy能够从经验池中进行经验回放，on policy的算法往往需要一更新参数就要重新采集数据，导致需要花费大量时间采集数据。事实上我们也可以使用重要性采样，从而提高PPO的数据使用效率。
重要性采样
From EasyRL:
假设你有一个函数 f(x)，你要计算从 p 这个分布采样 x，再把 x 带到 f 里面，得到 f(x)。你要该怎么计算这个 f(x) 的期望值？假设你不能对 p 这个分布做积分的话，那你可以从 p 这个分布去采样一些数据 x i x^i xi。把 x i x^i xi代到 f(x)里面，然后取它的平均值，就可以近似 f(x)的期望值。
现在有另外一个问题，我们没有办法从 p 这个分布里面采样数据。假设我们不能从 p 采样数据，只能从另外一个分布 q 去采样数据，q 可以是任何分布。
∫ f ( x ) p ( x ) d x = ∫ f ( x ) p ( x ) q ( x ) q ( x ) d x = E x ∼ q [ f ( x ) p ( x ) q ( x ) ] \int \mathrm{f}(\mathrm{x}) \mathrm{p}(\mathrm{x}) \mathrm{d} \mathrm{x}=\int \mathrm{f}(\mathrm{x}) \frac{\mathrm{p}(\mathrm{x})}{\mathrm{q}(\mathrm{x})} \mathrm{q}(\mathrm{x}) \mathrm{d} \mathrm{x}=\mathrm{E}_{\mathrm{x} \sim \mathrm{q}}\left[\mathrm{f}(\mathrm{x}) \frac{\mathrm{p}(\mathrm{x})}{\mathrm{q}(\mathrm{x})}\right] ∫f(x)p(x)dx=∫f(x)q(x)p(x)q(x)dx=Ex∼q[f(x)q(x)p(x)]我们可以对原本的公式做上面的变换，我们就可以写成对 q 里面所采样出来的 x取期望值。我们从 q 里面采样 x，然后再去计算 f ( x ) p ( x ) q ( x ) f(x) \frac{p(x)}{q(x)} f(x)q(x)p(x)，再去取期望值。所以就算我们不能从 p 里面去采样数据，只要能够从 q 里面去采样数据，然后代入上式，你就可以计算从 p 这个分布采样 x代入 f以后所算出来的期望值。
在上面的公式中， p ( x ) q ( x ) \frac{p(x)}{q(x)} q(x)p(x)就称作重要性权重，目的是修正两个分布之间的差别。值得注意的是两个分布之间的差别不能太大，因为经过了变换之后，公式算出来的结果的方差和原来不同。这也就是为什么PPO算法中有一个关于新旧策略的KL散度的计算，当二者相差过大时重要性采样的效果可能不够好。也就是说我们需要更新新策略，但是又不能让它更新的太快。有了重要性采样这个工具之后我们就可以更高效地利用PPO算法中的数据了。具体表现为可以使用旧的策略采样 θ ′ \theta' θ′得到很多的数据，然后多次更新 θ \theta θ,等 θ \theta θ更新了很多次之后，再重新用现在更新出来的参数进行数据的收集。只需要再乘上一个重要性权重就可以保证训练的效果。
PPO还有着第二种版本PPO_Clip,其思路也是限制新的策略和旧的策略不能够相差过大。
L
C
L
I
P
(
θ
)
=
E
^
t
[
min
(
r
t
(
θ
)
A
^
t
,
clip
(
r
t
(
θ
)
,
1
−
ϵ
,
1
+
ϵ
)
A
^
t
)
]
L^{C L I P}(\theta)=\hat{\mathbb{E}}_{t}\left[\min \left(r_{t}(\theta) \hat{A}_{t}, \operatorname{clip}\left(r_{t}(\theta), 1-\epsilon, 1+\epsilon\right) \hat{A}_{t}\right)\right]
LCLIP(θ)=E^t[min(rt(θ)A^t,clip(rt(θ),1−ϵ,1+ϵ)A^t)]
其中
E
^
t
[
π
θ
(
a
t
∣
s
t
)
π
θ
old
(
a
t
∣
s
t
)
A
^
t
]
=
E
^
t
[
r
t
(
θ
)
A
^
t
]
\hat{\mathbb{E}}_{t}\left[\frac{\pi_{\theta}\left(a_{t} \mid s_{t}\right)}{\pi_{\theta_{\text {old }}}\left(a_{t} \mid s_{t}\right)} \hat{A}_{t}\right]=\hat{\mathbb{E}}_{t}\left[r_{t}(\theta) \hat{A}_{t}\right]
E^t[πθold (at∣st)πθ(at∣st)A^t]=E^t[rt(θ)A^t]。看起来有些复杂，其实很朴素。clip的意思是在括号里面有三项，如果第一项小于第二项的话，那就输出 1−
ϵ
\epsilon
ϵ。第一项如果大于第三项的话，那就输出 1+
ϵ
\epsilon
ϵ，
ϵ
\epsilon
ϵ是一个超参数。
参考资料：
