RecursiveFrog 发表于 2021-12-7 16:13

【深度强化学习】PPO 算法理解

因为打算使用PPO,所以这两天又把算法仔仔细细理解了一遍,里面对于算法的分析借鉴了李宏毅老师的视频,spinning up官方文档,以及自己的理解,如果有理解不对的地方请在评论区指出来,谢谢!TRPO(trust region policy optimization, 信任域策略优化))与 PPO(proximal policy optimization,邻近策略优化)均属于 策略梯度 算法,算法的训练在 与环境交互采样数据 以及 利用随机梯度上升优化一个替代(surrogate)目标函数 之间交替进行。相较于标准梯度策略算法每次数据采样只能进行一次梯度更新,TRPO与PPO 所使用的目标函数能够利用同一批次数据进行多次梯度更新。PPO 比 TRPO(trust region policy optimization, 信任域策略优化)更为简单。
算法背景

策略梯度方法

策略梯度方法通过计算策略梯度的估计然后利用随机梯度上升算法对策略进行更新。最广泛使用的梯度计算公式为

https://www.zhihu.com/equation?tex=%5Chat%7Bg%7D%3D%5Chat%7B%5Cmathbb%7BE%7D%7D_%7B%28s_t%2Ca_t%29%5Csim%5Cpi_%5Ctheta%7D%5Cleft%5B%5Cnabla_%7B%5Ctheta%7D+%5Clog+%5Cpi_%7B%5Ctheta%7D%5Cleft%28a_%7Bt%7D+%5Cmid+s_%7Bt%7D%5Cright%29+%5Chat%7BA%7D%5E%5Ctheta_%7Bt%7D%5Cright%5D+%5C%5C
其中为随机策略,而 https://www.zhihu.com/equation?tex=%5Chat%7BA%7D%5E%5Ctheta_%7Bt%7D 为时刻 https://www.zhihu.com/equation?tex=t 对于优势函数的估计,它表示此时在状态 https://www.zhihu.com/equation?tex=s_t 下采取动作 https://www.zhihu.com/equation?tex=a_t 所能获得的优势,表示对有限批次样本的平均值。算法在实际进行梯度更新时,通常会构建一个梯度等于该策略梯度的目标函数,然后对该目标函数进行梯度上升,该目标函数为

https://www.zhihu.com/equation?tex=L%5E%7BP+G%7D%28%5Ctheta%29%3D%5Chat%7B%5Cmathbb%7BE%7D%7D_%7B%28s_t%2Ca_t%29%5Csim%5Cpi_%5Ctheta%7D%5Cleft%5B%5Clog+%5Cpi_%7B%5Ctheta%7D%5Cleft%28a_%7Bt%7D+%5Cmid+s_%7Bt%7D%5Cright%29+%5Chat%7BA%7D%5E%5Ctheta_%7Bt%7D%5Cright%5D+%5C%5C
代理目标函数(Surrogate Objective Function)

在标准梯度更新算法中,在环境中采集数据的策略与所要估计的策略是同一策略,这种方法被称为 **同策略(on-policy)**方法,在这种方法中,每进行一次数据采集,通常只能进行一次梯度更新,因为策略梯度计算公式中是根据策略   产生的样本所得到的平均,一旦发生了改变,原来的样本就不再具有实际意义。而在 **离策略(off-policy)**方法中,产生数据样本所使用的策略与要估计的策略不是同一策略,前者被称为行为策略,后者被称为目标策略,由于行为策略并不会因为目标策略的更新而发生改变,因此我们可以利用行为策略产生的数据样本对目标策略进行多次更新。离策略算法中,通常利用 **重要性采样(importance sampling)**的方法对梯度/目标函数进行修正,假设目标策略为 ,行为策略为 , 修正后的梯度与目标函数分别为

https://www.zhihu.com/equation?tex=%5Chat%7Bg%7D%27%3D%5Chat%7B%5Cmathbb%7BE%7D%7D_%7B%28s_t%2Ca_t%29%5Csim%5Cpi_%7B%5Ctheta%27%7D%7D%5Cleft%5B%5Cfrac%7B%5Cpi_%5Ctheta%28a_t%7Cs_t%29%7D%7B%5Cpi_%7B%5Ctheta%27%7D%28a_t%7Cs_t%29%7D%5Cnabla_%7B%5Ctheta%7D+%5Clog+%5Cpi_%7B%5Ctheta%7D%5Cleft%28a_%7Bt%7D+%5Cmid+s_%7Bt%7D%5Cright%29+%5Chat%7BA%7D%5E%7B%5Ctheta%27%7D_%7Bt%7D%5Cright%5D+%5C%5Chttps://www.zhihu.com/equation?tex=L%E2%80%99%5E%7BP+G%7D%28%5Ctheta%29%3D%5Chat%7B%5Cmathbb%7BE%7D%7D_%7B%28s_t%2Ca_t%29%5Csim%5Cpi_%7B%5Ctheta%27%7D%7D%5Cleft%5B%5Cfrac%7B%5Cpi_%5Ctheta%28a_t%7Cs_t%29%7D%7B%5Cpi_%7B%5Ctheta%27%7D%28a_t%7Cs_t%29%7D%5Chat%7BA%7D%5E%7B%5Ctheta%27%7D_%7Bt%7D%5Cright%5D+%5C%5C
可以看出,估计策略梯度时所使用的样本均从行为策略中采样得到,而 https://www.zhihu.com/equation?tex=%5Chat%7BA%7D%5E%7B%5Ctheta%27%7D_%7Bt%7D 也根据行为策略估计得到。
TRPO 把每一步策略的更新都当做是一个优化问题,算法借鉴了离策略方法中重要性采样的思想,设计了新的目标函数,即 代理目标函数(surrogate objective function):

https://www.zhihu.com/equation?tex=%5Cmax_%7B%5Ctheta_%7Bk%2B1%7D%7D%5C+%5Chat%7B%5Cmathbb%7BE%7D%7D_%7B%28s_t%2Ca_t%29%5Csim%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%7D%5Cleft%5B%5Cfrac%7B%5Cpi_%7B%5Ctheta_%7Bk%2B1%7D%7D%28a_t%7Cs_t%29%7D%7B%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%28a_t%7Cs_t%29%7D%5Chat%7BA%7D%5E%7B%5Ctheta_%7Bk%7D%7D_%7Bt%7D%5Cright%5D+%5C%5C
因此在每一次策略更新时,我们可以利用“老策略” https://www.zhihu.com/equation?tex=%5Ctheta_%7Bk%7D 采集得到的样本以及对应估计出来的优势函数 https://www.zhihu.com/equation?tex=%5Chat%7BA%7D%5E%7B%5Ctheta_%7Bk%7D%7D_%7Bt%7D ,对进行优化最终得到 。
但是需要注意的是,TRPO和PPO属于on-policy方法,因为他们依然是用采样的数据来更新变成 ,符合on-policy的定义,只不过借用了重要性采样的思想利用所采集的数据来表示   所对应的目标函数,使得 每一次策略更新都变成一个优化问题。总结来说,off-policy是带重要性采样系数的梯度上升,它可以使用任意策略的数据来更新当前策略,而TRPO和PPO的每一步更新都是一个优化问题,它只能使用老策略来更新新策略,这是两者的区别所在。
重要性采样的问题



李宏毅老师的视频中提到,在重要性采样中,行为策略和目标策略不能相差太多。在上面这幅图中, 和分别属于两个不同的分布,我们希望用中采样得到的样本去估计 https://www.zhihu.com/equation?tex=f%28x%29 在属于分布时的期望。上图中, 分布中大多集中在正值,而分布中大多集中在负数区域,当样本数量多时,理论上可以得到一个较为准确的估计值。但当样本数量太少时时,我们采集到的样本很有可能都是正数,此时我们得到的均值估计也是正的,很显然这不是一个准确的估计。只有当样本数量足够大, 能够取到整个定义域上的值时,我们才有可能将结果准确的估计出来。
信任域方法(Trust Region Method)

为了避免上述重要性采样中可能出现的问题,我们在对策略进行优化更新时,必须防止新策略与老策略相差得太远,因此TRPO中规定新策略与老策略之间的KL散度不能相差太多,即

https://www.zhihu.com/equation?tex=%5Cbar%7BD%7D_%7BK+L%7D%5Cleft%28%5Ctheta+%5C%7C+%5Ctheta_%7Bk%7D%5Cright%29%3D%5Cunderset%7Bs+%5Csim+%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%7D%7B%5Cmathrm%7BE%7D%7D%5Cleft%5BD_%7BK+L%7D%5Cleft%28%5Cpi_%7B%5Ctheta%7D%28%5Ccdot+%5Cmid+s%29+%5C%7C+%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%28%5Ccdot+%5Cmid+s%29%5Cright%29%5Cright%5D+%5Cle+%5Cdelta+%5C%5C
这里 KL散度 用于度量不同概率分布之间的相似程度,分布 https://www.zhihu.com/equation?tex=P_r 与 https://www.zhihu.com/equation?tex=P_f 之间KL散度的计算公式为

https://www.zhihu.com/equation?tex=K+L%5Cleft%28P_%7Br%7D+%5C%7C+P_%7Bf%7D%5Cright%29%3D%5Cmathbb%7BE%7D_%7Bx+%5Csim+P_%7Br%7D%7D%5Cleft%5B%5Clog+%5Cfrac%7BP_%7Br%7D%28x%29%7D%7BP_%7Bf%7D%28x%29%7D%5Cright%5D%3D%5Cint+P_%7Br%7D%28x%29+%5Clog+%5Cfrac%7BP_%7Br%7D%28x%29%7D%7BP_%7Bf%7D%28x%29%7D+d+x+%5C%5C
因此,在TRPO中,每一步策略梯度更新对应的完整优化问题可以表示为

https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%26%5Cmax_%7B%5Ctheta_%7Bk%2B1%7D%7D%5C+%5Chat%7B%5Cmathbb%7BE%7D%7D_%7B%28s_t%2Ca_t%29%5Csim%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%7D%5Cleft%5B%5Cfrac%7B%5Cpi_%7B%5Ctheta_%7Bk%2B1%7D%7D%28a_t%7Cs_t%29%7D%7B%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%28a_t%7Cs_t%29%7D%5Chat%7BA%7D%5E%7B%5Ctheta_%7Bk%7D%7D_%7Bt%7D%5Cright%5D%5C%5C+%26%5Ctext%7Bs.t.%7D%5C++%5Cbar%7BD%7D_%7BK+L%7D%5Cleft%28%5Ctheta+%5C%7C+%5Ctheta_%7Bk%7D%5Cright%29%3D%5Cunderset%7Bs+%5Csim+%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%7D%7B%5Cmathrm%7BE%7D%7D%5Cleft%5BD_%7BK+L%7D%5Cleft%28%5Cpi_%7B%5Ctheta%7D%28%5Ccdot+%5Cmid+s%29+%5C%7C+%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%28%5Ccdot+%5Cmid+s%29%5Cright%29%5Cright%5D+%5Cle+%5Cdelta+%5Cend%7Balign%2A%7D+%5C%5C
很显然,这是一个十分复杂的优化问题,TRPO利用泰勒展开将该问题进行了简化:

https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%7D+++%26+%7B%7B%5Ctheta+%7D_%7Bk%2B1%7D%7D%3D%5Carg+%7B%7B%5Cmax+%7D_%7B%5Ctheta+%7D%7D%7B%7Bg%7D%5E%7BT%7D%7D%5Cleft%28+%5Ctheta+-%7B%7B%5Ctheta+%7D_%7Bk%7D%7D+%5Cright%29%5Ctext%7B+%7D+%5C%5C+++%26+%5Cquad+%5Cquad+%5Cquad+%5Cquad+%5Cquad+%5Ctext%7Bs%7D%5Ctext%7B.t%7D%5Ctext%7B.+%7D%5Cfrac%7B1%7D%7B2%7D%7B%7B%5Cleft%28+%5Ctheta+-%7B%7B%5Ctheta+%7D_%7Bk%7D%7D+%5Cright%29%7D%5E%7BT%7D%7DH%5Cleft%28+%5Ctheta+-%7B%7B%5Ctheta+%7D_%7Bk%7D%7D+%5Cright%29%5Cle+%5Cdelta++%5C%5C++%5Cend%7Balign%7D+%5C%5C
这里的导数 https://www.zhihu.com/equation?tex=g 刚好等于策略梯度!然后根据拉格朗日对偶定理,可得到梯度的更新公式

https://www.zhihu.com/equation?tex=%7B%7B%5Ctheta+%7D_%7Bk%2B1%7D%7D%3D%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%2B%5Calpha%5Ej%5Csqrt%7B%5Cfrac%7B2%5Cdelta+%7D%7B%7B%7Bg%7D%5E%7BT%7D%7D%7B%7BH%7D%5E%7B-1%7D%7Dg%7D%7D%7B%7BH%7D%5E%7B-1%7D%7Dg+%5C%5C
这里的 https://www.zhihu.com/equation?tex=%5Calpha 表示回溯系数,它能够避免泰勒展开误差所导致的约束函数无法满足或者代理函数无法提升。
截断代理目标(Clipped Surrogate Objective)

很显然,TRPO算法在实际操作上是十分复杂的,PPO对TRPO进行了简化。
上面我们已经定义了代理目标函数

https://www.zhihu.com/equation?tex=%5Chat%7B%5Cmathbb%7BE%7D%7D_%7B%28s_t%2Ca_t%29%5Csim%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%7D%5Cleft%5B%5Cfrac%7B%5Cpi_%7B%5Ctheta_%7Bk%2B1%7D%7D%28a_t%7Cs_t%29%7D%7B%5Cpi_%7B%5Ctheta_%7Bk%7D%7D%28a_t%7Cs_t%29%7D%5Chat%7BA%7D%5E%7B%5Ctheta_%7Bk%7D%7D_%7Bt%7D%5Cright%5D+%5C%5C
如果直接对该代理目标函数进行更新,会导致与 https://www.zhihu.com/equation?tex=%5Cpi_%7B%5Ctheta_%7Bk%7D%7D 偏离太远,TRPO 设定了KL约束,但是这大大提升了策略更新的难度。为了防止过分的偏离,PPO的做法是直接对代理目标函数进行修正,提出了以下截断代理目标:

https://www.zhihu.com/equation?tex=L%5Cleft%28+s%2Ca%2C%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%2C%5Ctheta++%5Cright%29%3D%5Cmin+%5Cleft%28+%5Cfrac%7B%7B%7B%5Cpi+%7D_%7B%5Ctheta+%7D%7D%28a%7Cs%29%7D%7B%7B%7B%5Cpi+%7D_%7B%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%7D%7D%28a%7Cs%29%7D%7B%7BA%7D%5E%7B%7B%7B%5Cpi+%7D_%7B%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%7D%7D%7D%7D%28s%2Ca%29%2C%5Cquad+%5Coperatorname%7Bclip%7D%5Cleft%28+%5Cfrac%7B%7B%7B%5Cpi+%7D_%7B%5Ctheta+%7D%7D%28a%7Cs%29%7D%7B%7B%7B%5Cpi+%7D_%7B%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%7D%7D%28a%7Cs%29%7D%2C1-%5Cepsilon+%2C1%2B%5Cepsilon++%5Cright%29%7B%7BA%7D%5E%7B%7B%7B%5Cpi+%7D_%7B%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%7D%7D%7D%7D%28s%2Ca%29+%5Cright%29+%5C%5C
其中 https://www.zhihu.com/equation?tex=%5Cepsilon 是用于度量新策略与老策略之间偏差程度的超参数。下面这幅图描述了目标函数 https://www.zhihu.com/equation?tex=L%5Cleft%28+s%2Ca%2C%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%2C%5Ctheta++%5Cright%29 随 https://www.zhihu.com/equation?tex=r%3D%5Cfrac%7B%7B%7B%5Cpi+%7D_%7B%5Ctheta+%7D%7D%28a%7Cs%29%7D%7B%7B%7B%5Cpi+%7D_%7B%7B%7B%5Ctheta+%7D_%7Bk%7D%7D%7D%7D%28a%7Cs%29%7D 变化的情况,可以看出,当 https://www.zhihu.com/equation?tex=A%3E0 时,也就是优势函数为正时,增加对应动作出现的可能性,可以增加目标函数的值,但一旦超过了,目标函数就会截断为 ,此时再增加也没有用了,从而防止https://www.zhihu.com/equation?tex=%7B%5Cpi+%7D_%7B%5Ctheta_%7Bk%2B1%7D%7D%28a%7Cs%29 偏离https://www.zhihu.com/equation?tex=%7B%5Cpi+%7D_%7B%5Ctheta_%7Bk%7D%7D%28a%7Cs%29 太多。同样,当 https://www.zhihu.com/equation?tex=A%3C0 时,减少对应动作出现的可能性,可以增加目标函数的值,但一旦小于,目标函数就会截断为 ,此时不会再减小。


另外,为了近一步防止新策略偏离太多,不同PPO方法中还可以使用一系列有用的技巧,例如,提前终止(early stopping)——当新策略与老策略之间的平均KL-散度超过一定门限时,停止梯度上升。
广义优势估计(Generalized Advantage Estimation)

PPO中采用GAE的方法对优势函数进行估计,具体而言,其计算公式为

https://www.zhihu.com/equation?tex=%5Chat%7BA%7D_%7Bt%7D%5E%7BG+A+E%28%5Cgamma%2C+%5Clambda%29%7D%3D%5Csum_%7Bl%3D0%7D%5E%7B%5Cinfty%7D%28%5Cgamma+%5Clambda%29%5E%7Bl%7D+%5Cdelta_%7Bt%2Bl%7D%5E%7BV%7D%3D%5Csum_%7Bl%3D0%7D%5E%7B%5Cinfty%7D%28%5Cgamma+%5Clambda%29%5E%7Bl%7D%5Cleft%5Br_%7Bt%2Bl%7D%2B%5Cgamma+V%5Cleft%28s_%7Bt%2Bl%2B1%7D%5Cright%29-V%5Cleft%28s_%7Bt%2Bl%7D%5Cright%29%5Cright%5D+%5C%5C
其估计advantage的方法与 https://www.zhihu.com/equation?tex=TD%28%5Clambda%29 类似,从公式上可以看出GAE中分别考虑了状态 https://www.zhihu.com/equation?tex=S_t 后续各个时刻的advantage,然后按照距离当前状态的远近加权求和,从而起到了平滑作用。为了便于理解,考虑两种极限情况:

https://www.zhihu.com/equation?tex=%5Cbegin%7Barray%7D%7Bll%7D+%5Coperatorname%7BGAE%7D%28%5Cgamma%2C+0%29%3A+%5Cquad+%5Chat%7BA%7D_%7Bt%7D%3A%3D%5Cdelta_%7Bt%7D%3Dr_%7Bt%7D%2B%5Cgamma+V%5Cleft%28s_%7Bt%2B1%7D%5Cright%29-V%5Cleft%28s_%7Bt%7D%5Cright%29+%5C%5C+%5Coperatorname%7BGAE%7D%28%5Cgamma%2C+1%29%3A+%5Cquad+%5Chat%7BA%7D_%7Bt%7D%3A%3D%5Csum_%7Bl%3D0%7D%5E%7B%5Cinfty%7D+%5Cgamma%5E%7Bl%7D+%5Cdelta_%7Bt%2Bl%7D%3D%5Csum_%7Bl%3D0%7D%5E%7B%5Cinfty%7D+%5Cgamma%5E%7Bl%7D+r_%7Bt%2Bl%7D-V%5Cleft%28s_%7Bt%7D%5Cright%29+%5Cend%7Barray%7D+%5C%5C

https://www.zhihu.com/equation?tex=%5Clambda%3D0 时,advantage便是使用 https://www.zhihu.com/equation?tex=TD%280%29 估计的Q值与V值的差;https://www.zhihu.com/equation?tex=%5Clambda%3D1 时,advantage则是使用蒙特卡洛方法估计的收益 https://www.zhihu.com/equation?tex=G_t 值与V 值的差。可以看出 https://www.zhihu.com/equation?tex=%5Clambda 作为一个调整因子,它越接近1时,方差越大,偏差越小,接近0时反之。这也是GAE的一个优势,即可以更加不同环境的情况让我们可以调整参数来找到更合理的advantage。
另外,PPO原文还提到可以对GAE进行截断,即不需要在整个episode中进行平均,只需选取关联性较大的 https://www.zhihu.com/equation?tex=N 步即可:

https://www.zhihu.com/equation?tex=%5Chat%7BA%7D_%7Bt%7D%5E%7BTrunc-G+A+E%28%5Cgamma%2C+%5Clambda%29%7D%3D%5Csum_%7Bl%3D0%7D%5E%7BN%7D%28%5Cgamma+%5Clambda%29%5E%7Bl%7D+%5Cdelta_%7Bt%2Bl%7D%5E%7BV%7D%3D%5Csum_%7Bl%3D0%7D%5E%7BN%7D%28%5Cgamma+%5Clambda%29%5E%7Bl%7D%5Cleft%5Br_%7Bt%2Bl%7D%2B%5Cgamma+V%5Cleft%28s_%7Bt%2Bl%2B1%7D%5Cright%29-V%5Cleft%28s_%7Bt%2Bl%7D%5Cright%29%5Cright%5D+%5C%5C
算法流程

PPO算法的具体流程只需在标准策略梯度(vanilla policy gradient)的基础上做非常小的改动,简单来说,就是把策略更新时的损失函数从 https://www.zhihu.com/equation?tex=L%5E%7BPG%7D 替换成 https://www.zhihu.com/equation?tex=L,然后在每一次更新时对该目标函数进行多次梯度上升即可。


参考文献

J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, ‘Proximal Policy Optimization Algorithms’, arXiv:1707.06347 , Aug. 2017, Accessed: Nov. 22, 2021. . Available: http://arxiv.org/abs/1707.06347
J. Achiam, ‘SpinningUp2018’, 2018.
页: [1]
查看完整版本: 【深度强化学习】PPO 算法理解