马尔可夫决策过程

[拼音]：Ma^’erkefu juece guocheng

[外文]：Markovian decision process

研究一类可周期地或连续地进行观察的随机动态系统的最优化问题。在各个时刻根据观察到的状态，从它的允许决策（控制、行动、措施等）集合中选用一个决策而决定了系统下次的转移规律与相应的运行效果。并假设这两者都不依赖于系统过去的历史。在各个时刻选取决策的目的，是使系统运行的全过程达到某种最优运行效果，即选取控制（影响）系统发展的最优策略。

基本概念

　以简化的机器维修问题为例来说明。设机器的运行有两种状态：正常（记作1）和故障(记作2)。在任一时段，如正常运行，可得收益10元，到下一时段，机器仍保持正常运行的概率为 0.7，出现故障的概率为0.3。正常运行时，惟一可供选择的决策是继续生产（记作α¹），如出了故障，则有两种决策可供选择，一是快修（记作α²），需费用5元，且在该时段内能修复的概率为0.6；一是慢修（记作α³），需费用2.5元，在该时段能修复的概率则为0.4。状态转移如图1

和图2

所示。图中的方框表示状态，箭头表示状态转移，其上的数字表示相应的转移概率。根据各时段初观察到的状态来确定采取的决策，使得整个运行期的某种期望收益达到最大的问题，就是此例的最优化问题。

可以看出，每个时段的状态转移概率与收益依赖于选取的决策。以q(j│i，α)表示由状态i采取决策α的时段到下一时段初转移到状态j的概率；以r(i，α)表示在状态i下采取决策α时其相应时段的收益。于是，此例各值如表1所示。

从状态的允许决策集里选取决策的规则称为决策规则。这里可供选取的决策规则有二：一是在观察到状态1取α¹，观察到状态2取α²，并将此决策规则记为ƒ¹；一是观察到状态1取α¹，观察到状态2取α³，并将此决策规则记为ƒ²。它们对应的转移概率分别由表2和表3给出。机器在t＝0时所用的决策规则是从ƒ¹与ƒ²中任选一个，记为ƒ₀，则t=0到t=1的状态转移概率为q(j|i，ƒ₀(i))，i，j=1，2；在t=0到t=1的时段获得收益r(i，ƒ₀(i))，i=1，2。设t=1时，选用的决策规则记为ƒ₁，它也是ƒ¹与ƒ²中之一，则由t=1到t=2的状态转移概率为q(j｜i，ƒ₁(i))，i=1，2。如此类推，可得决策序列(ƒ₀，ƒ₁，…)，称之为策略，并记作π(它是一般策略的一种特殊形式)。当 t=0时从某一初始状态出发并使用这种策略π，则状态的演变形成一马尔可夫过程。这里在t=0到t=1时段获得的效益是确定的，其值为r(i，ƒ₀(i))，而t=1到t=2时段的收益则是随机的，它的期望值为。由于收益是从t=0开始计算的，基于经济上利率的考虑，未来时段的收益应打折扣，时段t=n的收益应乘以βⁿ(0<β<1)，β称为折扣因子，n≥1。于是长期的期望折扣总收益为

这种收益值是衡量诸维修策略优劣的一种指标，它显然是初始状态i和策略π的函数。

一般说来，一个离散时间马尔可夫决策过程（简记为MDP）必须包含下列五个组成部分。

（1）状态空间S，它是系统的全体状态所成之集合。如上例的S={1， 2}。

（2）A(i)是状态i允许的决策集，i∈S。若令，则A称为决策空间。如上例中，A(1)={α¹}，A(2)={α²，α³}，其中 A(2)就是在状态2允许采取的决策（快修与慢修）集。

（3）转移概率q(j│i，α)，式中i∈S，α∈A(i)，它表示在任一时刻t，观察到状态i，选取决策 α∈A(i)， 到时刻t+1系统转移到状态j的概率（它与时刻t 以前的历史无关）。

（4）收益（或费用）函数r(i，α)，式中 i∈S，α∈A(i)，它表示在观察到状态i而选取决策α∈A(i)的时段所获得的收益（它也与系统的历史无关）。

（5）指标函数V(π，i)，它依赖于初始状态i∈S与所选用的策略π∈П（П是全体允许策略之集），是衡量选用策略效果好坏的指标。因此，一个离散时间马尔可夫决策过程，可按上述意义定义为五元组{S，( A(i)│i∈S)，q，r，V }。每个组成部分均可采取各种不同形式。例如，S 和A(i)(i∈S)各自可以是有限集、可数无穷集、完备可分距离空间的波雷耳集或解析集等。转移概率可以是时间齐次的、非时间齐次的、半马氏的或漂移的等。收益函数和指标函数也可以有多种形式。这五个成分各取一种形式就是一种MDP模型，因此，有许多不同形式的MDP模型。

策略与指标的类别

从状态的允许决策集里选取决策的所谓决策规则，就是指，从状态空间S 到决策空间A的一个映射ƒ，对所有i∈S都有ƒ(i)∈A(i)成立。全体决策规则组成的集合，记作F。设在离散时刻t=0，1，2，…来考察系统，对每一时刻t选定一个决策规则ƒ_t∈F，于是这样选定的序列(ƒ₀，ƒ₁，ƒ₂，…)就是一个特殊策略，其特殊之处在于，每个时刻t选取决策的规则既与系统在时刻t以前的历史无关，又是由状态i所对应的一个确定的决策ƒ_t(i)∈A(i)，i∈S，因此这种策略称为决定性马氏策略，简称马氏策略。如果各个时刻选取的决策，虽然不依赖于系统的历史，却不是确定地选取，而是按某一条件概率分布在允许决策集上选取的，条件是当时观察到的状态，那么相应的策略称为随机马氏策略。一般策略是各个时刻决策的选取，既依赖于系统的历史，又要根据观察到的状态随机选取的情形。若各个时刻的决策规则都是相同(决定性)的马氏策略，则称为平稳策略。即(ƒ，ƒ，ƒ，…)，记作ƒ^∞。类似地可定义随机平稳策略。

由于平稳策略的简单性，因此它是实际应用中特别重要的一类策略。全体一般策略构成的集合，称为策略空间；其他各种特殊形式的策略的全体，就称为相应的策略类，如马氏策略的全体称为马氏策略类等。它们的习用符号如下:策略空间П，随机马氏策略类П_m，马氏策略类П，随机平稳策锣П_s，平稳策略类П。各类之间显然有下列包含关系：

给定了系统在t=0的初始状态Y₀和使用的策略π，令Y_t和墹_t分别表示系统在时刻t的状态和所选取的决策，则定义一随机序列(Y₀，墹₀，Y₁，墹₁，…)，通常称为由π产生的马尔可夫决策过程。常用的指标有三种，分别定义如下：

（1）有限阶段指标V_N为

　(1)式中N是给定的正整数；r是收益函数；E_π是使用策略π时取期望值的符号；V_N(π;i)表示t=0时从i出发，使用策略π时在N + 1阶段内的总期望收益。

（2）折扣指标V_β为

　 (2)式中β(0≤β <1)是给定的，称为折扣因子。V_β(π；i)表示 t=0从 i出发，使用策略π 时的长期折扣总期望收益。折扣指标也可用于有限阶段情形，这时求和的上限为N 。

（3）平均指标堸为

(i∈S)， (3)式中V_N(π;i)由(1)给出。堸(π;i)表示t=0从i出发，使用策略π时的长期的时间平均期望收益。

对于不同类别的指标，可以建立不同的策略最优性概念。例如，若存在π^*∈П，使得对于所有i∈S，π∈П都有(当r为费用时，则为，则称π^*关于折扣指标是最优的，简称β最优的。类似地可以定义关于有限阶段指标和平均指标的最优性。对同一指标也可以定义不同的最优性概念。研究各种模型中最优策略的存在性、最优条件以及最优策略的求解方法等，是MDP的主要内容。

扣折模型

假定S及所有 A(i) (i∈S)均为有限集。其指标由(2)式给出。可以证明，对此模型存在平稳策略是最优策略。因此，在П上寻求最优策略，只需在小得多的平稳策略类П上去寻求。以前面的机器维修问题为例来说明寻求最优平稳策略的一种算法，亦即策略迭代法。

首先，策略求值。对给定的或前一轮迭代求出的平稳策略ƒ^∞，由下列方程组求解值函数V(i)。

所得的解V(i)满足。在前述机器维修问题中，给定β =0.9与平稳策略(ƒ ²)^∞，于是方程组(4)即为

10+0.9[0.7V(1)+0.3V(2)]=V　　　(1)，

-2.5+0.9[0.4V(1)+0.6V(2)]=V　　　(2)，解方程组，得

V(1)=53.77，V(2)=36.64。

其次，策略改进。对于前一步求得的值函数求一个g∈F，使得

若达到左端最大的α不只一个，则任取其一，但是，如ƒ(i)含于其中，则取g(i)=ƒ(i)。又如在机器维修问题中，上一步已求得V(1)和V(2)，再解(5)式：当i=1时，A(1)仅含α¹，故(5)的解就是α¹；当i=2时，(5)即为

即g(1)=α¹，g(2)=α²，故g=ƒ¹。

最后，终止规则。若g呏ƒ，则ƒ^∞是所求的最优策略，而终止计算。若g扝ƒ，则以g代ƒ，再转入第二步骤，由于F仅包含有限个决策规则，因此经有限次迭代必终止于一最优平稳策略。例如机器维修问题中，F 仅包含两个元素，故(ƒ¹)^∞必为最优策略，再经第一步骤可解得

简史

MDP 是确定性动态规划与马尔可夫过程结合的产物。1953年L.S.沙普利在“随机对策”一文中曾讨论过对策的一方是无意志的情形，其实是一种 MDP模型。1957年，R.贝尔曼正式提出MDP的名称和借助于最优性原理求解最优策略的方法。1960年，R.A.霍华德在动态规划基础上对一类MDP模型提出了策略迭代法。同年，有人发现寻求最优策略问题可以化为求解相应的线性规划问题。在这项工作中，S 和A都假定为有限集，而且只在П或П_s上探讨最优策略。1962年，D.布莱克韦尔在较大的策略类П上探讨最优策略。他和Ε.Б.登金于1965年分别研究了S、A都是完备可分距离空间中的波莱尔集与S 、A都是可数无穷集且转移律是非时间齐次的MDP，推动了MDP的理论的发展。

MDP已在设备的更换和维修以及库存论、排队论、控制工程、可靠性理论、搜索论、水库调度、林渔业管理、电话网络等的最优化问题中都有应用，并正在向工程、生物、经济等领域渗透。

目前，MDP的工作日益增多，有独立发展的趋势。有关的文章，除较多地使用动态规划、马尔可夫决策过程的名称外，还有使用马尔可夫决策规划、序贯决策过程、受控马氏链等名称的。研究者注意的新问题主要有：模型更加一般化；连续时间、状态部分可观察、半马氏、适应性等模型的理论探讨；特殊模型更有效的解法；如何用易于处理的模型去逼近复杂的模型等。