第2卷第1期 智能系统学报 Vol.2 Ng 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 增强学习中的直接策略搜索方法综述 王学宁1，陈伟张锰徐昕1，贺汉根 (1.国防科技大学机电工程与自动化学院，湖南长沙410073：2.北京清河大楼子9，北京100085) 摘要：对增强学习中各种策略搜索算法进行了简单介绍，建立了策略梯度方法的理论框架，并且根据这个理论框 架的指导，对一些现有的策略梯度算法进行了推广，讨论了近年来出现的提高策略梯度算法收敛速度的几种方法， 对于非策略梯度搜索算法的最新进展进行了介绍，对进一步研究工作的方向进行了展望. 关键词：增强学习：策路搜索：策略梯度 中图分类号：TP242文献标识码：A文章编号：1673-4785(2007)01-001609 A survey of direct policy search methods in reinforcement learning WAN G Xue-ning',CHEN Wei ,ZHANG Meng?XU Xin',HE Hamgen' (1.School of Electromechanical Engineering and Automation,National University of Defense Technology,Changsha 410073, China;2.Qinghe Building Zi 9,Beijing 100085,China) Abstract:The direct policy search methods in reinforcement learning are described,and the theoretic frame- work of policy gradient methods is presented.According to this framework,some current policy gradient algorithms are generalized.The new methods of speeding up the policy gradient algorithms are discussed. The new nompolicy gradient search methods are also described.Finally,some future directions of research work are also given. Key words reinforcement learning;policy search;policy Gradient 增强学习(reinforcement learning,又称为强化往是随机策略.2)行为值的微小变化可能会引起策 学习或再励学习)，是近年来兴起的一类机器学习方 略很大的变化，这就使得值函数方法在很多问题中 法.增强学习强调在与环境的交互中学习，学习过程 不能保证收敛1.典型的值函数方法如Q学习算 中仅要求获得评价性的反馈信号(reward/rein- 法、Sarsa等方法如果采用函数逼近器，即使在小规 forcement signal,称为回报或增强信号)，以极大化 模的MDP问题中也可能会发散9.川.3)值函数方 未来的回报为学习目标.增强学习由于不需要给定 法需要找出具有最大值的那个行为，但是如果行为 各种状态下的教师信号，因此对于求解复杂的优化 空间是连续的，这将会是一个很难或者很费时的问 决策问题具有广泛的应用前景).目前，增强学习在 题 理论和算法研究方面已取得了许多成果，成为求解 增强学习的另外一大类方法是直接策略搜索方 序贯(sequential)优化决策问题（通常建模为马氏决 法.该类方法把策略参数化，并且估算优化指标相对 策问题，Markov decision problems)的一类有效方 于策略参数的梯度，然后利用这个梯度来调整这些 法2.1 参数，最后得到最优或者局部最优策略.直接策略搜 在过去的10年中，增强学习的研究主要集中在 索方法最后得到的策略既可以是确定性策略，也可 基于值函数的方法.但是基于值函数的学习方法具 以是随机性的策略.尽管值函数方法也可以利用 有以下几个缺陷：1)基于值函数估计的方法易于寻 soft-max方法得到随机策略，但是这需要引进新的 找确定性的最优策略，但是，许多问题的最优策略往 参数，并且设定“柔软度”(softness)也比较困难，没 有任何理论指导.相对于值函数方法，直接策略搜索 收稿日期：20060707. 方法的收敛性也容易证明.因此，近年来直接策略搜 基金项目：国家自然科学基金资助项目(60234030,60303012) 索方法引起了广泛的关注2.1) 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 增强学习中的直接策略搜索方法综述 王学宁1 ,陈 伟1 ,张 锰2 ,徐 昕1 ,贺汉根1 (1. 国防科技大学 机电工程与自动化学院 ,湖南 长沙 410073 ;2. 北京清河大楼 子 9 ,北京 100085) 摘 要 :对增强学习中各种策略搜索算法进行了简单介绍 ,建立了策略梯度方法的理论框架 ,并且根据这个理论框 架的指导 ,对一些现有的策略梯度算法进行了推广 ,讨论了近年来出现的提高策略梯度算法收敛速度的几种方法 , 对于非策略梯度搜索算法的最新进展进行了介绍 ,对进一步研究工作的方向进行了展望. 关键词 :增强学习 ;策略搜索 ;策略梯度 中图分类号 : TP242 文献标识码 :A 文章编号 :167324785 (2007) 0120016209 A survey of direct policy search methods in reinforcement learning WAN G Xue2ning 1 ,CH EN Wei 1 ,ZHAN G Meng 2 ,XU Xin 1 , H E Han2gen 1 (1. School of Electromechanical Engineering and Automation , National University of Defense Technology , Changsha 410073 , China ;2. Qinghe Building Zi 9 , Beijing 100085 , China) Abstract :The direct policy search met hods in reinforcement learning are described , and t he theoretic frame2 work of policy gradient met hods is presented. According to t his framework , some current policy gradient algorit hms are generalized. The new met hods of speeding up t he policy gradient algorit hms are discussed. The new non2policy gradient search met hods are also described. Finally , some f ut ure directions of research work are also given. Keywords :reinforcement learning ; policy search ; policy Gradient 收稿日期 :2006207207. 基金项目 :国家自然科学基金资助项目(60234030 , 60303012) . 增强学习 (reinforcement learning ,又称为强化 学习或再励学习) ,是近年来兴起的一类机器学习方 法. 增强学习强调在与环境的交互中学习 ,学习过程 中仅要求获得评价性的反馈信号 ( reward/ rein2 forcement signal ,称为回报或增强信号) ,以极大化 未来的回报为学习目标. 增强学习由于不需要给定 各种状态下的教师信号 ,因此对于求解复杂的优化 决策问题具有广泛的应用前景[1 ] . 目前 ,增强学习在 理论和算法研究方面已取得了许多成果 ,成为求解 序贯(sequential) 优化决策问题(通常建模为马氏决 策问题 ,Markov decision problems) 的一类有效方 法[2 - 7 ] . 在过去的 10 年中 ,增强学习的研究主要集中在 基于值函数的方法. 但是基于值函数的学习方法具 有以下几个缺陷 :1) 基于值函数估计的方法易于寻 找确定性的最优策略 ,但是 ,许多问题的最优策略往 往是随机策略. 2) 行为值的微小变化可能会引起策 略很大的变化 ,这就使得值函数方法在很多问题中 不能保证收敛[8 ] . 典型的值函数方法如 Q2学习算 法、Sarsa 等方法如果采用函数逼近器 ,即使在小规 模的 MDP 问题中也可能会发散[9 - 11 ] . 3) 值函数方 法需要找出具有最大值的那个行为 ,但是如果行为 空间是连续的 ,这将会是一个很难或者很费时的问 题. 增强学习的另外一大类方法是直接策略搜索方 法. 该类方法把策略参数化 ,并且估算优化指标相对 于策略参数的梯度 ,然后利用这个梯度来调整这些 参数 ,最后得到最优或者局部最优策略. 直接策略搜 索方法最后得到的策略既可以是确定性策略 ,也可 以是随机性的策略. 尽管值函数方法也可以利用 soft2max 方法得到随机策略 ,但是这需要引进新的 参数 ,并且设定“柔软度”(soft ness) 也比较困难 ,没 有任何理论指导. 相对于值函数方法 ,直接策略搜索 方法的收敛性也容易证明. 因此 ,近年来直接策略搜 索方法引起了广泛的关注[12 - 15 ]
第1期 王学宁，等：增强学习中的直接策略搜索方法综述 ·17 直接策略搜索算法的核心就是估算优化指标相 N.1 (4) 对于策略参数的梯度，根据在估算这个梯度的过程 中是否用到策略相对于自己参数的梯度，可以把直 上述2种决策优化目标函数在动态规划领域都 接策略搜索算法分为2类：策略梯度方法和非策略 得到了广泛的研究和应用，在增强学习算法和理论 梯度方法.如果用到了策略相对于自己参数的梯度， 的研究中，主要针对折扣总回报目标函数进行了大 则属于策略梯度方法，否则属于非策略梯度方法. 量研究.近年来，针对平均期望回报目标的增强学习 由于策略梯度方法的发展历程尚短，因此还没 方法也取得了一定的研究进展16..文献[17]对3 有文章介绍策略梯度方法的理论体系和各种算法. 种目标函数的性能差异进行了深入分析，指出折扣 文中详细地介绍了各种策略梯度算法，并建立了理 总回报目标函数可以在性能方面近似于平均期望回 论框架，在此框架的指导下，对现有的策略梯度方法 报目标.对于有限阶段的Markov决策问题，当折扣 进行了推广 因子Y=1时，2种目标函数等价.因此，文中将以具 有折扣总回报目标函数的Markov决策问题为研究 1增强学习 对象 增强学习中，往往把问题建模为马氏决策过程 定义2 Markov决策过程的一般随机策略 (Markov decision process,MDP).Markov决策过 记S,和A,分别为Markov决策过程在时刻t的状 程按照决策时间的特性和模型中其他因素的不同， 态集和行为集，集合T,=f(s,a:s∈S,a∈A.则 可以有多种分类方法，如平稳和非平稳Markov决 称测度序列π=（乃，乃，为Markov决策过程的 策过程、离散时间和连续时间Markov决策过程、离 随机策略，若对于任意1≥0，π为T。×… 散状态空间和连续状态空间Markov决策过程等. .1XS,到A,的转移概率.且满足： 在文中将以离散时间平稳Markov决策过程为研究 A,(s)1S,a1,31,m,0)=1.(5) 对象.其定义如下： 定义2给出了一般随机策略的严格数学定义 定义1离散时间平稳Markov决策过程一 从概念上讲，时刻t的策略兀，确定了在该时刻选择 个离散时间平稳Markov决策过程可以用如下的五 行为的规则.在理论研究和实际应用中，通常针对一 元组来表示，即：{S,A,r,P,g,式中：S为有限或连 类特殊的策略即马氏策略，其定义如下： 续状态空间，A为有限或连续行为空间，：SXA→R 定义3 Markov决策过程的马氏策略设 为回报函数，P为MDP的状态转移概率，满足如下 Markov决策过程的策略π=（而，乃，）满足： 的Markov性和时齐特性： (a(s)S,a.1,S.1,“,am,S0)= i,j∈S,a∈A,n≥0， 元(a(s)|s)1≥0. 6) p(X jl X i,A,a,X1.A... 则称Ⅱ为马氏策略.若对于任意1习，有乃-乃，则 Xo,Ao)=p(X =jl X,=i, (1) 称马氏策略π为平稳的， A=a p(i,a,i) 在定义了Markov决策过程的策略后，可以对 式中：n为决策优化的目标函数. 状态的值函数进行如下定义： 在上述定义中，状态转移概率P满足式2) 定义4 Markov决策过程的状态值函数设π 为平稳策略，则Markov决策过程的状态值函数定 2i.a》=1 (2) 义为 在每个时间点1∈0,1,2，…，状态、行为和回 w=[= 7) 报分别记为s∈S,a∈A,n∈R Markov决策过程的决策优化目标函数n主要 式中：数学期望E[]定义在状态转移概率P和平 有2种类型.即折扣总回报目标和平均期望回报目 稳策略π的分布上 标，分别如式(3)和式4所示 Markov决策过程的状态值函数确定了从某一 MDP折扣总回报目标： 状态出发按照策略π选择行为所获得的期望总回报 的大小.类似于状态值函数，Markov决策过程的行 几= (3) 为值函数确定了从某一状态·行为对出发，按照策 式中0<Y<1. 略π选择行为所获得的期望总回报的大小.在增强 MDP平均期望回报目标 学习算法中，为便于进行策略的更新，通常对行为值 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
直接策略搜索算法的核心就是估算优化指标相 对于策略参数的梯度 ,根据在估算这个梯度的过程 中是否用到策略相对于自己参数的梯度 ,可以把直 接策略搜索算法分为 2 类 :策略梯度方法和非策略 梯度方法. 如果用到了策略相对于自己参数的梯度 , 则属于策略梯度方法 ,否则属于非策略梯度方法. 由于策略梯度方法的发展历程尚短 ,因此还没 有文章介绍策略梯度方法的理论体系和各种算法. 文中详细地介绍了各种策略梯度算法 ,并建立了理 论框架 ,在此框架的指导下 ,对现有的策略梯度方法 进行了推广. 1 增强学习 增强学习中 ,往往把问题建模为马氏决策过程 (Markov decision process , MDP) . Markov 决策过 程按照决策时间的特性和模型中其他因素的不同 , 可以有多种分类方法 ,如平稳和非平稳 Markov 决 策过程、离散时间和连续时间 Markov 决策过程、离 散状态空间和连续状态空间 Markov 决策过程等. 在文中将以离散时间平稳 Markov 决策过程为研究 对象. 其定义如下 : 定义 1 离散时间平稳 Markov 决策过程 一 个离散时间平稳 Markov 决策过程可以用如下的五 元组来表示 ,即 :{ S , A , r, P,η} ,式中 : S 为有限或连 续状态空间 , A 为有限或连续行为空间 , : S ×A →R 为回报函数 , P 为 MDP 的状态转移概率 ,满足如下 的 Markov 性和时齐特性 : Πi , j ∈S , a ∈A , Πn ≥0 , p ( Xt+1 = j | Xt = i , A t = a , Xt- 1 , A t- 1 , …, X0 , A0 ) = p ( Xt+1 = j | Xt = i , (1) A t = a) = p ( i , a , j) . 式中 :η为决策优化的目标函数. 在上述定义中 ,状态转移概率 P 满足式(2) . j ∑∈S p ( i , a , j) = 1. (2) 在每个时间点 t ∈{ 0 , 1 , 2 , …} ,状态、行为和回 报分别记为 st ∈S , at ∈A , rt ∈R. Markov 决策过程的决策优化目标函数η主要 有 2 种类型. 即折扣总回报目标和平均期望回报目 标 ,分别如式(3) 和式(4) 所示. MDP 折扣总回报目标 : ηd = E ∑ ∞ t =0 γt rt . (3) 式中 :0 <γ< 1 , MDP 平均期望回报目标 : ηa = limsup N →∞ 1 N E ∑ N - 1 t = 0 rt . (4) 上述 2 种决策优化目标函数在动态规划领域都 得到了广泛的研究和应用 ,在增强学习算法和理论 的研究中 ,主要针对折扣总回报目标函数进行了大 量研究. 近年来 ,针对平均期望回报目标的增强学习 方法也取得了一定的研究进展[16 - 17 ] . 文献[ 17 ]对 3 种目标函数的性能差异进行了深入分析 ,指出折扣 总回报目标函数可以在性能方面近似于平均期望回 报目标. 对于有限阶段的 Markov 决策问题 ,当折扣 因子γ= 1 时 ,2 种目标函数等价. 因此 ,文中将以具 有折扣总回报目标函数的 Markov 决策问题为研究 对象. 定义 2 Markov 决策过程的一般随机策略 记 St 和 A t 分别为 Markov 决策过程在时刻 t 的状 态集和行为集 ,集合Γt = { (s, a) :s ∈St , a ∈A t} . 则 称测度序列π= (π0 ,π1 , …) 为 Markov 决策过程的 随机策略 , 若对于任意 t ≥0 ,πt 为 Γ0 ×Γ1 × … Γt - 1 ×St 到 A t 的转移概率 ,且满足 : πt ( A t (st) | st , at- 1 ,st- 1 , …, a0 ,s0 ) = 1. (5) 定义 2 给出了一般随机策略的严格数学定义 , 从概念上讲 ,时刻 t 的策略πt 确定了在该时刻选择 行为的规则. 在理论研究和实际应用中 ,通常针对一 类特殊的策略即马氏策略 ,其定义如下 : 定义 3 Markov 决策过程的马氏策略 设 Markov 决策过程的策略π= (π0 ,π1 , …,πt) 满足 : π1 ( at (st) | st , at- 1 ,st- 1 , …, a0 ,s0 ) = πt ( at (st) | st) Πt ≥0. (6) 则称π为马氏策略. 若对于任意 t ≥1 ,有πt =π0 ,则 称马氏策略π为平稳的. 在定义了 Markov 决策过程的策略后 ,可以对 状态的值函数进行如下定义 : 定义 4 Markov 决策过程的状态值函数 设π 为平稳策略 ,则 Markov 决策过程的状态值函数定 义为 V π (s) = E π ∑ ∞ t =0 γt rt | s0 = s . (7) 式中 :数学期望 E π [ ]定义在状态转移概率 P 和平 稳策略π的分布上. Markov 决策过程的状态值函数确定了从某一 状态出发按照策略π选择行为所获得的期望总回报 的大小. 类似于状态值函数 ,Markov 决策过程的行 为值函数确定了从某一状态 - 行为对出发 ,按照策 略π选择行为所获得的期望总回报的大小. 在增强 学习算法中 ,为便于进行策略的更新 ,通常对行为值 第 1 期 王学宁 ,等 :增强学习中的直接策略搜索方法综述 ·17 ·
·18 智能系统学报 第2卷 函数进行估计.下面的定义5给出了Markov决策 全行为(al-action)方法，因为在某个时间步估算梯 过程行为值函数的定义： 度时，必须考虑所有可能执行的行为.在实际的算法 定义5 Markov决策过程的行为值函数设π 中，经常采用单个行为方法(single-action),也就是 为平稳策略，则Markov决策过程的行为值函数定 在某个时间步估计梯度时，仅仅考虑该时刻实际执 义为 行的那个行为，即 '(s,a E"=s,a =d 8) (s. (11) 单个行为方法中，为了防止过于频繁地选择某一 2 策略梯度增强学习及其理论框架 个行为而忽略其他行为，往往还除以r(l0,s): 2.1策略梯度方法的理论框架 (12) 2.1.1基本概念和基本理论 后面的描述中，将不会过分注重区分全行为和 策略π决定了行为的选择，而行为的选择决定 单个行为方法，尽管二者在实际的执行过程中有不 了状态的转移概率，状态转移概率直接影响优化指 标1的计算，因此，不同的π具有不同的1值，所以 同之处，但是从理论上来说，二者的区别不大 2.1.2策略梯度算法的收敛条件 优化指标其实是关于策略π的函数.直接策略搜索 为了保证策略梯度算法收敛，必须满足以下几 方法的思想就是调整策略的参数，使得优化指标？ 个条件 达到最大或者局部最大称具有需要调整参数的策 略为参数化策略 V对任何的状态.行为a和参数8.存 定义6参数化策略参数化策略π是从状态 在，并且迹1 一致有界」 s∈S到行为空间上概率分布的映射.即在给s∈S d0n(s,a) 定以及策略的参数0时，选择行为a的概率为π(d 2)对任何的状态s,回报r(s)一致有界 0,s 3)针对任何一组参数0∈R所对应的状态转移 定义了参数化策略之后，自然而然就想到利用 矩阵P(),具有唯一的平稳分布入(9，满足如下的 梯度品米调整参数日一种计算方法为 平衡方程： 入(0P(0=入(9. a知a加aπ 现在问题的关键就是如何得到g(s,ad.因为 00=Ox 00 9) Q(s,往往是不知道的，需要对它的值进行估计 但是函数关系式)很难求出，尤其是当系统的状 其实，所有的策略梯度方法，不同之处仅仅在于估算 态转移概率未知时，无法得到函数)的解析式， 方法的不同.下面结合各种基本的策略梯度算法 因此其梯度也无法利用解析方法计算.所以，只有寻 g(s,d来证明这个论断 求其他途径来进行梯度估计.Sutton在文献[8]中 2.2各种基本算法 提出了一种梯度估计方法： 2.2.1 REINFORCE算法 定理1对于任意给定的MDP,无论是折扣型 最直接的想法就是把实际得到的回报R,= 回报还是平均型回报，都有下式成立 0=96gs,w. :来作为1时刻的的Q(s,a近似值.这种 (10) 算法就是Williams提出的REINFORCE算法I8] 式中：d(y=,无/P,m=m,y表示在初始状态为 这是在增强学习领域最早的策略梯度算法： 0的情况下，策略为π时，达到状态s的可能性.上 品应aRa (13) 述梯度估计公式最大的一个优点是：没有出现 作为最早被提出的策略梯度方法，REN- ,因此，策略的变化对状态的分布影响不大， FORCE算法并没有引起太多的关注，主要原因就 是该算法只能处理周期性的马氏决策问题，并且收 这就适合用采样方法来估计梯度.如果状态s是采 敛速度很慢， 用策略x时的采样，那么0s,)就是的无 2.2.2带有值函数逼近器的策略梯度方法 偏估计，如果采用P,0来近似品就称为 如果状态是连续的情况，那么此时，就需要函数 逼近器来对Q进行逼近.但是，函数逼近器必须满 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
函数进行估计. 下面的定义 5 给出了 Markov 决策 过程行为值函数的定义 : 定义 5 Markov 决策过程的行为值函数 设π 为平稳策略 ,则 Markov 决策过程的行为值函数定 义为 Q π (s, a) = E π ∑ ∞ t = 0 γt rt | s0 = s, a0 = a . (8) 2 策略梯度增强学习及其理论框架 2. 1 策略梯度方法的理论框架 2. 1. 1 基本概念和基本理论 策略π决定了行为的选择 ,而行为的选择决定 了状态的转移概率 ,状态转移概率直接影响优化指 标η的计算 ,因此 ,不同的π具有不同的η值 ,所以 优化指标其实是关于策略π的函数. 直接策略搜索 方法的思想就是调整策略的参数 ,使得优化指标η 达到最大或者局部最大. 称具有需要调整参数的策 略为参数化策略. 定义 6 参数化策略 参数化策略π是从状态 s ∈S 到行为空间上概率分布的映射. 即在给 s ∈S 定以及策略的参数θ时 ,选择行为 a 的概率为π( a| θ,s) . 定义了参数化策略之后 ,自然而然就想到利用 梯度 5η 5θ 来调整参数θ. 一种计算方法为 5η 5θ = 5η 5π 5π 5θ . (9) 但是函数关系式η(π) 很难求出 ,尤其是当系统的状 态转移概率未知时 ,无法得到函数η(π) 的解析式 , 因此其梯度也无法利用解析方法计算. 所以 ,只有寻 求其他途径来进行梯度估计. Sutton 在文献[8 ]中 提出了一种梯度估计方法 : 定理 1 对于任意给定的 MDP ,无论是折扣型 回报还是平均型回报 ,都有下式成立 5η 5θ = ∑s d π (s) ∑a 5π(s, a) 5θ Q π (s, a) . (10) 式中 :d π (s) = ∑ ∞ t = 0 γt Pr{ st = s| s0 ,π}表示在初始状态为 s0 的情况下 ,策略为π时 ,达到状态 s 的可能性. 上 述梯度估计公式最大的一个优点是 : 没有出现 5 d π (s) 5θ ,因此 ,策略的变化对状态的分布影响不大 , 这就适合用采样方法来估计梯度. 如果状态 s 是采 用策略π时的采样 ,那么 ∑a 5π 5θ Q π (s, a) 就是 5η 5θ 的无 偏估计[8 ] . 如果采用 ∑a 5π 5θ Q π (s, a) 来近似 5η 5θ ,就称为 全行为(all2action) 方法 ,因为在某个时间步估算梯 度时 ,必须考虑所有可能执行的行为. 在实际的算法 中 ,经常采用单个行为方法 (single2action) ,也就是 在某个时间步估计梯度时 ,仅仅考虑该时刻实际执 行的那个行为 ,即 5η 5θ ≈ 5π 5θ Q π (st , at) . (11) 单个行为方法中 ,为了防止过于频繁地选择某一 个行为而忽略其他行为 ,往往还除以π(a|θ,s) : 5η 5θ ≈ 5π 5θ Q π (st , at) 1 π(s, a) . (12) 后面的描述中 ,将不会过分注重区分全行为和 单个行为方法 ,尽管二者在实际的执行过程中有不 同之处 ,但是从理论上来说 ,二者的区别不大. 2. 1. 2 策略梯度算法的收敛条件 为了保证策略梯度算法收敛 ,必须满足以下几 个条件 : 1) 对任何的状态 s,行为 a 和参数θi , 5π(s, a) 5θi 存 在 ,并且 5π(s, a) 5θi 1 π(s, a) 一致有界. 2) 对任何的状态 s,回报 r(s) 一致有界. 3) 针对任何一组参数θ∈R n 所对应的状态转移 矩阵 P (θ) ,具有唯一的平稳分布λ(θ) ,满足如下的 平衡方程 : λ(θ) P(θ) =λ(θ) . 现在问题的关键就是如何得到 Q π (s, a) . 因为 Q π (s, a) 往往是不知道的 ,需要对它的值进行估计. 其实 ,所有的策略梯度方法 ,不同之处仅仅在于估算 方法的不同. 下面结合各种基本的策略梯度算法 Q π (s, a) 来证明这个论断. 2. 2 各种基本算法 2. 2. 1 REIN FORCE 算法 最直接的想法就是把实际得到的回报 Rt = ∑ ∞ k = 1 γk - 1 rt + k来作为 t 时刻的的 Q π (st , at) 近似值. 这种 算法就是 Williams 提出的 REINFORCE 算法[18 ] , 这是在增强学习领域最早的策略梯度算法 : 5η 5θ ∝ 5π(st , at) 5θ Rt 1 π(st , at) . (13) 作为最早被提 出的策略 梯度方法 , REIN2 FORCE 算法并没有引起太多的关注 ,主要原因就 是该算法只能处理周期性的马氏决策问题 ,并且收 敛速度很慢. 2. 2. 2 带有值函数逼近器的策略梯度方法 如果状态是连续的情况 ,那么此时 ,就需要函数 逼近器来对 Q 进行逼近. 但是 ,函数逼近器必须满 ·18 · 智 能 系 统 学 报 第 2 卷
第1期 王学宁，等：增强学习中的直接策略搜索方法综述 ·19· 足一定的条件，才能保证算法的收敛. 假设利用具有参数w的函数f。:SXA→R来 :山=+：亚aL++ 逼近Q,并且参数w满足条件： T(0,m) (s1 a) 又TSH.LaH,1 w arg min >(oi-f(s,.a))2. 14) (SH.1,aH-1 式中：⑨为O”的某种估计值，比如可以是R.如果 所以 函数f满足式14)，同时又满足相容性条件： atd-迹dL 15) a(s.n H.I v(s a) Cw 00 n(s,a) 21) 那么 =dw∑急.sw 此时可以看出，估计式Am就是在￠(s,a)= 16) 式16)的证明过程，请参看文献[81. 'n前提下，对梯度估计H次的平均值。 关于值函数逼近器的选择，一种可行的方案是 Baxter等分析了折扣因子y的取值对上述算 采用如下的形式： 法的影响：Y越接近于1，梯度估计越精确，事实上 (s.a wT Tais.al 估计的偏差正比于1-》，但是，Y1时，方差也无 (s,a 17) 限增大，所以，梯度估计的精确性与方差是一对矛 由式(17)方法可以很容易地构造出策略迭代方 盾，必须选择适当的Y对二者进行折衷处理.因此， 法1，并且该方法的收敛性也很容易证明.但是，由 尽管可以通过减小Y来减小方差，但是，这种方法的 于每次更新actor的参数之后，critic的参数需要重 调整能力有限. 新求解，从这个意义上来说，critic的参数并不具有 GPOMDP解除了REINFORCE算法只能求解 “学习"功能，并且求解critic参数的过程可能也比 周期性马氏决策问题的限制，但是仍然没能提高算 较耗时，这就影响了整个算法的收敛速度 法的收敛速度 2.2.3 GPOMDP算法 2.3现有策略梯度算法的推广 Baxter等提出了GPOMDP算法，尽管作者给 根据时域差分的思想，在策略梯度算法中可以 出了一种比较复杂的证明方法，但是，从迭代过程来 利用截断回报作为Q(s,ad的近似值，例如，t时刻的 看，GPOMDP仍然是利用式(12)来估计梯度，只不 Q(sr,a可以用一步截断回报来估计 过是行为值函数的估计采用了以下公式： Q(s,d≈R0=n+1+10(s+1,a+1.(22) H.t (s:.a)= (18 式中：Q为Q的某种估计值.也就是利用1+1时刻 的估计值，来对1时刻的估计值进行更新 下面证明这个结论： 把上式推广到k步截断回报为 GPOMDP算法中，迭代公式为 1=么，+404L Q(s,d≈Rw=n+1++2+…+ 80 (s:a) (19) 1n+k+(s+,a+ 23) △+1=△，++12+1. (20) 当k=时，就是实际回报 式中：，称为适合度轨迹，初始化为0向量，△。也初 始化为0向量.上述公式迭代H次后，梯度的估计 R=R=+.因此，REINFORCE算 法是截断回报算法的一种特例 值为品产为了简化证明过程，只分析△ 继续推广，可以利用各种截断回报的加权和来 为了书写简便，定义m(s,d=应心 Q(s,ad近似 08 因为0=0，所以 24 1=z4 (so ao) 只要是权系数满足a=1,则R为Qs,W的 a=yYT。L+I4 无偏估计.对比式18)和式(24，可以看出，GPOM T(0,w) T(S1,) DP其实是式24在a4=时的一个特例。 23=Y7匹4m y匹al+匹4mL H (so co) +y(s,a) T(2, 当然也可以利用回报来计算Q(s,d近似值： 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
足一定的条件 ,才能保证算法的收敛[8 ,19 ] . 假设利用具有参数 w 的函数 f w : S ×A →R 来 逼近 Q ,并且参数 w 满足条件 : w = arg min w ∑ t (Q^ π t - f (st , at) ) 2 . (14) 式中 :Q^ π t 为 Q π t 的某种估计值 ,比如可以是 Rt . 如果 函数 f 满足式(14) ,同时又满足相容性条件 : 5 f w (s, a) 5w = 5π(s, a) 5θ 1 π(s, a) . (15) 那么 5η 5θ = ∑s d π (s) ∑a 5π 5θ f w (s, a) . (16) 式(16) 的证明过程 ,请参看文献[8 ]. 关于值函数逼近器的选择 ,一种可行的方案是 采用如下的形式 : f w (s, a) = w T ý θπ(s, a) π(s, a) . (17) 由式(17) 方法可以很容易地构造出策略迭代方 法[8 ] ,并且该方法的收敛性也很容易证明. 但是 ,由 于每次更新 actor 的参数之后 ,critic 的参数需要重 新求解 ,从这个意义上来说 ,critic 的参数并不具有 “学习”功能 ,并且求解 critic 参数的过程可能也比 较耗时 ,这就影响了整个算法的收敛速度. 2. 2. 3 GPOMDP 算法 Baxter 等提出了 GPOMDP 算法 ,尽管作者给 出了一种比较复杂的证明方法 ,但是 ,从迭代过程来 看 , GPOMDP 仍然是利用式 (12) 来估计梯度 ,只不 过是行为值函数的估计采用了以下公式 : Q^ (st , at) = ∑ H- t k =1 γk- 1 rt+k . (18) 下面证明这个结论 : GPOMDP 算法中 ,迭代公式为 zt+1 = γzt + 5π(st , at) 5θ 1 π(st , at) . (19) Δt+1 = Δt + rt+1 zt+1 . (20) 式中 :zt 称为适合度轨迹 ,初始化为 0 向量 ,Δ0 也初 始化为 0 向量. 上述公式迭代 H 次后 ,梯度的估计 值为 5η 5θ = 1 H ΔH . 为了简化证明过程 ,只分析ΔH . 为了书写简便 ,定义 ýπ(s, a) = 5π(s, a) 5θ . 因为 z0 = 0 ,所以 z1 = ýπ(s0 , a0 ) π(s0 , a0 ) , z2 =γ ýπ(s0 , a0 ) π(s0 , a0 ) + ýπ(s1 , a1 ) π(s1 , a2 ) , z3 =γ2 ýπ(s1 , a0 ) π(s0 , a0 ) +γ ýπ(s1 , a1 ) π(s1 , a1 ) + ýπ(s2 , a2 ) π(s2 , a2 ) , … z H =γH - 1 ýπ(s0 , a0 ) π(s0 , a0 ) +γH - 2 ýπ(s1 , a1 ) π(s1 , a1 ) + …+ ýπ(s H - 1 , a H - 1 π(s H - 1 , a H - 1 , 所以 , ΔH = ∑ H t =1 rtzt = ∑ H t = 1 ýπ(st , at) π(st , at) ∑ H- t k =1 γk- 1 rt+k . (21) 此时可以看出,估计式 1 H ΔH 就是在 Q^ π (st , at) = ∑ H - t k = 1 γk - 1 rt + k前提下 ,对梯度估计 H 次的平均值. Baxter 等分析了折扣因子γ的取值对上述算 法的影响 :γ越接近于 1 ,梯度估计越精确 ,事实上 , 估计的偏差正比于(1 - γ) ,但是 ,γ→1 时 ,方差也无 限增大 ,所以 ,梯度估计的精确性与方差是一对矛 盾 ,必须选择适当的γ对二者进行折衷处理. 因此 , 尽管可以通过减小γ来减小方差 ,但是 ,这种方法的 调整能力有限. GPOMDP 解除了 REINFORCE 算法只能求解 周期性马氏决策问题的限制 ,但是仍然没能提高算 法的收敛速度. 2. 3 现有策略梯度算法的推广 根据时域差分的思想 ,在策略梯度算法中可以 利用截断回报作为 Q(s, a) 的近似值 ,例如 , t 时刻的 Q (st , at) 可以用一步截断回报来估计 Q(s, a) ≈ R (1) t = rt+1 +γQ^ (st+1 , at+1 ) . (22) 式中 :Q^ 为 Q 的某种估计值. 也就是利用 t + 1 时刻 的估计值 ,来对 t 时刻的估计值进行更新. 把上式推广到 k 步截断回报为 Q(s, a) ≈ R ( k) t = rt+1 +λrt+2 + …+ γk- 1 rt+k +γkQ^ (st+k , at+k ) . (23) 当 k = ∞时 ,就是实际回报 R ( ∞) t = Rt = ∑ ∞ k = 1 γk - 1 rt + k . 因此 , REINFORCE 算 法是截断回报算法的一种特例. 继续推广 ,可以利用各种截断回报的加权和来 Q(s, a) 近似 Q(s, a) ≈ R a t = ∑ H k =1 αk R ( k) t . (24) 只要是权系数满足 ∑ H k = 1 αk = 1 ,则 R α t 为 Q (s, a) 的 无偏估计. 对比式(18) 和式(24) ,可以看出 , GPOM2 DP 其实是式(24) 在αk = 1 H 时的一个特例. 当然也可以利用λ2回报来计算 Q (s, a) 近似值 : 第 1 期 王学宁 ,等 :增强学习中的直接策略搜索方法综述 ·19 ·
·20 智能系统学报 第2卷 的梯度，所以利用自然梯度的方法，并没有解决梯度 Q(s,d≈R=(1-少热1R 25) 估计过程中方差过大的问题 3 提高收敛速度的几种方法 3.2方差减小方法 策略梯度方法一个缺陷就是在梯度估计的过程 策略梯度方法最大的问题就是收敛速度太慢， 中方差过大，这影响了算法的收敛速度，成为策略梯 因此，提高策略梯度方法的收敛速度，是该领域目前 度方法实用化的一个很大障碍.因此，如何减小梯度 的研究热点.尽管近年来涌现了各种各样的算法.总 估计过程中的方差，就成为了一个研究重点.一般来 的来说，主要分为3类，下面逐一进行介绍 说，有2类方法可以减小方差：回报基线方法和结合 3.1自然梯度方法 值函数方法.Greensmith详细论述了减小方差的2 常规的梯度方法，估计的是忍然后利用该梯 种方法231. 3.2.1回报基线方法 度方向更新参数.但是，这个方向并不一定是指标函 事实上，在式(10)中增加一个常数不会影响梯 数增加最快的方向.为了说明这个问题，需要定 度估计的期望值，也就是 义2个概念 定义7参数之间的距离假设参数日，给它一 0=9∑ǔe0gs,d 个很小的扰动d日，如果参数空间是具有正交基的欧 式空间，那么，0+d0和0的距离为 t9∑ga.8.2 ld0P=∑d,2 式中：B为常数，称为回报基线 (26) 为了证明上式，只需证明： 但是，对于具有非正交基的空间，其距离为 ld0l=∑gu9ddg 27 ∑ps,w=∑器tsw.助 因为πs,为概率，所以满足(s,d=1,因此 实际上，式27)是式26)的推广，对于具有正交基的 欧式空间： 工e6d。-工部aB2路- i=j. g..( 0i≠j n(s.a 式27)就成了式26).定义了参数之间的距离，就可 30 以定义指标函数增加最快的方向。 o. 定义8指标函数？增加最快的方向当 品上. 回报基线的引入，不会改变期望，但是会影响方 Id02固定为一个很小的正数2，使得1n(0+d4 最大的d0,就是使得指标函数增加最快的方向. 差，有可能使得方差增大，也可能使得方差减小，使 如果，参数空间是黎曼空间，那么，参数距离应 得方差最小的那个值，称为最优回报基线1.因此 该是式27)，此时，使得指标函数增加最快的方向不 在利用回报基线的算法中，一定要找到这个最优回 再是常规梯度方向，而是自然梯度(natural gradi- 报基线，才能有效地减小方差.Weaver等把回报基 en)方向.如果定义矩阵G=(g.),那么，根据文献 线引入到GPOMDP算法中，并且求出了最优的回 20],有下面的定理： 报基线2！.王学宁等把回报基线应用到求解部分可 定理2：优化指标相对于策略参数的自然梯度 观测的马氏决策过程中，取得了较好的效果) 为 Munous提出的几何方法，其实也是一种基线方 法251 品-G'品 28) 3.2.2结合值函数方法 Amari等证明了上述定理.并指出，具有多层感 结合值函数方法，也称执行器.评判器(actor- 知器的神经网络的参数空间是黎曼空间21.基于上 critic)算法，可以融合策略梯度方法和值函数方法 述分析，kakade提出了自然策略梯度方法2)，以及 的优点.其中，actor表示策略，用来选择行为.critic Perters等提出了NAC算法(natural actor-crit- 利用一个函数逼近器来学习值函数，用来对策略进 ic)22 行评价.在这个体系中，actor的参数只要是基于梯 尽管自然梯度方法比常规的梯度方法收敛速度 度方法来更新的，那么就有可能收敛到局部最优，因 要快，但是，求解自然梯度时，仍然需要先估计常规 此actor-critic算法保留了策略梯度算法的收敛性 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
Q(s, a) ≈ R λ t = (1 - λ) ∑ ∞ k =1 λk- 1 R ( k) t . (25) 3 提高收敛速度的几种方法 策略梯度方法最大的问题就是收敛速度太慢 , 因此 ,提高策略梯度方法的收敛速度 ,是该领域目前 的研究热点. 尽管近年来涌现了各种各样的算法. 总 的来说 ,主要分为 3 类 ,下面逐一进行介绍. 3. 1 自然梯度方法 常规的梯度方法 ,估计的是 5η 5θ,然后利用该梯 度方向更新参数. 但是 ,这个方向并不一定是指标函 数增加最快的方向[20 ] . 为了说明这个问题 ,需要定 义 2 个概念. 定义 7 参数之间的距离 假设参数θ,给它一 个很小的扰动 dθ,如果参数空间是具有正交基的欧 式空间 ,那么 ,θ+ dθ和θ的距离为 ‖dθ‖2 = ∑ n i =1 (dθi) 2 . (26) 但是 ,对于具有非正交基的空间 ,其距离为 ‖dθ‖2 = ∑i , j g i , j (θ) dθi dθj . (27) 实际上 ,式(27) 是式(26) 的推广 ,对于具有正交基的 欧式空间 : gi , j (θ) = 1 i = j , 0 i ≠j. 式(27) 就成了式(26) . 定义了参数之间的距离 ,就可 以定义指标函数增加最快的方向. 定义 8 指标函数 η增加最快的方向 当 ‖dθ‖2固定为一个很小的正数ε2 ,使得|η(θ+ dθ| 最大的 dθ,就是使得指标函数增加最快的方向. 如果 ,参数空间是黎曼空间 ,那么 ,参数距离应 该是式(27) ,此时 ,使得指标函数增加最快的方向不 再是常规梯度方向 ,而是自然梯度 ( natural gradi2 ent) 方向. 如果定义矩阵 G = ( gi , j) ,那么 ,根据文献 [20 ] ,有下面的定理 : 定理 2 :优化指标相对于策略参数的自然梯度 为 5η 5θN = G - 1 5η 5θ . (28) Amari 等证明了上述定理. 并指出 ,具有多层感 知器的神经网络的参数空间是黎曼空间[20 ] . 基于上 述分析 ,kakade 提出了自然策略梯度方法[21 ] ,以及 Perters 等提出 了 NAC 算 法 ( natural actor2crit2 ic) [22 ] . 尽管自然梯度方法比常规的梯度方法收敛速度 要快 ,但是 ,求解自然梯度时 ,仍然需要先估计常规 的梯度 ,所以利用自然梯度的方法 ,并没有解决梯度 估计过程中方差过大的问题. 3. 2 方差减小方法 策略梯度方法一个缺陷就是在梯度估计的过程 中方差过大 ,这影响了算法的收敛速度 ,成为策略梯 度方法实用化的一个很大障碍. 因此 ,如何减小梯度 估计过程中的方差 ,就成为了一个研究重点. 一般来 说 ,有 2 类方法可以减小方差 :回报基线方法和结合 值函数方法. Greensmit h 详细论述了减小方差的 2 种方法[ 23 ] . 3. 2. 1 回报基线方法 事实上 ,在式(10) 中增加一个常数不会影响梯 度估计的期望值 ,也就是 5η 5θ = ∑s d π (s) ∑a 5π(s, a) 5θ Q π (s, a) = ∑s d π (s) ∑a 5π(s, a) 5θ ( Q π (s, a) - B) . (29) 式中 :B 为常数 ,称为回报基线. 为了证明上式 ,只需证明 : ∑a 5π 5θ Q π (s, a) = ∑a 5π 5θ ( Q π (s, a) - B) . 因为π(s, a) 为概率 ,所以满足 ∑a π(s, a) = 1 ,因此 ∑a 5π 5θ (Q π (s, a) - B) = ∑a 5π 5θ Q π (s, a) - B ∑a 5π 5θ = ∑a 5π 5θ Q π (s, a) - B 5 ∑a π(s, a) 5θ = ∑a 5π 5θ Q π (s, a) - B 51 5θ = ∑a 5π 5θ Q π (s, a) . 回报基线的引入 ,不会改变期望 ,但是会影响方 差 ,有可能使得方差增大 ,也可能使得方差减小 ,使 得方差最小的那个值 ,称为最优回报基线[ 15 ] . 因此 , 在利用回报基线的算法中 ,一定要找到这个最优回 报基线 ,才能有效地减小方差. Weaver 等把回报基 线引入到 GPOMDP 算法中 ,并且求出了最优的回 报基线[ 24 ] . 王学宁等把回报基线应用到求解部分可 观测的马氏决策过程中 ,取得了较好的效果[15 ] . Munous 提出的几何方法 ,其实也是一种基线方 法[25 ] . 3. 2. 2 结合值函数方法 结合值函数方法 ,也称执行器 - 评判器 (actor2 critic) 算法 ,可以融合策略梯度方法和值函数方法 的优点. 其中 ,actor 表示策略 ,用来选择行为. critic 利用一个函数逼近器来学习值函数 ,用来对策略进 行评价. 在这个体系中 ,actor 的参数只要是基于梯 度方法来更新的 ,那么就有可能收敛到局部最优 ,因 此 actor2critic 算法保留了策略梯度算法的收敛性. ·20 · 智 能 系 统 学 报 第 2 卷