马尔可夫决策规划4.docVIP

定理4.7 最优马氏策略总是存在的。（报酬函数r有界） [证明] 记V，则当r有界时，V为有界数集。 于是V为有界数集，所以V必有上确界（最小的上界）。 设上确界为，则对于任意的存在V，使得 存在使得。 显然是最优的。 [证毕] 注：这个定理实际上是在r-有界折扣模型上成立的，扩大了F有限折扣模型。 定理4.8 在r有界的范围内，最优平稳策略总是存在的。 [证明] 由定理4.7，存在最优马氏策略，设，记，则有 即 是最优策略。 [证毕] 作业题: 对于F有限折扣模型，总存在最优平稳策略。 注意：在上述证明中均没有提到初始状态，这意味着我们得到的决策是相对于所有初始状态而言的一致最优策略。 综合结论可得出如下事实在全体策略类上寻求最优策略，等价于在平稳策略类上寻求最优策略。因为在平稳策略类上所获得的最优策略，在全体策略类上对同一来说，它同样是最优的。考虑到状态集S为有限以及所有A(i)）均为有限的假设下，平稳策略类仅包含有限个不同的元素或仅有有限个平稳策略，这就得寻求最优策略的问题大为简化。§4.3 策略迭代法 利用定理.1(2)及定理.5的结论可得如下策略迭代法的算法步骤： 第一步，策略求值运算取一个决策规则，求解如下个线性方程组： 或 其解。 第二步，策略改进运算将第一步求得的代入（.2）式，以求得一个新的决策函数，使其各分量分别满足下述关系: (4.2) 注意若同时有几个a使（.2）左端达最大，则可任取其一作为。 第三步，终止规则若对所有的，（.2）式均成立等式，则终止计算，并有结论：为最优策略；若至少存在一个，使（.2）式成立严格不等式，则以g代替f，并转入第步，此时有结论。 下面来说明上述算法步骤的原理。对于任一个决策规则，由算法第二步所定出的g，按矩阵、向量符号书写为： 于是可得到 ……………………….(4.3) 由定理.4有 即经第二步所得的至少是与一样好的策略。现分两种情况讨论若式等号成立，则由（.2）式对任给的必有 此即 由定理.5知是最优策略。 若式严格不等号成立，即 则由定理.1(2)知有，即是比更好的策略这种策略得到改进根据算法步骤，将转入第一步，并重复上述计算，直到程序终止。其中需说明的是，由于为有限集，而每次迭代都实现严格改进，因此不会出现循环现象，即经过有限次迭代后，将无法再做改进根据前述论证，此时的必定在全体策略上是折扣最优的。 设有一工厂为市场生产某种产品。每年年初对产品的销售情况进行一次检查，其可能结果有两种：销路好（记为状态1）和销路差（记为状态2）。若销路好一年可获利6千元；若销路差一年要亏本3千元。在每个状态工厂管理人员采用的行动有两个：不登记广告（记做b）或登记广告（记做c）。若不登广告，自然无广告费；若登广告，一年要花2千元广告费。对于今年的各种状态所采取的行动，由于随机因素的干扰，转为下年初的状态概率及相应的状态花费的费用见表.1。工厂希望考虑长期折扣期望收益，取折扣因子=0.9。用策略迭代法求此MDP最优决策及其最优值函数（计算取两位小数）表.1 状态转移概率及费用表 状态 行动 转移概率 报酬（千元） 1 b 0.5 0.5 6 c 0.8 0.2 4 2 b 0.4 0.6 -3 c 0.7 0.3 -5 解由设知，状态集={1,2},行动集。该Markov决策过程的决策准则共有个，们分别是 1）任取一决策函数，（实际上是最差的折扣目标值）做策求值运算，解线性方程组 解得 2）将上述计算得到的代入式(.2)，以求解新的决策函数。注意到，故(.2)式当时，取有 故取。 由于，故(.2)式当时取有 故取。此时显然有。 3）以代替转入第一步作策略求值运算，即解下述线性方程组： 或有 求解得 4）将上述代入（.2）求解。与上同理，由于，故（.2）式当时有 故取。类似地，由于，故（.2）式当时有 故取。 注意到，这说明已无法再做改进，满足算法终止条件。故为之最优平稳策略。 相应的最优值函数为 一般来说，当状态空间S不很大时，直接利用策略迭代算法来确定最优平稳策略但当状态空间S较大时，需要解个未知量的个线性方程组，计算量较大，是比较麻烦的。§ 4.4 逐次逼近法 只简单将逐次逼近法的步骤叙述如下，详细介绍请有关文献。 第一步，取维向量或。 第二步，归纳定义向量序列{} 此中的ax是按分量分别取的，即有 …(4.5) 由于均为有限数，故一定存在。 初始向量的选取将影迭代所需要的步数。因此在采用逐次逼近法解决实际问题时，应根据已有的经验，尽量选取较优的向量作为。若无先验知识可