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

《马尔可夫决策规划4(2)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、定理4.7最优马氏策略总是存在的。（报酬函数r有界）[证明]记V，则当r有界时，V为有界数集。于是V为有界数集，所以V必有上确界（最小的上界）。设上确界为，则对于任意的存在V，使得存在使得。显然是最优的。[证毕]注：这个定理实际上是在r-有界折扣模型上成立的，扩大了F有限折扣模型。定理4.8在r有界的范围内，最优平稳策略总是存在的。[证明]由定理4.7，存在最优马氏策略，设，记，则有即是最优策略。[证毕]作业题:对于F有限折扣模型，总存在最优平稳策略。82009.11注意：在上述证明中均没有提到初始状态，这意味着我们得到的决策是相对于所有初

2、始状态而言的一致最优策略。综合结论可得出如下事实：在全体策略类上寻求最优策略，等价于在平稳策略类上寻求最优策略。因为在平稳策略类上所获得的-最优策略，在全体策略类上对同一来说，它同样是最优的。考虑到在状态集S为有限以及所有A(i)（）均为有限的假设下，平稳策略类仅包含有限个不同的元素、或仅有有限个平稳策略，这就使得寻求最优策略的问题大为简化。§4.3策略迭代法利用定理4.1(2)及定理4.5的结论可得如下策略迭代法的算法步骤：第一步，策略求值运算任取一个决策规则，，求解如下l个线性方程组：或其解。第二步，策略改进运算将第一步求得的代入（4.

3、2）式，以求得一个新的决策函数，使其各分量分别满足下述关系:(4.2)注意：若同时有几个a使（4.2）式左端达最大，则可任取其一作为。第三步，终止规则若对所有的，（4.2）式均成立等式，则终止计算，并有结论：为-82009.11最优策略；若至少存在一个，使（4.2）式成立严格不等式，则以g代替f，并转入第1步，此时有结论。下面来说明上述算法步骤的原理。对于任一个决策规则，由算法第二步所定出的g，按矩阵、向量符号书写为：设计：于是可得到：……………………….(4.3)由定理4.4有：即经第二步所得的至少是与一样好的策略。现分两种情况讨论:1)

4、若式(4.3)等号成立，则由（4.2）式对任给的必有此即由定理4.5知是-最优策略。2)若式(4.3)严格不等号成立，即则由定理4.1(2)知有，即是比更好的策略，这种策略得到改进。根据算法步骤，将转入第一步，并重复上述计算，直到程序终止。其中需说明的是，由于F为有限集，而每次迭代都实现严格改进，因此不会出现循环现象，即经过有限次迭代后，将无法再做改进。于是根据前述论证，此时的必定在全体策略上是-折扣最优的。例4.1设有一工厂为市场生产某种产品。每年年初对产品的销售情况进行一次检查，其可能结果有两种：销路好（记为状态1）和销路差（记为状态2

5、）。若销路好，82009.11一年可获利6千元；若销路差，一年要亏本3千元。在每个状态，工厂管理人员采用的行动有两个：不登记广告（记做b）或登记广告（记做c）。若不登广告，自然无广告费；若登广告，一年要花2千元广告费。对于今年的各种状态所采取的行动，由于随机因素的干扰，转为下年初的状态概率及相应的状态花费的费用见表4.1。工厂希望考虑长期折扣期望收益，取折扣因子β=0.9。用策略迭代法求此MDP的最优决策及其最优值函数（计算取两位小数）。表4.1状态转移概率及费用表状态行动转移概率报酬（千元）1b0.50.56c0.80.242b0.40.

6、6-3c0.70.3-5[解]：由题设知，状态集S={1,2},行动集。该Markov决策过程的决策准则共有4个，它们分别是1）任取一决策函数，（实际上是最差的折扣目标值），做策略求值运算，即解线性方程组解得：2）将上述计算得到的代入式(4.2)，以求解新的决策函数。注意到，故(4.2)式当时，取有故取。82009.11由于，故(4.2)式当时，取有故取。此时显然有。3）以代替f转入第一步作策略求值运算，即解下述线性方程组：或有求解得：4）将上述代入（4.2）式求解。与上同理，由于，故（4.2）式当i=1时有故取。类似地，由于，故（4.2）

7、式当i=2时有故取。注意到，这说明已无法再做改进，满足算法终止条件。故为之最优平稳策略。相应的最优值函数为82009.11一般来说，当状态空间S不很大时，直接利用策略迭代算法来确定最优平稳策略；但当状态空间S较大时，需要解l个未知量的l个线性方程组，计算量较大，是比较麻烦的。§4.4逐次逼近法下面只简单地将逐次逼近法的步骤叙述如下，详细介绍请参考有关文献。第一步，取l维向量或。第二步，归纳地定义向量序列{}此中的max是按分量分别取的，即有…(4.5)由于A(i)均为有限数，故fn一定存在。初始向量的选取将影响迭代所需要的步数。因此在采用逐

8、次逼近法解决实际问题时，应根据已有的经验，尽量选取较优的向量作为。若无先验知识可用，通常可取V0=0或取。若取后者，则按逐次逼近法经第n次迭代得到的Vn正好是从0到n周期内获得的