自适应启发式与批判

1、 自适应启发式与批判应用到航空公司收益管理文摘:自适应评论家启发式算法已成为一种流行,特别在强化学习和近似动态规划方面。它是第一个RL和ADP的算法。RL和ADP算法有效的解决马尔可夫决策过程,遭受诅咒的维数和建模。许多现实世界的问题,然而,往往是半马尔科夫决策过程(我们知道的时间花在每个过渡的底层的马尔可夫链本身是一个随机变量。)不幸的是,对于一般的奖励情况,不像这个折扣奖励情况,没有一个简单的扩展。我们知道的例子可以发现在该地区的供应链管理、维修管理、和航空公司收益管理。在本文中,我们提出一种自适应启发式SMDP的批评家在长期平均报酬标准。我们给出了收敛算法的分析显示,在特定条件温和,可以

2、确保在一个模拟器,收敛到最优解的概率1。我们测试了算法的广泛问题航空公司收益管理,经理必须设置价格的机票预订地平线。这个问题有一个大规模的,从痛苦的维数灾难,因此很难解决它通过经典方法的动态编程。我们的数值结果令人鼓舞,它们表明该算法优于现有的启发式广泛使用在航空行业。关键字: 自适应批评家; 演员批评家; 半马尔科夫近似动态规划; 加固;知识1介绍马尔可夫决策问题和决策的系统动力学是由马尔可夫链,并在每个到访的国家系统,控制器必须选择一个从两个或更多的交流组织。的目标是最大化的控制器给出的一些奖励获得在每个到访的国家在一个有限或无限一事的时间范围。在开衩的是在1950年代,更夫1,他们开发了

3、什么是现在叫行李员最优方程。op-erations管理之外,那里的MDP已广泛综采,最近MDPs发现应用程序在其他领域的工程(自主直升机控制2)和人工智能(玩计算机游戏3,4)。经典的方法来解决这个问题包括线性规划和动态规划(DP),例如。,值迭代5,6策略迭代法。DP方法打破下来当数量的国家行动对很大,例如,超过几千,这称为诅咒的维度,也缺乏优化中的概率潜在的马尔可夫链,这是称为诅咒的建模。通常,在大型在现实世界中遇到的难题,国家行动对的数量太大(维数灾难)和转移概率模型太复杂(mod鹅岭诅咒)工作方法对古典DP。这本质上是因为它是困难的,如果不是不可能,存储或过程所有元素的转移概率矩阵,是

4、需要在迪拜。特别是,这些矩阵是一个部分所谓的更夫方程,解决导致一个最优的解决方案。它是在问题遭受这些诅咒,学习(RL)肯定的控制和自适应/近似动态编程(ADP)方法变得有用。RL / ADP方法绕过跃迁概率矩阵和解决的一个变体底层更夫方程没有转移概率矩阵的。这些方法通常依赖于一个模拟器的系统通常是生成的变迁概率。对于教科书引用这个话题,看到例句。,7 - 9。在本文中,我们提出一种新的自适应评论家算法这适用于与在每个状态所花费的时间是一个随机变量和的性能度量花时间考虑。对于所谓的折扣奖励情况下,性能指标是净现值之和的奖励赢得了一个无限的时间范围,适应评论家有一个简单的扩展研究了,在10;所有的

5、改变是折扣系数。然而,对于一般的奖励情况,其中一个试图最大化期望的奖励每单位吗该算法对于SMDP不能开发一个简单的改变算法因为更新MDP包含最优值的性能指标开始时是未知的。为此,我们引入一个另外一对一步迭代的算法更新一个标量到的最优值的性能指标。 2010年7月,修订后的2011年3月16日。这项工作是由美国国家科学基金会(No.ECS0841055)。cSouth中国科技大学和科学院数学与系统科学,CAS和斯普林格出版社柏林海德堡2011422 k . KULKARNI et al。/ J控制理论Appl2011 9(3)421 - 430优化。正如上面提到的,RL算法时非常有用这个问题受到

6、诅咒的维数和建模。因此,我们测试了算法上的问题从航空公司收益管理的国家行动空间是巨大的和变迁概率很难锡箔。我们的算法显示了令人鼓舞的表现这问题,优于工业启发式,广泛所使用的大多数航空公司。我们所掌握的最好知识,这是第一篇论文提出算法收敛的自适应评论家为下位控制平均报酬。其余的文章是有组织的如下。第二节提供了一个背景。新算法是在第3节描述。收敛性能的研究了该算法在第四节。应用程序的该算法对航空公司收益管理问题随着数值计算结果给出了在第五部分,而本研究得出的结论提出了sec名诗6。2 SMDPs和RLSMDP的一个问题是,找到最佳的行动每个州当花费的时间在每一个状态转换是一个随机变量,这个随机时间

7、是一部分功能,即长期平均报酬在我们案例。我们将首先讨论长期平均的re病房2.1长期平均报酬我们首先呈现一些符号需要我们的讨论。让表示有限集的状态在,(i)fi夜间套动作允许在statei,(我)在国家的行动赵森我当政策是跟随,在那里i年代(i)=一个。此外,让r(,.,.·):S××S一个r表示一步法直接奖励,t(,.,.·):S××S一个R表示在一个过渡的时间,和p(,.,.·):S×一个×S0,1表示相关的转移概率。然后,预期报酬直接在状态我当行动被选择在它可以表示为和预期的时间关联的转换:我们现在可

8、以定义长期平均报酬,或sim卡厚度平均报酬,如下所示。定义1让然后进行常规的马尔可夫链,从定理7.5在11(160页),长期平均报酬的一个政策的一开始我是SMDP状态(i)= R(i)/ T(i)。常规的马尔可夫链,(·)是独立的开始状态。2.2 贝尔曼方程平均回报都是关于寻找政策最大化。最优平均报酬将本文通过表示。以下是一个中央再保险饥饿,显示了存在一个最优的解决方案SMDP。结果可以发现在任何标准文本在迪拜,如。,。定理1的平均报酬SMDP所有马尔可夫链是有规则的,存在一个矢量3 自适应批评家发明了一种框架,现在是著名的为启发式动态规划(黄芪丹参滴丸)。一个in-tegral这个

9、框架的一部分,自适应算法是评论家这是基于策略的迭代。黄芪丹参滴丸导致了众多重要算法德章,如。,双启发式的编程和操作依赖黄芪丹参滴丸。一个在这一领域的并行开发的算法是她的。它使用观念的加强品德学习。这是稍后显示在,该算法在并趋近于概率1。我们注意到自适应评论家只是其中的许多算法在ADP / RL。其他著名的算法分为学习和近似策略迭代法大部分文献调查文学在教科书上面命名。感兴趣的读者也提到一些最近的调查论文:看控制理论的观点和看对于一个运筹学和机器学习的观点。ADP / RL目前形式一个活跃的研究领域内的连续时间控制社区;看到如。中央的想法在自适应(演员)批评家是一个政策被选中(读表演),然后制定

10、的政策,即。,sim-ulated(读课目的政策),然后加以改进在一个自适应的方式。自适应批评的力量在于他们有能力解决无需生成概率的过渡。这是自适应暴击打破诅咒的建模和维度。在休息的这一节中,我们讨论我们的新算法。在sec名诗3.1,我们提出一个推导的算法直觉底层,在3.2节中,我们给出了k . KULKARNI et al。/ J控制理论Appl2011 9(3)421 - 430一步一步详细的算法。3.1半马尔科夫适应性批评家自适应评论家启发式的MDP主要有两个组件:一个“演员”,选择一个政策和“评论家”评估值函数相关。波尔冰冷SMDP的,我们需要添加一个第三步中评论家除了估算值函数的平均

11、报酬也国际化程度的机台的政策。这个额外的步骤是由于元素所需的平均报酬和过渡次SMDPs更夫方程。我们将试图解决以下版本的信号工方程:这种假设可以很容易地在实践验证问题的过渡结构,即。,但总体而言,跃迁概率,奖励,和时间,是已知的。然后,的价值可以确定实证。在第五部分,我们将验证这种假设的小问题过渡结构是已知的。在本文中,我们试图使用上面的方程问题的过渡结构是未知的,因此我们将使用一个推测的的价值。Guestimating的价值是一种常见的实践文献中的政策梯度25,26,在那里它一直显示的实际价值可能取决于转移矩阵的特征值,值的不需要非常接近1。然而,自特征值可以确定只有当结构可用的,它是一种标

12、准实践文献中的政策梯度使用一个推测的。在同样的精神,我们将使用一个推测在我们的算法。贴现-MDP我们将为了分析构造一个辅助(或虚拟)贴现MDP为分析我们的SMDP。注意,方程(2)可以视为是贝尔曼方程折扣MDP在该奖励结构改变的;直接的奖励吗是一个函数的,这是固定的和已知的,以及优化中的时间:第六步如果k < kmax,设置我j,然后转到步骤2。否则,转到步骤7。步骤7对于每个l年代,选择d(l)arg马克斯b一(左)P(l,b)。该政策(解决方案)生成的算法D。停止。上面的方法是使用一个合适的值的算法的不到1为了生成一个解决方程(2)这样的that方法平均回报的政策包含在价值函数V。这

13、在假设1确保我们获得最优解。在上面的算法描述,增加清晰的表示,我们已经镇压了上标,k,发票,P,也在一步,大小。然而,我们将在需要的时候使用这些superscripts。“演员”的算法上面选择政策是在步骤3中,虽然“评论家”更新值函数在步骤4和平均奖励在步骤5。步骤大小,和必须满足以下条件。这些条件是必须显示的趋同算法在数学上,不难发现步骤大小满足这些条件。例子的步骤大小遵守这些条件,将提供在第五部分(见方程(14)。最后,我们注意到,选择动作策略在步骤2中被称为玻耳兹曼的策略并透彻研究文献中的RL84算法收敛我们现在学习的收敛性,该算法。连续时间过程的时间内插接轨(见库什纳和克拉克27为经典

14、的描述的每个类的过程)底层迭代。我们将名字迭代的x,y,和z,x,y,将对应最高V,z,R和T。让x(t),y(t)、z(t)表示这些连续时间过程。考虑一个同步的updat-ing循环遍历两个时间尺度以下方案在上面的,f,g,h是函数,将取决于该算法,而MK是鞅差se -在k阶迭代联系在一起。在异步更新,上述方案将被修改的指标函数-优化乘以步骤大小;指标函数返回一个1如果磁带信息处理机组件的迭代更新k阶迭代的模拟器和0否则。注意,在上下文的算法,为x,m(我),y、m我和z,我代表国家和一个动作。我们定义的函数f,g,h和鞅差序列如下:有一个全局渐近稳定的临界点。假设5遍历x,y,和z仍然有限

15、。我们现在我们的主要结果。定理2自适应算法提出了批评以上与概率1收敛于最优政策在假设1的SMDP。为一个固定值of证明,我们已经从定理5.13在16,该算法收敛于一个解决方案是最优的-MDP打折。如果它可以证明收敛to,然后如果假设2 - 5举行,主要的结果在28意味着算法收敛于op -解决方案的timal打折mdp。现在,如果Assump -优化1成立,与一个合适的选择,算法将然后收敛到最优解的SMDP。因此什么还有待证明,该算法满足作为-假设2认为只要一步尺寸遵循规则定义在方程(8)。假设3是适用于任何在从结果的遵循在16。同时,这个迭代P和V仍然有界对于任何价值已经将lished在16。

16、剩下的关于假设5 t表明,仍将有界。然后,在利用引理4.429,就像在(29岁),我们有,as。,k,K0,即。,K,即。,Assump -优化4也满意。这就完成了证明。注意,是否可以验证假设1持有当问题结构是已知的。在实践中,在大-规模的问题,这是排除,我们必须假设一个可以估算值这样,假设1持有。5. 航空公司收益管理在美国的管制下的民航业，机票价格的设定问题，自1978年以来一直备受研究。然而,只有在最近的时代,由于模拟和动态进展程序的发明,研究这个问题中要使用最优或接近最优的技术已经成为可能。收益管理问题是一个连续性的决策问题,决策者已经决定是否接受或拒绝一个可进入的顾客。对于顾客到来(

17、几乎)的网站，航空承运人或其他旅行社的网站(如。Expedia)提供的票价应该给予一致的通过。每条航线提供的每个座位，都需要定期的更新,即每天晚上或每周或每月。座位的价格变化与提供情况、航班出发前剩余时间,客户的喜好,和许多其他因素。结果表明,除非价格调整是一种超智能的方式, 否贼航空公司不能生存在一个有激烈的竞争、需要昂贵的资源的环境中, 不仅低利润,低支出比率，而且还能很好的盈利。接下来，用多种操作的角度看这个问题,以及将一个便于交流计数的文献运用在这个话题讨论中。本质上的问题可以归结为设定价格在解决分配问题中,一个座位的数量被分配到一个给定的票价f 1或所有票价高于f 1。乘客支付同样的

18、费用是属于舱位票价相同类。当座椅对于一个给定的票出售, 下一个更高的票价类是为客户开放。这个问题常出现在取消和超额预定问题中。客户经常取消他们的预订和支付的价格，根据不同的情况他们购买了不同的票。因此,航空公司的飞机,即在超额预订,他们出售更多的席位是在飞机上。通常,由于这种可取消的行为,人们有权力拒绝登机请求。然而,过量的超额预定会导致很多乘客被反复重叠, 这是非常昂贵的。如果不是超额订购已经完成, 飞机飞行中会有一些空位,这损害了航空公司的利益,特别是在他们的高需求,因为航班竞争是可能使用超额预定和飞行接近饱和。飞行中的空位特别是存在于在高需求航线，航空公司会提高他们的票价,或在总体上降低

19、需求。分割的想法用在多样的客户需求上。不同的票价出现是基于不同的乘客会有不同的期望。更多客户想买一个交高价位的座位，同时在取消预订座位时会有较低的罚金。当然,这样的乘客往往有更高的概率取消座位，这些客户往往是商务旅行者。休闲旅客提前计划他们的行程,因此往往更多数字数据显示他们提早预订线。他可以解决以上问题描述的一个启发式，即通过什么方式被普遍称作预期的边际座位收入(EMSR)启发式。它来源于小木的方程30。这个版本在业界被流行地称为EMSR-b31。优秀的评论文学在收益管理已经出现在32、33; 参见34、35教材引用收入管理。强化学习已经用于解决收益管理问题在36、37,但是这些算法的使用是

20、基于自适应没有批评者。该算法在36是一个启发式的基于多步更新,而基于迭代算法的近似政策37确实有收敛担保, 但它既慢且容易现象叫做跳跃现象。以我们最好的知识,本研究提出了第一个数值试验，自适应批评一个大型航空公司收益管理问题。5.1 符号 这里出现的一些符号,将需要多次使用在这部分的文献中。si: 舱位 i销售的座位数量;n:舱位编号;fi: 舱位i的费用;c: 流通的舱位;t: 飞机起飞的剩余时间;H : 预订范围的长度;Yi:舱位i的旅客需求量;C : 飞机的容量; :所有客户的泊松到达率5.2. SMDP我们现在用SMDP模型来解决问题。我们假设这个问题有无限的时间范围，在这预订线是反复

21、的。目标是最大化平均单位时间的奖励。行为空间这个问题是由两个动作:(接受, 否认)。状态空间的问题可以被定义为符合低点:(c, s1,s2,.,sn ,1 ,2 ,.,n,t ),在i是一个向量的大小si包含的时代所有的客户舱位i。的基数有限组件的状态空间应该不超过nAn，A表示多给定的最大的客户舱位。即使有限的组件的状态空间往往是巨大的。为为了地图萍的高维状态空间到一个较低的可管理的维度,我们使用以下函数使用在37。在fi代表的票价类i和D是一个标量的必须确定价值通过试验和错误。我们的状态空间现在定义为(c、P I)而不是定义在(12)。上面的结果是,我们有一个状态空间与一个较小的尺寸,这让

22、我们到一个可控制的范围和允许我们使用查表。5.3 EMSR-b我们现在解释EMSR-b启发式,我们有作为我们的自适应算法的基准评论家。请注意,在我们的表示法:f1< f2<< fn,fi表示第i类的票价。现在将指示要求的总和所有票价类i以上和i。现在,总收益为第i 类是定义为加权平均收入的所有费用i以上和包括i如下:著名的利特尔伍德的方程30在上下文的EMSR-b是对i= 1,2,n1,Pi ,保护水平, 表示数量的席位来保护票价类i,i+ 1,n。没有保护水平最低的类1。预订限制第i类定义因为i= 1,2,n1;注意,预订限制的最高的类应该是能力的n的飞机。Can-cell

23、ations可以占在利特尔伍德的方程在上面的方程代替C通过C /(1问),问是取消了所有的平均概率的票价类。一个人应该注意,一个需要分配的每个随机变量Yi解决上面的方程。5.4 实证结果我们首先实证验证假设1(第5.4.1之前) 然后现在的实证结果在收入管理问题(部分5 4 2)。5.4.1实证验证假设1我们研究的十个小SMDPs过渡概率, 奖励,和时间显示为表1。 的价值对于每个SMDP决心通过详尽的评估然后古典贴现值迭代进行减小值从0.9开始。企业化的贴现值迭代是基于优化方程(2)和= 。这个政策造成的价值迭代的最优政策来比较获得详尽的评估。的值在这个政策不同于最优政策从而确定以经验为主地

24、;这个值当然是上面定义的是。表2显示了值为所有的10 SMDPs描绘在表1。解释结果在表2, 解决-SMDP的任何值大于但少比1相当于解决最初的平均报酬SMDP。9日和10日为例,我们发现that可以承担任何值在0和1之间。结果表明,在一般情况下, 必须经过精心挑选,在实践中,一个值接近吗1应该是一个安全的选择。Tab1 输入问题用于验证假设1。5.4.2收益管理案例研究我们进行了一次广泛的实证分析我们的新算法在收入管理问题描述以上。我们进行了一系列的实验问题3类和4类费用费用。不同的票价类已经被详细的在表3。我们假设一个同质的泊松过程和速率= 1.4每天飞机容量的100个席位。预订地平线是1

25、00天漫长。泊松过程的对于每个票价类是一个独立的泊松过程一个速度Pr公关(我)(我)是到达的概率类i。取消的概率为票价类是与一位顾客的概率能力在一个给定的票价类取消。可以发生的任何时间取消与统一从时间分布的离开预订,直到飞机。详细的到达概率,取消概率和处罚,表4中提供。为3票类系统,我们使用Div = 500, 对4票类系统,我们使用Div = 1000;Div 一个重要的比例常数在方程(13)为一个低维的背包状态空间为我们的问题。这些值到达经过多次实验。我们使用= 0.9在我们的计算,虽然我们发现价值低至0.5不影响政策获得。在遵循步骤大小被用于三个主要的更新算法:该算法是运行在所有的系统上

26、面所描述的(10的3票类和10的4票类), 学习阶段花了最多26秒Pen-tium英特尔处理器的速度2.66 GHz在64位系统歌剧院让人胆怯。一旦得到了最优策略,这是重新运行与政策冻结100复制, ()获得的平均报酬从每个复制是平均计算的平均报酬政策生成的算法,我们表示交流为自适应评论家算法。结果呈现在表5 和6是冻阶段100复制。这个从EMSR-b溶液,用 EMSR ,也估计通过使用100复制。在测试了确定结果在统计上是不同的,是积极的在每一个再保险封山案例研究在95%信心。改善在表5和6是定义在百分比作为从表中可以很清楚的看到,改善在av消除奖励范围从1.35%到18.5%。平均收入等于

27、H每航班。作为样品,我们现一些数字演示平均报酬im证明与迭代在学习阶段。分别地，1和2显示了学习曲线为3票类和一个4票类系统。Fig. 1图表显示了平均报酬的提高在学习阶段迭代系统的FS1d 3票类问题。Fig. 2图表显示了平均报酬的提高在学习阶段迭代系统的FS2c 4票类问题。6.总结自适应评论家已经成为不可或缺的部分文献在ADP / RL自出版的影响力论文Werb¨os13,提出了策略迭代法，作为一种重要的机制,ADP / RL。她的论文et al。15是一个了不起的发展在这一领域。他们的算法设计为MDPs,和收敛性他们的算法成立于16。有些惊人的是,尽管这种性质的算法先于q学习算法17从历史上看,他们收到在文献上的关注更少。另外,还有一个缺口是一种自适应算法文献批评为SMDP下平均报酬。在本文中,我们试图填补这一空缺而提出一个算法,估计最优平均和奖励值函数。我们证明我们的算法的收敛性在数学上使