找到成功政策的最简单的可能性是所有政策的组合，如第7章所述。6.然而，即使在简单的例子
10.1中，也存在很多策略，这导致组合搜索与极高的计算成本相关联。在图 10.5中，给出了每个州的可能行动数量。由此，可能的策略数量计算为给定值的乘积，如表 10.2 所示。
对于nx和ny的任意值，总有四个角节点具有两个可能的动作，2 （nx – 2 ）+ 2 （ny – 2 ）个边缘节点具有三个动作，以及（nx – 2 ）（ny – 2 ）个内部节点有四个动作。因此有
2 4 3 2 （n x
– 2 ）+ 2 （n y
– 2 ）4
（n x – 2 ）（n y
– 2 ）
图10.6 示例的两个不同策略
固定nx和ny的不同政策。因此，政策数量随着州的数量呈指数增长。如果每个州有多个可能的行动，则通常都是如此。因此，对于实际应用，该算法是无用的。甚至是启发式搜索，在Chap中描述。6，不能在这里使用。由于几乎所有动作的直接奖励为零，因此不能用作启发式评估函数。
当我们考虑（除了枚举所有策略）之外，计算成本甚至更高，必须为每个生成的策略π和每个起始状态s计算值Vπ（s）。必须切断Vπ（s）中的无穷和以用于实际计算; 然而，由于指数减少的γ我在（因素10.1 ）页上的260，这不存在问题。
–
在实施例10.1 页257的差XT + 1个XT可以用作一个的IM中介奖励的动作在，这意味着机器人的每一个移动
–
=≈
右侧的身体被奖励为1，左侧机器人身体的每次运动都会受到1的惩罚。在图10.6中，显示了两个策略。除了状态空间的底行之外，其他地方的直接奖励为零。左策略π 1是在长期更好，因为，长期的动作序列，平均每次操作进展为3 / 8 0 。375 π 1和2 / 6 0 。333为π2 。如果我们在第260 页上使用（10.1 ）得到Vπ（s），结果如下表左上角的起始状态s 0和各种γ值：
|
γ 0.9 |
0.8375 |
0.8 |
|
V π 1（S 0）2.52 |
1.156 |
0.77 |
|
V π 2（S 0）2.39 |
1.156 |
0.80 |
=≈
=
在这里我们看到政策π1在伽马 0 时优于政策π2 。当伽马 0 时，反之亦然。8.对于γ 0 。8375这两项政策同样出色。我们可以清楚地看到，更大的γ导致更大的时间范围用于评估策略。
