期月20年609电子学报ATLCRNC

基于高斯过程分类器的连续空间强化学习王雪松１，２，张依阳１，程玉虎１（１．中国矿业大学信息与电气工程学院，江苏徐州２２１１１６；２．中国科学院自动化研究所，北京１００１９０）摘要：如何将强化学习方法推广到大规模或连续空间，是决定强化学习方法能否得到广泛应用的关键．不同于已有的值函数逼近法，把强化学习构建为一个简单的二分类问题，利用分类算法来得到强化学习中的策略，提出一种基于高斯过程分类器的连续状态和连续动作空间强化学习方法．首先将连续动作空间离散化为确定数目的离散动作，然后利用高斯分类器对系统的连续状态－离散动作对进行正负分类，对判定为正类的离散动作按其概率值进行加权求和，进而得到实际作用于系统的连续动作．小船靠岸问题的仿真结果表明所提方法能够有效解决强化学习的连续空间表示问题．关键词：高斯过程；分类器；连续空间；强化学习；小船靠岸问题中图分类号：ＴＰ１８文献标识码：Ａ文章编号：０３７２２１１２（２００９）０６１１５３０６ＲｅｉｎｆｏｒｃｅｍｅｎｔＬｅａｒｎｉｎｇｆｏｒＣｏｎｔｉｎｕｏｕｓＳｐａｃｅｓＢａｓｅｄｏｎＧａｕｓｓｉａｎＰｒｏｃｅｓｓＣｌａｓｓｉｆｉｅｒＷＡＮＧＸｕｅｓｏｎｇ１，２，ＺＨＡＮＧＹｉｙａｎｇ１，ＣＨＥＮＧＹｕｈｕ１（１ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＥｌｅｃｔｒｉｃａｌＥｎｇｉｎｅｅｒｉｎｇ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＭｉｎｉｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｘｕｚｈｏｕ，Ｊｉａｎｇｓｕ２２１１１６，Ｃｈｉｎａ；２．ＩｎｓｔｉｔｕｔｅｏｆＡｕｔｏｍａｔｉｏｎ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１００１９０，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｈｅｇｅｎｅｒａｌｉｚａｔｉｏｎｏｆｒｅｉｎｆｏｒｃｅｍｅｎｔｌｅａｒｎｉｎｇｍｅｔｈｏｄｓｔｏｌａｒｇｅｓｃａｌｅｏｒｃｏｎｔｉｎｕｏｕｓｓｐａｃｅｓｈａｓｂｅｃｏｍｅａｍａｊｏｒｆｏｃｕｓｉｎｔｈｅｒｅｓｅａｒｃｈｆｉｅｌｄｏｆｒｅｉｎｆｏｒｃｅｍｅｎｔｌｅａｒｎｉｎｇ．Ｕｎｌｉｋｅｔｈｅｐｒｅｓｅｎｔｒｅｉｎｆｏｒｃｅｍｅｎｔｌｅａｒｎｉｎｇｍｅｔｈｏｄｓｆｏｒｃｏｎｔｉｎｕｏｕｓｓｐａｃｅｓｂａｓｅｄｏｎａｖａｌｕｅｆｕｎｃｔｉｏｎａｐｐｒｏｘｉｍａｔｉｏｎｍｅｔｈｏｄ，ｔｈｅｒｅｉｎｆｏｒｃｅｍｅｎｔｌｅａｒｎｉｎｇｉｓｃｏｎｓｔｒｕｃｔｅｄａｓａｓｉｍｐｌｅｂｉｎａｒｙｃｌａｓｓｐｒｏｂｌｅｍ．ＡｋｉｎｄｏｆｒｅｉｎｆｏｒｃｅｍｅｎｔｌｅａｒｎｉｎｇｍｅｔｈｏｄｆｏｒｃｏｎｔｉｎｕｏｕｓｓｔａｔｅａｎｄａｃｔｉｏｎｓｐａｃｅｓｂａｓｅｄｏｎａＧａｕｓｓｉａｎｐｒｏｃｅｓｓｃｌａｓｓｉｆｉｅｒｉｓｐｒｏｐｏｓｅｄｕｓｉｎｇａｃｌａｓｓｉｆｉｃａｔｉｏｎａｌｇｏｒｉｔｈｍｔｏｏｂｔａｉｎａｃｏｎｔｒｏｌｐｏｌｉｃｙ．Ａｔｆｉｒｓｔ，ａｃｏｎｔｉｎｕｏｕｓａｃｔｉｏｎｓｐａｃｅｉｓｄｉｓｃｒｅｔｉｚｅｄｉｎｔｏｄｉｓｃｒｅｔｅａｃｔｉｏｎｓｗｉｔｈｄｅｆｉｎｉｔｅｎｕｍｂｅｒ，ａｎｄｔｈｅＧａｕｓｓｉａｎｐｒｏｃｅｓｓｃｌａｓｓｉｆｉｅｒｉｓｕｓｅｄｔｏｐｒｅｄｉｃｔｔｈｅｐｒｏｂａｂｉｌｉｔｙｏｆｃｌａｓｓｆｏｒａｃｏｎｔｉｎｕｏｕｓｓｔａｔｅｄｉｓｃｒｅｔｅａｃｔｉｏｎｐａｉｒ．Ｔｈｅｎａｃｏｎｔｉｎｕｏｕｓａｃｔｉｏｎｉｓｇｅｎｅｒａｔｅｄｂａｓｅｄｏｎａｗｅｉｇｈｔｅｄｏｐｅｒａｔｉｏｎｏｆｔｈｅｐｏｓｉｔｉｖｅａｃｔｉｏｎｓｗｉｔｈｔｈｅｉｒｐｒｏｂａｂｉｌｉｔｙｖａｌｕｅｓ．Ｃｏｍｐｕｔｅｒｓｉｍｕｌａｔｉｏｎｓｉｎｖｏｌｖｉｎｇａｂｏａｔｐｒｏｂｌｅｍｉｌｌｕｓｔｒａｔｅｔｈｅｖａｌｉｄｉｔｙｏｆｔｈｅｐｒｏｐｏｓｅｄｒｅｉｎｆｏｒｃｅｍｅｎｔｌｅａｒｎｉｎｇｍｅｔｈｏｄ．Ｋｅｙｗｏｒｄｓ：Ｇａｕｓｓｉａｎｐｒｏｃｅｓｓ；ｃｌａｓｓｉｆｉｅｒ；ｃｏｎｔｉｎｕｏｕｓｓｐａｃｅ；ｒｅｉｎｆｏｒｃｅｍｅｎｔｌｅａｒｎｉｎｇ；ｂｏａｔｐｒｏｂｌｅｍ１引言强化学习基于动物学习心理学的有关原理，采用人类和动物学习中的试错法机制，强调在与环境的交互中学习，可以不需要系统模型而实现无导师的在线学习．对于很多领域的实际问题，从人工智能的博弈问题、调度优化、智能机器人到实际的工业过程控制都可以描述为强化学习问题，因而强化学习具有广阔的应用前景．但是，实际系统的空间往往是大规模或连续的，强化学习不可避免的存在状态变量的空间复杂度问题，即维数灾难．因此，与强化学习问题的理论模型相比，实际的应用问题要复杂得多，这导致了强化学习理论在实际应用中的困难．在强化学习领域，解决连续空间的表示问题主要有三类方法：离散化方法、参数化函数逼近法以及非参数化函数逼近法．离散化方法的核心概念是任务分解，将连续的空间量化为若干个离散的区域，在同一区域的状态认为其值函数相等，于是一个连续或较大规模的马尔可夫决策问题（ＭａｒｋｏｖＤｅｃｉｓｉｏｎＰｒｏｂｌｅｍ，ＭＤＰ）被离散化为规模较小的ＭＤＰ问题．离散化的方法主要有ＢＯＸ方法，模糊划分以及聚类方法等．采用离散化方法的强化学习已经被证明是收敛的，但其并不一定收敛到原问题的最优解上．要使收敛的值函数达到一定的精度，离散化的区域不能太少．因此，对于大规模的ＭＤＰ问题，它收稿日期：２００８０５１６；修回日期：２００９０２１６基金项目：教育部新世纪优秀人才支持计划（ＮｏＮＣＥＴ０８０８３６）；国家自然科学基金（Ｎｏ．６０８０４０２２）；江苏省自然科学基金（Ｎｏ．ＢＫ２００８１２６）；高等学校博士学科点专项科研基金（Ｎｏ．２００７０２９０５３７，２００８０２９０１５０６）；国家博士后科学基金（Ｎｏ．２００７０４１１０６４）第６期２００９年６月电子学报ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡＶｏｌ．３７Ｎｏ．６Ｊｕｎ．２００９仍然面临着维数灾难的困难，进而在学习时间和存储空间两方面也将降低强化学习控制系统的性能．在已提出的参数化函数逼近方法中，按照函数逼近器的类型，可以分为基于线性值函数和非线性值函数逼近的连续空间强化学习．前者的具体做法是，首先假定强化学习的值函数是一些给定线性基函数的加权组合，然后采用最小二乘或递归最小二乘方法对权值进行估计，进而得到关于值函数的估计值．该方法的缺陷是，若假定不合适，则估计的偏差会很大．基于非线性值函数逼近方法的思想是，利用神经网络的并行计算、容错性和非线性函数逼近能力，对连续空间下强化学习的值函数进行回归估计．但是，基于神经网络的值函数逼近法存在网络结构不易确定、参数调整过程比较复杂、易于陷入局部极小等缺点．由Ｖａｐｎｉｋ依据结构风险最小化原则提出的支持向量机具有坚实的理论基础，良好的泛化性能，可以在一定程度上解决神经网络中的局部极小、网络结构难以确定以及泛化能力问题［１］．近年来，一些学者采用支持向量机来解决强化学习的连续空间表示问题，并成为强化学习领域研究的热点方向之一．该方法的思想是，类似于神经网络值函数逼近，首先将强化学习问题构造为能用支持向量机求解的数学描述形式，然后采用经典的支持向量机及其各种改进形式，如最小二乘支持向量机、岭回归等方法对状态的值函数、状态动作对的值函数或回报函数进行回归估计计算［２，３］，应用实例包括资源限制排程问题［４］、３维现场可编程门阵列的布局与布线［５］等．为了将强化学习方法推广到连续空间，上述函数逼近法均是将强化学习构建为值函数或回报函数的回归估计问题，通过计算系统的值函数来组织对最优策略的搜索．不同于已有的值函数逼近法，本文把强化学习构建为一个简单的二分类问题，利用分类算法来得到强化学习中的策略，提出一种基于高斯过程分类器的连续空间强化学习方法．该方法的主要思想是，首先将连续动作空间离散化为确定数目的离散动作，然后利用高斯过程分类器对系统的连续状态离散动作对进行正负分类，对判定为正类的离散动作进行加权求和，进而得到实际作用于系统的连续动作．小船靠岸问题的仿真结果表明所提方法能够有效解决强化学习的连续空间表示问题．２基于高斯过程分类器的强化学习强化学习以马尔可夫决策过程为基础，通过试错机制来获得最优行为策略［６］．一个有限的ＭＤＰ可由一个５元组表示：｛Ｓ，Ａ，ｐ（ｓｔ，ａｔ，ｓｔ＋１），ｒ（ｓｔ，ａｔ），Ｑ；ｓｔ，ｓｔ＋１∈Ｓ，ａｔ∈Ａ｝，其中Ｓ为状态空间，Ａ为动作空间，ｐ（ｓｔ，ａｔ，ｓｔ＋１）为系统处于状态ｓｔ时，执行决策动作ａｔ后转移到下一状态ｓｔ＋１的转移概率，ｒ（ｓｔ，ａｔ）为在状态ｓｔ下执行动作ａｔ获得的立即回报，Ｑ为值函数，按下式进行迭代计算：Ｑｔ＋１（ｓ，ａ）＝（１－η）Ｑｔ（ｓ，ａ）＋η［ｒｔ＋γｍａｘａｔ＋１Ｑｔ（ｓｔ＋１，ａｔ＋１）］（１）其中，学习率０≤η≤１控制学习的速度，学习率越大，收敛越快，但容易产生振荡；学习率越小，收敛越慢．折扣因子０≤γ≤１表示学习系统的远视程度，如果取值比较小，则表示系统更关注最近的动作的影响；如果比较大，则对比较长的时间内的动作都很关注．一般来说，η取得较小，γ取得较大．状态转移中两相邻状态值函数的时间差分定义为ＴＤ误差：δｔ＝ｒｔ＋γＱ（ｓｔ＋１）－Ｑ（ｓｔ）（２）强化学习的基本思想为：若某一动作获得环境正的奖赏，那么系统以后产生这个动作的趋势便会加强；否则，系统产生这个动作的趋势便减弱．因此，ＴＤ误差实际上反映了所选动作的优劣程度．如果把分类器和强化学习结合起来，必须转换观点：在学习过程中，若ＴＤ误差呈减小趋势，则将当前所选动作定义为“正类”；反之，将其定义为“负类”，这样就可将整个状态动作空间粗略地划分为两类．高斯过程是一种概率意义上的核机器，主要优点体现在：它是一种非参数概率模型，不仅能对未知输入做输出预测，而且同时给出该预测的精度参数；可以以先验概率的形式表示过程的先验知识，从而提高过程模型性能；与神经网络、支持向量机等方法相比，高斯过程模型参数明显减少，因而参数优化相对容易，且更易收敛［７］．因此，可以利用高斯过程分类器来得到强化学习中的策略．基于高斯过程分类器的强化学习如图１所示．图中，ｓｔ∈Ｒｎ表示ｔ时刻ｎ维系统状态，待选动作集Ａ＝ａｋ∈Ｒｋ＝１，２，…，{}ｍ，ｍ为待选动作的个数．将系统的状态与ｍ个待选动作分别配对，构成状态动作对（ｓｔ，ａｋ）顺序输入给高斯过程分类器，高斯过程分类器的输出πｋ为（ｓｔ，ａｋ）属于正类的预测概率值．然后，对判定为正类的离散动作（πｋ＞０５）按其概率值进行加权求和，即可得到实际作用于系统的连续动作ａｔ，具体操作如式（３）和（４）所示．环境在动作ａｔ的作用下，得到立即回报ｒｔ，由式（２）计算系统的ＴＤ误差．根据ＴＤ误差判断（ｓｔ，ａｋ）的类别标签ｙｔ，进而得到高斯过程分类器新的训练样本（ｓｔ，ａｔ），ｙ()ｔ．πｋ＝πｋ，πｋ＞０５０，πｋ≤{０５（３）４５１１电子学报２００９年ａｔ＝∑ｍｋ＝１ａｋπｋ∑ｍｋ＝１πｋ（４）由于强化学习强调在与环境的交互中学习，可以不需要环境模型而实现无导师的在线学习．因此，高斯过程模型的训练样本需要通过强化学习系统不断地与环境交互而顺序生成，如果将新增样本与已有样本合并后处理，一方面会增加学习的难度，另一方面也因样本集过大而消耗过多的时间和存储空间．为此，引入滚动时间窗机制实现高斯过程模型的在线学习，即在强化学习系统学习的同时获取样本数据并进行高斯过程模型的训练．建立一个随时间窗滚动的建模数据区间［８］，并保持该区间长度不变，随着新数据（（ｓｔ，ａｔ），ｙｔ）的不断加入，旧数据则从建模区间滚动出去．３在线高斯过程分类器学习设图１中的时间窗宽度为Ｌ，则当前ｔ时刻高斯过程模型的学习训练样本集由过去Ｌ组数据构成Ｄ＝（ｘｉ，ｙｉ）ｉ＝ｔ－Ｌ，ｔ－Ｌ＋１，…，ｔ{}－１，其中样本输入数据ｘｔ－１＝（ｓｔ－１，ａｔ－１）Ｔ∈Ｘ＝Ｒｎ＋１表示由（ｔ－１）时刻ｎ维系统状态ｓｔ－１和１维动作ａｔ－１构成的状态动作对，样本输出数据ｙｉ∈Ｙ＝－１，{}＋１为类别标签，其中＋１和－１分别对应正负类．假定高斯过程模型的训练集是按Ｘ×