???V0.9(g2)?(V0.9(g1,1),V0.9(g2,2))?(22.20,12.31)
一般来说，当状态空间S不很大时，直接利用策略迭代算法来确定最优平稳策略；
但当状态空间S较大时，需要解l个未知量的l个线性方程组，计算量较大，是比较麻烦的。
§ 4.4 逐次逼近法
下面只简单地将逐次逼近法的步骤叙述如下，详细介绍请参考有关文献。 第一步，取l维向量V0r(i,a)(i?S)。 ?0或V0(i)?maxa?A(i)第二步，归纳地定义向量序列{Vn}
Vn?1?TVn?max?r(f)??P(f)Vn??r(fn)??P(fn)Vn
f?F此中的max是按分量分别取的，即有
??Vn?1(i)?max?r(i,f(i))???p(j|i,f(i))Vn(j)?f(i)?A(i)j?S?? …(4.5)
?r(i,fn(i))???p(j|i,fn(i))Vn(j)j?S由于A(i)均为有限数，故fn一定存在。
初始向量V0的选取将影响迭代所需要的步数。因此在采用逐次逼近法解决实际问题时，应根据已有的经验，尽量选取较优的向量作为V0。若无先验知识可用，通常可取V0=0或取V0(i)?maxr(i,a)(i?S)。若取后者，则按逐次逼近法经第n次迭
a?A(i)代得到的Vn正好是从0到n周期内获得的最优折扣期望总报酬。
另外，需要指出的是：一般来说，逐次逼近法并不提供一个得到最优策略的有限步迭代算法。事实上，最优值函数一般仅是逼近，而不一定能达到，但是经过n次迭代后的值向量Vn与最优值函数V?之间的误差，是可以根据已有公式得到粗略的估计的。
例4.2 利用逐次逼近法求解例4.1中的MDP问题，取?迭代值向量以及作相应的误差估计。 [解]：根据逐次逼近法的计算步骤，取V02009.11
??0.9，并计算n?57时的
?0，按（4.5）式作一次迭代运算
6
2??V1(1)?max?r(1,a)?0.9?p(j|1,a)V0(j)?a?A(1)j?1??
?max?r(1,b),r(1,c)??r(1,b)?6达到右边最大的行动是b，故取
f1?1??b。类似的，有
2??V1(2)?max?r(2,a)?0.9?p(j|2,a)V0(j)?a?A(2)j?1??
?max?r(2,b),r(2,c)??r(2,b)??3达到右边最大的行动是b，故取f1(2)然后作第二次迭代运算
?b。
2??V2(1)?max?r(1,a)?0.9?p(j|1,a)V1(j)?a?A(1)j?1???r(1,b)?0.9(0.5*6?0.5*(?3)),??max???r(1,c)?0.9(0.8*6?0.2*(?3))?
?max?6?0.9*0.5,4?0.9*4.2??max?7.35,7.78??7.78故取
f2(1)?c。类似的，有
2??V2(2)?max?r(2,a)?0.9?p(j|2,a)V1(j)?a?A(2)j?1??2??r(2,b)?0.9p(j|2,b)V(j),?1??j?1???max??2?r(2,c)?0.9p(j|2,c)V(j))??1 ??j?1????3?0.9(0.4*6?0.6*(?3)),??max???5?0.9(0.7*6?0.3*(?3))???max??2.946,?2.03???2.03故取f2(2)?c。
重复上述迭代计算，将n2009.11
?57次迭代计算结果列成表4.2。不难验证，V57还不
7
满足最优方程TV?V，即V57还不是最优值函数。因此还需要继续进行迭代。
误差的进一步估计可参见有关文献。
表4.2 逐次逼近法的迭代步骤
Vn(1) Vn(2) fn?1(1) fn?1(2) Vn(1) Vn(2) fn?1(1) fn?1(2) nn0 1 2 3 4 5 6 7 8 9 10 0 0 6 -3 7.78 -2.03 9.24 -0.65 10.54 0.65 11.71 1.82 12.76 2.87 13.70 3.81 14.55 4.66 15.32 5.42 16.01 6.12 b c c c c c c c c c b c c c c c c c c c 15 20 25 30 35 40 45 50 55 57 18.55 20.05 20.93 21.44 21.76 21.94 22.06 22.11 22.16 22.16 8.66 10.16 11.04 11.55 11.87 12.05 12.17 12.22 12.26 12.27 c c c c c c c c c c c c c c c c c c c c c c 可以看出，策略迭代法当状态空间S所包含的元素个数l不太大时，是一种有效的算法，它比逐次逼近法所需的计算量要小得多；但当l大时，由于每次迭代策略迭代法要解l个未知量的l个线性方程组，所需计算量甚多。而逐次逼近法由于迭代规则简单，很适合计算机计算，因而有它的优越性。因此采用策略迭代法与逐次迭代法的混合计算法将更有效。借助于最优函数的逐次逼近法可以在策略迭代法中选择一个比较理想的初始决策函数，具体的做法请参见有关文献。即
? 当S中的元素较少时，用策略迭代法较好
? 当S中的元素较多时，用逐次逼近法
最后如前所述，考虑使长期内每单位时间的平均期望报酬达到最大、并采用平均准则作为目标时的模型称为平均准则Markov决策规划，在此不再做介绍。
2009.11 8