定理4.7
??最优马氏策略总是存在的。（报酬函数r有界）
L?1D?{V?R????VM使得V?V?(?)}，则当r有界时，V为有界
[证明] 记数集。
V?(?)??n??(?Pf)rfn?0i?0i?n?1n
?11?1??M?????n??????????M??n?0?11?1??M?????(L?1)M?1???
设上确界为V，则对于任意的??(L?1)M???n?????n?0?(L?1)M????
于是V为有界数集，所以V必有上确界（最小的上界）。
?0存在V?V，使得V?V*??
*D*???V(?)?V。 ?存在M使得?显然V?(?*)是??最优的。 [证毕]
注：这个定理实际上是在r-有界折扣模型上成立的，扩大了F有限折扣模型。 定理4.8 在r有界的范围内，
??最优平稳策略总是存在的。
?*??{f0,f1,f2,?,fn,?}，?[证明] 由定理4.7，存在??最优马氏策略，设
记?'}，则有V?(?')?V?(??)?? ?{f1,f2,?,fn,?'?TV(?)?T[V(?)??] ? f0?f0???V(?)?T[V(?)]??Pf0?? 即 ?f0?? TfV?(??)?V?(??)??'
0??'V(f)?V(?)??? ?0 ??'V(f? ?0)是???最优策略。 [证毕]
作业题: 对于F有限折扣模型，总存在最优平稳策略。
注意：在上述证明中均没有提到初始状态，这意味着我们得到的决策是相对于所
2009.11
1
有初始状态而言的一致最优策略。
综合结论可得出如下事实：在全体策略类?上寻求最优策略，等价于在平稳策略类上寻求最优策略。因为在平稳策略类上所获得的?-最优策略，在全体策略类?上对同一?来说，它同样是最优的。考虑到在状态集S为有限以及所有A(i)（i?S）均为有限的假设下，平稳策略类仅包含有限个不同的元素、或仅有有限个平稳策略，这就使得寻求最优策略的问题大为简化。
§4.3 策略迭代法
利用定理4.1(2)及定理4.5的结论可得如下策略迭代法的算法步骤：
第一步，策略求值运算 任取一个决策规则
f?F，i?S?{1,2,3....,l}，求解如下l个线性方程组：
j?Sr(i,f(i))???p(j|i,f(i))V(j)?V(i)
或V?r(f)??P(f)V
?V(i)?V(f,i)。 其解?第二步，策略改进运算
将第一步求得的V(i)(i?S)代入（4.2）式，以求得一个新的决策函数
g?(g(1),g(2),......,g(l))，使其各分量分别满足下述关系:
max{r(i,a)???p(j|i,a)V(j)}
a?A(i)j?S?r(i,g(i))???p(j|i,g(i))V(j)j?S?r(i,f(i))???p(j|i,f(i))V(j)(i?S) (4.2)
j?S注意：若同时有几个a使（4.2）式左端达最大，则可任取其一作为g(i)(i?S)。 第三步，终止规则
若对所有的i?S，（4.2）式均成立等式，则终止计算，并有结论：
f?为?-
2009.11 2
最优策略；若至少存在一个i?S，使（4.2）式成立严格不等式，则以g代替f，并
??V(g)?V(f)。 转入第1步，此时有结论??下面来说明上述算法步骤的原理。对于任一个决策规则定出的g，按矩阵、向量符号书写为：
f?F，由算法第二步所
r(g)??P(g)V?(f?)?r(f)??P(f)V?(f?)
设计：V?(f?)?r(f)??P(f)V?(f?)
TgV?(f?)?r(g)??P(g)V?(f?)
于是可得到：
TgV?(f?)?V?(f?) ……………………….(4.3)
由定理4.4有：V?(g即经第二步所得的
?)?V?(f?)
g?至少是与f?一样好的策略。现分两种情况讨论:
1) 若式(4.3)等号成立，则由（4.2）式对任给的h?F必有
r(h)??P(h)V?(f?)?r(g)??P(g)V?(f?)?V?(f?)
??TV(f)?V(f) 此即h??由定理4.5知
f?是?-最优策略。
2) 若式(4.3)严格不等号成立，即
TgV?(f?)?V?(f?)
则由定理
????fV(g)?V(f)g4.1(2)知有?，即是比更好的策略，这种?策略得到改进。根据算法步骤，将转入第一步，并重复上述计算，直到程序终止。其
中需说明的是，由于F为有限集，而每次迭代都实现严格改进，因此不会出现循环现象，即经过有限次迭代后，将无法再做改进。于是根据前述论证，此时的全体策略?上是?-折扣最优的。
例4.1 设有一工厂为市场生产某种产品。每年年初对产品的销售情况进行一次检查，其可能结果有两种：销路好（记为状态1）和销路差（记为状态2）。若销路好，一年
2009.11
3
f?必定在
可获利6千元；若销路差，一年要亏本3千元。在每个状态，工厂管理人员采用的行动有两个：不登记广告（记做b）或登记广告（记做c）。若不登广告，自然无广告费；若登广告，一年要花2千元广告费。对于今年的各种状态所采取的行动，由于随机因素的干扰，转为下年初的状态概率及相应的状态花费的费用见表4.1。工厂希望考虑长期折扣期望收益，取折扣因子β=0.9。用策略迭代法求此MDP的最优决策及其最优值函数（计算取两位小数）。
表4.1 状态转移概率及费用表 状态i 行动 转移概率 报酬（千元） a?f(i) 1 2 b c b c p(1|i,f(i)) p(2|i,f(i)) 0.5 0.8 0.4 0.7 0.5 0.2 0.6 0.3 r(a,i) 6 4 -3 -5 [解]：由题设知，状态集S={1,2},行动集过程的决策准则共有4个，它们分别是
A(1)?A(2)?{b,c}。该Markov决策
f?(f(1),f(2))?(b,b),g?(g(1),g(2))?(b,c)h?(h(1),h(2))?(c,b),??(?(1),?(2))?(c,c)
1）任取一决策函数
?f?(f(1),f(2))?(b,b)，（实际上V0.9(f)是最差的
折扣目标值），做策略求值运算，即解线性方程组
?6?0.9[0.5V1(1)?0.5V1(2)]?V1(1)? ?3?0.9[0.4V(1)?0.6V(2)]?V(2)111???V?(V(1),V(2))?(V(f,1),V(f,2)) 解得：1110.90.9
?(15.49,5.60)
2）将上述计算得到的
V1代入式(4.2)，以求解新的决策函数
g1?(g1(1),g1(2))。注意到A(1)?{b,c}，故(4.2)式当i?1时，取??0.9有
22??max?r(1,b)???p(j|1,b)V1(j),r(1,c)???p(j|1,c)V1(j)?j?1j?1??
?max{15.49,16.16}?16.16故取g1(1)?c。
2009.11 4
由于A(2)?{b,c}，故(4.2)式当i?2时，取??0.9有
22??max?r(2,b)???p(j|2,b)V1(j),r(2,c)???p(j|2,c)V1(j)?j?1j?1??
?max{5.60,7.52}?7.52故取g1(2)3）以g1?c。此时显然有V0.9(g1?)?V0.9(f?)。
?(g1(1),g1(2))?(c,c)代替f转入第一步作策略求值运算，即解下述
线性方程组：
?r(1,c)??p(1|1,c)p(2|1,c)??V2(1)??V2(1)??r(2,c)????p(1|2,c)p(2|2,c)??V(2)???V(2)? ?????2??2??4??0.80.2??V2(1)??V2(1)?????? ?或有????50.70.3V(2)V(2)?????2??2?求解得：V2?(V2(1),V2(2))?(22.20,12.31)
4）将上述V2代入（4.2）式求解g2?(g2(1),g2(2))。与上同理，由于
A(1)?{b,c}，故（4.2）式当i=1时有
22??max?r(1,b)???p(j|1,b)V2(j),r(1,c)???p(j|1,c)V2(j)?j?1j?1??
?max{21.54,22.20}?22.20故取g2(1)?c。类似地，由于A(2)?{b,c}，故（4.2）式当i=2时有
22??max?r(2,b)???p(j|2,b)V2(j),r(2,c)???p(j|2,c)V2(j)?
j?1j?1???max{11.64,12.31}?12.31
故取g2(2)?c。
?g1?(c,c)，这说明g1?注意到g2已无法再做改进，满足算法终止条件。故
?g2?g1?为??0.9之最优平稳策略。
相应的最优值函数为
2009.11
5