5.4　价值迭代法

在刚刚的简单示例中，为了计算状态和动作的价值，我们利用了环境的结构：在转移中没有循环，因此可以从最终状态开始，计算其价值，然后回到中心的状态。但是，环境中只要有一个循环就会给这个方法造成障碍。我们来考虑具有两个状态的此类环境，如图5.7所示。

我们从状态s1开始，唯一可以采取的行动会使我们进入状态s2。我们得到奖励r=1，并且从s2的唯一个动作会使我们回到s1。因此，智能体会进入无限的状态序列[s1, s2, s1, s2, s1, s2, s1, s2, …]。要处理这种无限循环，可以使用折扣因子：γ=0.9。现在的问题是，两个状态的价值分别是什么？实际上，答案并不复杂。从s1到s2的每次转移的奖励为1，反向转移的奖励为2。因此，奖励序列为[1, 2, 1, 2, 1, 1, 2, 1, 2, …]。由于在每个状态下只有一个动作，智能体没有选择余地，因此可以省略公式中的max运算（只有一种选择）。

状态的价值如下：

严格来讲，我们无法计算状态的确切价值，但由于γ=0.9，随着时间的推移，每次转移的贡献值在减小。例如，在10步以后，γ10=0.910=0.349，但是在100步以后，该折扣因子变成0.000 026 6。由于以上原因，我们在50次迭代后停止计算，也可以得到比较精确的估计值。

前面的示例有助于理解更通用的价值迭代算法。这使我们能够以数值计算已知状态转移概率和奖励值的马尔可夫决策过程（Markov Decision Process，MDP）的状态价值和动作价值。该过程（对于状态价值）包括以下步骤：

1）将所有状态的价值Vi初始化为某个值（通常为零）。

2）对MDP中的每个状态s，执行Bellman更新：

3）对许多步骤重复步骤2，或者直到更改变得很小为止。

对于动作价值（即Q），只需要对前面的过程进行较小的修改即可：

1）将每个Qs, a初始化为零。

2）对每个状态s和动作a执行以下更新：

3）重复步骤2。

这只是理论。实际中，此方法有几个明显的局限性。首先，状态空间应该是离散的并且要足够小，以便对所有状态执行多次迭代。对于FrozenLake-4x4甚至是FrozenLake-8x8（Gym中更具挑战性的版本），这都不是问题，但是对于CartPole，并不完全清楚该怎么做。我们对CartPole的观察结果是4个浮点值，它们代表系统的某些物理特征。这些值之间即使是很小的差异也会对状态价值产生影响。一个可能的解决方案是离散化观察值。例如，可以将CartPole的观察空间划分为多个箱体，并将每个箱体视为空间中的单个离散状态。然而，这将产生很多实际问题，例如应该用多大的间隔来划分箱体，以及需要多少环境数据来估计价值。我将在后续章节中（在Q-learning中使用神经网络时）解答该问题。

第二个实际局限问题是我们很少能知道动作的转移概率和奖励矩阵。记住Gym所提供给智能体的接口：观察状态、决定动作，然后才能获得下一个观察结果以及转移奖励。我们不知道（在不查看Gym的环境代码时）从状态s0采取动作a0进入状态s1的概率是多少。

我们所拥有的仅仅是智能体与环境互动的历史。然而，在Bellman更新中，既需要每个转移的奖励，也需要转移概率。因此，显然可以利用智能体的经验来估计这两个未知值。可以根据历史数据来决定奖励，我们只需要记住从s0采取动作a转移到s1所获得的奖励即可，但是要估计概率，需要为每个元组（s0, s1, a）维护一个计数器并将其标准化。

好了，现在来看价值迭代方法是怎么作用于FrozenLake的。