第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 卷
第1期 王学宁，等：增强学习中的直接策略搜索方法综述 ·21 同时，由于值函数可以减小估计过程的方差，因此， 式中： 又具有较好的收敛速度] 1Q(·a 35) 假设critic的函数逼近器采用线性基函数形 MI(s,,a)(s1,a) 式 go=1'(su a (36) M(s:,a)(s,a) O"(s,al= %(s,d. 30) 而 , 式中：r=(r,子，，")∈R"表示critic的参数.基 可={gs,al+gsa,a 37) 函数根据actor,也就是策略的参数构造出来，如果 H.t 令： 如果令g(s,a)='+k,式中：H表示一个周 k■1 %s,=迹4山_L (31U 期内的时间步数 d0 n(s,a) 则 a 构造基函数的一种最简单的方法就是令(s,山= 0=∑9 (s,ad.可以看出，actor-critic算法和前面提到的 P a≠a+1, 策略迭代算法在结构上完全相同，但是actor-critic 而= 0.otherwise. 算法与前面提到的策略迭代方法最根本的区别是： 算法的基本出发点为：只是在行为改变的时候 actorcritic算法在每一个时间步，都利用时域差分 才估计梯度，并且只关心(，a)和心(s+1,a+) (temporal-difference)来更新critic的参数r,利用 相对差异.Grudic证明了上述算法的收敛性2， 式(12)来更新actor的参数.而策略迭代算法是求 3.4其他改进算法 解值函数逼近器的参数时，策略参数不动，以保证策 Schraudolph等提出的利用增益向量自适应的 略的平稳性.当根据值函数调整了策略参数之后，值 方法(SMDPOMDP)来提高策略梯度算法的收敛速 函数的参数需要重新求解.因此，actor-critic算法较 度.仿真实验表明，SMDPOMDP方法比GPOMDP 策略迭代算法有了改进，在收敛速度上也有了提高， 和自然梯度策略梯度方法收敛的都要快2] 己经被应用到实际的系统中26) Bagnell等提出了一种基于核的非参数化策略 3.3局部搜索的策略梯度估计方法 搜索算法.这个算法可以看作是REINFORCE算法 REINFORCE算法的一个缺陷就是梯度估计 的推广2.基于核的策略搜索算法，可以很好地把 的过程中方差过大.Grudic等指出，方差过大的原 增强学习和核方法结合起来.随着该类算法的进一 因就是每当访问一个状态时，策略梯度算法都要进 步发展，有望得出高效的算法 行梯度计算.策略梯度算法的核心是根据在每一个 状态下选择不同行为对优化指标的影响不同来调整 4其他策略搜索方法 参数.因此，REINFORCE算法收敛的一个必要条 4.1 PEGASUS算法 件就是需要对所有状态进行无限遍历，并且在访问 PEGASUS算法不同于上述的各种算法0.3 同一个状态时，最好是采用不同的行为，这就导致了 它没有利用式(10)进行梯度估计，而是通过预先设 计算过程中的方差过大2.基于上述分析，Grudic 定一组随机变量，把随机问题转化为确定性的问题 等在式(32)、(33)的基础之上，构造出了ATPG算 来对问题求解，文献[31]证明了下面的定理： 法： 定理3：给定某个满足定义1的MDP模型为 =∑w∑治g0.rw on M,以及策略空间Π，可以构造出一个确定性的模型 (32) M,及其策略空间T. 该确定性的模型的状态转移为确定的，而非随 r=，d 33) 机的.给定状态行为对(s,d的情况下，下一时刻 式中：M表示在状态s时可以选择的行为的个数.式 的状态是根据状态概率来确定的.在计算机的仿真 (32)比基本的梯度公式(10多了一项V”(s,这一 过程中，往往是首先产生一个在之间均匀分布的随 项可以看成是回报基线，因此，并不影响梯度的估 机数P,然后根据这个随机数p以及状态转移概率 计.ATPG算法如下：令 来决定下一时刻的状态.也就是说有了这个随机数 a0lg,+迹(uL p,=迹&au P,下一时刻的状态就是完全确定的了.为了构造确 ∂0 q+1.(34) 定性的模型M',这里定义一个确定性的转移函数： 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
同时 ,由于值函数可以减小估计过程的方差 ,因此 , 又具有较好的收敛速度[19 ] . 假设 critic 的函数逼近器采用线性基函数形 式 : Q θ r (s, a) = ∑ m j =1 r j < j θ(s, a) . (30) 式中 :r = ( r 1 , r 2 , …, r m ) ∈R m 表示 critic 的参数. 基 函数根据 actor ,也就是策略的参数构造出来 ,如果 令 : φj θ(s, a) = 5π(s, a) 5θj 1 π(s, a) . (31) 构造基函数的一种最简单的方法就是令 < j θ(s, a) = φj θ(s, a) . 可以看出 ,actor2critic 算法和前面提到的 策略迭代算法在结构上完全相同 ,但是 actor2critic 算法与前面提到的策略迭代方法最根本的区别是 : actor2critic 算法在每一个时间步 ,都利用时域差分 (temporal2difference) 来更新 critic 的参数 r ,利用 式(12) 来更新 actor 的参数. 而策略迭代算法是求 解值函数逼近器的参数时 ,策略参数不动 ,以保证策 略的平稳性. 当根据值函数调整了策略参数之后 ,值 函数的参数需要重新求解. 因此 ,actor2critic 算法较 策略迭代算法有了改进 ,在收敛速度上也有了提高 , 已经被应用到实际的系统中[ 26 ] . 3. 3 局部搜索的策略梯度估计方法 REINFORCE 算法的一个缺陷就是梯度估计 的过程中方差过大. Grudic 等指出 ,方差过大的原 因就是每当访问一个状态时 ,策略梯度算法都要进 行梯度计算. 策略梯度算法的核心是根据在每一个 状态下选择不同行为对优化指标的影响不同来调整 参数. 因此 , REINFORCE 算法收敛的一个必要条 件就是需要对所有状态进行无限遍历 ,并且在访问 同一个状态时 ,最好是采用不同的行为 ,这就导致了 计算过程中的方差过大[27 ] . 基于上述分析 , Grudic 等在式(32) 、(33) 的基础之上 ,构造出了 A TPG 算 法 : 5η 5θ = ∑s d π (s) ∑a 5π(s, a) 5θ ( Q π (s, a) - V π (s) ) . (32) V π (s) = 1 M ∑ M j = 1 Q π (s, a j ) . (33) 式中 : M 表示在状态 s 时可以选择的行为的个数. 式 (32) 比基本的梯度公式 (10) 多了一项 V π (s) ,这一 项可以看成是回报基线 ,因此 , 并不影响梯度的估 计. A TPG算法如下 :令 Pt = 5π(st , at) 5θ qt + 5π(st+1 , at+1 ) 5θ qt+1 . (34) 式中 : qt = 1 M Q^ π (st , at) - Qt π(st , at)π(st+1 , at+1 ) . (35) qt+1 = 1 M Q^ π (st+1 , at+1 ) - Qt π(st , at)π(st+1 , at+1 ) . (36) 而 Qt = 1 2 Q^ π (st , at) + Q^ π (st+1 , at+1 ) . (37) 如果令 Q^ π (st , at) = ∑ H - t k = 1 γk - 1 rt + k ,式中 : H 表示一个周 期内的时间步数. 则 5η 5θ = ∑ H t =1 φt . 而φt = Pt , at ≠at + 1 , 0 ,ot herwise. 算法的基本出发点为 :只是在行为改变的时候 才估计梯度 ,并且只关心 Q^ π (st , at) 和 Q^ π (st + 1 , at + 1 ) 相对差异. Grudic 证明了上述算法的收敛性[27 ] . 3. 4 其他改进算法 Schraudolp h 等提出的利用增益向量自适应的 方法(SMDPOMDP) 来提高策略梯度算法的收敛速 度. 仿真实验表明 ,SMDPOMDP 方法比 GPOMDP 和自然梯度策略梯度方法收敛的都要快[28 ] . Bagnell 等提出了一种基于核的非参数化策略 搜索算法. 这个算法可以看作是 REIN FORCE 算法 的推广[ 29 ] . 基于核的策略搜索算法 ,可以很好地把 增强学习和核方法结合起来. 随着该类算法的进一 步发展 ,有望得出高效的算法. 4 其他策略搜索方法 4. 1 PEGASUS 算法 PEGASUS 算法不同于上述的各种算法[30 - 31 ] , 它没有利用式(10) 进行梯度估计 ,而是通过预先设 定一组随机变量 ,把随机问题转化为确定性的问题 来对问题求解. 文献[31 ]证明了下面的定理 : 定理 3 :给定某个满足定义 1 的 MDP 模型为 M ,以及策略空间 ∏,可以构造出一个确定性的模型 M′,及其策略空间 ∏′. 该确定性的模型的状态转移为确定的 ,而非随 机的. 给定状态 —行为对 (s, a) 的情况下 ,下一时刻 的状态是根据状态概率来确定的. 在计算机的仿真 过程中 ,往往是首先产生一个在之间均匀分布的随 机数 p ,然后根据这个随机数 p 以及状态转移概率 来决定下一时刻的状态. 也就是说有了这个随机数 p ,下一时刻的状态就是完全确定的了. 为了构造确 定性的模型 M′,这里定义一个确定性的转移函数 : 第 1 期 王学宁 ,等 :增强学习中的直接策略搜索方法综述 ·21 ·
·22· 智能系统学报 第2卷 g:S XA Xp→S 广.它首先学习系统模型，然后利用该模型计算当前 根据MDP模型为M,构造确定性模型M的过 策略的值，并且可以计算策略值相对于策略参数的 程如下： 梯度.在自行车问题中，EDA算法比PEGASUS收 行为空间不变，状态由原来的S变成S':SX 敛要快，并且利用的策略也比较简单.但是，EDA 0,11°，也就是说，在M中，一个状态为向量(s,p1, 算法需要学习系统模型，并且认为系统模型的模型 p2,),s为M的状态.例如，假设在1时刻状态为 是线性的，或者至少是局部线性的，这就限制了该算 (s,p1,p2,y,行为为a,则1+1时刻的状态为 法的应用范围 (s+1,p2,p,,式中：s+1=g(s,a,p).对于某 4.3和SVM结合的策略搜索方法 个策略π∈Π，其在策略空间Π的对应策略为π' 策略梯度方法由于方差过大，导致收敛速度很 (s,p1,p2,…=I(.最后，令R'(s,p1,p2,…=R 慢，即使很简单的问题，也要学习很长的时间.并且， ( 往往初始策略是随机给定的，因此学习的过程中，尤 根据上述的构造方法，对于2个对应的策略π 其是学习的早期，学习体会选择一些不正确的行为， ∈和π'∈Π'有下式成立： 在实际的试验中，这些不正确的行为可能会引起各 Vwπ)=Vr(I 38 种事故.基于上述2点，王学宁等把SVM引入到策 这也就隐含了关系式opt(M,=op1(M', 略梯度学习方法中来，提出了一种混合式策略梯度 T),也就是说，根据模型M',在策略空间中寻找到 增强学习方法1.在该方法中，初始策略不是随机 的最优策略，其对应策略也是在原问题中的最优策 给定的，而是根据先验知识，或者人为控制，产生一 略.在确定性模型中，因为状态转移是确定性的，所 些样本点，然后根据这些样本点，利用SVM方法产 以如果给定策略π∈Π'，状态s∈S',那么此时刻以 生一个初始策略.这个初始策略往往是可行的，但不 后的所有状态也就完全确定了.因此计算该状态值 是最优的，因此，再利用策略梯度方法对这个初始策 V(s)也就相应的简单了.假设问题有m个初始状 略进行优化.再利用优化之后的策略产生一些样本 态，第1个初始状态记为s,则策略r的值可用下 点，根据这些样本点，利用SVM方法产生一个初始 式计算： 策略，再利用策略梯度方法进行优化，如此循环往 (39 复，使得策略达到一个局部最优解」 m 4.4层次化策略梯度方法 使得优化指标n最大的策略，也就是使得V)最大 对于大规模的问题，比如说状态和行为都是连 的策略，因此，现在问题转化为寻找最优策略 续的，直接求解比较困难，甚至是无法求解.但是如 '=arg maxv() 40 果把问题分解成若干个小问题，往往就能迎刃而解， 为此需要知道求解该梯度有2种方法。一 这就是层次化增强学习方法的基本思想.在cha 种是数值方法，一种是解析方法).数值方法就是 vamzadeh等提出层次化策略梯度(Hierarchical Policy Gradient)算法之前36]，已经有很多关于层次 给每个参数一个小小的扰动，根据这个扰动来计算 梯度，梯度的第1个分量为 化值函数方法的文献B7. ay@-L0±el:'0.l Chavamzadeh等提出的HPG算法中，把问题 80 2a 分为2层，下层是分解后的小问题，上层是在某一时 式中：e=0,0,…1,0,…,0,即第i个分量为1， 刻选择需要解决哪个小问题.利用策略梯度算法进 其他分量为0的向量，其维数和8相同.解析方法比 行下层问题的求解，而利用值函数方法进行上层的 较繁琐，这里不在赘述，详情请参看文献[31]： 学习.该方法可以有效地解决大规模问题 相比较而言，PEGAUSU算法收敛速度比其他 5结论 算法都快，但是，该算法只能应用到仿真试验中，目 前，己经有利用PEGASUS算法成功控制直升机的 尽管策略梯度增强学习方法从1992年已经被 例子z],Strens等利用成对比较法(paired compari- 提出，但是，到了2000年前后，才逐渐引起人们的注 sions)提高了PEGASUS算法的性能，并且解决了 意.虽然刚刚经过几年的发展时间，己经有众多的策 “过拟合”的问题3 略梯度算法被提出.但是，由于策略梯度方法的收敛 4.2本质动力学算法 速度太慢，导致策略梯度还不能应用到大规模的问 本质动力学算法实质上是线性二次调节器的推 题之中因此，策略梯度算法中需要研究的就是如何 @1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
g ∶S ×A ×p →S 根据 MDP 模型为 M ,构造确定性模型 M′的过 程如下 : 行为空间不变 , 状态由原来的 S 变成 S′: S × [0 ,1 ] ∞ ,也就是说 ,在 M′中 ,一个状态为向量(s, p1 , p2 , …) ,s 为 M 的状态. 例如 ,假设在 t 时刻状态为 (st , p1 , p2 , …) ,行为为 at , 则 t + 1 时刻的状态为 (st + 1 , p2 , p3 , …) ,式中 :st + 1 = g (st , at , p1 ) . 对于某 个策略π∈∏,其在策略空间 ∏′的对应策略为π′ (s, p1 , p2 , …) =π(s) . 最后 ,令 R′(s, p1 , p2 , …) = R (s) . 根据上述的构造方法 ,对于 2 个对应的策略π ∈∏和π′∈∏′,有下式成立 : V M (π) = V M′(π′) . (38) 这也就隐含了关系式 opt ( M , ∏) = opt ( M′, ∏′) ,也就是说 ,根据模型 M′,在策略空间中寻找到 的最优策略 ,其对应策略也是在原问题中的最优策 略. 在确定性模型中 ,因为状态转移是确定性的 ,所 以如果给定策略π∈∏′,状态 s ∈S′,那么此时刻以 后的所有状态也就完全确定了. 因此计算该状态值 V π M′(s) 也就相应的简单了. 假设问题有 m 个初始状 态 ,第 i 个初始状态记为 s ( i) 0 ,则策略π的值可用下 式计算 : V M′(π) ≈ 1 m ∑ m i = 1 V π M′(s ( i) 0 ) . (39) 使得优化指标η最大的策略 ,也就是使得 V (π) 最大 的策略 ,因此 ,现在问题转化为寻找最优策略 π3 = arg max π V (π) . (40) 为此需要知道 5V 5θ,求解该梯度有 2 种方法 ,一 种是数值方法 ,一种是解析方法[31 ] . 数值方法就是 给每个参数一个小小的扰动 ,根据这个扰动来计算 梯度 ,梯度的第 i 个分量为 5V (θ) 5θi = V (θ+αei) - V (θ- αei) 2α . 式中 :ei = (0 ,0 , …, 1 , 0 , …, 0) ,即第 i 个分量为 1 , 其他分量为 0 的向量 ,其维数和θ相同. 解析方法比 较繁琐 ,这里不在赘述 ,详情请参看文献[31 ]. 相比较而言 ,PEGAUSU 算法收敛速度比其他 算法都快 ,但是 ,该算法只能应用到仿真试验中. 目 前 ,已经有利用 PEGASUS 算法成功控制直升机的 例子[ 32 ] . Strens 等利用成对比较法(paired compari2 sions) 提高了 PEGASUS 算法的性能 ,并且解决了 “过拟合”的问题[ 33 ] . 4. 2 本质动力学算法 本质动力学算法实质上是线性二次调节器的推 广. 它首先学习系统模型 ,然后利用该模型计算当前 策略的值 ,并且可以计算策略值相对于策略参数的 梯度. 在自行车问题中 , EDA 算法比 PEGASUS 收 敛要快 ,并且利用的策略也比较简单[34 ] . 但是 ,EDA 算法需要学习系统模型 ,并且认为系统模型的模型 是线性的 ,或者至少是局部线性的 ,这就限制了该算 法的应用范围. 4. 3 和 SVM 结合的策略搜索方法 策略梯度方法由于方差过大 ,导致收敛速度很 慢 ,即使很简单的问题 ,也要学习很长的时间. 并且 , 往往初始策略是随机给定的 ,因此学习的过程中 ,尤 其是学习的早期 ,学习体会选择一些不正确的行为 , 在实际的试验中 ,这些不正确的行为可能会引起各 种事故. 基于上述 2 点 ,王学宁等把 SVM 引入到策 略梯度学习方法中来 ,提出了一种混合式策略梯度 增强学习方法[35 ] . 在该方法中 ,初始策略不是随机 给定的 ,而是根据先验知识 ,或者人为控制 ,产生一 些样本点 ,然后根据这些样本点 ,利用 SVM 方法产 生一个初始策略. 这个初始策略往往是可行的 ,但不 是最优的 ,因此 ,再利用策略梯度方法对这个初始策 略进行优化. 再利用优化之后的策略产生一些样本 点 ,根据这些样本点 ,利用 SVM 方法产生一个初始 策略 ,再利用策略梯度方法进行优化 ,如此循环往 复 ,使得策略达到一个局部最优解. 4. 4 层次化策略梯度方法 对于大规模的问题 ,比如说状态和行为都是连 续的 ,直接求解比较困难 ,甚至是无法求解. 但是如 果把问题分解成若干个小问题 ,往往就能迎刃而解. 这就是层次化增强学习方法的基本思想. 在 Cha2 vamzadeh 等提出层次化策略梯度 ( Hierarchical Policy Gradient) 算法之前[36 ] ,已经有很多关于层次 化值函数方法的文献[37 - 39 ] . Chavamzadeh 等提出的 HPG 算法中 ,把问题 分为 2 层 ,下层是分解后的小问题 ,上层是在某一时 刻选择需要解决哪个小问题. 利用策略梯度算法进 行下层问题的求解 ,而利用值函数方法进行上层的 学习. 该方法可以有效地解决大规模问题. 5 结 论 尽管策略梯度增强学习方法从 1992 年已经被 提出 ,但是 ,到了 2000 年前后 ,才逐渐引起人们的注 意. 虽然刚刚经过几年的发展时间 ,已经有众多的策 略梯度算法被提出. 但是 ,由于策略梯度方法的收敛 速度太慢 ,导致策略梯度还不能应用到大规模的问 题之中. 因此 ,策略梯度算法中需要研究的就是如何 ·22 · 智 能 系 统 学 报 第 2 卷
第1期 王学宁，等：增强学习中的直接策略搜索方法综述 ·23· 提高收敛速度.根据前面的分析，提高收敛速度，有 1995 以下几类方法： [10]TSITSIKL IS J N,ROY V B.Feature-based methods 1)减小方差，相对来说，这类方法研究的已经很 for large scale dynamic programming [J ]Machine 多，但是效果有限 Learning,1996(22):59.94. 2)利用自然梯度方法，这类方法依然要用到常 [11]徐昕，贺汉根.神经网络增强学习的梯度算法研究 [01.计算机学报，2003,26(2)：227.233. 规的梯度，这就离不开梯度估计算法，仍然不能避免 XU Xin,HE Hangen.A gradient algorithm for rein- 梯度估计过程中的方差过大的问题 forcement learning based on neural networks[J].Chi- 3)利用先验知识.利用先验知识，是策略梯度算 nese Journal of Computers,2003,26(2):227-233. 法走向实用化的一个很有效并且很重要的手段.但 [12 ]BAXTER J,BARTL ETT P L.Infinite-horizon policy- 是，如何方便有效地利用先验知识？先验知识的引 gradient estimation[J].Journal of Artificial Intelligence 入是否影响算法的收敛性？先验知识并不能百分之 Research,200115):319.350 百的正确，如何消除错误的先验知识带来的错误导 [13]ABERDEEN D A.Policy-gradient algorithms for par- 向？这3个问题有待进一步的研究 tially observable Markov decision processes [D].Aus- 4)利用层次化策略梯度方法.对于能分解的问 tralian National University,2003. 题，这是一个有效的方法.但是并不是所有的问题都 [14]GREENSMITH P L,BAXTER J.Variance reduction techniques for gradient estimation in reinforcement 可以分解。 learning [J ]Journal of Machine Learning Reseach, 利用局部策略梯度估计方法.由于仅仅考虑行 2002(4):1471-1530. 为改变时的情况，因此极大地减小了运算量，这类方 [15]王学宁，徐昕，吴涛，贺汉根.策略梯度强化学习中 法虽然目前还没有引起足够的重视，但是有望能较 的最优回报基线卩1.计算机学报，2005,28(6)：1021- 大幅度地提高算法的性能， 1026. WANG Xuening,XU Xin,WU Tao,HE Hangen.The 参考文献： optimal reward baseline for policy-gradient reinforce- [1]徐昕，增强学习及其在移动机器人导航与控制中的应 ment learning[J ]Chinese Journal of Computers,2005, 用研究[D].长沙：国防科技大学，2002. 28(6):1021-1026. XU Xin.Reinforcement learning and its applications in [16]SCHWARTZ A.A reinforcement learning method for navigation and control of mobile robots[D].Changsha: maximizing undiscounted rewards[A ]In Proceedings National University of Defence Technology,2002 of the Tenth International Conference on Machine [2]SUTTON R ,BARTO A.Reinforcement learning,an in- Learning[C].Morgan Kaufmann,San Mateo,CA,1993. troduction[M].MIT Press,1998. [17]MA HADEVAN S.To discount or not to discount in re- [3 SIN GH S P.Learning to solve Markovian decision inforcement learning a case study comparing R-learn- processes[D].University of Massachusetts,1994. ing and Q-learning[A].In:Proc.Of International Ma- [4]RO Y B V.Learning and value function approximation in chine Learning Conf[C].New Brunswick,USA,1994. complex decision processes[M].MIT Press,1998. [18 WILLIAMS R J.Simple statistical gradient-following [5]WA TKINS C.Learning from delayed rewards[D].Cam- algorithms for connectionist reinforcement learning[J ] brideg:University of Cambridge,1989. Machine Learning,1992(8):229-256. [6]HUMPHRYS M.Action selection methods using rein- [19]KONDA V R,TSITSIKL IS J N.Actor-critic algo- forcement learning [D].Cambrideg:University of Cam- rithms[J].Adv.Neural Inform Processing Syst,2000 bridge,1996. (12):1008.1014. [7]BERTSEKAS D P,TSITSIKLIS J N.Neuro-dynamic [20]AMARI S.Natural gradient works efficiently in learning programming[M].Athena Scientific,Belmont,Mass., [J].Neural Computation,1998,10(2):251-276. 1996. [21]KA KADE S.A natural policy gradient[A].Advances (8]SUTTON R S,MCALL ESTER D,SIN GH S,et al. in Neural Information Processing Systems 14[C].MIT Policy gradient methods for reinforcement learning with Press.2002. function approximation[A].In:Advances in Neural In [22]PETERS J,VUAYA KUMAR S,SCHAAL S.Natural formation Processing Systems[C].Denver,USA,2000. actor-critic[A].In 16th European Conference on Ma- [9]BAIRD L C.Residual algorithms:reinforcement learning chine Learning (ECML 2005)[C].[s.I.],2005. with function approximation[A].In:Proc.Of the 12 [23]GREENSMITH E.Variance reduction techniques for Int.Conf.on Machine Learning [C].San Francisco, gradient estimation in reinforcement learning[J].Jour- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
提高收敛速度. 根据前面的分析 ,提高收敛速度 ,有 以下几类方法 : 1) 减小方差 ,相对来说 ,这类方法研究的已经很 多 ,但是效果有限. 2) 利用自然梯度方法 ,这类方法依然要用到常 规的梯度 ,这就离不开梯度估计算法 ,仍然不能避免 梯度估计过程中的方差过大的问题. 3) 利用先验知识. 利用先验知识 ,是策略梯度算 法走向实用化的一个很有效并且很重要的手段. 但 是 ,如何方便有效地利用先验知识 ? 先验知识的引 入是否影响算法的收敛性 ? 先验知识并不能百分之 百的正确 ,如何消除错误的先验知识带来的错误导 向 ? 这 3 个问题有待进一步的研究. 4) 利用层次化策略梯度方法. 对于能分解的问 题 ,这是一个有效的方法. 但是并不是所有的问题都 可以分解. 利用局部策略梯度估计方法. 由于仅仅考虑行 为改变时的情况 ,因此极大地减小了运算量 ,这类方 法虽然目前还没有引起足够的重视 ,但是有望能较 大幅度地提高算法的性能. 参考文献 : [1 ]徐 昕. 增强学习及其在移动机器人导航与控制中的应 用研究[D]. 长沙 :国防科技大学 , 2002. XU Xin. Reinforcement learning and its applications in navigation and control of mobile robots[ D ]. Changsha : National University of Defence Technology , 2002. [2 ]SU TTON R ,BARTO A. Reinforcement learning , an in2 troduction[ M]. MIT Press , 1998. [3 ] SIN GH S P. Learning to solve Markovian decision processes[D]. University of Massachusetts , 1994. [4 ]RO Y B V. Learning and value function approximation in complex decision processes[ M]. MIT Press , 1998. [ 5 ]WA T KINS C. Learning from delayed rewards[D]. Cam2 brideg : University of Cambridge , 1989. [6 ] HUMPHR YS M. Action selection methods using rein2 forcement learning [ D ]. Cambrideg : University of Cam2 bridge ,1996. [7 ] BERTSEKAS D P , TSITSIKL IS J N. Neuro2dynamic programming[ M ]. Athena Scientific ,Belmont , Mass. , 1996. [8 ] SU TTON R S , MCALL ESTER D , SIN GH S , et al. Policy gradient methods for reinforcement learning with function approximation[ A ]. In : Advances in Neural In2 formation Processing Systems[C]. Denver , USA ,2000. [9 ]BAIRD L C. Residual algorithms: reinforcement learning with function approximation[ A ]. In : Proc. Of the 12 # Int. Conf. on Machine Learning [ C ]. San Francisco , 1995. [10 ] TSITSIKL IS J N , RO Y V B. Feature2based methods for large scale dynamic programming [ J ]. Machine Learning ,1996 (22) :59 - 94. [11 ]徐 昕 ,贺汉根. 神经网络增强学习的梯度算法研究 [J ]. 计算机学报 ,2003 ,26 (2) :227 - 233. XU Xin , HE Hangen. A gradient algorithm for rein2 forcement learning based on neural networks[J ]. Chi2 nese Journal of Computers , 2003 , 26 (2) : 227 - 233. [12 ]BAXTER J , BARTL ETT P L. Infinite2horizon policy2 gradient estimation[J ]. Journal of Artificial Intelligence Research ,2001 (15) :319 - 350. [13 ]ABERDEEN D A. Policy - gradient algorithms for par2 tially observable Markov decision processes [ D ]. Aus2 tralian National University , 2003. [14 ] GREENSMITH P L , BAXTER J. Variance reduction techniques for gradient estimation in reinforcement learning [J ]. Journal of Machine Learning Reseach , 2002 (4) : 1471 - 1530. [15 ]王学宁 ,徐 昕 ,吴 涛 ,贺汉根. 策略梯度强化学习中 的最优回报基线[J ]. 计算机学报 ,2005 ,28 (6) :1021 - 1026. WAN G Xuening , XU Xin , WU Tao , HE Hangen. The optimal reward baseline for policy2gradient reinforce2 ment learning[J ]. Chinese Journal of Computers , 2005 , 28 (6) :1021 - 1026. [ 16 ] SCHWARTZ A. A reinforcement learning method for maximizing undiscounted rewards[ A ]. In Proceedings of the Tenth International Conference on Machine Learning[C]. Morgan Kaufmann ,San Mateo ,CA ,1993. [ 17 ]MA HADEVAN S. To discount or not to discount in re2 inforcement learning : a case study comparing R2learn2 ing and Q2learning[A ]. In : Proc. Of International Ma2 chine Learning Conf[C]. New Brunswick , USA ,1994. [ 18 ] WILL IAMS R J. Simple statistical gradient2following algorithms for connectionist reinforcement learning[J ]. Machine Learning ,1992 (8) :229 - 256. [19 ] KONDA V R , TSITSIKL IS J N. Actor2critic algo2 rithms[J ]. Adv. Neural Inform Processing Syst , 2000 (12) : 1008 - 1014. [20 ]AMARI S. Natural gradient works efficiently in learning [J ]. Neural Computation , 1998 , 10 (2) :251 - 276. [21 ] KA KADE S. A natural policy gradient [ A ]. Advances in Neural Information Processing Systems 14[ C]. MIT Press , 2002. [22 ]PETERS J , VIJ A YA KUMAR S ,SCHAAL S. Natural actor2critic[ A ]. In 16th European Conference on Ma2 chine Learning ( ECML 2005) [C]. [s. l. ] ,2005. [23 ] GREENSMITH E. Variance reduction techniques for gradient estimation in reinforcement learning[J ]. Jour2 第 1 期 王学宁 ,等 :增强学习中的直接策略搜索方法综述 ·23 ·
·24· 智能系统学报 第2卷 nal of Machine Learning Reseach,2002(4):1471- [35]WANG X N,XU X,WU T,HE H G,ZHANGM.A 1530. hybrid reinforcement learning combined with SVM and [24]WEAVER L,TAO N.The optimal reward baseline for its applications [A ]Proceedings of the International gradient-based reinforcement learning[A ]Proceedings Conference on Sensing,Computing and Automation of 17#Conference in Uncertainty in Artificial Intelli- [C].Chongqing,China,2006. gence[C].Washington ,2001. [36]GHAVAMZADEH M,MA HADEVAN S.Hierarchi- [25]MUNOS R.Geometric variance reduction in Markov cal policy gradient algorithms[A].In Proceedings of chains:application to value function and gradient esti- the Twentieth International Conference on Machine mation [J ]Journal of Machine Learning Research, Learning[C].Washington,D.C.,2003. 2006(7):413,427. [37]DIETTERICH T.The MAXQ method for hierarchical [26]BERENJI H R,VEN GEROV D.A convergent actor- reinforcement learning[A].In:Proceedings of the fif- critic-based FRL algorithm with application to power teenth international conference on machine learning[C]. management of wireless tansmitters[J ]IEEE Transac- [s.1.1,1998. tions on Fuzzy Systems,2003,11(4):478-485. [38]PARR R.Hierarchical control and learning for Markov [27]GRUDIC GZ,UNGER L R.Localizing policy gradient decision processes[D].University of California,Berk- estimates to action transitions [A ]Seventeenth int. ley,1998 Conference on Machine Learning,Stanford University [39]SUTTON R,PRECUP D,SIN GH.Between MDPs [C].2000:343-350. and Semi-MDPs:a framework for temporal abstraction [28 ]NICOL N S,YU Jin,ABERDEEN D.Fast online poli- in reinforcement learning [J ]Artificial Intellignce, cy gradient learning with SMD gain vector adaptation 1999(112):181-211. [A ]In Advances in Neural Information Processing 作者简介： Systems (NIPS)[C].The MIT Press,Cambridge, 王学宁，男，1976年生，博士研究 MA,2006. 生，主要研究方向为增强学习、智能控 [29 ]BA GN ELL J A,SCHNEIDER J.Policy search in ker- 制等，参加国家自然科学基金重点项目 nel hilbert space EB/OL].http://citeseer.ist.psu. 一项、青年基金项目一项，863项目一 cduW650945.html.2005-05-27. 项，己发表论文10余篇，其中被SCI收 [30]NG A,JORDAN M.Pegasus:a policy search method 录3篇，EI收录5篇 for large MDPs and POMDPs approximation[A ]In E mail wxn9576 @yahoo.com.cn Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence [C].San Francisco,2000. [31 ]Diplomarbeit.The Reinforcement Learning Toolbox, 陈伟，男，1976年生，博士研究 Reinforcement Learning for Optimal Control Tasks[D], 生，主要研究方向为机器人定位与见 University of Technology,Graz,2005. 图、机器学习等，参加国家自然科学基 [32]NGA Y,KIM H J,MICHAEL I,SASTRY S.Au- 金重点项目一项。 tonomous helicopter flight via Reinforcement Learning [A ]In Neural Information Processing Systems 16[C]. [s.1.],2004. 张锰，男，1972年生，2001年毕 [33]STRENS MJ,MOORE A.Policy search using paired 业于国防科技大学计算机学院，获硕士 comparisons [J].Journal of Machine Learning Re- 学位.主要研究方向为指挥自动化.曾 search,2002(3):921-950. 获全军科技进步二等奖2项，全军科技 [34]MARTIN C.The essential dynamics algorithm:fast policy 进步三等奖3项，并在国内外科技期刊 Search in continuous worlds[R].MIT Media Laboratory, 上发表论文12篇，其中SCI检索1篇， Vsion and Modelling Technical Report.2004. EI检索3篇 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
nal of Machine Learning Reseach , 2002 ( 4) : 1471 - 1530. [ 24 ]WEAV ER L , TAO N. The optimal reward baseline for gradient2based reinforcement learning[ A ]. Proceedings of 17 # Conference in Uncertainty in Artificial Intelli2 gence[C]. Washington ,2001. [25 ] MUNOS R. Geometric variance reduction in Markov chains: application to value function and gradient esti2 mation [J ]. Journal of Machine Learning Research , 2006 (7) :413 - 427. [26 ]BERENJ I H R , V EN GEROV D. A convergent actor2 critic2based FRL algorithm with application to power management of wireless tansmitters[J ]. IEEE Transac2 tions on Fuzzy Systems , 2003 , 11 (4) : 478 - 485. [27 ] GRUDIC G Z , UN GER L R. Localizing policy gradient estimates to action transitions [ A ]. Seventeenth int. Conference on Machine Learning , Stanford University [C]. 2000 :343 - 350. [28 ]NICOL N S , YU Jin ,ABERDEEN D. Fast online poli2 cy gradient learning with SMD gain vector adaptation [ A ]. In Advances in Neural Information Processing Systems ( NIPS) [ C ]. The MIT Press , Cambridge , MA , 2006. [29 ]BA GNELL J A , SCHN EIDER J. Policy search in ker2 nel hilbert space [ EB/ OL ]. http :/ / citeseer. ist. psu. edu/ 650945. html. 2005 - 05 - 27. [30 ]N G A , JORDAN M. Pegasus: a policy search method for large MDPs and POMDPs approximation [ A ]. In Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence [C]. San Francisco , 2000. [ 31 ] Diplomarbeit. The Reinforcement Learning Toolbox , Reinforcement Learning for Optimal Control Tasks[D] , University of Technology , Graz , 2005. [32 ]N G A Y, KIM H J , MICHA EL I , SASTR Y S. Au2 tonomous helicopter flight via Reinforcement Learning [ A ]. In Neural Information Processing Systems 16[C]. [s. l. ] , 2004. [33 ]STRENS M J , MOORE A. Policy search using paired comparisons [ J ]. Journal of Machine Learning Re2 search , 2002 (3) :921 - 950. [34 ]MARTIN C. The essential dynamics algorithm: fast policy Search in continuous worlds[ R]. MIT Media Laboratory , Vsion and Modelling Technical Report. 2004. [35 ]WAN G X N , XU X , WU T , HE H G, ZHAN G M. A hybrid reinforcement learning combined with SVM and its applications [ A ]. Proceedings of the International Conference on Sensing , Computing and Automation [C]. Chongqing , China , 2006. [36 ] GHAVAMZADEH M , MA HADEVAN S. Hierarchi2 cal policy gradient algorithms [ A ]. In Proceedings of the Twentieth International Conference on Machine Learning[C]. Washington , D. C. , 2003. [ 37 ]DIETTERICH T. The MAXQ method for hierarchical reinforcement learning[ A ]. In : Proceedings of the fif2 teenth international conference on machine learning[C]. [s. l. ] ,1998. [38 ]PARR R. Hierarchical control and learning for Markov decision processes[D ]. University of California , Berk2 ley ,1998. [39 ] SU TTON R , PRECU P D , SIN GH. Between MDPs and Semi2MDPs: a framework for temporal abstraction in reinforcement learning [J ]. Artificial Intellignce , 1999 (112) :181 - 211. 作者简介 : 王学宁 ,男 , 1976 年生 ,博士研究 生 ,主要研究方向为增强学习、智能控 制等 ,参加国家自然科学基金重点项目 一项、青年基金项目一项 ,863 项目一 项 ,已发表论文 10 余篇 ,其中被 SCI 收 录 3 篇 ,EI 收录 5 篇. E2mail :wxn9576 @yahoo. com. cn 陈 伟 ,男 , 1976 年生 ,博士研究 生 ,主要研究方向为机器人定位与见 图、机器学习等 ,参加国家自然科学基 金重点项目一项. 张 锰 ,男 ,1972 年生 ,2001 年毕 业于国防科技大学计算机学院 ,获硕士 学位. 主要研究方向为指挥自动化. 曾 获全军科技进步二等奖 2 项 ,全军科技 进步三等奖 3 项 ,并在国内外科技期刊 上发表论文 12 篇 ,其中 SCI 检索 1 篇 , EI 检索 3 篇. ·24 · 智 能 系 统 学 报 第 2 卷