强化学习自然策略梯度Natural Policy Gradient推导
强化学习自然策略梯度Natural Policy Gradient推导
前言
最近在学习TRPO,发现里面好多好多完全陌生的概念。为了能够尽量多地去理解TRPO算法的原理,所以正在一步一步地学习里面的新概念,其中一个就是自然策略梯度:Natural Policy Gradient (NPG)。在这里整理出来,一方面防止自己忘记,另一方面哪里接错了,还请各位大佬指正一下^_^。
预先准备的知识
似然函数与对数似然函数
有一个随机变量
X
X
X,它的理想概率分布为:
x
∼
p
(
x
;
θ
)
x \sim p(x;\theta)
x∼p(x;θ)。
X
X
X是啥样的不知道,
p
p
p是啥样的也不知道。现对
X
X
X进行
n
n
n次采样,得到
n
n
n组独立同分布的样本
{
x
1
,
x
2
,
⋯
,
x
n
}
\left\{x_1, x_2, \cdots, x_n\right\}
{x1,x2,⋯,xn}。那么定义其似然函数为:
L
(
X
;
θ
)
=
∏
i
=
1
n
p
(
x
i
∣
θ
)
L(X;\theta)=\prod_{i=1}^n{p(x_i|\theta)}
L(X;θ)=i=1∏np(xi∣θ)
对数似然为:
ln
L
=
ln
∏
i
=
1
n
p
(
x
i
∣
θ
)
=
∑
i
=
1
n
ln
p
(
x
i
∣
θ
)
=
ln
p
(
x
∣
θ
)
\ln L=\ln{\prod_{i=1}^n{p(x_i|\theta)}}=\sum_{i=1}^n{\ln{p(x_i|\theta)}}=\ln{p(x|\theta)}
lnL=lni=1∏np(xi∣θ)=i=1∑nlnp(xi∣θ)=lnp(x∣θ)
只不过最后一个等式的
p
p
p是向量函数了,
p
p
p的导数要加转置符号。
Score function
Score function,记为
S
S
S,被定义为对数似然的雅克比矩阵 (一阶导数):
S
=
J
a
(
ln
L
)
=
J
a
(
ln
p
(
x
∣
θ
)
)
S=Ja(\ln L)=Ja(\ln{p(x|\theta)})
S=Ja(lnL)=Ja(lnp(x∣θ))
其中
J
a
(
)
Ja()
Ja()是求雅可比矩阵,score function 有一个特性:期望为零。
E
x
∼
p
(
x
∣
θ
)
[
S
]
=
∫
x
p
(
x
∣
θ
)
∇
ln
p
(
x
∣
θ
)
d
x
=
∫
x
p
(
x
∣
θ
)
1
p
(
x
∣
θ
)
∇
p
(
x
∣
θ
)
d
x
=
∇
∫
x
p
(
x
∣
θ
)
d
x
=
∇
1
=
0
\begin{align} \begin{aligned} \mathbb{E}_{x\sim p(x|\theta)}[S] &= \int_x p(x|\theta)\nabla\ln{p(x|\theta)}dx \\ &= \int_x p(x|\theta)\frac{1}{p(x|\theta)}\nabla p(x|\theta)dx \\ & =\nabla \int_x p(x|\theta)dx \\ &=\nabla1=0 \end{aligned} \end{align}
Ex∼p(x∣θ)[S]=∫xp(x∣θ)∇lnp(x∣θ)dx=∫xp(x∣θ)p(x∣θ)1∇p(x∣θ)dx=∇∫xp(x∣θ)dx=∇1=0
这是一个蛮重要的性质。
Fisher Information Matrix (FIM)
FIM的定义是Score function 的二阶距
F
(
θ
)
=
E
x
∼
p
(
x
∣
θ
)
[
S
2
]
F(\theta)=\mathbb{E}_{x\sim p(x|\theta)}[S^2]
F(θ)=Ex∼p(x∣θ)[S2]
F
(
θ
)
F(\theta)
F(θ)也有一个不是一眼能看出来的性质:
F
(
θ
)
=
−
E
x
∼
p
(
x
∣
θ
)
[
H
(
ln
p
(
x
∣
θ
)
)
]
F(\theta)= -\mathbb{E}_{x\sim p(x|\theta)}\left[H(\ln p(x|\theta))\right]
F(θ)=−Ex∼p(x∣θ)[H(lnp(x∣θ))]
其中,
H
H
H是Hessian矩阵 (二阶导数)。
为方便推导,先把FIM化简 (将
p
(
x
∣
θ
)
p(x|\theta)
p(x∣θ)简记为
p
p
p):
F
(
θ
)
=
E
x
∼
p
(
x
∣
θ
)
[
S
2
]
=
E
x
∼
p
(
x
∣
θ
)
[
S
2
]
−
0
=
E
x
∼
p
(
x
∣
θ
)
[
S
2
]
−
[
E
x
∼
p
(
x
∣
θ
)
(
S
)
]
2
=
E
x
∼
p
(
x
∣
θ
)
[
∇
ln
p
(
∇
ln
p
)
T
]
\begin{align} \begin{aligned} F(\theta) &= \mathbb{E}_{x\sim p(x|\theta)}[S^2] \\ &= \mathbb{E}_{x\sim p(x|\theta)}[S^2] - 0 \\ &= \mathbb{E}_{x\sim p(x|\theta)}[S^2] -[\mathbb{E}_{x\sim p(x|\theta)}(S)]^2 \\ &= \mathbb{E}_{x\sim p(x|\theta)}\left[\nabla\ln p (\nabla\ln p)^T\right] \end{aligned} \end{align}
F(θ)=Ex∼p(x∣θ)[S2]=Ex∼p(x∣θ)[S2]−0=Ex∼p(x∣θ)[S2]−[Ex∼p(x∣θ)(S)]2=Ex∼p(x∣θ)[∇lnp(∇lnp)T]
接下来从
ln
p
\ln p
lnp的Hessian矩阵开始推
H
(
ln
p
)
=
J
a
(
∇
ln
p
)
=
J
a
(
∇
p
p
)
=
H
(
p
)
p
−
∇
p
∇
p
T
p
⋅
p
T
\begin{align} \begin{aligned} H(\ln p) = Ja(\nabla \ln p)=Ja\left(\frac{\nabla p}{p}\right)=\frac{H(p)p-\nabla p\nabla p^T}{p\cdot p^T} \end{aligned} \end{align}
H(lnp)=Ja(∇lnp)=Ja(p∇p)=p⋅pTH(p)p−∇p∇pT
等式两边同时取期望,有
E
[
H
(
ln
p
)
]
=
E
[
H
(
p
)
p
−
∇
p
∇
p
T
p
⋅
p
T
]
=
E
[
H
(
p
)
p
p
⋅
p
T
]
−
E
[
∇
p
∇
p
T
p
⋅
p
T
]
=
∫
x
p
H
(
p
)
p
p
⋅
p
T
d
x
−
E
[
∇
p
p
⋅
∇
p
T
p
T
]
=
H
[
∫
x
p
d
x
]
−
E
[
∇
ln
p
⋅
(
∇
ln
p
)
T
]
=
H
(
1
)
−
F
(
θ
)
=
−
F
(
θ
)
\begin{align} \begin{aligned} \mathbb{E}\left[H(\ln p)\right] &= \mathbb{E}\left[\frac{H(p)p-\nabla p\nabla p^T}{p\cdot p^T}\right] \\ &= \mathbb{E}\left[\frac{H(p)p}{p\cdot p^T}\right] -\mathbb{E}\left[\frac{\nabla p\nabla p^T}{p\cdot p^T}\right] \\ &=\int_xp\frac{H(p)p}{p\cdot p^T}dx-\mathbb{E}\left[\frac{\nabla p}{p}\cdot\frac{\nabla p^T}{p^T}\right] \\ &=H\left[\int_xpdx\right]-\mathbb{E}\left[\nabla\ln p\cdot (\nabla\ln p)^T\right] \\ &=H(1)-F(\theta)\\ &=-F(\theta) \end{aligned} \end{align}
E[H(lnp)]=E[p⋅pTH(p)p−∇p∇pT]=E[p⋅pTH(p)p]−E[p⋅pT∇p∇pT]=∫xpp⋅pTH(p)pdx−E[p∇p⋅pT∇pT]=H[∫xpdx]−E[∇lnp⋅(∇lnp)T]=H(1)−F(θ)=−F(θ)
推导完毕。
KL散度 (KL divergence)
KL散度是用来衡量两个概率分布的“差异性”的。当概率分布函数的参数
θ
\theta
θ发生一个微小变化
d
→
0
d\rightarrow 0
d→0时,其KL散度为
K
L
[
p
(
θ
)
∣
∣
p
(
θ
′
)
]
=
∫
x
∼
p
(
θ
)
p
(
θ
)
ln
p
(
θ
)
p
(
θ
′
)
d
x
=
∫
x
∼
p
(
θ
)
p
(
θ
)
ln
p
(
θ
)
d
x
−
∫
x
∼
p
(
θ
)
p
(
θ
)
ln
p
(
θ
′
)
d
x
\begin{align} \begin{aligned} KL\left[p(\theta)||p(\theta')\right] &= \int_{x\sim p(\theta)}{p(\theta)\ln{\frac{p(\theta)}{p(\theta')}}}dx \\ &= \int_{x\sim p(\theta)}{p(\theta)\ln{p(\theta)}}dx-\int_{x\sim p(\theta)}{p(\theta)\ln{p(\theta')}}dx \end{aligned} \end{align}
KL[p(θ)∣∣p(θ′)]=∫x∼p(θ)p(θ)lnp(θ′)p(θ)dx=∫x∼p(θ)p(θ)lnp(θ)dx−∫x∼p(θ)p(θ)lnp(θ′)dx
在
θ
′
=
θ
\theta'=\theta
θ′=θ处将上面第二项Taylor展开,有 (积分符号下边的
x
∼
p
(
θ
)
x\sim p(\theta)
x∼p(θ)省略)
K
L
[
p
(
θ
)
∣
∣
p
(
θ
′
)
]
=
∫
p
(
θ
)
ln
p
(
θ
)
d
x
−
∫
p
(
θ
)
ln
p
(
θ
′
)
d
x
=
∫
p
(
θ
)
ln
p
(
θ
)
d
x
−
∫
p
(
θ
)
[
ln
p
(
θ
)
+
∇
ln
p
(
θ
)
T
d
+
1
2
d
T
∇
2
ln
p
(
θ
)
d
]
d
x
=
−
∫
p
(
θ
)
∇
ln
p
(
θ
)
T
d
x
⋅
d
−
1
2
d
T
∫
p
(
θ
)
∇
2
ln
p
(
θ
)
d
x
⋅
d
=
−
∇
∫
p
(
θ
)
p
(
θ
)
p
(
θ
)
d
x
⋅
d
−
1
2
d
T
∫
p
(
θ
)
∇
2
ln
p
(
θ
)
d
x
⋅
d
=
−
1
2
d
T
∫
p
(
θ
)
∇
2
ln
p
(
θ
)
d
x
⋅
d
=
−
1
2
d
T
∫
p
(
θ
)
(
−
H
[
ln
p
(
θ
)
]
)
d
x
⋅
d
=
1
2
d
T
E
[
H
(
ln
p
)
]
d
=
1
2
d
T
F
(
θ
)
d
\begin{align} \begin{aligned} KL\left[p(\theta)||p(\theta')\right] &= \int{p(\theta)\ln{p(\theta)}}dx-\int{p(\theta)\ln{p(\theta')}}dx \\ &= \int{p(\theta)\ln{p(\theta)}}dx-\int{p(\theta)\left[\ln p(\theta)+\nabla\ln p(\theta)^Td+\frac{1}{2}d^T\nabla^2\ln p(\theta)d\right]}dx \\ &= -\int p(\theta)\nabla\ln p(\theta)^Tdx\cdot d-\frac{1}{2}d^T\int p(\theta)\nabla^2\ln p(\theta)dx\cdot d \\ &= -\nabla\int p(\theta)\frac{p(\theta)}{p(\theta)}dx\cdot d-\frac{1}{2}d^T\int p(\theta)\nabla^2\ln p(\theta)dx\cdot d \\ &= -\frac{1}{2}d^T\int p(\theta)\nabla^2\ln p(\theta)dx\cdot d \\ &= -\frac{1}{2}d^T\int p(\theta)(-H\left[\ln p(\theta)\right])dx\cdot d \\ &=\frac{1}{2}d^T\mathbb{E}\left[H(\ln p)\right]d \\ &=\frac{1}{2}d^TF(\theta)d \end{aligned} \end{align}
KL[p(θ)∣∣p(θ′)]=∫p(θ)lnp(θ)dx−∫p(θ)lnp(θ′)dx=∫p(θ)lnp(θ)dx−∫p(θ)[lnp(θ)+∇lnp(θ)Td+21dT∇2lnp(θ)d]dx=−∫p(θ)∇lnp(θ)Tdx⋅d−21dT∫p(θ)∇2lnp(θ)dx⋅d=−∇∫p(θ)p(θ)p(θ)dx⋅d−21dT∫p(θ)∇2lnp(θ)dx⋅d=−21dT∫p(θ)∇2lnp(θ)dx⋅d=−21dT∫p(θ)(−H[lnp(θ)])dx⋅d=21dTE[H(lnp)]d=21dTF(θ)d
如果取费雪信息矩阵
F
(
θ
)
F(\theta)
F(θ)作为度量矩阵,那么
∥
d
∥
2
=
d
T
F
(
θ
)
d
=
2
K
L
[
p
(
θ
)
∣
∣
p
(
θ
+
d
)
]
\left\|d\right\|^2=d^TF(\theta)d=2KL\left[p(\theta)||p(\theta+d)\right]
∥d∥2=dTF(θ)d=2KL[p(θ)∣∣p(θ+d)],即参数更新的模长平方约等于二倍的参数更新前后概率分布的KL散度。
Natural Gradient
在得到上面的结论之后,我们可以通过将参数更新前后的KL散度约束在某一个区域内的方式,来实现既快又准的更新参数。
d
∗
=
arg min
d
s
.
t
.
K
L
[
p
θ
∣
∣
p
θ
+
d
]
=
c
L
(
θ
+
d
)
d^*=\argmin_{d\ \ s.t. KL\left[p_{\theta}||p_{\theta+d}\right]=c}\mathcal{L(\theta+d)}
d∗=d s.t.KL[pθ∣∣pθ+d]=cargminL(θ+d)
运用拉格朗日乘子法,有
D
=
L
(
θ
+
d
)
+
λ
(
K
L
[
p
θ
∣
∣
p
θ
+
d
]
−
c
)
=
L
(
θ
)
+
∇
θ
L
(
θ
)
T
d
+
λ
K
L
[
p
θ
∣
∣
p
θ
+
d
]
−
λ
c
=
L
(
θ
)
+
∇
θ
L
(
θ
)
T
d
+
1
2
λ
d
T
F
(
θ
)
d
−
λ
c
\begin{align} \begin{aligned} D &= \mathcal{L(\theta+d)}+\lambda(KL\left[p_{\theta}||p_{\theta+d}\right]-c) \\ &= \mathcal{L(\theta)} + \nabla_{\theta}L(\theta)^Td+\lambda KL\left[p_{\theta}||p_{\theta+d}\right]-\lambda c \\ &= \mathcal{L(\theta)} + \nabla_{\theta}L(\theta)^Td + \frac{1}{2}\lambda d^TF(\theta)d-\lambda c \end{aligned} \end{align}
D=L(θ+d)+λ(KL[pθ∣∣pθ+d]−c)=L(θ)+∇θL(θ)Td+λKL[pθ∣∣pθ+d]−λc=L(θ)+∇θL(θ)Td+21λdTF(θ)d−λc
令
∂
D
∂
d
=
0
\frac{\partial D}{\partial d}=0
∂d∂D=0,有
∇
θ
L
(
θ
)
+
λ
F
(
θ
)
d
=
0
\begin{align} \begin{aligned} \nabla_{\theta}L(\theta) + \lambda F(\theta)d=0 \end{aligned} \end{align}
∇θL(θ)+λF(θ)d=0
进而可得
d
=
−
1
λ
F
(
θ
)
−
1
∇
θ
L
(
θ
)
=
−
1
λ
∇
~
θ
L
(
θ
)
\begin{align} \begin{aligned} d= -\frac{1}{\lambda}F(\theta)^{-1}\nabla_{\theta}L(\theta)=-\frac{1}{\lambda} \widetilde{\nabla}_{\theta}L(\theta) \end{aligned} \end{align}
d=−λ1F(θ)−1∇θL(θ)=−λ1∇
θL(θ)
参数更新方向为:
d
←
d
−
α
∇
~
θ
L
(
θ
)
\begin{align} \begin{aligned} d \leftarrow d-\alpha \widetilde{\nabla}_{\theta}L(\theta) \end{aligned} \end{align}
d←d−α∇
θL(θ)
Natural Policy Gradient
自然策略梯度是自然梯度与策略梯度的结合,策略梯度算法中使用目标函数对参数的导数为参数更新提供方向, α \alpha α为更新步长。Natural Policy Gradient是使用上面推导得到的自然梯度来为参数更新提供方向。
普通的策略梯度可以表示为:
∇
J
(
θ
)
=
∫
S
ρ
π
(
s
)
∫
S
∇
θ
π
(
a
∣
s
;
θ
)
⋅
Q
π
(
s
,
a
)
⋅
d
a
⋅
d
s
\begin{align} \begin{aligned} \nabla J(\theta)=\int_{\mathcal{S}}\rho^{\pi}(s)\int_{\mathcal{S}} \nabla_{\theta}\pi(a|s;\theta)\cdot Q^{\pi}(s,a) \cdot da\cdot ds \end{aligned} \end{align}
∇J(θ)=∫Sρπ(s)∫S∇θπ(a∣s;θ)⋅Qπ(s,a)⋅da⋅ds
策略函数本身就是一个概率分布
π
(
a
∣
s
;
θ
)
\pi(a|s;\theta)
π(a∣s;θ),它的Fisher信息矩阵为
F
s
(
θ
)
=
E
π
(
a
∣
s
;
θ
)
[
(
∇
ln
π
)
(
∇
ln
π
)
T
]
\begin{align} \begin{aligned} F_s(\theta)=\mathbb{E}_{\pi(a|s;\theta)}\left[(\nabla\ln\pi) (\nabla\ln\pi)^T\right] \end{aligned} \end{align}
Fs(θ)=Eπ(a∣s;θ)[(∇lnπ)(∇lnπ)T]
考虑到状态空间的一个平稳概率分布
ρ
π
(
s
)
\rho^{\pi}(s)
ρπ(s),整体的Fisher信息矩阵为
F
(
θ
)
=
E
ρ
π
(
s
)
F
s
(
θ
)
\begin{align} \begin{aligned} F(\theta)=\mathbb{E}_{\rho^{\pi}(s)}F_s(\theta) \end{aligned} \end{align}
F(θ)=Eρπ(s)Fs(θ)
最终,自然策略梯度里面的梯度可以表示为:
∇
~
θ
J
(
θ
)
=
F
(
θ
)
−
1
∇
J
(
θ
)
\begin{align} \begin{aligned} \widetilde{\nabla}_{\theta}J(\theta)= F(\theta)^{-1}\nabla J(\theta) \end{aligned} \end{align}
∇
θJ(θ)=F(θ)−1∇J(θ)
实际使用时,可以用一个
Q
Q
Q网络来近似
Q
π
(
s
,
a
)
Q^{\pi}(s,a)
Qπ(s,a),用一个
π
\pi
π网络近似
π
(
s
,
a
)
\pi(s, a)
π(s,a)。虽然神经网络很多东西说不清楚,但是不得不承认用着效果挺好的。
以上就是Natural Policy Gradient 的内容,thanks。