2022年马尔可夫决策规划 .pdf

《2022年马尔可夫决策规划 .pdf》由会员分享，可在线阅读，更多相关《2022年马尔可夫决策规划 .pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2008.10 1 马尔可夫决策规划第五讲 有限阶段模型及其他有限阶段模型的目标只有有限项，即1110210100PPPPPPP)(2)(nnnfffffnffffffnrrrrV1) 当 n 充分大时，近似令n2) 用动态规划法求解注意：用 Bellmon 最优化原理可推出平稳策略优势。 5.1 向后归纳法在确定性动态规划问题求解中，向后归纳法是寻求最优策略的一种有效解法，同样也是求解有限阶段 Markov 决策规划 问题中最优策略与最优值函数的有效解法。定理 5.1 在状态集与所有行动集均为有限的有限阶段模型中，定义函数nVi，使其满足如下等式：SjniAanjVai jpairiV1*,

2、maxSjnnnjVifi jpifir1*, .(5.1) 0,.,2, 1,NNNnSi其中01*jVN。则由上述算式求出的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - 2008.10 2 00001 ,2 ,.,VVVVl即为有限阶段模型的最优值函数，即对每个iS，均有0sup,NViVi；与此同时求得的决策序列01,.,Nfff即为最优策略，其中1,2,., Sl。由于所有的,A iiS及1,2,., Sl均为有限集，

3、故由(5.1)式求得的nfi一定存在，且达到最优的行动可能多于一个（此时可任取一个作为nfi） 。定理 5.1 不仅解决了有限阶段模型求解最优策略的方法问题，而且还表明对任何n，iVn*表示在阶段 n，从状态i 出发，在余下1Nn 的阶段的最优期望总报酬，1,.,nnNfff也构成从 n 到阶段 N 的最优策略，这体现了Bellman 的最优化原理。例 5.1 求解例 3.1 中当 N=3 时的最优策略与最优值函数。解：由题意知，机器只有两个状态，即S=1, 2 ，对应的行动集分 别 为321,2,1aaAaA。 故 最 优 值 函 数 的 形 式 为0001 ,2VVV，其中01V与02V可

4、通过（ 5.1）式分别求解得到。注意题设3N，因而根据向后归纳法的求解顺序应为iViViViViV0*1*2*3*4*，其中1,2iS。下面分别列出n=3, 2, 1, 0 时按照 (5.1)式计算的有关结果。1) n=3，有：0214*4*VVSjAajVajparV4*13*, 1, 1max110, 1, 1max11ararAa名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 2008.10 3 到达31V右边最大的行动为

5、a1，故令311fa ；SjAajVajparV4*23*,2, 2max222,5max,2,2max32arar到达右端最大的行动为a3，故令332fa。2) n=2，由 (5.1)式及上一步计算得到的331 ,2VV有SjAajVajparV3*12*, 1, 1max14 .1623. 0107.0, 11ar故令211fa ；SjAajVajparV3*22*, 2, 2max226 .0104 .0,2,24.0106 .0,2max32arar8 .08. 0,2.0max达到22V右端最大的行动为a3，故令232fa。3) n=1，由 (5.1)式及上一步计算得到的221 ,2

6、VV有SjAajVajparV2*11*, 1, 1max172.218.03.04.167.010故令111fa；SjAajVajparV2*21*, 2,2max28.06.04 .164.0,2,8.04.04 .166.0,2max32arar名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - 2008.10 4 16.504.5,16. 5max达到12V右端最大的行动为2a，故令122fa。4) n=0，由 (5.1)式

7、及上一步计算得到的111 ,2VV有SjAajVajparV1*10*, 1, 1max1752.2616.53 .072.217.010故令011fa；SjAajVajparV1*20*, 2, 2max216.56 .072.214 .02,16.54.072.216.05max096.10784.9,096.10max达到02V右端最大的行动为a2，故令022fa。由 定 理5.1可 知 最 优 函 数 为2,10*0*0*VVV=(26.752, 10.096)=2,1 ,*3*3VV， 相 应 的 最 优 策 略 为*ggffffff,*3*2*1*0， 其 中111agf，22af

8、，32ag。注：本例中的最优策略不是平稳的，决策函数f2, f1, f0不同。由此可见，有限阶段问题的最优策略一般不是平稳策略。例 5.2假设一设备制造厂承接了某工程中一台关键设备的制造任务，工程对此设备的质量标准有非常严格的要求。以该厂现有的技术水准而言，每台制成的设备能通过质量检验而被接受的概率仅为 0.25。再因该工程对此设备又有一定的时限要求，所以厂名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 9 页 - - - - - - - - - 2008.10 5 方决

9、定，至多安排三个生产周期完成此项任务，每一生产周期可制造03jj台设备。 在每一生产周期结束时，均对已制成的设备进行检验，只要其中有一台是合格的，便不再安排新的生产周期。在每一生产周期，只要开工制造这种设备便须一固定的开工费用1C。此外，生产每台设备的费用为2C。若在第三个生产周期结束时，厂方仍未能生产出一台合格的设备，从而无法向工程供货，则需履行事先签订的合同，向工程方面支付一笔违约费用3C。试问厂方应制订怎样的生产策略，以使期望总费用最小？解：此例中生产周期至多为3，故取 N+1=3，即 N=2。在每一生产周期结束时厂方只关心是否制造出合格设备，取状态空间0, 1S，0 表示厂方已制造出合

10、格设备，1 则表示还未制造出合格设备。以03jj行动表示在一生产周期内生产j 台设备，则有如下行动集为00,10,1,2,3AA。 再以 r(i, j)表示状态为 i 时采取行动j 所导致的费用，则有, 00, 1,21其他jijCCjir最终费用函数用R i表示，有1,0,03iCiiR最后根据题意，若在一生产周期内制造了j 台设备，则此j 台设备均被拒收的概率为34j。于是，转移概率族采用如下转移概率矩阵形式：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 -

11、 - - - - - - - - 2008.10 6 10010P，4/34/1011P，16/916/7012P，64/2764/37013P假定12310,5,64,CCC于是有,00, 1,510,其他jijjir1,640, 0iiiR下面将递推地计算最优值函数并确定相应的最优策略。首先，考虑状态0。由于00,A且3000VR，故SjjVjprV3*2*0,00,00000, 000, 03*3*VVpr类 似 可 求 得1000VV， 于 是 显 然 有00*1*0ff00*2f。其次，考虑状态1。作为初始值有3300,164VV。下面依次递推以求出2101 ,1 ,1VVV。由于1

12、0,1,2,3A，有1, 11, 113*12*VaparmixVAa6427643, 1,169642, 1,43641 , 1,6410, 1rrrrmix名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - 2008.10 7 522725,3620,4815,640mix故令31*2f。再由2200,152VV，可得1, 11, 112*11*VaparmixVAa64275225,1695220,435215, 1520mi

13、x9375.46故可令113f。最后，类似可求得801758.4410*V，31*0f。于 是 ， 本 题 中 三 阶 段 模 型 的 最 优 值 函 数 为0000,10 ,4 4 . 8 0 1 7 5 8VVV，最优策略为012,fff，其中00,1302iiffi。这表明厂方采取这样的策略：在每一生产周期结束时，只要还未制造出合格的设备，便在下一周期生产三台设备：若至少已制造出一台合格设备，便终止生产。此外，在第三个生产周期结束时，生产也自动停止。显然，如厂方最初有合格设备的库存，则立即交货，从而费用为0；否则，在采取上述生产策略后，可使期望总费用达最小，即44.801758。直观上不

14、难看出，因最终惩罚费用相对地要比固定的与可变的生产费用水平大很多，厂方采取上述策略是很自然的，此处可以想象，一旦费用结构改变，最优策略也相应地有所改变。用有限阶段模型的向后归纳法来求解Markov 决策规划问题虽然方法较简单，但前提是要确定该序贯决策问题将在某有限时名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 2008.10 8 段内结束。然而，很多实际情况是人们往往无法确定该系统什么时候结束，即使知道它在有限时间结束，但阶段

15、数N+1 很大，导致了较大的计算量，因而还需要考虑其他算法。 5.2 其他模型简介1、S 有限和 A 无限此时 F 是无限集（与F 有限折扣模型相同） 。对)(),(maxjjijAkVkpkir，能否找到Ak、即可否找到最优*f是上述算法的关键，而与A 的有限或无限无关。1) 在上式中如能找到最优*k，则可找到最优*f; 2) 在上式中如能找到最优*k，则可找到最优*f。2、S 和 A 都是无限集方 法 ： 用 有 限 集S 近 似 表 示S， 即1Sxpl， 而95. 0SSxpl，从而转化为S有限折扣模型。3、连续时间马尔科夫决策规划定义 5.1： 一个 连续时间的MDP 可表为由如下六

16、个元素组成的系统：,),(,),( ,TVairAaaqASiiiif其中： S状态空间，这里仍假定S有限，即,2, 1 ,0lS；A所有行动方案的集合；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 2008.10 9 )(iifaq表示瞬时转移率，),(Aaaqiiif所有转移率的集合；)()(,|totaqaiXjXpiifittt，ji),(iair（Si）为系统于时刻t 处于状态 i、而选用行动方案ia 时 的 瞬 时

17、 收 益 率 ， 即 系 统 在 时 段,ttt内 的 收 益 为)(),(totairiV目标函数T时间集，, 0T1）决策函数：ASf :（同前）记)(ifqQiff，由马氏链的构造性质，如果1）fQ是一保守的Q 矩阵2）fQ一致有界则在不记初始分布情况下，fQ唯一地决定了一个齐次马氏过程，它是向前方程和向后方程的唯一解。记由fQ决定的马氏过程的转移概率函数为),()(jitPPftf2）报酬过程：),0),(ttRf，其中)()(tffxrtRffifrtPeixtR)(|)(E03）目标函数：dtrtPefVfft0)()(4）连续时间的MDP 可表为F,)I()(1frQtVOptff5）算法：与离散时间相同。注：目前对MDP 的研究还未超出生灭过程名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -