ch08马尔可夫链和马尔可夫决策过程ppt课件.ppt

《ch08马尔可夫链和马尔可夫决策过程ppt课件.ppt》由会员分享，可在线阅读，更多相关《ch08马尔可夫链和马尔可夫决策过程ppt课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、教学要求：教学要求：第八章第八章 马尔可夫链和马尔可夫决策过程马尔可夫链和马尔可夫决策过程 掌握掌握掌握马尔可夫分析的基本原理和方法 会运用马尔可夫决策过程解决一些基本问题 了解了解马尔可夫决策过程的建模和求解方法 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去目目 录录p马尔可夫链马尔可夫链 pn步转移概率步转移概率 p马尔可夫链中状态的分类马尔可夫链中状态的分类 p稳态概率稳态概率 p马尔可夫决策规划马尔可夫决策规划 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去目目

2、 录录p马尔可夫链马尔可夫链 pn步转移概率步转移概率 p马尔可夫链中状态的分类马尔可夫链中状态的分类 p稳态概率稳态概率 p马尔可夫决策规划马尔可夫决策规划 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去定义定义p离散时间随机过程离散时间随机过程：假设我们观测一个系统在离散时间点上某个特性的情况，令 为此系统特性在时刻t的值。离散时间的随机过程离散时间的随机过程就是关于随机变量 之间关系的描述。p马尔可夫链马尔可夫链：称一个离散时间随机过程为马尔可夫链马尔可夫链，如果对于所有的 和状态，成立 称概率规则在时间上是平稳的链为平稳马尔

3、可夫链平稳马尔可夫链。p转移概率转移概率：在马尔可夫链中，对于所有的状态i和j，以及所有的时刻t，有 ，称 为马尔可夫链的转移概率转移概率。对于平稳马尔可夫链，转移概率可以用一个转移概率矩阵转移概率矩阵P表示。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例题例题赌徒问题赌徒问题 考虑一赌徒，在时刻0拥有赌金2元，在时刻 进行赌局。在每赌博中，赢一元的概率是 ，输一元的概率是 。赌徒的目标是赌金增加到4元，所以当赌金增加到4元或输光时赌博结束。请描述此离散时间随机过程，并判断其是否为一个平稳马尔可夫链？若是，请写出其概率转移矩阵。火

4、灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去解答解答 我们定义 为赌徒在第t场赌局结束后的赌金，则可以把 看作是离散时间的随机过程。注意到 是已知条件，但是 和其后的 值是随机的。因为赌徒在第t+1场赌局结束时的赌金概率分布只依赖于赌徒在第t场赌局结束时的赌金，所以此为一个马尔可夫链。因为赌博输赢的概率并不因时间而改变，所以此又为一个平稳马尔可夫链。其转移概率矩阵如下：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去目目 录录p马尔可夫链马尔可夫链 pn步转移概率步转移概率

5、 p马尔可夫链中状态的分类马尔可夫链中状态的分类 p稳态概率稳态概率 p马尔可夫决策规划马尔可夫决策规划 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去n步转移概率步转移概率 假设已知马尔可夫链的转移概率矩阵P。问：如果一个马尔可夫链在时刻m处于状态i，那么在n个阶段后，此马尔可夫链处于状态j的概率是多少？因为研究的是平稳马尔可夫链，所以这个概率与m无关，可以记作：其中，称作从状态i到状态j的n步转移概率步转移概率。显然，；又由转移概率矩阵，得：就是矩阵 的第i行第j列元素。推而广之，可知对于n1，火灾袭来时要迅速疏散逃生，不可蜂拥

6、而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例题例题饮料的市场份额问题饮料的市场份额问题 假设目前饮料市场上只有两种饮料。假定顾客上一次购买时选择饮料1，则下次选购饮料1的概率为90%；顾客上一次购买时选择饮料2，则下次选购饮料2的概率为80%。a)如果顾客当前选购的是饮料2，则在此后的第二次购买时选择饮料1的概率是多少？b)如果顾客当前选购的是饮料1，则在此后的第三次购买时选择饮料1的概率是多少？火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去解答解答1 我们可以把顾客的饮料选购过程看作一个马尔可夫链，

7、其中任何给定时刻的状态为顾客在最近一次购买时选择的饮料种类。由此，顾客的饮料选购过程可表示为两个状态的马尔可夫链，其中 状态1=顾客最近一次选购的是饮料1，状态2=顾客最近一次选购的是饮料2。定义 为顾客在将来第次购买时选择的饮料种类（当前一次选购的饮料种类为 ），则 可被表示为具有如下转移概率矩阵的马尔可夫链，火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去解答解答 2回答问题a）我们知道 的第2行第1列元素。所以，这就意味着当前购买饮料2的顾客在此后第二次购买时选择饮料1的概率是0.34。回答问题b）我们知道 的第1行第1列元素。

8、所以，火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去初始状态未知的情况初始状态未知的情况 在许多情况下，我们不知道马尔可夫链在时刻0时的状态。令 为系统在时刻0时处于状态的概率，则我们可以确定系统在n时刻处于状态j的概率 时刻n处于状态j的概率 =jis12火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去目目 录录p马尔可夫链马尔可夫链 pn步转移概率步转移概率 p马尔可夫链中状态的分类马尔可夫链中状态的分类 p稳态概率稳态概率 p马尔可夫决策规划马尔可夫决策规划 火灾袭来

9、时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去定义定义1p路径：路径：给定两个状态i和j。从i到j的一条路径路径，是指以为i起点，以j为终点的一系列状态转移，且每次转移都具有正的发生概率。p可达性：可达性：如果存在一条从i到j的路，则称状态j是从i状态可可达的达的。p相通性：相通性：如果状态j是从i状态可达的，且i是从j可达的，则称状态i和j是相通的相通的。p闭集：闭集：如果对于马尔可夫链中的一个状态集合S，满足任何一个S外的状态都不可能从S内的某个状态可达的，则称S为闭集闭集。p吸收状态：吸收状态：如果 ，则称状态i为吸收状态吸收状态。火

10、灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去定义定义2p滑过状态：滑过状态：如果存在一个状态j，j是从i可达的，而i不是从j可达的，则称状态i为滑过状态滑过状态。p常返状态：常返状态：如果一个状态不是滑过的，则称它为常返状态常返状态。p周期性：周期性：称状态i为周期的周期的，并有周期k1，如果所有从i出发又返回到i的路径的长度（段数）都是k的倍数，且k是满足这样条件的最小数。p非周期性：非周期性：如果一个常返状态不是周期的，则称为非周期的非周期的。p遍历性：遍历性：如果在马尔可夫链中的所有状态都是常返的，非周期性的，且互相相通的，则

11、称这个马尔可夫链为遍历的遍历的。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例题例题 对分别具有下面转移矩阵的三个马尔可夫链，判断其是否为遍历 转移矩阵P1和P3对应的马尔可夫链是遍历的，但P2对应的马尔可夫链不是遍历的，这是因为它有两个状态闭集（闭集1=1，2 ，闭集2=3，4），而不同闭集中的状态不是互相相通的。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去目目 录录p马尔可夫链马尔可夫链 pn步转移概率步转移概率 p马尔可夫链中状态的分类马尔可夫链中状态的分类 p

12、稳态概率稳态概率 p马尔可夫决策规划马尔可夫决策规划 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去稳态概率稳态概率 定理定理1：令P为一个s-状态遍历马尔可夫链的转移概率矩阵，则存在一个向量 ，使得 称向量 为马尔可夫链的稳态概率稳态概率。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去确定稳态概率确定稳态概率由定理1可知，对于足够大的n和所有的i，有 得到稳态概率得到稳态概率 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被

13、褥勇敢地冲出去例题例题以上节的饮料市场份额问题为例，其转移概率矩阵为 可得稳态方程组为得到 ，。即经过长时间，顾客购买饮料时，选择饮料1的概率是2/3，选择饮料2的概率是1/3。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去稳态概率的直观解释稳态概率的直观解释由式子 ，两边同减去得到在稳定状态下从状态j转移出去的概率=（当前阶段处于状态j的概率）*（从状态j转移出去概率）=从别的状态转移进入状态j的概率=（当前阶段以k j开始的概率）*（从状态k转移到状态j 的概率）=火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披

14、上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去稳态概率在决策中的运用稳态概率在决策中的运用 在饮料市场份额问题中，假设有10000万位饮料顾客，每位顾客每周购买一次饮料（52周=1年）；一单位饮料的成本价是1元，销售价是2元。一家广告公司保证可以将由购买饮料1转为购买饮料2的顾客比例从10%降低至5%，广告费是每年50000万元。请问饮料1的生产公司是否该雇用此广告公司？解解：现有2/3的顾客购买饮料1，所以饮料1公司现在的年利润是(2/3)*(520000)=346667万元 广告公司承诺将转移概率矩阵变为 通过解新的稳态方程，可得 ，。此时饮料1公司的年利润是:(0.8)*520000-50

15、000=366000万元 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去目目 录录p马尔可夫链马尔可夫链 pn步转移概率步转移概率 p马尔可夫链中状态的分类马尔可夫链中状态的分类 p稳态概率稳态概率 p马尔可夫决策规划马尔可夫决策规划 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去马尔可夫决策规划的表示马尔可夫决策规划的表示p马尔科夫决策规划马尔科夫决策规划(MDP)：通常用一个四元组来表示 分别是状态空间、决策集合、转移概率和期望报酬。p状态空间状态空间：在每个阶段开始

16、时系统会处于某个状态，把所有可能的状态记为集合 ，S被称为系统的状态空状态空间间。p决策集合决策集合：表示在某阶段系统状态为i时可供选择的有限个可行决策集合决策集合。p转移概率转移概率：假设在某阶段，系统处于状态 ，决策为 ，则下一阶段的状态为 的转移概率转移概率为 。p期望报酬：期望报酬：系统在某阶段处于状态 i，决策为 ，所获得的期望报酬期望报酬记为 。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去马尔可夫决策规划的分类马尔可夫决策规划的分类p根据多阶段的特征，我们将马尔可夫决策规划分为有限阶段马尔可夫决策规划和无限阶段马尔可夫

17、决策规划。p有限阶段马尔可夫决策规划有限阶段马尔可夫决策规划：有限阶段马尔可夫决策规划要解决 个阶段内的期望收益最大化（或期望成本最小化）问题。被称为阶段长度。有限阶段马尔可夫决策规划实际上是一种随机动态规划方法。p无限阶段马尔可夫决策规划无限阶段马尔可夫决策规划：当面临的问题阶段很长，并且难以确定阶段究竟有多长时，比较简便的做法是假定阶段长度是无限的，即 。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例题例题 随机需求的单商品存贮问题随机需求的单商品存贮问题 每个月，仓库经理都会清点某种商品的当前库存量，从而决定是否要从供应商那

18、里进货，进货的话要进多少。在此过程中，他需要权衡该商品库存带来的成本，和不能满足消费者对该商品的需求所带来的损失。他的目标就是最大化各月所得收益和的期望值。我们设商品的需求量是一个已知概率分布的随机变量，且积压订单是不允许的，故库存量不会为负数 ：第t个月月初库存量，它是状态变量；：第t个月订货量，它是决策变量；：第t个月的随机需求量，假定该需求满足一个时间齐次的分布 由状态转移方程 火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例题假设例题假设p每个月月初作出是否订货和订货数量的决策，并假定定货可以及时送到；p对商品的需求贯穿整个

19、月，但是在该月的最后一天所有订单必须得到满足；p如果顾客对某商品的需求超过该商品的库存量（即顾客需求得不到满足），顾客可以到别处去购买他所需的商品。因此不会有因供货不足而造成订单积压；p收益和成本，以及需求分布不会按月改变；p产品售出量都是整数；p仓库容量为M个单位。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去马尔可夫决策规划模型马尔可夫决策规划模型-1 决策阶段决策阶段：；状态空间状态空间：；决策集合决策集合：，令 ；转移概率转移概率：期望报酬期望报酬：其中 ：当前月订购u个单位商品的成本；：月库存量为u个单位时库存成本；：有限

20、阶问题中最后一个决策阶段的剩余库存价值；：需求为u个单位时的收入；火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去马尔可夫决策规划模型马尔可夫决策规划模型-2 策略策略：称选取每个阶段决策的规则为一个策略策略。一个有限阶段的马尔可夫策略可以写成 其中 是阶段t下状态为i时采用的决策。动态规划递归方程动态规划递归方程：:当第t阶段状态是i时，采用最优策略，从第t阶段到第T阶段的最大总期望收益。:当第1阶段状态为i时，采用最优策略获得的T阶段最大总期望收益。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上

21、湿毛毯、湿被褥勇敢地冲出去实例计算实例计算-1 对参数赋值，令 ，且 根据上述数值，库存量不能多于3个单位，所有的成本和收益都是线性的，这意味着每订购一个单位的商品花费为2，每单位商品每月的库存费用为1，每单位商品售出的收益为8。可向顾客供应的商品数量为u时的期望收益 如下所示：UF(u)00123火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去实例计算实例计算-2 如果在第t月初库存量为s，购进a个单位新商品，结合订购商品的花费以及库存持有成本，我们可得到期望收益。表1为期望收益表，其中表示不可行的情况。表2为状态转移概率表，它只依

22、赖于该月可向顾客供应的商品数量，因此对不同的s和a，只要是s+a相同的，转移概率就是一样的。表1 表2a0123s00-1-2-5150-326-135j0123s+a010001002030火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去动态规划逆序递归算法动态规划逆序递归算法-1 (1)令t=4，且 (2)令t=3，且 通过查上面的期望收益表可知，每个状态下使上式最大化的决策都是 ，也就是不订购新商品，我们得到：i000150260350火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被

23、褥勇敢地冲出去动态规划逆序递归算法动态规划逆序递归算法-2ia=0a=1a=2a=3001/421/222125/445/225/402109/2100321/221/20 (3)令t=2，且 ，计算结果表示如下 (4)令t=1，且 ，计算结果表示如下ia=0a=1a=2a=30233/1666/1667/1667/1631129/1698/1699/16129/1602194/16131/16194/1603227/16227/160火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去动态规划逆序递归算法动态规划逆序递归算法-3 (5)

24、令t=1，算法终止。该算法产生最优期望总报酬函数 和最优策略 ，列表如下 i032067/161000129/162000194/163000227/16 注意：注意：该例中最优策略是唯一的。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去无限阶段马尔可夫决策规划无限阶段马尔可夫决策规划 假定决策者要对一个阶段长度无限的问题最大化期望报酬，在很多时候这种情况下的期望报酬是无穷的。在这种情况下，决策者就很难做出适当的决策。我们通常可用折现的方法解决该问题。假定下一阶段所得到的每单位报酬同在当前阶段得到的 单位报酬是等值的。这就等同于决策

25、者要最大化折现期望报酬。假定M是在所有可能的状态和决策下单个阶段所得的最大报酬，则当T无限时最大折现期望报酬按如下方式计算（以当前阶段所得报酬来衡量）阶段长度无限的马尔可夫决策规划又称为马尔可夫决策过程。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去最优平稳策略最优平稳策略 p平稳策略：平稳策略：称马尔可夫策略 为一个平稳策略平稳策略。如果每个阶段都作相同的决策。即无论状态i出现在哪个阶段，平稳策略 始终选取相同的决策。p如果某一平稳策略 对所有 ，都有 则称 是一个最优平稳策略最优平稳策略。p确定最优平稳策略的三种方法：（1）策略

26、迭代法 价值确定方程 Howard 策略迭代法（2）线性规划法（3）价值迭代法。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去机器更新问题机器更新问题 p在每周开始时，某台机器总是处于以下四种状态之一：精良（E）、好（G）、一般（A）和差（B）。处于各状态下的该机器每周创造的收益如下：精良：1000元；好：800元；一般：500元；差：100元。p在每周开始时要检测这台机器所处的状态。我们可以马上花费2000元把原机器更换为状态精良的机器。p下周开始时机器所处状态的概率 本周开始时机器的状态 精良（E）好（G）一般（A）差（B）精良

27、（E）0.70.300好（G）00.70.30一般（A）000.60.4差（B）0001火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去策略迭代法策略迭代法 p价值确定方程价值确定方程 设状态空间S=1,2,s；是一个决策函数，可以通过求解如下s个线性方程（即价值确定方程）得到：火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去Howard 策略迭代法策略迭代法Step1：（策略计算）选取一个初始稳定策略 ，用价值确定方程计算Step2：（策略改进）对所有状态，计算：Step3：如果 ，那么 就是最优策略。否则，对进行改进，使之在各状态i下所作的决策正好是使达到最大的决策；返回Step1，重复以上过程。火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去线性规划法线性规划法p最优平稳策略可以通过求解以下的线性规划问题得到min s.t.设上述线性规划的最优解为 ，是最优平稳策略，则 (1)(2)当，