2.1.3 最优策略的迭代算法

与式（2.1）和式（2.2）类似，可以观察到式（2.6）和式（2.7）也有一个递归的结构，也就是当前步的函数和下一步的函数有依赖关系。这就给我们使用动态规划的算法提供了基础。有关具体的算法步骤，这里用估计最优状态价值函数V∗（s）作为例子阐述如下。

（1）要有一个初始化的状态价值函数作为最初的估计，记为V₀（s），在最简单的情况下可以将这个函数初始化为零。

（2）在给定环境条件下做出模拟，基于上一步中给出的状态价值V_t（s）函数估算最优的动作，以及该动作能够获得的奖励，并且根据式（2.6）更新状态价值函数，得到新的状态价值函数V_t+1（s）。

（3）重复以上步骤，直到相邻两次迭代的状态价值函数的差值小于给定的标准。在状态价值函数收敛之后，可以直接采用得到的函数进行决策。可以从数学上证明（对应的每次迭代更新称之为将贝尔曼算子（即Bellman Operator）作用于状态价值函数，根据压缩映射定理可以证明这个算子存在一个不动点，即收敛的最优状态函数），这样迭代的算法被称为价值迭代，将会在后续的内容中进一步阐述。

下面用一个实际的例子来阐述计算最优价值函数的算法。我们从一个简单的4×4的网格强化学习环境开始。图2.3给出了该强化学习环境的一个实例。在这个强化学习环境中，智能体可以从任意一点出发，移动到相邻的格点（前、后、左、右）。在图中可以注意到，有两个特殊的点，其中如果智能体到达B点，会被传送到A点，并且获得+5的奖励。除此之外，在其他网格点移动的时候智能体不获得任何奖励。具体模拟的代码如代码2.1所示。在笔者的计算机上，取γ=0.9，控制两次最大的价值函数差值小于0.001为收敛标准，在第81步迭代的时候算法收敛，最后收敛的结果如图2.3右图所示。在图中可以观察到，任取一点C，状态价值函数增大的方向总是向下和向右，也就意味着最优策略的方向总是倾向于往B点的方向，从而能够在B点获得奖励。这也与我们的直觉相符，即一个合理的智能体总是倾向于获取最大的奖励。有兴趣的读者可以试着修改代码2.1，使用不同的参数和不同的奖励来观察最后收敛到的状态价值函数的值的变化。

代码2.1 简单的最优策略迭代算法代码示例。