马尔可夫决策规划4(2).doc

定理4.7 最优马氏策略总是存在的。（报酬函数r有界）证明 记V，则当r有界时，V为有界数集。于是V为有界数集，所以V必有上确界（最小的上界）。设上确界为，则对于任意的存在V，使得存在使得。显然是最优的。 证毕注：这个定理实际上是在r-有界折扣模型上成立的，扩大了F有限折扣模型。定理4.8 在r有界的范围内，最优平稳策略总是存在的。证明 由定理4.7，存在最优马氏策略，设，记，则有 即 是最优策略。 证毕作业题: 对于F有限折扣模型，总存在最优平稳策略。注意：在上述证明中均没有提到初始状态，这意味着我们得到的决策是相对于所有初始状态而言的一致最优策略。综合结论可得出如下事实：在全体策略类上寻求最优策略，等价于在平稳策略类上寻求最优策略。因为在平稳策略类上所获得的-最优策略，在全体策略类上对同一来说，它同样是最优的。考虑到在状态集S为有限以及所有A(i)（）均为有限的假设下，平稳策略类仅包含有限个不同的元素、或仅有有限个平稳策略，这就使得寻求最优策略的问题大为简化。4.3 策略迭代法利用定理4.1(2)及定理4.5的结论可得如下策略迭代法的算法步骤：第一步，策略求值运算任取一个决策规则，求解如下l个线性方程组：或其解。第二步，策略改进运算将第一步求得的代入（4.2）式，以求得一个新的决策函数，使其各分量分别满足下述关系: (4.2)注意：若同时有几个a使（4.2）式左端达最大，则可任取其一作为。第三步，终止规则若对所有的，（4.2）式均成立等式，则终止计算，并有结论：为-最优策略；若至少存在一个，使（4.2）式成立严格不等式，则以g代替f，并转入第1步，此时有结论。下面来说明上述算法步骤的原理。对于任一个决策规则，由算法第二步所定出的g，按矩阵、向量符号书写为：设计：于是可得到： .(4.3)由定理4.4有：即经第二步所得的至少是与一样好的策略。现分两种情况讨论:1) 若式(4.3)等号成立，则由（4.2）式对任给的必有此即由定理4.5知是-最优策略。2) 若式(4.3)严格不等号成立，即则由定理4.1(2)知有，即是比更好的策略，这种策略得到改进。根据算法步骤，将转入第一步，并重复上述计算，直到程序终止。其中需说明的是，由于F为有限集，而每次迭代都实现严格改进，因此不会出现循环现象，即经过有限次迭代后，将无法再做改进。于是根据前述论证，此时的必定在全体策略上是-折扣最优的。例4.1 设有一工厂为市场生产某种产品。每年年初对产品的销售情况进行一次检查，其可能结果有两种：销路好（记为状态1）和销路差（记为状态2）。若销路好，一年可获利6千元；若销路差，一年要亏本3千元。在每个状态，工厂管理人员采用的行动有两个：不登记广告（记做b）或登记广告（记做c）。若不登广告，自然无广告费；若登广告，一年要花2千元广告费。对于今年的各种状态所采取的行动，由于随机因素的干扰，转为下年初的状态概率及相应的状态花费的费用见表4.1。工厂希望考虑长期折扣期望收益，取折扣因子=0.9。用策略迭代法求此MDP的最优决策及其最优值函数（计算取两位小数）。表4.1 状态转移概率及费用表状态行动转移概率报酬（千元）1b0.50.56c0.80.242b0.40.6-3c0.70.3-5解：由题设知，状态集S=1,2,行动集。该Markov决策过程的决策准则共有4个，它们分别是1）任取一决策函数，（实际上是最差的折扣目标值），做策略求值运算，即解线性方程组解得： 2）将上述计算得到的代入式(4.2)，以求解新的决策函数。注意到，故(4.2)式当时，取有故取。由于，故(4.2)式当时，取有故取。此时显然有。3）以代替f转入第一步作策略求值运算，即解下述线性方程组：或有求解得：4）将上述代入（4.2）式求解。与上同理，由于，故（4.2）式当i=1时有故取。类似地，由于，故（4.2）式当i=2时有故取。注意到，这说明已无法再做改进，满足算法终止条件。故为之最优平稳策略。相应的最优值函数为 一般来说，当状态空间S不很大时，直接利用策略迭代算法来确定最优平稳策略；但当状态空间S较大时，需要解l个未知量的l个线性方程组，计算量较大，是比较麻烦的。 4.4 逐次逼近法下面只简单地将逐次逼近法的步骤叙述如下，详细介绍请参考有关文献。第一步，取l维向量或。第二步，归纳地定义向量序列此中的max是按分量分别取的，即有 (4.5)由于A(i)均为有限数，故fn一定存在。初始向量的选取将影响迭代所需要的步数。因此在采用逐次逼近法解决实际问题时，应根据已有的经验，尽量选取较优的向量作为。若无先验知识可用，通常可取V0=0或取。若取后者，则按逐次逼近法经第n次迭代得到的Vn正好是从0到n周期内获得的最优折扣期望总报酬。另外，需要指出的是：一般来说，逐次逼近法并不提供一个得到最优策略的有限步迭代算法。事实上，最优值函数一般仅是逼近，而不一定能达到，但是经过n次迭代后的值向量与最优值函数之间的误差，是可以根据已有公式得到粗略的估计的。例4.2 利用逐次逼近法求解例4.1中的MDP问题，取，并计算时的迭代值向量以及作相应的误差估计。解：根据逐次逼近法的计算步骤，取，按（4.5）式作一次迭代运算达到右边最大的行动是b，故取。类似的，有达到右边最大的行动是b，故取。然后作第二次迭代运算故取。类似的，有故取。重复上述迭代计算，将次迭代计算结果列成表4.2。不难验证，还不满足最优方程，即还不是最优值函数。因此还需要继续进行迭代。误差的进一步估计可参见有关文献。表4.2 逐次逼近法的迭代步骤0001518.558.66cc16-3bb2020.0510.16cc27.78-2.03cc2520.9311.04cc39.24-0.65cc3021.4411.55cc410.540.65cc3521.7611.87cc511.711.82cc4021.9412.05cc612.762.87cc4522.0612.17cc713.703.81cc5022.1112.22cc814.554.66cc5522.1612.26cc915.325.42cc5722.1612.27cc1016.016.12cccc可以看出，策略迭代法当状态空间S所包含的元素个数l不太大时，是一种有效的算法，它比逐次逼近法所需的计算量要小得多；但当l大时，由于每次迭代策略迭代法要解l个未知量的l个线性方程组，所需计算量甚多。而逐次逼近法由于迭代规则简单，很适合计算机计算，因而有它的优越性。因此采用策略迭代法与逐次迭代法的混合计算法将更有效。借助于最优函数的逐次逼近法可以在策略迭代法中选择