ch08马尔可夫链和马尔可夫决策过程

教学要求：第八章马尔可夫链和马尔可夫决策过程掌握掌握马尔可夫分析的基本原理和方法会运用马尔可夫决策过程解决一些基本问题了解马尔可夫决策过程的建模和求解方法目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划定义离散时间随机过程：假设我们观测一个系统在离散时间点上某个特性的情况，令为此系统特性在时刻t的值。离散时间的随机过程就是关于随机变量之间关系的描述。马尔可夫链：称一个离散时间随机过程为马尔可夫链，如果对于所有的和状态，成立称概率规则在时间上是平稳的链为平稳马尔可夫链。),,,,(00111111iXiXiXiXiXPtttttt)(11ttttiXiXP转移概率：在马尔可夫链中，对于所有的状态i和j，以及所有的时刻t，有，称为马尔可夫链的转移概率。对于平稳马尔可夫链，转移概率可以用一个转移概率矩阵P表示。ijttpiXjXP)(1tXXX,,,10tXijp,2,1,0t例题赌徒问题考虑一赌徒，在时刻0拥有赌金2元，在时刻进行赌局。在每赌博中，赢一元的概率是，输一元的概率是。赌徒的目标是赌金增加到4元，所以当赌金增加到4元或输光时赌博结束。请描述此离散时间随机过程，并判断其是否为一个平稳马尔可夫链？若是，请写出其概率转移矩阵。,2,1pp1解答我们定义为赌徒在第t场赌局结束后的赌金，则可以把看作是离散时间的随机过程。注意到是已知条件，但是和其后的值是随机的。因为赌徒在第t+1场赌局结束时的赌金概率分布只依赖于赌徒在第t场赌局结束时的赌金，所以此为一个马尔可夫链。因为赌博输赢的概率并不因时间而改变，所以此又为一个平稳马尔可夫链。其转移概率矩阵如下：t10,,,XXX20X1XtXtX10000010000100001000014$3$2$1$0$4$3$2$1$0$ppppppP状态目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划n步转移概率假设已知马尔可夫链的转移概率矩阵P。问：如果一个马尔可夫链在时刻m处于状态i，那么在n个阶段后，此马尔可夫链处于状态j的概率是多少？因为研究的是平稳马尔可夫链，所以这个概率与m无关，可以记作：其中，称作从状态i到状态j的n步转移概率。显然，；；又由转移概率矩阵，得：就是矩阵的第i行第j列元素。推而广之，可知对于n1，)()()(0nPiXjXPiXjXPijnmnm)(nPijijijpP)1(skkjikijppP1)2()2(ijP2P列元素行第的第jiPnPnij)(例题饮料的市场份额问题假设目前饮料市场上只有两种饮料。假定顾客上一次购买时选择饮料1，则下次选购饮料1的概率为90%；顾客上一次购买时选择饮料2，则下次选购饮料2的概率为80%。a)如果顾客当前选购的是饮料2，则在此后的第二次购买时选择饮料1的概率是多少？b)如果顾客当前选购的是饮料1，则在此后的第三次购买时选择饮料1的概率是多少？解答1我们可以把顾客的饮料选购过程看作一个马尔可夫链，其中任何给定时刻的状态为顾客在最近一次购买时选择的饮料种类。由此，顾客的饮料选购过程可表示为两个状态的马尔可夫链，其中状态1=顾客最近一次选购的是饮料1，状态2=顾客最近一次选购的是饮料2。定义为顾客在将来第次购买时选择的饮料种类（当前一次选购的饮料种类为），则可被表示为具有如下转移概率矩阵的马尔可夫链，,,10XX0XtX80.020.010.090.02121饮料饮料饮料饮料P解答2回答问题a）我们知道的第2行第1列元素。所以，，这就意味着当前购买饮料2的顾客在此后第二次购买时选择饮料1的概率是0.34。回答问题b）我们知道的第1行第1列元素。所以，22102)2()21(PPXXP66.034.017.083.080.020.010.090.080.020.010.090.02P34.0)2(21P311)3(PP562.0438.0219.0781.066.034.017.083.080.020.010.090.0)(23PPP781.0)3(11P初始状态未知的情况在许多情况下，我们不知道马尔可夫链在时刻0时的状态。令为系统在时刻0时处于状态的概率，则我们可以确定系统在n时刻处于状态j的概率时刻n处于状态j的概率==iqjis121q2qiqsq)(1nPj)(2nPj)(nPij)(nPsjsijnii1)()(的概率步转移到状态经过从状态的概率初始状态为siijinPq1)(目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划定义1路径：给定两个状态i和j。从i到j的一条路径，是指以为i起点，以j为终点的一系列状态转移，且每次转移都具有正的发生概率。可达性：如果存在一条从i到j的路，则称状态j是从i状态可达的。相通性：如果状态j是从i状态可达的，且i是从j可达的，则称状态i和j是相通的。闭集：如果对于马尔可夫链中的一个状态集合S，满足任何一个S外的状态都不可能从S内的某个状态可达的，则称S为闭集。吸收状态：如果，则称状态i为吸收状态。1iip定义2滑过状态：如果存在一个状态j，j是从i可达的，而i不是从j可达的，则称状态i为滑过状态。常返状态：如果一个状态不是滑过的，则称它为常返状态。周期性：称状态i为周期的，并有周期k1，如果所有从i出发又返回到i的路径的长度（段数）都是k的倍数，且k是满足这样条件的最小数。非周期性：如果一个常返状态不是周期的，则称为非周期的。遍历性：如果在马尔可夫链中的所有状态都是常返的，非周期性的，且互相相通的，则称这个马尔可夫链为遍历的。例题对分别具有下面转移矩阵的三个马尔可夫链，判断其是否为遍历转移矩阵P1和P3对应的马尔可夫链是遍历的，但P2对应的马尔可夫链不是遍历的，这是因为它有两个状态闭集（闭集1={1，2}，闭集2={3，4}），而不同闭集中的状态不是互相相通的。4341212132311000P4341313221212121200000000P31323132412141300P目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划稳态概率定理1：令P为一个s-状态遍历马尔可夫链的转移概率矩阵，则存在一个向量，使得称向量为马尔可夫链的稳态概率。s21sssnnP212121lims21确定稳态概率由定理1可知，对于足够大的n和所有的i，有得到稳态概率kjskikjijijijpnPPnPnP1)()1n()()1(skkjkjp11)(s1kkinP121sns21例题以上节的饮料市场份额问题为例，其转移概率矩阵为可得稳态方程组为得到，。即经过长时间，顾客购买饮料时，选择饮料1的概率是2/3，选择饮料2的概率是1/3。80.020.010.090.0P80.020.010.090.02121121321231稳态概率的直观解释由式子，两边同减去得到在稳定状态下从状态j转移出去的概率=（当前阶段处于状态j的概率）*（从状态j转移出去概率）=从别的状态转移进入状态j的概率=（当前阶段以kj开始的概率）*（从状态k转移到状态j的概率）=skkjkjp1jjjpjkkjkjjjpp)1()1(jjjpjkkjkpk稳态概率在决策中的运用在饮料市场份额问题中，假设有10000万位饮料顾客，每位顾客每周购买一次饮料（52周=1年）；一单位饮料的成本价是1元，销售价是2元。一家广告公司保证可以将由购买饮料1转为购买饮料2的顾客比例从10%降低至5%，广告费是每年50000万元。请问饮料1的生产公司是否该雇用此广告公司？解：现有2/3的顾客购买饮料1，所以饮料1公司现在的年利润是(2/3)*(520000)=346667万元广告公司承诺将转移概率矩阵变为通过解新的稳态方程，可得，。此时饮料1公司的年利润是:(0.8)*520000-50000=366000万元80.020.005.095.01P8.012.02目录马尔可夫链n步转移概率马尔可夫链中状态的分类稳态概率马尔可夫决策规划马尔可夫决策规划的表示马尔科夫决策规划(MDP)：通常用一个四元组来表示分别是状态空间、决策集合、转移概率和期望报酬。状态空间：在每个阶段开始时系统会处于某个状态，把所有可能的状态记为集合，S被称为系统的状态空间。决策集合：表示在某阶段系统状态为i时可供选择的有限个可行决策集合。转移概率：假设在某阶段，系统处于状态，决策为，则下一阶段的状态为的转移概率为。期望报酬：系统在某阶段处于状态i，决策为，所获得的期望报酬记为。}|,,,||{iAaSiairiAaSjiapSiiASij，；；；},,2,1{sS)(iASiiAaSjapijiAaair,马尔可夫决策规划的分类根据多阶段的特征，我们将马尔可夫决策规划分为有限阶段马尔可夫决策规划和无限阶段马尔可夫决策规划。有限阶段马尔可夫决策规划：有限阶段马尔可夫决策规划要解决个阶段内的期望收益最大化（或期望成本最小化）问题。被称为阶段长度。有限阶段马尔可夫决策规划实际上是一种随机动态规划方法。无限阶段马尔可夫决策规划：当面临的问题阶段很长，并且难以确定阶段究竟有多长时，比较简便的做法是假定阶段长度是无限的，即。)(TTTT例题随机需求的单商品存贮问题每个月，仓库经理都会清点某种商品的当前库存量，从而决定是否要从供应商那里进货，进货的话要进多少。在此过程中，他需要权衡该商品库存带来的成本，和不能满足消费者对该商品的需求所带来的损失。他的目标就是最大化各月所得收益和的期望值。我们设商品的需求量是一个已知概率分布的随机变量，且积压订单是不允许的，故库存量不会为负数：第t个月月初库存量，它是状态变量；：第t个月订货量，它是决策变量；：第t个月的随机需求量，假定该需求满足一个时间齐次的分布由状态转移方程tstatD,2,1,0),(jjDpptj][}0,max{1tttttttDasDass例题假设每个月月初作出是否订货和订货数量的决策，并假定定货可以及时送到；对商品的需求贯穿整个月，但是在该月的最后一天所有订单必须得到满足；如果顾客对某商品的需求超过该商品的库存量（即顾客需求得不到满足），顾客可以到别处去购买他所需的商品。因此不会有因供货不足而造成订单积压；收益和成本，以及需求分布不会按月改变；产品售出量都是整数；仓库容量为M个单位。马尔可夫决策规划模型-1决策阶段：；状态空间：；决策集合：，令；转移概率：期望报酬：其中：当前月订购u个单位商品的成本；：月库存量为u个单位时库存成本；：有限阶问题中最后一个决策阶段的剩余库存价值；：需求为u个单位时的收入；Tt,,2,1},,2,1,0{sSSiisiA},,,2,1,0{)(SiiAA)(0,,0,,0),(jaiMqjaiMpaijMaijpaijait1,,2,1),()()(),(TtaihaOaiFairtTtigirT),()()(uO)(uh)(ug)(ufuujjqufpjf