《强化学习：原理与Python实现 》 —3.2　有模型策略迭代

3.2　有模型策略迭代

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

策略评估（policy evaluation）：对于给定的策略，估计策略的价值，包括动作价值和状态价值；

策略改进（policy improvement）：对于给定的策略，在已知其价值函数的情况下，找到一个更优的策略；

策略迭代（policy iteration）：综合利用策略评估和策略改进，找到最优策略。

3.2.1　策略评估

本节介绍如何用迭代方法评估给定策略的价值函数。如果能求得状态价值函数，那么就能很容易地求出动作价值函数。由于状态价值函数只有个自变量，而动作价值函数有个自变量，所以存储状态价值函数比较节约空间。

用迭代的方法评估给定策略的价值函数的算法如算法3-1所示。算法3-1一开始初始化状态价值函数，并在后续的迭代中用Bellman期望方程的表达式更新一轮所有状态的状态价值函数。这样对所有状态价值函数的一次更新又称为一次扫描（sweep）。在第次扫描时，用的值来更新的值，最终得到一系列的。

算法3-1　有模型策略评估迭代算法

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

迭代次数不能超过最大迭代次数，这里是一个比较大的正整数；

如果某次迭代的所有状态价值的变化值都小于误差容忍度（），则认为迭代达到了精度，迭代可以停止。

误差容忍度和最大迭代次数可以单独使用，也可以配合使用。

值得一提的是，算法3-1没必要为每次扫描都重新分配一套空间来存储。一种优化的方法是，设置奇数次迭代的存储空间和偶数次迭代的存储空间，一开始初始化偶数次存储空间，当是奇数时，用偶数次存储空间来更新奇数次存储空间；当是偶数时，用奇数次存储空间来更新偶数次存储空间。这样，一共只需要两套存储空间就可以完成算法。

如果想进一步减少空间使用，可以考虑算法3-2。算法3-2只使用一套存储空间。每次扫描时，它都及时更新状态价值函数。这样，在更新后续的状态时，用来更新的状态价值函数有些在本次迭代中已经更新了，有些在本次迭代中还没有更新。所以，算法3-2的计算结果和算法3-1的计算结果不完全相同。不过，算法3-2在迭代次数不限的情况下也能收敛到状态价值函数。

算法3-2　有模型策略评估迭代算法（节省空间的做法）

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