【学术论文】回报函数学习的学徒学习综述

第4卷第3期 智能系统学报 Vol.4 No.3 2009年6月 CAAI Transactions on Intelligent Systems Jn.2009 doi:10.3969/j.issn.16734785.2009.03.003 回报函数学习的学徒学习综述 金卓军，钱徽，陈沈轶，朱森良 (浙江大学计算机学院，浙江杭州310027)】 摘要：通过研究基于回报函数学习的学徒学习的发展历史和目前的主要工作，概述了基于回报函数学习的学徒学 习方法.分别在回报函数为线性和非线性条件下讨论，并且在线性条件下比较了2类方法一基于逆向增强学习 (L)和最大化边际规划(MMP)的学徒学习.前者有较为快速的近似算法，但对于演示的最优性作了较强的假设； 后者形式上更易于扩展，但计算量大.最后，提出了该领域现在还存在的问题和未来的研究方向，如把学徒学习应用 于POMDP环境下，用PBVI等近似算法或者通过PCA等降维方法对数据进行学习持征的提取，从而减少高维度带来 的大计算量问题。 关键词：学徒学习：回报函数：逆向增强学习：最大化边际规划 中图分类号：TP181文献标识码：A文章编号：16734785(2009)03-020805 Survey of apprenticeship learning based on reward function learning JIN Zhuo-jun,QIAN Hui,CHEN Shen-yi,ZHU Miao-liang (Department of Computer Science,Zhejiang University,Hangzhou 310027,China) Abstract:This paper focuses on apprenticeship leaming,based on reward function learning.Both the historical ba- sis of this field and a broad selection of current work were investigated.In this paper,two kinds of algorithm-ap- prenticeship learning methods based on inverse reinforcement leaming (IRL)and maximum margin planning (MMP)frameworks were discussed under respective assumptions of linear and nonlinear reward functions.Compar- ison was made under the linear assumption conditions.The former can be implemented with an efficient approxi- mate method but has made a strong supposition of optimal demonstration.The latter has a relatively easy to extend form but may take large amounts of computation.Finally,some suggestions were given for further research in re- ward function leaming in a partially observable Markov decision process (POMDP)environment and in continuous/ high dimensional space,using either an approximate algorithm such as point-based value iteration (PBVI)or a fea- ture abstraction algorithm using dimension reduction methods such as principle component analysis (PCA).Adop- ting these may alleviate the curse of dimensionality. Keywords:apprenticeship leaming;reward function;inverse reinforcement leaming;maximum margin planning 学徒学习(apprenticeship leaming),又称为示教对基于逆向增强学习的学徒学习和MMP框架2类 学习(imitation leaming)、模仿学习(imitation leam 方法的作了更具体的分析和比较，另外讨论了近几 ing)或者观察学习(leaming by watching)等.它是指 年来该领域的一些最新进展. 学习者模仿专家的行为或者控制策略的过程].文 在移动机器人控制当中，规划模块将回报函数作 献[2]介绍了基于边际最大化的学徒学习的发展过 为输入，然后算出一条使回报函数值最大的决策序列， 程，其重点放在MMP(maximum margin planning)框 这种方法已经成为自动移动机器人系统的核心.但是， 架的提出、解决及优化.本文在文献[3]的基础上， 要建立回报函数的过程在实际操作中是比较困难的， 回报函数常常需要手工调节，然后观察运行结果，继而 收稿日期：2008-10-08 再调整回报函数，如此迭代来完成回报函数的构建这 基金项目：国家自然科学基金资助项目(90820306)：渐江省科技厅重 样的过程在现实情况中往往是不可取的： 大资助项目(006c13096). 通信作者：钱徽.E-mail:qianhui(@u.d.cn 基于回报函数学习的学徒学习被用来从专家演

第3期 金卓军，等：回报函数学习的学徒学习综述 .209 示的策略序列中近似还原出怡当的回报函数，之后便 严(s)=R(s)+y∑Po(s')(s') 可以用传统的规划方法寻求最优策略.目前用于从示 教中还原回报函数的主要方法有基于逆向增强学习 Q(s)=R(s)+y>P(s)(s'). 的学徒学习和MMP框架2种.Ng和Russell提出了 学习特征是状态的组合，是代表某一特征的状 逆向增强学习(inverse reinforcement learning, 态的集合.学习特征的基回报函数简称为基回报函 RL),它通过最大化专家演示策略和其他策略的 数，是使符合某一学习特征的策略回报值最高的回 差别，还原出一个能得出和专家演示相似策略的回报 报函数基回报函数形式化表达为/eS×A→R,d 函数.Abbeel等人将逆向增强学习进行拓展，称为学 为学习特征的个数.回报函数R:S×A→R,代价函 徒学习)，并且在文中以一个驾驶模拟实验系统证明 数是负的回报函数c:S×A→R. 了该算法可以快速通过学徒学习掌握不同的驾驶风 2基于线性回报函数的学习 格.近年来，Kolter等人又将层次的概念引入学徒学 习，并首次应用于四足机器人的实验中.另一方面， 在基于线性回报函数的假设下，线性回报函数 Rat诳等人通过将该问题转化为二次最优化问题，并 是基于回报函数的线性组合： 由之提出了MMP框架)，同时在此基础上设计了一 R(s)=0f(s)+w22(s)+…+0f(s). 系列基于梯度下降的算法).近年来，Syed等人又从 式中：i,…,∫是确定的基回报函数(base func- 线性规划]和博弈论角度讨论了该问题，将该问题 ion),每一个学习特征对应一个基回报函数；w= 转化成线性规划问题，运算效率得到大大提高；但在 [和102…wa]为各个基回报函数之间的权值向量. 专家示教是否为最优末知时，作者没有提出一个统一 下面介绍2种基于以上假设的学徒学习的方 的有效算法.文献[9]中将学习过程解释为2个玩家 法，它们分别是基于逆向增强学习的学徒学习和基 间的零和博弈，此方法改进了基于逆向增强学习的学 于P框架的学徒学习.针对回报函数为非线性 徒学习在专家示教非最优情祝下学习结果不理想的 假设的算法将在后面提及 缺点.另外，为了将该算法应用到实际情况中，Grimes 2.1逆向增强学习 和Rao等人在文献中[10]中探讨了在不确定环境下 在逆向增强学习中4)，算法通过专家的演示得 的学徒学习系统设计， 到回报函数，它假设专家是基于一个能产生最优或 目前为止，基于回报函数学习的学徒学习已经 者近似最优策略的回报函数来进行演示的.学习者 被应用到如直升机特技表演，四足机器人的复杂 没有必要也不可能找出真实的回报函数，因为要找 地形穿越及机器手臂控制等领域[6,23]，并且取得 出真实回报函数是一个数学病态问题，因此，学习者 只需近似“还原”出适当的回报函数. 了良好的效果， Ng和Russell提出逆向增强学习后[，Abbeel 1 模型及符号约定 和Ng将增强学习引入学徒学习)，策略π对应的 值函数可以表示成： 本文介绍的方法都是基于马尔可夫决策过程 00 (Markov desision process,MDP)模型的，关于MDP V()=w.E[∑yp(s)I]. 1=0 模型及基于MDP的机器学习可以参考相关文 式中：y为折合因子；等式右边除了”以外的部分称 献[14-15]，在此仅以符号约定为目的简述如下： 为特征期望，记为以，作为算法中2种策略之间相近 MDP模型可以表示为五元组 程度的衡量标准 (S,A,Pa(·）,y,R) 逆向增强学习通过使执行专家演示策略和次优策 式中：S是有限个状态的集合，设状态个数为N;A= 略时获得的回报值的差最大来求得各特征之间的权值 {a1,…,ae}是k个动作的集合；Pa(·)是在状态s ,因此，该学习问题可以归结为以下的最优化问题： 中执行动作a后的转移概率；Y是折合因子，范围在 maXx,w:Iwl2≤1T, [0,1]之间；R是状态到实数集的映射，表示状态所 8.t.V(mg）≥Vw(m)+T,i=1,…,t-1.（1) 对应的回报值. 式中：Tg为专家演示策略.T:为已有的第次迭代 策略πER→A,某策略的值函数可表示为 产生的策略. (s1)=E[R(s1)+yR(s2)+yR(s3)+…Iπ] 文献[5]中提出了基于逆向增强学习的学徒学习 Q函数定义为 迭代算法，并且提出2种方法，分别为边际最大化方法 Q"(s,a)=R(s)+yE-r()[(s')]. (max-margin method)和投影法(projection method).前 Bellman方程可表示为 者将专家策略的回报期望与目前次优策略回报期望的

.210 智能系统学报 第4卷 距离作为目标函数，然后可以通过SVM方法来求解； 义，该优化问题又要优先考虑值较小的".综合以上 而后者是一种更为简单的近似计算方法，其优点是避 考虑，该问题可写成凸函数最优化问题： 免了求解二次最优化问题。由于专家示教的不准确性， miR(w）), 专家演示的最优条件较难达到，Coate8等人提出通过 1 多次次优演示来提取最优策略的方法6. R(w） 2(wa4-w取-a)+ ,民目月 2.2MMP框架 (2) Taskar首先提出了结构最大边际(structured 含1w月 large margin)框架]，在此框架下，RatlifT等人将学 式中：“∈R'14代表每个状态-动作对所对应的访 徒学习归结为在策略空间上的边际最大化结构化预 问频率；F∈Rx1541为基回报函数的矩阵；G:为u 测问题(structured prediction problem)i].在这种方 所在的空间；w'Eg-min{wF-μ}=专：为引入 第eG: 法当中，学习的对象是从特征回报函数到代价函数 的一组松弛变量，代表每个示例中违反约束时的惩 的映射.学习者的目标是接收示例策略，然后通过学 罚；，ER4表示在示例i中的损失函数；A≥0是 习做出相同或者类似的决策.为了解决这个问题， 一个用于正规化的参数.式(2)的优化目标是在违 Ratlif等人提出了MMP框架 反最少的约束条件下找到尽可能小的. 由于Rali道等人在提出该方法时学习的是代价 MMP模型的数值计算方法采用了子梯度方 函数，因此这里沿用了这一概念；但在实际中，代价函 法[i9的改进方法)，其他的计算方法还包括cutting 数和回报函数的意义是类似的，因为代价函数可看作 plane0和extra-gradient方法等.Ratlif等人还结 是负的回报函数.为了还原代价函数，需要不断调整 合boosting思想提出了MMPBOOST算法，使原算法 代价函数来使得示例路径看起来是最优的.算法的目 能够很好地适应新的学习特征.另外，文献[21]研 标就是导找一个这样的代价函数，在使用这个代价函 究了在某些学习特征缺失的情况下的学徒学习， 数时，专家给出的示例路径有最小的代价值.因此，该 2.3基于RL和MMP的学徒学习的比较 算法把示例路径的代价值和拥有最小代价的路径的 基于RL的学徒学习是一种用不同基回报函数的 代价之差作为优化程序的衡量标准.上面的问题可以 线性组合来逼进真实回报函数的迭代过程.而M皿方 用机器学习中的MMSC(maximum margin structured 法可以看作是二次最优化问题的基于梯度下降求解 classification)来描述 法.2类方法的处理过程如图1和图2所示. 当示例的策略和其他的策略相差较小时，算法 需要调整”来使之增大；但是为了使w的值有意 结 束 单个专家演示 逆问增强学习 散函数 杖重向量 学习特征函数 达到要求 正建加报函数 新的策略 增强学习 叫报所数 图1基于逆向增强学习的学徒学习 Fig.1 Apprenticeship learning based on IRL 初始权重向量 学习特征函数 十成山报数 叫报数 损失修币 修正回报函数 结束 收敛 权五向量 最大边际规划 多个专家波示 图2基于MMP的学徒学习 Fig.2 Apprenticeship learing based on MMP

第3期 金卓军，等：回报函数学习的学徒学习综述 .211 这2种方法的共同处在于2点：一是它们都将学 3 习问题转化为对二次最优化问题的求解，优化模型的 结束语 基本思想都是使最优策略与其他非最优策略的边际最 学徒学习让人们摆脱通过反复实验手动调节代 大化，即使得专家演示和其他策略所获得的回报之差 价函数的烦琐过程，使学习者可以通过学习专家的 尽可能大.二是它们的学习的目标相同，即通过学习各 演示来学习最优代价函数，从而生成最优策略.本文 学习特征之间的权重向量来还原回报函数 的主要探讨对象为基于回报函数学习的学徒学习方 这2种方法的区别类似于生成式学习和判别式 法，这也是目前学徒学习的主要方法.文中在回报函 学习2).首先，基于RL的学徒学习只针对一个MDP 数为基回报函数的线性组合和回报函数为非线性2 模型，MP方法的专家示例则可以来自多个不同的 种假设下分别作了概述，主要介绍了基于RL和 MDP模型，这些DP模型可以有各自的状态、动作 MP框架的学徒学习，并且比较了它们的优缺点。 及转移矩阵，它们之间通过学习特征向量(feature 基于回报函数学习的学徒学习中存在许多亟待 vectors)来取得统一.基于RL的学徒学习假定专家 解决的问题.首先应考虑非完全观察状态下的学徒 的演示是最优或者近似最优的，或者说它假定存在一 学习.上面的方法都是建立在MDP模型上的，然而 个使得专家产生最优策略的回报函数，而专家则是根 在实际应用中情况往往是非完全观察状态下的，即 据它来进行演示的.这样的假设条件相对较强，而 是建立在POMDP上的学徒学习.其次，在上面的方 皿的假设则弱得多.其次，二者对每一轮迭代中回 法中，学习特征的提取和设计都是人为完成的，这样 报函数的更新方法不同.基于RL的方法是通过将新 就导致结果受学习特征的选择影响很大，事实上学 产生的策略加入到已有策略集合，然后通过最优化方 习特征有可能通过对状态空间用PCA等方法降维 法求出下一轮的回报.MMP过程中采用根据专家演 来得到.另外，高维空间下学徒学习所带来的巨大计 示修正回报函数的方法，将专家演示所涉及到的学习 算量成为该学习方法被应用到更广泛的领域的主要 特征对应的回报增加，其余的减小，且保证离专家演 障碍，因此，设计高维状态空间下更有效的求解方法 示越远的策略回报减小越多，从而更新回报函数.最 也成为人们关心的问题之一 后，二者解最优化模型采用的方法不同，前者用的是 SVM和投影法，后者用的是梯度下降法. 参考文献： 基于逆向增强学习的学徒学习算法目前还有以 [1]ATKESON C G,SCHAAL S.Robot learning from demon- 下缺点：1)它对于基回报函数的设计非常敏感.这 stration [C]//Proceedings of the Fourteenth International 使得该算法过于依赖人为的基回报函数的设计.尽 Conference on Machine Learing.Nashville,USA,1997: 管P℃A等方法可以被用来从状态中提取学习特征， 12-20. 但在实际应用中这会使算法在特征的提取上花很多 [2]RATLIFF N D,BAGNELL J A,ZINKEVICH M A.Maxi- 时间.2)该算法的不足之处在于缺乏那些部分专家 mum margin planning[C//Proceedings of the 23rd Interna- 演示较少访问到的状态相关信息，从而导致学习结 tional Conference on Machine Learning.Pittsburgh,USA, 果在某些状态不理想.文献[22]针对这2个问题进 2006:729-736. 行了研究，并结合梯度算法给出了解决方案.3)该 [3]金卓军，钱徽，陈沈轶，等.基于回报函数逼近的学徒 学习综述[J].华中科技大学学报：自然科学版，2008 算法的局限性来自于上面提到的线性假设.而下面 (S1):288-290,294 的基于MP的改进算法则去掉了代价函数的线性 JIN Zhuojun,QIAN Hui,CHEN Shenyi,et al.Survey of 假设. apprenticeship leaming based on reward function approxima- MP框架可以被扩展到非线性回报函数的情况， ting[J].Joumal of Huazhong University of Science and Ratliff等人基于boosting的泛函梯度下降理论建立了 Technology:Nature Science,2008,36 (S1):288-290, 指数梯度下降的一般化算法，称为LEARCH算法， 294. LEARCH用更一般化的形式c(”)来表示代价 [4]NG A Y,RUSSELL S J.Algorithms for inverse reinforce 函数，这样式(2)中的wF:就可以写为 ment learing[C]//Proceedings of the Seventeenth Intema- ,系)μ“.式(2)就可以写成下面的形式： tional Conference on Machine Learing.San Francisco, USA,2000:663670. [5]ABBEEL P,NG A Y.Apprenticeship leamning via inverse (t,a)eM: reinforcement learing[C]//Proceedings of the Twenty-first mi{∑.(c(r)“-产)“}).(3) International Conference on Machine Learning.Banff,Can- eG(,a)M ada,2004:1-8

·212· 智能系统学报 第4卷 [6]KOLTER JZ,ABBEEL P,NG A Y.Hicrarchical appren- proach [C]//Proceedings of the 22nd International Confer- ticeship learning with application to quadruped locomotion ence on Machine Learning.New York,USA:ACM, [C]//Advances in Neural Information Processing Systems. 2005.896-903. Cambridge,USA:MIT Press,2008. [18]TASKAR B,LACOSTE-JULIEN S,JORDAN M.Strue- [7]RATLIFF N,BAGNELL J A,ZINKEVICH M A.Subgradi- tured prediction via the extragradient method [C]//Pro- ent methods for maxrimum margin structured learning[C]/ ceedings of Neural Information Processing Systems.Van- Workshop on Learing in Structured Outputs Spaces at IC- couver,Canada,2005:1345-1352. ML.Pittsburgh,USA,2006. [19]SHOR N Z,KIWIEL K C.RUSZCAYNSKI A.Minimiza- [8]SYED U,BOWLING M,SCHAPIRE R E.Apprenticeship tion methods for non-differentiable functions M].New learning using linear programming[C]//Proccedings of the York,USA:Springer-Verlag,1985. 25 International Conference on Machine Learning (ICML [20]TSOCHANTARIDIS I,JOACHIMS T,HOFMANN T,et 2008).Helsinki,inland,2008:1032-1039. al.Large margin methods for structured and interdepend- [9]SYED U,SCHAPIRE R E.A game-theoretic approach to ent output variables[J].The Journal of Machine Learning apprenticeship leaming[C]//Advances in Neural Informa- Re8 earch,2005,6:1453-1484. tion Processing Systems.Cambridge,USA:MIT Press, [21 ]CHECHIK G,HEI'TZ G,ELIDAN G,et al.Max-margin 2008. classification of incomplete data [C]//Advances in Neural [10]GRIMES D B,RAJESH D R,RAO R P N.Leamning non- Information Processing Systems:Proceedings of the 2006 parametric models for probabilistic imitation [C]//Pro- Conference.Cambridge,USA:MIT Press,2007:233- ceedings of Neural Information Processing Systems.Cam- 240. bridge,USA:MIT Press,2007:521-528. [22]NEU G,SZEPESVARI C.Apprenticeship leaming using [11]ABBEEL P,COATES A,QUIGLEY M,et al.An appli- inverse reinforcement learing and gradient methods[C]/ cation of reinforcement leaming to acrobatic helicopter Proceedings of Uncertainty in Artificial Intelligence.Van- flight[C]//Proceedings of Neural Information Processing couver,Canada,2007:295-302 Systems.Cambridge,USA:MIT Press,2007:1-8. 作者简介： [12]KOLTER JZ,RODGERS M P,NG A Y.A complete con- 金卓军，男，1984年生，博士研究 trol architecture for quadruped locomotion over rough ter- 生，主要研究方向为机器学习. rain[C]//IEEE International Conference on Robotics and Automation.Pasadena,USA,2008:811-818. [13]REBULA J R,NEUHAUS P D,BONNLANDER B V,ct al.A controller for the littledog quadruped walking on rough terrain[C]//2007 IEEE International Conference on Robotics and Automation.Roma,Italy,2007:1467- 钱徽，男，1974年生，副教授，人 1473. 工智能学会智能机器人专业委员会委 [14]KAELBLING L P,LITTMAN M L,MOORE A W.Rein- 员，主要研究方向为人工智能、计算机 forcement learning:a survey [J].Journal of Artificial In- 视觉. telligence Research,1996,4:237-285. [15]SUTTON R S,BARTO A G.Reinforcement learning:an introduction[M].Cambridge,USA:MIT Press,1998. [16]COATES A,ABBEEL P,NG A Y.Reinforcement learn- 陈沈轶，男，1980生，博士研究生， ing with multiple demonstrations [C]//The Twenty-first 主要研究方向为机器学习 Annual Conference on Neural Information Processing Sys- tems (NIPS 2007).Vancouver,Canada,2007. [17]TASKAR B,CHATALBASHEV V,KOLLER D,et al. Learing structured prediction models:a large margin ap-