点击查看第一章
点击查看第二章

第3章

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

3.1　度量空间与压缩映射

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

3.1.1　度量空间及其完备性

度量（metric，又称距离），是定义在集合上的二元函数。对于集合X，其上的度量，需要满足：
非负性：对任意的x',x''∈X，有d(x',x'')≥0；
同一性：对任意的x',x''∈X，如果d(x',x'')=0，则x'=x''；
对称性：对任意的x',x''∈X，有d(x',x'')=d(x'',x')；
三角不等式：对任意的x',x'',x'''∈X，有d(x',x'')≤d(x',x'')+d(x'',x''')。
有序对(X,d)又称为度量空间（metric space）。
我们来看一个度量空间的例子。考虑有限Markov决策过程状态函数v（s）（s∈S），其所有可能的取值组成集合，定义如下：

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

可得三角不等式。）所以，是一个度量空间。
对于一个度量空间，如果Cauchy序列都收敛在该空间内，则称这个度量空间是完备的（complete）。
例如，实数集R就是一个著名的完备空间（事实上实数集就是由完备性定义出来的。有理数集不完备，加上无理数集就完备了），对于度量空间也是完备的。（证明：考虑其中任意Cauchy列，即对任意的正实数，存在正整数K使得任意的k',k'>K，均有。对于，所以是Cauchy列。由实数集的完备性，可以知道收敛于某个实数，记这个实数为。所以，对于，存在正整数，对于任意，有。取，有，所以收敛于，而，完备性得证）。

3.1.2　压缩映射与Bellman算子

本节介绍压缩映射的定义，并证明Bellman期望算子和Bellman最优算子是度量空间上的压缩映射。
对于一个度量空间和其上的一个映射，如果存在某个实数，使得对于任意的
，都有

则称映射t是压缩映射（contraction mapping，或Lipschitzian mapping）。其中的实数γ被称为Lipschitz常数。
第2章中介绍了Bellman期望方程和Bellman最优方程。这两个方程都有用动作价值表示动作价值的形式。根据这个形式，我们可以为度量空间定义Bellman期望算子和Bellman最优算子。
给定策略的Bellman期望算子：

Bellman最优算子：

下面我们就来证明，这两个算子都是压缩映射。
首先来看Bellman期望算子。由的定义可知，对任意的，有

所以

考虑到是任取的，所以有

当时，就是压缩映射。
接下来看Bellman最优算子。要证明是压缩映射，需要用到下列不等式：

其中f'和f''是任意的以为自变量的函数。（证明：设，则

同理可证，于是不等式得证。）利用这个不等式，对任意的，有

进而易知，所以是压缩映射。

3.1.3　Banach不动点定理

对于度量空间上的映射，如果使得，则称x是映射t的不动点（fix point）。
例如，策略π的状态价值函数满足Bellman期望方程，是Bellman期望算子的不动点。最优状态价值满足Bellman最优方程，是Bellman最优算子的不动点。
完备度量空间上的压缩映射有非常重要的结论：Banach不动点定理。Banach不动点定理（Banach fixed-point theorem，又称压缩映射定理，compressed mapping theorem）的内容是：是非空的完备度量空间，是一个压缩映射，则映射t在x内有且仅有一个不动点。更进一步，这个不动点可以通过下列方法求出：从x内的任意一个元素x0开始，定义迭代序列，这个序列收敛，且极限为。（证明：考虑任取x0的及其确定的列，我们可以证明它是Cauchy序列。对于任意的且，用距离的三角不等式和非负性可知，

再反复利用压缩映射可知，对于任意的正整数k有，代入得：

由于，所以上述不等式右端可以任意小，得证。）
Banach不动点定理给出了求完备度量空间中压缩映射不动点的方法：从任意的起点开始，不断迭代使用压缩映射，最终就能收敛到不动点。并且在证明的过程中，还给出了收敛速度，即迭代正比于的速度收敛（其中是k迭代次数）。在3.1.1节我们已经证明了是完备的度量空间，而3.1.2节又证明了Bellman期望算子和Bellman最优算子是压缩映射，那么就可以用迭代的方法求Bellman期望算子和Bellman最优算子的不动点。由于Bellman期望算子的不动点就是策略价值，Bellman最优算子的不动点就是最优价值，所以这就意味着我们可以用迭代的方法求得策略的价值或最优价值。在后面的小节中，我们就来具体看看求解的算法。

3.2　有模型策略迭代

本节介绍在给定动力系统的情况下的策略评估、策略改进和策略迭代。策略评估、策略改进和策略迭代分别指以下操作。

• 策略评估（policy evaluation）：对于给定的策略π，估计策略的价值，包括动作价值和状态价值；
• 策略改进（policy improvement）：对于给定的策略π，在已知其价值函数的情况下，找到一个更优的策略；
• 策略迭代（policy iteration）：综合利用策略评估和策略改进，找到最优策略。

3.2.1　策略评估

本节介绍如何用迭代方法评估给定策略的价值函数。如果能求得状态价值函数，那么就能很容易地求出动作价值函数。由于状态价值函数只有个自变量，而动作价值函数有个自变量，所以存储状态价值函数比较节约空间。
用迭代的方法评估给定策略的价值函数的算法如算法3-1所示。算法3-1一开始初始化状态价值函数v0，并在后续的迭代中用Bellman期望方程的表达式更新一轮所有状态的状态价值函数。这样对所有状态价值函数的一次更新又称为一次扫描（sweep）。在第k次扫描时，用的值来更新的值，最终得到一系列的。

在实际迭代过程中，迭代不能无止境地进行下去。所以，需要设定迭代的终止条件。迭代的终止条件可以有多种形式，这里给出两种常见的形式。

• 迭代次数不能超过最大迭代次数，这里是一个比较大的正整数；
• 如果某次迭代的所有状态价值的变化值都小于误差容忍度，则认为迭代达到了精度，迭代可以停止。
  误差容忍度和最大迭代次数可以单独使用，也可以配合使用。

值得一提的是，算法3-1没必要为每次扫描都重新分配一套空间来存储。一种优化的方法是，设置奇数次迭代的存储空间和偶数次迭代的存储空间，一开始初始化偶数次存储空间，当k是奇数时，用偶数次存储空间来更新奇数次存储空间；当k是偶数时，用奇数次存储空间来更新偶数次存储空间。这样，一共只需要两套存储空间就可以完成算法。
如果想进一步减少空间使用，可以考虑算法3-2。算法3-2只使用一套存储空间。每次扫描时，它都及时更新状态价值函数。这样，在更新后续的状态时，用来更新的状态价值函数有些在本次迭代中已经更新了，有些在本次迭代中还没有更新。所以，算法3-2的计算结果和算法3-1的计算结果不完全相同。不过，算法3-2在迭代次数不限的情况下也能收敛到状态价值函数。

这里的迭代策略评估算法具有以下两大意义：一方面，这个策略评估算法将作为策略迭代算法的一部分，用于最优策略的求解；另一方面，在这个策略评估算法的基础上进行修改，可以得到迭代求解最优策略的算法。相关内容将分别在3.2.3节和3.3节中介绍。

3.2.2　策略改进

对于给定的策略π，如果得到该策略的价值函数，则可以用策略改进定理得到一个改进的策略。
策略改进定理的内容如下：对于两个确定性的策略π和π'，如果

则，即

在此基础上，如果存在状态使得（3-1）式的不等号是严格小于号，那么就存在状态使得（3-2）式中的不等号也是严格小于号。（证明：考虑到

有

严格不等号的证明类似。）
对于一个确定性策略π，如果存在着，使得，那么我们可以构造一个新的确定策略π'，它在状态做动作，而在除状态以外的状态的动作都和策略π一样。可以验证，策略π和π'满足策略改进定理的条件。这样，我们就得到了一个比策略π更好的策略π'。这样的策略更新算法可以用算法3-3来表示。

值得一提的是，在算法3-3中，旧策略π和新策略π'只在某些状态上有不同的动作值，新策略π'可以很方便地在旧策略π的基础上修改得到。所以，如果在后续不需要使用旧策略的情况下，可以不为新策略分配空间。算法3-4就是基于这种思路的策略改进算法。

3.2.3　策略迭代

策略迭代是一种综合利用策略评估和策略改进求解最优策略的迭代方法。
见图3-1和算法3-5，策略迭代从一个任意的确定性策略开始，交替进行策略评估和策略改进。这里的策略改进是严格的策略改进，即改进后的策略和改进前的策略是不同的。对于状态空间和动作空间均有限的Markov决策过程，其可能的确定性策略数是有限的。由于确定性策略总数是有限的，所以在迭代过程中得到的策略序列一定能收敛，使得到某个k，有（即对任意的均有）。由于在的情况下，，进而，满足Bellman最优方程。因此，就是最优策略。这样就证明了策略迭代能够收敛到最优策略。

策略迭代也可以通过重复利用空间来节约空间。在算法3-6中，为了节约空间，在各次迭代中用相同的空间来存储状态价值函数，用空间来存储确定性策略。

3.3　有模型价值迭代

价值迭代是一种利用迭代求解最优价值函数进而求解最优策略的方法。在3.2.1节介绍的策略评估中，迭代算法利用Bellman期望方程迭代求解给定策略的价值函数。与之相对，本节将利用Bellman最优方程迭代求解最优策略的价值函数，并进而求得最优策略。
与策略评估的情形类似，价值迭代算法有参数来控制迭代的终止条件，可以是误差容忍度或是最大迭代次数。
算法3-7给出了一个价值迭代算法。这个价值迭代算法中先初始化状态价值函数，然后用Bellman最优方程来更新状态价值函数。根据第3.1节的证明，只要迭代次数足够多，最终会收敛到最优价值函数。得到最优价值函数后，就能很轻易地给出确定性的最优策略。

与策略评估的迭代求解类似，价值迭代也可以在存储状态价值函数时重复使用空间。算法3-8给出了重复使用空间以节约空间的版本。

3.4　动态规划

3.2.1节介绍的策略评估迭代算法和3.3节介绍的价值迭代算法都应用了动态规划这一方法。本节将介绍动态规划的思想，并且指出动态规划的缺点和可能的改进方法。

3.4.1　从动态规划看迭代算法

动态规划（Dynamic Programming，DP）是一种迭代求解方法，它的核心思想是：

• 将原问题分解成多个子问题，如果知道了子问题的解，就很容易知道原问题的解；
• 分解得到多个子问题中，有许多子问题是相同的，不需要重复计算。

求解Bellman期望方程和Bellman最优方程的迭代算法就实践了动态规划的思想。在第k次迭代的过程中，计算中的每一个值，都需要用到中所有的数值。但是，考虑到求解各个元素时使用了相同的数值，所以并不需要重复计算。从这个角度看，这样的迭代算法就使用了动态规划的思想。
在求解的过程中，和都是的估计值。用一个估计值来估计另外一个估计值的做法又称为自益（bootstrap）。动态规划迭代算法就运用了自益的思想。
在实际问题中，直接使用这样的动态规划常出现困难。原因在于，许多实际问题有着非常大的状态空间（例如AlphaGo面对的围棋问题的状态数约为种），仅仅扫描一遍所有状态都是不可能的事情。在一遍全面扫描中，很可能大多数时候都在做无意义的更新：例如某个状态所依赖的状态（即那些的状态）都还没被更新过。下一节将给出一些针对这个问题的改进。

3.4.2　异步动态规划

上一节提到，扫描一遍全部状态可能会涉及许多无意义的状态，浪费过多的时间和计算资源。本节介绍的异步动态规划（asynchronous dynamic programming）可以解决部分问题。
异步动态规划的思想是，每次扫描不再完整地更新一整套状态价值函数，而是只更新部分感兴趣的值。例如，有些状态不会转移到另一些状态（例如对任意均有的状态），那么更新状态的价值函数后再更新的价值函数就没有意义。通过只做有意义的更新，可能会大大减小计算量。
在异步动态规划中，优先更新（prioritized sweeping）是一种根据Bellman误差来选择性更新状态的算法。在迭代过程中，当更新一个状态后，试图找到一个Bellman误差最大的状态并更新该状态。具体而言，当更新一个状态价值函数后，针对这个状态价值函数会影响到的状态价值函数，计算Bellman误差：

并用一个优先队列来维护各状态的Bellman误差。然后从队头中取出Bellman误差最大的状态，更新其状态价值函数。

3.5　案例：冰面滑行

冰面滑行问题（FrozenLake-v0）是扩展库Gym里内置的一个文本环境任务。该问题的背景是这样的：在一个大小为的湖面上，有些地方结冰了，有些地方没有结冰。我们可以用一个的字符矩阵来表示湖面的情况，例如：
SFFF
FHFH
FFFH
HFFG
其中字母“F”（Frozen）表示结冰的区域，字母“H”（Hole）表示未结冰的冰窟窿，字母“S”（Start）和字母“G”（Goal）分别表示移动任务的起点和目标。在这个湖面上要执行以下移动任务：要从“S”处移动到“G”处。每一次移动，可以选择“左”、“下”、“右”、“上”4个方向之一进行移动，每次移动一格。如果移动到“G”处，则回合结束，获得1个单位的奖励；如果移动到“H”处，则回合结束，没有获得奖励；如果移动到其他字母，暂不获得奖励，可以继续。由于冰面滑，所以实际移动的方向和想要移动的方向并不一定完全一致。例如，如果在某个地方想要左移，但是由于冰面滑，实际也可能下移、右移和上移。任务的目标是尽可能达到“G”处，以获得奖励。
本节将基于策略迭代算法和价值迭代算法求解冰面滑行问题。通过这个AI的开发，我们将更好地理解有模型算法的原理及其实现。

3.5.1　实验环境使用

本节我们来看如何使用扩展库Gym中的环境。
首先，用下列语句引入环境对象：
import gym
env = gym.make('FrozenLake-v0')
env = env.unwrapped
这个环境的状态空间有16个不同的状态，表示当前处在哪一个位置；动作空间有4个不同的动作，分别表示“左”“下”“右”“上”四个方向。在扩展库Gym中，直接用int型数值来表示这些状态和动作。下列代码可以查看环境的状态空间和动作空间：
print(env.observation_space)
print(env.action_space)
这个环境的动力系统存储在env.P里。可以用下列方法查看在某个状态（如状态14）某个动作（例如右移）情况下的动力：
env.unwrapped.P14
它是一个元组列表，每个元组包括概率、下一状态、奖励值、回合结束指示这4个部分。例如，env.P14 返回元组列表 [(0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False)]，这表明：

接下来我们来看怎么使用环境。与之前在第1章介绍的内容一致，要使用env.reset() 和env.step() 来执行。执行一个回合的代码如代码清单3-1所示，其中的play_policy() 函数接收参数policy，这是一个16×4的np.array对象，表示策略π。play_policy() 函数返回一个浮点数，表示本回合的奖励。

接下来用刚刚定义的play_policy() 函数来看看随机策略的性能。下面的代码构造了随机策略random_policy，它对于任意的均有。运行下列代码，可以求得随机策略获得奖励的期望值。一般情况下的结果基本为0，这意味着随机策略几乎不可能成功到达目的地。

3.5.2　有模型策略迭代求解

本节实现策略评估、策略提升和策略迭代。
首先来看策略评估。代码清单3-3给出了策略评估的代码。代码清单3-3首先定义了函数v2q()，这个函数可以根据状态价值函数计算含有某个状态的动作价值函数。利用这个函数，evaluate_policy() 函数迭代计算了给定策略policy的状态价值。这个函数使用theta作为精度控制的参数。代码清单3-4测试了evaluate_policy() 函数。它首先求得了随机策略的状态价值函数，然后用函数v2q() 求得动作价值函数。

接下来看看策略改进。代码清单3-5的improve_policy() 函数实现了策略改进算法。输入的策略是policy，改进后的策略直接覆盖原有的policy。该函数返回一个bool类型的值，表示输入的策略是不是最优策略。代码清单3-6测试了improve_policy() 函数，它对随机策略进行改进，得到了一个确定性策略。

实现了策略评估和策略改进后，我们就可以实现策略迭代。代码清单3-7的iterate_policy() 函数实现了策略迭代算法。代码清单3-8对iterate_policy() 进行测试。针对冰面滑行问题，该代码求得了最优策略，并进行了测试。

3.5.3　有模型价值迭代求解

现在我们用价值迭代算法求解冰面滑行问题的最优策略。代码清单3-9的iterate_value()函数实现了价值迭代算法。这个函数使用参数tolerant来控制价值迭代的精度。代码清单3-10在冰面滑行问题上测试了iterate_value()函数。

策略迭代和价值迭代得到的最优价值函数和最优策略应该是一致的。最优状态价值函数为：

最优策略为：

3.6　本章小结

本章对动力已知的Markov决策过程进行迭代的策略评估和最优策略求解。严格意义上说，这些迭代算法都是求解Bellman方程的数值算法，而不是从数据中进行学习的机器学习算法。从下一章开始，我们将利用经验进行学习，进入机器学习的部分。
本章要点
策略评估是求解给定策略的价值。利用Banach不动点定理，可以用迭代的方法求解Bellman期望方程，得到价值估计。
对于给定的价值函数，可以进行策略改进。策略改进的一种方法是为每个状态选择动作。
策略迭代交替使用策略评估算法和策略改进算法求解给定环境的最优策略。
利用Banach不动点定理，可以用迭代的方法求解Bellman最优方程，得到最优价值估计。这就是价值迭代算法。可以用迭代得到的最优价值估计计算得到最优策略估计。
基于迭代的策略评估和最优价值估计都用到了动态规划方法和自益的思想。
传统动态规划的一次扫描需要对所有状态进行全面更新，这样会有不必要的计算。异步动态规划算法部分避免了这个缺陷。