教学要求：第八章 马尔可夫链和马尔可夫决策过程 掌握掌握马尔可夫分析的基本原理和方法 会运用马尔可夫决策过程解决一些基本问题 了解马尔可夫决策过程的建模和求解方法 目 录p马尔可夫链 pn步转移概率 p马尔可夫链中状态的分类 p稳态概率 p马尔可夫决策规划 目 录p马尔可夫链 pn步转移概率 p马尔可夫链中状态的分类 p稳态概率 p马尔可夫决策规划 定义p离散时间随机过程 ：假设我们观测一个系统在离散时间 点上某个特性的情况，令 为此系统特性在时刻t的值。 离散时间的随机过程就是关于随机变量 之间 关系的描述。 p马尔可夫链 ：称一个离散时间随机过程为马尔可夫链， 如果对于所有的 和状态，成立称概率规则在时间上是平稳的链为平稳马尔可夫链。p转移概率 ：在马尔可夫链中，对于所有的状态i和j，以 及所有的时刻t，有 ，称 为马尔可 夫链的转移概率。对于平稳马尔可夫链，转移概率可以 用一个转移概率矩阵P表示。 例题赌徒问题 考虑一赌徒，在时刻0拥有赌金2元，在时刻 进 行赌局。在每赌博中，赢一元的概率是 ，输一元的概率 是 。赌徒的目标是赌金增加到4元，所以当赌金增加 到4元或输光时赌博结束。请描述此离散时间随机过程 ，并判断其是否为一个平 稳马尔可夫链？若是，请写出其概率转移矩阵。解答 我们定义 为赌徒在第t场赌局结束后的赌金，则可以 把 看作是离散时间的随机过程。注意到 是 已知条件，但是 和其后的 值是随机的。因为赌徒在第t+1场赌局结束时的赌金概率分布只依赖 于赌徒在第t场赌局结束时的赌金，所以此为一个马尔可夫 链。因为赌博输赢的概率并不因时间而改变，所以此又为一 个平稳马尔可夫链。其转移概率矩阵如下： 目 录p马尔可夫链 pn步转移概率 p马尔可夫链中状态的分类 p稳态概率 p马尔可夫决策规划 n步转移概率假设已知马尔可夫链的转移概率矩阵P。问：如果一 个马尔可夫链在时刻m处于状态i，那么在n个阶段后，此 马尔可夫链处于状态j的概率是多少？因为研究的是平稳马尔可夫链，所以这个概率与m无 关，可以记作：其中， 称作从状态i到状态j的n步转移概率。显然， ； ；又由转移概率矩阵，得：就是矩阵 的第i行第j列元素。推而广之，可知对于n1， 例题饮料的市场份额问题 假设目前饮料市场上只有两种饮料。假定顾客上一次 购买时选择饮料1，则下次选购饮料1的概率为90%；顾 客上一次购买时选择饮料2，则下次选购饮料2的概率为 80%。p如果顾客当前选购的是饮料2，则在此后的第二次购买时 选择饮料1的概率是多少？ p如果顾客当前选购的是饮料1，则在此后的第三次购买时 选择饮料1的概率是多少？解答1 我们可以把顾客的饮料选购过程看作一个马尔可夫链， 其中任何给定时刻的状态为顾客在最近一次购买时选择的饮 料种类。由此，顾客的饮料选购过程可表示为两个状态的马 尔可夫链，其中状态1 = 顾客最近一次选购的是饮料1，状态2 = 顾客最近一次选购的是饮料2。 定义 为顾客在将来第次购买时选择的饮料种类（当 前一次选购的饮料种类为 ），则 可被表示为具有 如下转移概率矩阵的马尔可夫链， 解答 2回答问题a）我们知道 的第2行第1列元素。所以， ，这就意味着当前购买饮料2的顾客在此 后第二次购买时选择饮料1的概率是0.34。 回答问题b） 我们知道 的第1行第1列元素。所以，初始状态未知的情况在许多情况下，我们不知道马尔可夫链在时刻0时的状 态。令 为系统在时刻0时处于状态的概率，则我们可以确 定系统在n时刻处于状态j的概率 时刻n处于状态j的概率=j is12目 录p马尔可夫链 pn步转移概率 p马尔可夫链中状态的分类 p稳态概率 p马尔可夫决策规划 定义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为吸收状态。定义2p滑过状态：如果存在一个状态j，j是从i可达的，而i不是从j 可达的，则称状态i为滑过状态。p常返状态：如果一个状态不是滑过的，则称它为常返状态。p周期性：称状态i为周期的，并有周期k1，如果所有从i出 发又返回到i的路径的长度（段数）都是k的倍数，且k是满 足这样条件的最小数。p非周期性：如果一个常返状态不是周期的，则称为非周期的 。p遍历性：如果在马尔可夫链中的所有状态都是常返的，非周 期性的，且互相相通的，则称这个马尔可夫链为遍历的。 例题对分别具有下面转移矩阵的三个马尔可夫链，判断其是否 为遍历转移矩阵P1和P3对应的马尔可夫链是遍历的，但P2对 应的马尔可夫链不是遍历的，这是因为它有两个状态闭集（ 闭集1=1，2 ，闭集2=3，4），而不同闭集中的 状态不是互相相通的。 目 录p马尔可夫链 pn步转移概率 p马尔可夫链中状态的分类 p稳态概率 p马尔可夫决策规划 稳态概率定理1： 令P为一个s-状态遍历马尔可夫链的转移概率矩 阵，则存在一个向量 ，使得称向量 为马尔可夫链的稳态概率 。确定稳态概率由定理1可知，对于足够大的n和所有的i，有 得到稳态概率 例题以上节的饮料市场份额问题为例，其转移概率矩阵为 可得稳态方程组为得到 ， 。 即经过长时间，顾客购买饮料时，选择饮料1的概率是2/3， 选 择饮料2的概率是1/3。 稳态概率的直观解释由式子 ，两边同减去 得到在稳定状态下 从状态j转移出去的概率 =（当前阶段处于状态j的概率）*（从状态j转移出去概率） =从别的状态转移进入状态j的概率 = （当前阶段以k j开始的概率）*（从状态k转移到状态j 的概率）=稳态概率在决策中的运用 在饮料市场份额问题中，假设有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万元目 录p马尔可夫链 pn步转移概率 p马尔可夫链中状态的分类 p稳态概率 p马尔可夫决策规划 马尔可夫决策规划的表示p马尔科夫决策规划(MDP)：通常用一个四元组来表示分别是状态空间、决策集合、转移概率和期望报酬。 p状态空间 ：在每个阶段开始时系统会处于某个状态，把所 有可能的状态记为集合 ，S被称为系统的状态 空间。 p决策集合 ： 表示在某阶段系统状态为i时可供选择的有限 个可行决策集合。p转移概率 ：假设在某阶段，系统处于状态 ，决策为 ，则下一阶段的状态为 的转移概率为 。p期望报酬：系统在某阶段处于状态 i，决策为 ，所获 得的期望报酬记为 。 马尔可夫决策规划的分类p根据多阶段的特征，我们将马尔可夫决策规划分为有限阶段 马尔可夫决策规划和无限阶段马尔可夫决策规划。p有限阶段马尔可夫决策规划 ：有限阶段马尔可夫决策规划 要解决 个阶段内的期望收益最大化（或期望成本最 小化）问题。 被称为阶段长度。有限阶段马尔可夫决策规 划实际上是一种随机动态规划方法。p无限阶段马尔可夫决策规划 ：当面临的问题阶段很长，并 且难以确定阶段究竟有多长时，比较简便的做法是假定阶段 长度是无限的，即 。 例题 随机需求的单商品存贮问题每个月，仓库经理都会清点某种商品的当前库存量，从 而决定是否要从供应商那里进货，进货的话要进多少。在此 过程中，他需要权衡该商品库存带来的成本，和不能满足消 费者对该商品的需求所带来的损失。他的目标就是最大化各 月所得收益和的期望值。我们设商品的需求量是一个已知概 率分布的随机变量，且积压订单是不允许的，故库存量不会 为负数 ：第t个月月初库存量，它是状态变量； ：第t个月订货量，它是决策变量；：第t个月的随机需求量，假定该需求满足一个时间齐次 的分布由状态转移方程 例题假设p每个月月初作出是否订货和订货数量的决策，并假定定货可 以及时送到；p对商品的需求贯穿整个月，但是在该月的最后一天所有订单 必须得到满足；p如果顾客对某商品的需求超过该商品的库存量（即顾客需求 得不到满足），顾客可以到别处去购买他所需的商品。因此 不会有因供货不足而造成订单积压；p收益和成本，以及需求分布不会按月改变；p产品售出量都是整数；p仓库容量为M个单位。 马尔可夫决策规划模型-1 决策阶段： ；状态空间： ；决策集合： ，令 ；转移概率：期望报酬：其中 ：当前月订购u个单位商品的成本 ；：月库存量为u个单位时库存成本； ：有限阶问题中最后一个决策阶段的剩余库存价值 ；：需求为u个单位时的收入；马尔可夫决策规划模型 -2 策略：称选取每个阶段决策的规则为一个策略。一个有限阶段的马尔可夫策略可以写成其中 是阶段t下状态为i时采用的决策。动态规划递归方程 ：:当第t阶段状态是i时，采用最优策略，从第t阶段到第T 阶段的最大总期望收益。:当第1阶段状态为i时，采用最优策略获得的T阶段最大 总期望收益。 实例计算-1对参数赋值，令 ， ， ， ， ， ，且根据上述数值，库存量不能多于3个单位，所有的成本和收 益都是线性的，这意味着每订购一个单位的商品花费为2， 每单位商品每月的库存费用为1，每单位商品售出的收益为 8。可向顾客供应的商品数量为u时的期望收益 如下所示 ： UF(u) 00 1 2 3实例计算-2 如果在第t月初库存量为s，购进a个单位新商品，结合订购 商品的花费以及库存持有成本，我们可得到期望收益。表1为期望收益表，其中表示不可行的情况。表2为状态转移概率表，它只依赖于该月可向顾客供应的商 品数量，因此对不同的s和a，只要是s+a相同的，转移概率 就是一样的。表1 表2 a 0123s00-1 -2 -5 150-3 26-1 35j 0123s+ a01000 100 20 30动态规划逆序递归算法 -1(1)令t=4，且(2)令t=3，且通过查上面的期望收益表可知，每个状态下使上式最大化的 决策都是