TRPO 算法详细介绍
TRPO 的最终目标是找到新的策略使得累积回报值单调递增,或者单调不减。
首先定义强化学习的某个策略的期望价值函数(累积回报)函数定义为:
=
E
t
0
t
r s
t
将新策略的回报函数拆分为【旧策略回报函数+其他项】,若是保证其他项>=0
=
E
0, 0,
s a
则:新的回报函数单调不减
t
,
A s a
t
用表示旧策略, 表示新策略:
其中
E
将(1)展开可得:
A s a Q s a V s
,
,
0
t
t
'~
,
s P s s a
'|
=
E
0, 0,
s a
t
,
A s a
t
t
P s
t
t
0
=
+
t
s
s
|
|
a s
a
s
s
a
,
a s A s a
|
(1)有证明
r s
V s
'
V s
A s a
,
(2)
t
其中
s
t
0
t
P s
t
s
,表示的是任意时刻状态 s 的访问概率和。
|
由于 s 中使用的是新策略,导致其存在一定的困难,所以使用旧策略进
行近似来对其进行解决【忽略状态分布的变化,依然采用旧的策略所对应的状态
分布,是对原代价函数的一次近似,可将原来的代价函数近似为:】
(3)
,t
|
a s A s a
t
s
s
a
针对于上式,第二项策略部分,这时的动作是由新策略 产生的,新策略是
带参数,这个参数是未知的,无法用来产生动作,此时需要引入第二个技巧:
使用重要性采样对动作分布进行处理,因为新旧策略之间的差异较小,因此使用
重要性采样能够取得较好的结果:
|
a s
,
|
q a s
a
再将 s 求和写为期望形式如下所示:
,
a s A s a
,
A s a
~
|
a q a s
E
|
t
t
t
t
L
+E
s
~
old
, ~
s a
old
old
|
a s
|
a s
|
a s
,
A
old
,
s a
t
t
(4)
对比(2)与(4),
L 与
的区别就是状态分布不同,都是 的函数,
且都在策略
old 处一阶近似,通过证明发现,对当前策略来说,两个公式在数
值和导数上是相同的,所以在有限的范围内两个目标函数的数值相差比较有限。
L
old
old
old
L
old
|
old
|
old
如上所示,在 old 有限的范围内,两个目标函数相差十分相似,梯度也相同,
因此可以使用近似函数
oldL 来进行代替原先的目标函数,接下来可以沿着近
似函数的导数方向做有限步长的参数更新,因为近似函数与目标函数在很小的区
域可以做到近似,那么步长如何进行限定,此时需要引入一个约束用于限定新旧
策略的差异,若是将策略看作是概率分布,那就可以使用 KL 散度来表示两个分
布之间的差异:
|
s
命名
max
D
D
max
KL
|
KL
||
s
,
s
当
=argmax
L
'
'
时,满足:
L
C D
max
KL
,
此处
C
2
2
1-
令:
M
i
L
i
max
C D
KL
,
i
可得到:
1
i
M
i
1
i
i
M
i
i
两式相减得:
i
1
i
M
i
1
i
M
i
i
若要使得值函数单调不减,则新策略 1i 能够使得 iM 最大即可,则问题转
换为:
max
L
old
C D
max
KL
,
old
首先优化的目标是 KL 散度,将优化形式进行转变,得到由约束条件的优化
问题:
maximize
L
old
. .
s t D
max
KL
,
old
由于约束条件中需要对最大值进行约束,为了简化运算,这里将最大值变为
均值,可以降低计算难度,并且实际效果不会下降:
D
KL
2
,
1
=
E
s
~
D
KL
1
|
s
||
2
|
s
为两个策略的平均散度,于是问题
maximize
L
old
old
变为:
. .
s t D
KL
old
,
old
s
old
s
a
|
a s A
old
,
s a
(5)
上式中的第二项使用重要性采样可以写为:
s E
,
s a
A
~
old
old
a
s
,继续使用重要性采样将公式变为:
a
a s A
|
old
,
s a
a
old
|
a s
old
|
a s
|
a s
A
old
,
s a
E
a
~
old
old
|
a s
|
a s
A
old
,
s a
最后可将 TRPO 的问题定义如下:
max imize
E
a
~
old
old
|
a s
|
a s
A
old
,
s a
. .
s t D
KL
old
,
old
(6)
这个带约束的优化问题可以使用共轭梯度算法近似解决,使用惩罚项来替代
约束:
max imize
E
a
~
old
old
|
a s
|
a s
A
old
,
s a
KL
old
|
s
,
|
s
最大步长的求解:
使得最大步长为:,通过共轭梯度法来求解s 方向,则参数更新的最大
值为:s ,前面提到的约束为:
1
N
使用s 代替 ,可以得到:
N
n
1
1
2
I
old
1
N
N
n
1
1
2
s
I
old
s
s
1
2
2
1
N
N
n
1
s
I
old
s
整理可得:
2
s
N
1
n
1
N
I
old
s
最终算法可以总结为三点:
1、 采样一系列的状态、行动对,用蒙特卡洛方法估计他们的行为价值函数;
2、 通过平均这些样本,建立公式(6)中的目标函数与约束;
3、 求解最大步长,结合方向 s 来对参数进行更新。
PPO 算法介绍
OpenAI 文章
使用
tr 表示概率分布的比率
r
t
=
old
|
a s
t
t
|
a s
t
t
,可以看出
r ,在
t
1
old
TRPO 中是最大化下面目标函数:
CPI
L
ˆ=
t
old
|
a s
t
t
|
a s
t
t
ˆ
A
t
ˆ
E
t
r
t
ˆ
A
t
若是没有 TRPO 中的约束,这个目标函数会非常快地增长,因此需要对目标
函数进行修改,使得当
CLIP
L
ˆ min
E
t
r
t
tr 偏离 1 时增加一些惩罚:
ˆ
A clip r
t
t
,1+
ˆ
A
t
,1
,
使用 clip 对目标函数进行处理下,通过最外层的 min 函数取裁剪过与未裁剪
的最小值。
当 A>0 时,表示当前行为的选取比较好,的那策略的更新幅度不能太大,当
比率超过1+时,目标函数不再增大
当 A<0 时,表示当前行为选的不好,同理,选取这个行为的策略需要减少,
但减少幅度也不能太大,当比率小于1-时,进行裁剪,使目标函数不再减小。
其中红点表示优化的起点。
还有另外一种约束方法,使用 KL 散度的惩罚项,与 TRPO 不同的是,为散
度的系数增加一些适应性变化,让 KL 散度与我们事先定义好的 argtd 在每一次策
略更新时相接近,具体如下所示:
1、 使用 mini-batch 的随机梯度下降的方法,优化带 KL 散度惩罚项的目
标函数:
KLPEN
L
ˆ=
t
old
|
a s
t
t
|
a s
t
t
ˆ
A
t
KL
old
|
s
,
|
s
2、 计算
d
KL
old
|
s
,
|
s
ˆ
t
/1.5,
1.5,
if d
if d
d
d
t
arg
t
arg
/ 2
2
经过一些小的改变将上面两个替代的目标函数运用到策略梯度算法中,为了
减少优势函数的方差,经常会使用状态价值函数 V,若是让策略与状态价值函数
共享同一个神经网络参数,我们需要将策略与状态价值函数的误差整合到一个损
失函数中去,同时也可以增加一个信息熵奖励项来增加探索,将这三项组合可以
得到如下的目标函数:
CLIP VF S
L
t
ˆ
t
CLIP
L
t
VF
c L
1
t
c S
2
s
t
其中 1
2,c c 为系数,S 代表信息熵奖励, VF
tL 代表平方误差
V s
t
V
t
argt
2
算法:
每一次迭代,N 个 actor 并行采样 T 步数据,然后使用 NT 步数据构建替代
的损失函数,并使用 mini-batch 的随机梯度下降算法进行优化 K 次。
DeepMind 文章
DeepMind 在该论文中提出了分布式的 PPO 算法(DPPO)
t
'
ˆ
A
t
'
t
t
r
t
'
t
:表示的是轨迹采样获得衰减过后的奖励
t
'
t
t
'
t
r V s
'
t
t
:表示的是优势函数:
A3C 算法介绍
核心时使用 python 的多线程 threading 来实现 A3C 算法,是最有效率的策略
算法。主要的代码如下所示:
主要使用的是 CartPole-v0 模型来进行实验:
游戏的规则:
车杆游戏,小车需要左右移动来保持杆子的竖直,如果角度大于 15°那么
游戏结束,且小车不能移动出一个范围(中间到两边各 2.4 个单位长度);
动作空间(2 个):
左移、右移
状态变量(4 个):
小车在轨道中的位置;
垂直杆的角度;
小车的速度;
角度的变化率
奖励规则:
左移或者右移小车的 action 之后,都会获得一个+1 的 reward,到达 200 个
reward 之后游戏结束。
移动规则:
若是杆子的角度为正,则左移,否则右移
代码详解:
PPO 算法限制了新策略的更新,解决了策略梯度不好确定 learning rate 或者
step size 的问题,因为 step size 过大的情乱搞,学习出来的 Policy 会一直乱动,
不会收敛,利用新策略与老策略的比例来限制新策略的更新幅度,使其对大的
step size 不会太敏感。
网络分为两部分
网络结构:
actor 网络:【4,256,128,2】
网络中使用的激活函数为 relu 函数,最后一层为 softmax 分类器,获得动作