CHAPTER  3

第3章

有模型数值迭代

在实际问题中，直接求解Bellman期望方程和Bellman最优方程往往有困难。其中的一大困难在于直接求解Bellman方程需要极多的计算资源。本章在假设动力系统完全已知的情况下，用迭代的数值方法来求解Bellman方程，得到价值函数与最优策略。由于有模型迭代并没有从数据里学习，所以一般不认为是一种机器学习或强化学习方法。

3.1　度量空间与压缩映射

本节介绍有模型策略迭代的理论基础：度量空间上的Banach不动点定理。度量空间和Banach不动点定理在一般的泛函分析教程中都会介绍。本节对必要的概念加以简要的复习，然后证明Bellman算子是压缩映射，可以用Banach不动点定理迭代求解Bellman方程。

3.1.1　度量空间及其完备性

度量（metric，又称距离），是定义在集合上的二元函数。对于集合，其上的度量，需要满足：

非负性：对任意的，有；

同一性：对任意的，如果，则；

对称性：对任意的，有；

三角不等式：对任意的，有。

有序对又称为度量空间（metric space）。

我们来看一个度量空间的例子。考虑有限Markov决策过程状态函数（），其所有可能的取值组成集合，定义如下：

.

可以证明，是上的一个度量。（证明：非负性、同一性、对称性是显然的。由于对于有

可得三角不等式。）所以，是一个度量空间。

对于一个度量空间，如果Cauchy序列都收敛在该空间内，则称这个度量空间是完备的（complete）。

例如，实数集就是一个著名的完备空间（事实上实数集就是由完备性定义出来的。有理数集不完备，加上无理数集就完备了），对于度量空间也是完备的。（证明：考虑其中任意Cauchy列，即对任意的正实数，存在正整数使得任意的，均有。对于，，所以是Cauchy列。由实数集的完备性，可以知道收敛于某个实数，记这个实数为。所以，对于，存在正整数，对于任意，

有。取，有，所以收敛于，而，完备性得证）。