17.2.2 价值迭代算法
贝尔曼方程是用于求解MDP的价值迭代算法的基础。如果有n个可能的状态，那么就有n个贝尔曼方程，每个状态一个方程。这 n 个方程包含了 n 个未知量——状态的效用值。所以我们希望能够同时解开这些方程得到效用值。但是存在一个问题：这些方程是非线性的，因为其中的“max（最大值）”算符不是线性算符。尽管线性方程系统可以很快地用线性代数技术求解，但是非线性方程系统则有很多问题。一个办法是用迭代法。从任意的初始效用值开始，我们算出方程右边的值，再把它代入到左边——从而根据它们的邻接状态的效用值来更新每个状态的效用值。如此重复直到达到一种均衡。令 Ui(s)为状态 s在第 i次迭代中的效用值。那么被称作贝尔曼更新的迭代步骤是如下的样子：
如果我们经常无限地应用贝尔曼更新，那么我们可以保证达到均衡（参见下一小节），在这种情况下最后的效用值一定是贝尔曼方程组的解。实际上，这也是唯一解，而对应的策略（从公式（17.4）得到的）是最优的。这个算法称为VALUE_ITERATION（价值迭代算法），如图17.4所示。
图17.4 用于计算状态效用值的价值迭代算法。终止条件来自公式（17.8）
我们可以把价值迭代法应用于图17.1（a）中的4×3世界。初始值为0，效用值演化曲线如图17.5（a）所示。注意与（4, 3）不同距离的状态是如何积累负回报的；直到到达某点，发现了一条到达（4, 3）的路径，之后效用值才开始增长。我们可以把价值迭代算法理解为在状态空间中通过局部更新的方式传播信息。
图17.5 （a）使用价值迭代，显示被选中状态的效用值演变的曲线图。（b）为了保证误差最大为ε=c⋅Rmax所需要的价值迭代次数k，对于不同的c值，k显示为折扣因子γ 的函数
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
