（概率论与数理统计专业论文）有限阶段半马尔可夫决策过程.pdf

中山大学硕士学位论文 有限阶段半马尔可夫决策过程 【中文摘要】 本文主要研究有限阶段半马尔可夫决策过程( 简记为s m d p s ) 我们考虑有限阶段期 望报酬准则，研究可数状态空间，有限行动空间和无界报酬的模型与无限阶段半马氏过 程不同，在本文中当系统达到计划时间t 后就立即结束，达到t 之前系统的转移次数是不 确定的我们希望找到一个方法来刻画有限阶段s m d p s 的最优方程和最优策略全文主 要由三部分组成第一部分简单介绍了有限阶段s m d p s 的模型，通过引入剩余时间，首次 给出了既依赖于系统当前状态又依赖于系统当前剩余时间的决策规则和策略，并在此基 础上构建了概率空间和相应的期望报酬最优准则第二部分首先提出了全文的一个基本 假设在给定假设的基础上得到了一个计算策略7 r 期望报酬的迭代算法然后由不动点理 论，我们证明了最优值函数是最优方程的唯一解，并给出了一个计算最优值函数的迭代算 法另外，从最优方程出发，我们证明了最优平稳策略的存在性和最优策略的一些性质最 后用一个设备维护的实际例子进一步阐明本文得到的结论第三部分研究了在半马尔可 夫核q 的某种特殊情形下s m d p s 有限阶段模型转化成了连续时间马尔可夫决策过程( 简记 为c t m d p s ) 有限阶段模型和离散时间马尔可夫决策过程( 简记为d 1 m d p s ) 有限阶段模型， 于是本文是对有限阶段c t m d p s 和d t m d p s 的推广 【关键词】 半马尔可夫决策过程，有限阶段，最优策略，最优方程 堡一一一 查堡堕壁兰呈签里壅达筮垄塑 a b s t r a c t f i n i t eh o r i z o ns e m i - m a r k o vd e c i s i o np r o c e s s e s t h i sp a p e rc o n c e r n sw i t ht h ef i n i t eh o r i z o ns e m i - m a r k o vd e c i s i o np r o c e s s e s ( s m d p s ) w i t h d e n u m e r a b l es t a t e s ，f i n i t ea c t i o ns e t sa n du n b o u n d e dr e w a r d t h ec r i t e r i o nt ob eo p t i m i z e di s t h ef i n i t eh o r i z o ne x p e c t e dr e w a r d s d i f f e r e n tf r o mt h o s ei nt h ei n f i n i t eh o r i z o ns m d p s t h e s y s t e mi nt h i sp a p e rt e r m i n a t e sa ss o o na st h ep l a n n i n gh o r i z o ni sr e a c h e d ，a n dt h en u m b e ro f t r a n s i t i o n si su n c e r t a i n w ew a n tt op r e s e n ta s i m p l et e c h n i q u ef o rc h a r a c t e r i z i n gt h eo p t i m a l i t v e q u a t i o na n do p t i m a lp o l i c i e sf o rt h ef i n i t eh o r i z o ns m d p s t h i sp a p e r m a i n l yc o n s i s t so fm r e e p a r t s t h ef i r s tp a r tp r e s e n t st h em a t h e m a t i c a ld e s c r i p t i o no ft h ef i n i t eh o r i z o ns m d p sm o d e l b yi n t r o d u c i n gt h er e m a i n i n gt i m e ，w ef i r s ti n t r o d u c et h ec l a s so fp o l i c i e sw h i c hd e p e n do n b o t ht h es t a t eo ft h es y s t e ma n dt h et i m er e m a i n i n gi nt h ep l a n n i n gh o r i z o n s a n dt h e nw e c o n s t r u c tt h ec o r r e s p o n d i n gp r o b a b i l i t ym e a s u r es p a c ea n de x p e c t e dr e w a r dc r i t e r i o n i nt h e s e c o n dp a r t ，w eg i v eab a s i ca s s u m p t i o nf i r s n y a n do nt h i sb a s i s ，a l le v a l u a t i o na l g o r i t h mf o r c a l c u l a t i n gt h ee x p e c t e dr e w a r do b t a i n e db yu s i n gp o l i c y7 ri sp r o v i d e d f u r t h e r m o r e ，w e p r o v e t h a tt h eo p t i m a lv a l u ef u n c t i o ni sa u n i q u es o l u t i o nt ot h eo p t i m a l i t ye q u a t i o n a n dav a l u e i t e r a t i o na l g o r i t h mf o rc a l c u l a t i n gt h ev a l u ef u n c t i o ni sp r o v i d e d w ea l s os h o w t h a tt h eo p t i m a l s t a t i o n a r yp o l i c ye x i s t s a n ds o m ep r o p e r t i e so fo p t i m a lp o l i c i e sa r ed e v e l o p e d h n a l l y , 锄 e x a m p l ei sg i v e nt oi l l u s t r a t eo u rr e s u l t so ft h i sp a p e r i nt h et h i r dp a r t ，w es h o wt h a tt h ef i n i t e h o r i z o nm o d e l sf o rs m d p sc a nb er e d u c e dt ot h ef i n i t eh o r i z o nm o d e l sf o r d i s c r e t et i m em a r k o v d e c i s i o np r o c e s s e s ( d t m d p s ) o rc o n t i n u o u st i m em a r k o vd e c i s i o np r o c e s s e s ( c t m d p s ) i f t h e s e m i - m a r k o vd e c i s i o nk e r n e lqi st a k e na ss o m es p e c i a lf o r m s a s ar e s u l t 。0 u rn l o d e li s 锄 e x t e n s i o no ft h ef i n i t eh o r i z o nm o d e l sf o rb o t hd t m d p sa n dc t m d p s k e y w o r d s s e m i - m a r k o vd e c i s i o np r o c e s s e s ，f i n i t e h o r i z o n ，o p t i m a lp o l i c y , o p t i m a l i t ye q u a t i o n 中山大学硕士学位论文 l 。 入 s a ，a ( i ) q ( t ，j l i ，a ) r ( i ，a ) h 竹 玩 & l f 西 雪 汐( a ( ) ) 1 1 1 ：t m i i d m 凡s 1ids ( q ，留( q ) ，p i ：，a ) ) 豫( i ，a ) v 丌( t a ) ”忆 h n ，h 毕，h 符号说明 系统的有限计划阶段 当前系统的剩余阶段 状态空间，状态集 行动空间，行动集 半马尔可夫决策核 系统的报酬函数 直到第1 1 个决策时刻的历史 全体h 。的集合 第n 次决策时刻 确定性决策规则 确定性决策规则集合 随机马氏决策规则 随机马氏决策规则集合 4 ( i ) 上的概率分布集 随机马氏策略类 马氏策略类 随机平稳策略类 平稳策略类 概率空间 策略丌的前m 项期望报酬和 策略7 r 的期望报酬 鼠空间上的范数 民空间上的算子 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体己经发表或撰写过的作品成果 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式 标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：栋步央 日期：l o l o 年5 月碣日 学位论文使用授权声明 本人完全理解中山大学有关保留、使用学位论文的规定，即： 学校有权保留学位论文并向国家主管部门或其指定机构送交论文 的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论文 的内容编入有关数据库进行检索，可以采用复制、缩印或其他方法 保存学位论文保密的学位论文在解密后使用本规定 学位论文作者签名：脉步卖 日期：2 0 l o 年5 月2 8 日 导师躲前蝎 导师签名：dj 入9 1 日期：研睥f 月7 日 第一章绪论 1 1 问题提出的背景 作为二十世纪五十年代产生的随机运筹学的一门分支，在过去的几十年中。马尔可 夫决策过程( m a r k o vd e c i s i o np r o c e s s e s ，简记为m d p ) 的理论和应用得到了长足的发展马 尔可夫决策过程是为了研究和控制随机系统未来的发展而建立起来的- 1 7 年轻且极富生 命力的学科，它以马尔可夫( 或半马尔可夫) 过程作为数学模型，是研究一类随机序贯决策 问题的理论，起源于二十世纪五十年代b e l l m a n 1 和b l a c k w e l l 2 】关于动态规划的工作，以 及s h a p l e y 3 2 】有关随机对策的文章二十世纪六十年代h o w a r d 1 6 、b l a c k w e l l 2 】等人的 工作为马尔可夫决策过程奠定了理论基础因此m d p 是( 确定性) 动态规划与马尔可夫过 程相结合的产物，既是应用概率的一门分支，也是随机运筹学的一门分支同时，作为马尔 可夫系统最优控制的理论，亦属于随机系统最优控制的范畴 所谓的随机序贯决策问题，是指在一系列相继的或者连续的时刻( 称之为决策时刻) 点 上作出决策，在每个决策时刻点，决策者根据观察到的状态从可用的行动集中选取一个行 动作为决策；将决策付诸实施后，系统将获得与所处状态和所采取行动有关的一项报酬( 或 费用等) ，并影响系统在下一决策时刻所处的状态系统在下一决策时刻点的状态是随机 的在这一新的决策时刻点上，决策者要观察系统所处的新的状态( 即收集新的信息) 并采 取新的决策，如此一步一步进行下去在每一决策时刻采取的决策都会影响下一决策时 刻系统的运行( 状态，决策等) ，并以此影响将来决策的目的是使系统的运行在某种意义 下( 称为准则) 达到最优而马氏决策过程模型的特点是可采用的行动集，即得报酬( 或费用 等) 和转移概率( 或转移速率) 只依赖于当前系统的状态和选取的行动，与过去的历史无关 半马尔可夫决策过程( s e m im a r k o vd e c i s i o np r o c e s s e s ，简记为s m d p s ) 是马尔可夫决 策过程的一个重要分支连续时间马尔可夫决策过程( c o n t i n u o u st i m em a r k o vd e c i s i o n p r o c e s s e s ，简记为c t m d p s ) 要求相邻的状态跳跃时间服从指数分布，这在一般的过程中 是不满足的马氏更新理论拓广了马氏过程的不足在这个框架下研究的m d p 问题，就 是半马氏模型半马氏模型有很强的实际应用意义，它适用于一般的排队模型，延迟时间 不是指数分布的库存模型和维修更新模型等l i p p m a n 2 3 用不动点理论研究了无界报酬 折扣半马氏决策规划的最优平稳策略的存在性问题以及最优策略的性质董泽清、宋京 生 3 5 1 用初等的证明方法更快的得至u j l i p p m a n 2 3 的结果董泽清、刘克【3 6 】研究了最优 策略的结构侯振挺、郭先平【3 7 】提出了个新的折扣目标，不仅证明了最优平稳策略的 存在性，而且将折扣目标的s m d p 和c 1 m d p 两种模型的结果统一了起来 但是上面的研究都是在无限阶段中进行的，在现实生活中我们通常需要考虑如何在 i 2有限阶段半马尔可夫决策过程 给定的期限内获得最大报酬( 或最小费用) 的问题，因此对于有限阶段模型的研究是非常 重要的在离散时间马尔可夫决策过程( d i s c r e t et i m em a r k o vd e c i s i o np r o c e s s e s ，简记 为d t m d p s ) 中，有限阶段模型是最基础的模型p u t e r m a n 3 1 ( 第4 章) 对这个模型进行了 全面的总结，证明了存在一个确定性马氏策略在策略类中是最优的并给出了寻求这种策 略的的迭代算法另外对a ( t ) 为紧致距离空间，r 是上半连续函数时，给出了一个充分条件 以保证一个确定性马氏策略在上是最优的在连续时间m d p s 中，由于既要考虑当前系 统的状态，又要考虑在计划阶段内系统的剩余时间，有限阶段的策略比无限阶段的策略 要复杂得多，因此对于有限阶段c t m d p s 的研究比较少在先前的研究工作中，通常的分 析方法是把时间间距分割成离散的阶段，然后研究一系列的d t m d p s g e r t s b a k h 5 ( 第一 章) 和h o w a r d 1 7 ( 第1 5 章) 详细地讨论了这个方法h o r d i j ka & d u y ns c h o u t e nk 1 3 ，1 4 ，1 5 】 发展了一个非常普遍的方法来用d t m d p s 逼近c t m d p s 他们的连续时间马尔可夫决策漂 移过程包括了s m d p s 作为特例另外，l i p p m a n 2 5 ，m i l l e r 2 9 ，w a l d m a n n 3 4 等人也分别 讨论了有限阶段c t m d p s 在本文中，我们主要研究有限阶段半马尔可夫决策过程m a m e r 2 7 介绍了一个用逐 步逼近的方法来刻画这个模型的最优策略他发展了一个新的观点来看待这个问题，即决 策者不仅需要考虑当前的系统状态，而且要考虑在有限的计划阶段内系统当前的剩余时 间这个观点在实际应用中是非常有意义的例如在考虑维修更新模型中，决策者在做决 策时常常会把该设备还需要使用的剩余时间也考虑进来 在s m d p s 中，相继两次转移间的状态逗留时间服从一个任意的概率分布，且行动在 每次转移发生时被选取如果假设相继两次转移间的逗留时间服从一个指数分布或者恒 等于一个常数，则s m d p s 就分别转化为c t m d p s 和d t m d p s 因此，我们的模型是有限阶 段c t m d p s 和d t m d p s 的推广 1 2 本文的目的及主要内容 本文主要研究有限阶段半马尔可夫决策问题我们考虑期望报酬准则，研究可数状 态空间，有限行动空间和无界即时报酬的模型与无限阶段半马氏过程不同，在本文中 当系统达到计划阶段t 后就立即结束了，达到t 之前系统的转移次数是不确定的我们借 用m a m e r 2 7 1 的观点，即决策者做决策时不仅需要考虑系统当前的状态，而且要考虑系统当 前的剩余时间这和有限阶段d t m d p s 的马氏决策规n d , ( i 。) 既依赖于当前系统的状态i t 又 依赖于决策阶段t 的模型是类似的我们希望找到一个方法来刻画这个有限阶段半马尔可 夫决策过程，确定在这个模型下的最优方程和证明最优策略的存在性具体来说，本文分 为以下几个章节： 中山大学硕士学位论文 3 第二章给出了有限阶段半马尔可夫决策过程的模型，首先简单介绍了有限阶段s m d p s 模型的数学描述，然后引入剩余时间入，首次给出了既依赖于系统当前状态i ，也依赖于系 统当前剩余时间a 的决策规则妒( z ，a ) 和策略7 r 并在此基础上构建了概率空间( q ，留( q ) ， 礤、) 最后我们给出相应的期望报酬最优准则 ， 第三章首先给出了全文的一个基本假设，这里我们的假设与m a m e r 2 7 的假设有所不 同在给定假设的基础上我们得到了一个计算策略7 r 期望报酬的迭代算法然后通过证明 压缩算子日，由不动点理论证明了最优值函数是最优方程的唯一解，并给出了一个计算最 优值函数的迭代算法接着我们证明了最优平稳策略的存在性及最优策略的一些性质 与m 锄e r 2 7 】只在确定性马氏策略类中寻找最优策略不同，这里我们考虑的是随机的历史 依赖的策略类最后我们用一个设备维护的例子进一步阐明本文得到的结论 第四章研究了在半马尔可夫核q 的某种特殊情形下s m d p s 有限阶段模型转化成了 c t m d p s 和d t m d p s 有限阶段模型，于是本文是对有限阶段c t m d p s 和d t m d p s 的推广 第五章对全文做了总结和展望 第二章有限阶段半马尔可夫决策过程模型 本章给出了有限阶段半马尔可夫决策过程的模型首先简单介绍了有限阶段半马 尔可夫决策过程模型的数学描述然后通过引入剩余时间a ，首次给出了既依赖于系统 当前状态，又依赖于系统当前剩余时间的决策规则和策略并在此基础上构建了概率空 间( q ，留( q ) ，罐，a ) ) 和诱导的随机过程最后给出相应的期望报酬的最优准则 2 1 模型描述 本文所讨论的有限阶段半马尔可夫决策过程模型由如下的五重组描述： t ，s ，a g ) ，q ( t ，j l i ，o ) ，r ( i ，口) 】， 其中各元素的含义如下： ( 1 ) t 是系统的所有决策时刻( 选取行动的时间点) 所构成的集合这里t = 【o ，刀，其 中t 为所讨论的有限计划时间，当系统达到t 后就立即结束另外 o ，列是连续的集合，决策 可以在【o ，卅的任何时刻发生，在这里我们约定决策时刻只发生在状态发生变化的时刻，这 样的过程轨迹是片状连续的 ( 2 ) s 是所观察系统的全体状态所构成的集合，称为状态空间这里所讨论的s 是可列 集，我们常用小写字母i ，j 来表示系统的状态 ( 3 ) a ( i ) 是系统处于状态空f t s 中任一状态i 时的可用行动集合，常用小写字母a 表示行 动令 a ：= ua ( i ) l s 表示全体可用的行动集令 k ：= ( t ，a ) l i sa a ( z ) ， 表示所有可行的状态行动对所组成的集合 ( 4 ) q ( t ，歹l t ，口) 是半马尔可夫决策核，它表示当前的状态为i ，选取行动a 后，在t 时间内状 态转移至| j j 的概率满足： ( a ) 对任意固定的j s ，( i ，a ) k ，q ( ，歹i ，a ) 是一个非降的右连续实值函数，且 q ( o ，j l i ，a ) = 0 6 有限阶段半马尔可夫决策过程 ( b ) 对任意t r + ，q ( t ，i ，) 是一个在给定k 的条件下，定在s 上的子随机核，且满足： d ( t l i ，o ) ：= q ( t ，小口) 1 ， v ( i ，n ) k j s ( c ) p ( 小，) ：= q ( o o ，小，) 是一个在给定k 的条件下，定在s 上的随机核，且满足： 芝：p ( j l i ，n ) = 1 ， v ( i ，o ) k j s ( 5 ) r ( i ，o ) 是定义在k 上的可测实值函数，称为报酬函数报酬函数通常可包括两个部 分，一个是做出决策时的即时报酬，一个是停留在状态i 尚未转移时的报酬率这里我们只 考虑即时报酬，且报酬不依赖于决策时刻t 和未来的状态当r ( i ，口) 为正值时，表示收入； 当r ( i ，o ) 为负值时，表示费用 半马尔可夫决策模型的动态过程可以这样描述：系统在初始时刻t o = 0 处于状态i o s ，决策者有有限计划阶段入o = t ，此时决策者根据系统当前状态和剩余时间从可用的行 动集中选取一个行动a o a ( i o ) ，将决策付诸实施后，决策则获得一个即时报酬r ( i o ，a o ) 然后系统依照半马尔可夫决策核q ( t 1 ，i l i t o ，a o ) 的分布在t 1 时间内从i o 状态转移到状态i 1 接着下一个决策时刻发生在决策时刻亡1 ，同样有一个剩余时间a l ，其中入1 = 【知一t 1 】+ 依 据新的系统状态和剩余时间，决策者选取行动a 1 a ( i 1 ) ，获得即时报酬r ( i l ，a 1 ) 过程这样 继续进行下去当系统达到给定的计划阶段t 或等价的当入n = 0 时系统就立即结束 注这里我们考虑的决策时刻t 【0 ，t 】是有限的，这与通常的s m d p s 模型( 见参考 文献p u t e r m a n 3 1 第1l 章) 有所不同 5 2 2 决策规则、策略及概率空间 我们将系统从时刻o 到第n 个决策时刻的记录着相继的逗留时间，状态i m ，剩余时 间a m 和行动a m 的轨迹，记为h n ，即 k ：= ( t o ，i o ，入o ，a o ，t l ，i l ，a 1 ，a n - 1 ，t n ，i l ，a n ) ， 称为直到第n 个决策时刻的一个历史其中t o = 0 ，入o = t ，r + ，( i m ，a m ) k ，入m + l ：= 【a 仇一+ l 】+ ，m = 0 ，1 ，一，死一1 且有循环结构k = ( k 一1 ，a n 一1 ，如，i 付，a n ) 全体k 所 构成的集合记为巩其中对风赋予b o r e l 仃代数，且 上k = ( r + s 【0 ，t 】a ) 楚o = 月么一1 a 月0 xs 【0 ，卅 注这里k 的定义类似于文献p u t e r m a n 3 1 ( 第1 l 章) ，但在此我们利用了嵌入变量的 方法引入了剩余时间k 这里的k 可由t 一得到 中山大学硕士学位论文 7 一个决策规则描述了决策者在具体的决策时刻采取行动的规则s m d p s 可以在任一 时刻做决策来控制系统，但是在这里我们约定决策时刻只在系统状态发生变化的时刻在 有限阶段决策问题的实际应用中，决策者在做决策时不仅需要考虑系统当前的状态i ，而 且常常会考虑系统当前的剩余时间入在本文中，我们将剩余时间a 引入来给出一个新的决 策规则下面给出决策规则的具体定义 定义2 1 ( 1 ) 如果sx 【0 ，t 】上的可测函数，满足：对v ( t ，入) sx 【0 ，t 】，有 f ：sx 0 ，卅_ a ( i ) ， 甚p f ( i ，入) a ( t ) ，称，为确定性决策规则，或称为决策函数或者马氏决策函数全体决策函 数构成的集合记为f ( 2 ) 如果sx 【0 ，卅上的可测概率分布函数妒满足：对v ( i ，a ) sx 【0 ，z l ，有 妒：s 【0 ，列_ 伊( a ( i ) ) ， 即妒( l t ，a ) 汐( a ( i ) ) 是a ( i ) 上的一个概率分布函数，满足妒( n l i ，入) o 秕o ( a ( i ) l i ，入) = 1 ， 称妒为一个随机的马氏决策规则，或称为马氏决策规则全体随机的马氏决策规则构成的 集合记为西 ( 3 ) 如果巩上的可测概率分布函数族7 r n 满足：对v h n = ( k 一1 ，a n 一1 ，t n ，i n ，k ) 巩， 有 7 y n ：风_ 汐( a ( i n ) ) ， 即( i h n ) 伊( a ( 如) ) 是a ( k ) 上的一个概率分布函数，满足( n i k ) o 且( 弦) i k ) = 1 ，称为第n 个决策时刻的随机的历史依赖的决策规则，或称为一般决策规则 注( a ) 汐( a ( z ) ) 表示a ( ) 上的所有概率分布 ( b ) 由定义不难看出确定性决策规则，是随机马氏决策规则妒退化到单点分布的一个 特例，既有fc 西，而随机马氏决策规则是随机的历史依赖的决策规则的退化情况 ( c ) 这里所定义的决策规则类似与通常的s m d p s 模型中的定义( 见参考文献p u t e r m a n 3 1 】 第1 1 章) ，不同的是这里的决策规则除了依赖与当前系统的状态汐 ，还依赖与当前系统的 剩余时间a 对给定的当前的系统状态z s 和当前的剩余时间a 【0 ，卅，如果g 是sx a 上的实值 可测函数，对于如上定义的确定性决策规则，和随机马氏决策规则妒，我们定义 g ( i ，妒) ：= 妒( 口l t ，a ) g ( i ，口) a e a ( i ) g ( i ，f ) ：= a ( i ，f ( i ，a ) ) dq 圣 f 如 w 8 有限阶段半马尔可夫决策过程 因此，对给定的当前的系统状态i s 和当前的剩余时间入【0 ，刀，在具体的确定性决策 规则厂和随机马氏决策规则妒下，半马尔可夫核和报酬函数可转换为s 【0 ，卅上的函数 q ( t ，m 妒) = v ( o l i ，a ) q ( t ，j l i ，o ) v 妒西 q ( t ，删竺螂胞入) ) 小f f ( 2 2 ) r ( i ，妒) = q o ( a l i ，a ) r ( i ，o ) v 妒圣 、。 r ( i ，f ) = r ( i ，f ( i ，入) )v f f 定义2 2 ( 1 ) 一个随机的历史依赖的决策规则序列7 r = ( f r o ，7 r l ，7 r 2 ) ，称为一个策 略全体策略所组成的集合称为策略空间，记为 ( 2 ) 一个随机的马氏决策规则序列7 r = ( 伽，咿1 ，妒2 ) ，西，n n ，称为随机马氏 策略全体随机马氏策略所组成的集合称为随机马氏策略类，记为r m ( 3 ) 一个随机马氏策略7 r = ( 妒o ，妒1 ，忱) i i r m ，如果对每个佗n ，都有妒n = 妒，则 称这样的策略为随机平稳策略，记作妒o o 全体随机平稳策略组成的集合称为随机平稳策 略类，记为i i m ( 4 ) 一个确定性决策规则序列丌= ( f o ， ，如) ，厶e 几n ，称为马氏策略全体 马氏策略所组成的集合称为马氏策略类，记为n d f ( 5 ) 一个马氏策略7 r = ( f o ， ，尼) i i d m ，如果对每个礼n ，都有厶= f ，则称 这样的策略7 r 为( 确定性) 平稳策略，记作厂全体平稳策略组成的集合称为平稳策略类，记 为l i d s 注( a ) 这里所定义的随机平稳策略和( 确定性) 随机平稳策略虽然依赖于剩余时间，但 是不依赖于第1 1 个的决策时刻即对每个佗n ，第n 个对策时刻的决策规则( i ，a ) 都等 于妒( i ，a ) 这与有限阶段d t m d p s 的定义( 见参考文献p u t e r m a n 3 1 第4 章) 有所区别又有所 相似如果我们把( t ，入) 看做一个新的状态时，这里定义的平稳策略就与通常的s m d p s 中 的定义相统一了( 见参考文献p u t e r m a n 3 1 第1 l 章) ( b ) 从上面的定义可以看到策略类之间的关系为： l i d s i i d m 冬i i r m i i l i d s h r ssy i r m i i 下面我们介绍一个由半马尔可夫决策过程诱导的随机过程的模型 一个概率模型包括3 个元素：样本空间q ，样本空间q 上的b 刃e ? 0 - - 代数历( q ) 以及其 中山大学硕士学位论文 9 上的概率测度p 在有限阶段半马尔可夫决策过程中，我们令 q = ，9x 【0 ，卅xa ，“s 【o ，卵ax = ( r + xs 【0 ，卅xa ) 黯。 一个元素u q 包含了一系列的逗留时间t n ，状态i 住，剩余时间k 和行动a n ，即 u = ( t o ，i o ，知，a o ，t l ，i l ，a 1 ，a l ，) 其e p t o = 0 ，知r + ，且( 亡n ，i 竹，a ，1 ) j 外xs a ，入n + l ：= 【a 忭一t n + l 】+ ，对v 佗n ，我f f 】 称为样本点令留( q ) 为q 上的b d r e 2o - - 代数，则( q ，留( q ) ) 为一个可测空间 定义q 上的随机变量瓦，a n ，a n ，n n 为 墨w ) = t n ，kw ) = 如，a n ) = k ，a nw ) = a n ，( 2 3 ) 其中随机变量表示从第n 一1 个决策时刻到第1 1 个决策时刻系统的逗留时间，k ，a 忆分别 表示第n 个决策时刻系统所处的状态和决策者选取的行动，：= a 。一1 一t q + 表示第n 个 决策时刻系统的剩余时间，其取值范围为 o ，入n 一1 】定义q 上随机变量& 为 & ( u ) = t 七 ( 2 4 ) k = 0 则& 表示第个决策时刻的时间，且有& = e 警ot k ，瓦= & 一晶一1 ，于是随机变t a h n = 【a 俨1 一( & 一& 一1 ) 】+ 对任意初始状态和给定的计划阶段( z ，入) s x o ，卅以及7 r = ( i r e ，7 r i ，) 1 - ，i o n c s c u t u l c e a 定理( 参见文献 2 9 1 拘5 1 节) ，存在唯一( q ，留( q ) ) 上的概率测度g 认g l 满足： 礤，a ) m = 0 ，x o = i ，知= a ) = 1 ( a = 口l b ) 2 ( 。 ( 2 5 ) 邱，a ) ( 死+ 1 t ，k + 1 = ；i h n = ( h - 1 ，a n _ 1 t 竹，i 住，入n ) ，a n ) = q ( t ，；l i n ，a 竹) 邱，a ) ( a n + l = k 一+ 1 i = ( k 一1 ，a n - 1 ，气，i n ，k ) ，a n ，t n + 1 ) = l 则( q ，留( q ) ，a ) ) 为一个概率空间 于是对v o r = ( 7 t o ，7 1 1 ，) i i ，样本点u = ( t o ，i o ，知，a o ，t l ，i x ，入1 ，a l ，) 的概率为： p 磊，知) ( u ) = 尸瓦，a 。) ( ，i o ，知，a o ，t x ，i l ，入1 ，a l ，) = 7 r o ( a o l t o ，i o ，a o ) q ( t x ，i x l i o ，口o ) 7 r 1 ( 0 1 l t o ，i o ，入o ，a o ，t l ，i l ，a x ) q ( t ：，i 2 l i , ，a 1 ) 特别的，对v 打i i r m ，样本点u 的概率为： 。知) ( u ) = 7 r o ( a o l i o ，a o ) q ( t 1 ，f i l i o ，a o ) 7 q ( a , l f i ，) q ) q ( t z i u l i l ，a 1 ) 1 0 有限阶段半马尔可夫决策过程 对v 丌n d m ，样本点u 的概率为： 尸盈，a 。) ( u ) = q ( h ，i l l i o ，f o ( i o ，入o ) ) q ( 亡2 ，i 2 1 i x ，f l ( i l ，知一t 1 ) ) 令表示概率空间( q ，历( q ) ，露，a ) ) 上的实值随机变量，我们定义w 的相应于策略7 r 的 期望为： 彤m ( ) = w ( u ) ”( “，) u n = 伽碌m ( w ( u ) = 加) r 其中u = ( t o = 0 ，i o = i ，a o = 入，a o ，亡1 ，i l ，a 1 ，a 1 ，) q 通过上面的讨论，我们现在定义一个相应于过程 & ，k ，a n ，n ) 的连续时间状 态一行动过程 z ( t ) ，a ( t ) ，t r + ) ，其中 z ( t ) = j 乞，a ( t ) = a n ， 对v t 岛+ 1 ，t r + ，n 定义2 3 随机过程 z ( 亡) ，a ( t ) ，t 皿) 称为( 连续时间) 半马尔可夫决策过程 对v 丌，定义( q ，留( q ) ，碌，a ) ) 上的随机变量序列( r ( ，山) ，r ( 蜀，a 1 ) ，) ，称为 由策略丌产生的报酬过程我们将要研究由报酬过程确定的一些数字特征以及作为衡量策 略优劣的效用准则函数 注( a ) 上面概率空间( q ，留( q ) ，a ) ) 的构造过程和性质可参见文献【1 9 】 ( b ) 我们只考虑给定初始状态t 和计划时间入的概率测度邱，a ) ，对更一般的给出初始状 态分布u 的概率测度磁m 可由，a ) 2 荟u ( i ) 镙，砷给出 为了使讨论的问题有意义，必须避免在有限阶段【o ，卅内系统的跳跃次数是无穷的在 本节的最后我们给出以下的假设 假设2 1 对任意的( i ，入) sx 【0 ，t 】和7 r ，有 礤，a ) ( 恕晶 t ) = 1 ( 2 6 ) 假设2 1 ( 以概率1 ) 保证了系统在t 时间内只有有限次的状态变化下面我们给出一个 假设2 i 的充分条件 条件2 1 存在6 0 和i s 0 ，使得对所有的状态i s 和行动a a ( i ) 都有： q ( 删1 叱 ( 2 7 ) 中山大学硕士学位论文u 注( a ) 条件2 1 的直观描述就是从任意个状态i s 出发，使用任何行动a a ( t ) ， 系统下一次发生状态转移的时间不超过6 的概率严格小于1 它( 以概率1 ) 保证了在任意有 限的阶段内系统发生状态转移的次数不是无穷的，即对任意的( t ，a ) sx 【0 ，刀和7 r n 有磁 、( 1 i m & = ) = 1 因此，条件2 1 蕴含了假设2 1 、7 t i 。十 ( b ) 事实上，条件2 1 是m a m e r 2 7 文中的重要假设，在本文中我们的假设是l l m a m e r 2 7 】 弱的假设2 1 2 3 最优准则 对前面所介绍的半马尔可夫决策模型 正s ，a ( i ) ，q ( t ，j l i ，口) ，r ( i ，d ) ) ，在选定一个策 略7 r 并实施以后，决策者在有限计划阶段【o ，t 内，在决策时刻岛，& ，依一定的概率获 得一串报酬序n ( n ( x o ，a o ) ，r ( x 1 ，a 1 ) _ ，) 对任给( t ，入) s 【0 ，明，令( a ) 表示在入时间前系统状态转移的次数我们定义在策 略7 r 下的有限阶段期望报酬为： ( ) w ( i ，a ) = ，a ) 【r ，a n ) 】 ( 2 8 ) n = 0 它表示在决策时期内使用策略，系统在初始时刻的状态为i ，剩余时间为a 的条件下，获得 的期望报酬 注表达式与有限阶段离散时间马尔可夫过程的期望总报酬是类似的( 见参考文献 31 】 第4 章) ，不同的是这里的表达式依赖于剩余时间入，并且这里的决策次数( a ) 是个随机变 量而非常量 在有限阶段半马尔可夫决策过程中，我们关注的是如何确定策略丌，使得期望报 酬最大。并且计算它的最大值伊 定义2 4 令 v + g ，入) = s u p v 霄0 ，入) ，v ( i ，入) s 1 0 ，t 】 ( 2 9 ) n e l l 为最优值函数 定义2 5 策略7 r n 称为最优策略，若 v 丌( i ，入) = v + ( t ，a ) ，v ( i ，a ) sx 0 ，卅 ( 2 1 0 ) 注这里我们的定义与无限阶段半马氏过程的最优值函数和最优策略的定义有所区 别又有所相似，区别的是我们这里的函数和策略是既依赖于状态i 又依赖于剩余时间入的 有限阶段半马尔可夫决策过程 当我们把( ，a ) 看做一个新的状态时，我们的定义与无限阶段半马氏过程里的定义就一致 了 在一般的策略类中寻找最优策略是很难的，而且实用性也不强s t r a u c h 等人已经证明 了对于期望报酬准则，在最一般的策略类中的优化问题可以等价于在随机马氏策略类里 的优化问题 命题2 1 对于任意一个策略丌n 和( ，入) s 【0 ，t 】，存在策略7 r 7 n r m ，有 v ”( ta ) = y 一( i ，a ) 证明 证明过程可参见文献【3 1 】定理1 1 1 1 或文献【3 9 】引理6 2 的证明 口 因此，在以下的内容中，我们限制在r m 中讨论 第三章最优方程及最优策略的存在性 在这一章中。我们首先给出了全文的一个基本假设在给定假设的基础上我们得到了 一个计算策略7 r 期望报酬的迭代算法然后通过证明压缩算子日，由不动点理论证明了最 优值函数是最优方程的唯一解，并给出了一个计算最优值函数的迭代算法接着我们证明 了最优平稳策略的存在性及最优策略的一些性质最后我们用一个设备维护的例子进一 步阐明本文得到的结论 3 1 策略7 r 的迭代算法 对于上一章所介绍的半马尔可夫决策模型 t ，s4 ( i ) ，q ( t ，j l i ，口) ，n ( i ，口) ) ，考虑在期 望报酬的准则下，下面我们给出全文的两个基本假设 假设3 1 对v i s ，a ( z ) 有限 假设3 2 存在s 上的实值函数w ( i ) l 及常数m 0 ，0 口 记战为b 上满足l l u l l 伽 o 。的函数展开的b a n a c h 空间对任意的扎b w ，( i ，入) s 【0 ，t i ，a a ( i ) ，妒西，定义上的算子日n ，日妒，日为： 1 3 1 4 有限阶段半马尔可夫决策过程 俨札( i ，a ) ：= r ( i ，口) + f o a q ( d t ，巾，o ) u ( j ，a t ) ， h 妒u ( i ，入) ：= o ( a l i ，a ) h 口u ( i ，入) ， o a ( i ) 日牡( 训：_ 。m 刚& x 日。让( 训 注由算子日口，日p ，h 的定义可得它们都是单调算子，即如果u ，秽巩，且u ， 那么h 口u 日o u ，日妒乱日妒u ，h u h v 引理3 1 算子日口，日i p ，日将风中函数映回民 证明 要证日口将b w 中函数映回玩，既要证对任意的u 民，i s ，都有h 。u ( i ，) 关 于【0 ，卅可测且l i h a u l l o o 对任意的缸民，( i ，入) s 【o ，卅，a a ( i ) ，m h a 的定 义 日口饥( i ，a ) = 冗( i , a ) + z q(出，歹fi，n)仳u，af)，jes ，u 则日口u ( i ，) 关于【o ，t 】可测是很明显的另外，由范数的定义及假设3 2 有， i g 口u o