5.5　价值迭代实践

完整的示例在Chapter05/01_frozenlake_v_iteration.py中。此示例中的主要数据结构如下：

• 奖励表：带有复合键“源状态”+“动作”+“目标状态”的字典。该值是从立即奖励中获得的。
• 转移表：记录了各转移的次数的字典。键是复合的“状态”+“动作”，而值则是另一个字典，是所观察到的目标状态和次数的映射。例如，如果在状态0中，执行动作1十次，其中有三次导致进入状态4，七次导致进入状态5。该表中带有键（0, 1）的条目将是一个字典，内容为{4：3,5：7}。我们可以使用此表来估计转移概率。
• 价值表：将状态映射到计算出的该状态的价值的字典。

代码的总体逻辑很简单：在循环中，我们从环境中随机进行100步，填充奖励表和转移表。在这100步之后，对所有状态执行价值迭代循环，从而更新价值表。然后，运行几个完整片段，使用更新后的价值表检查改进情况。如果这些测试片段的平均奖励高于0.8，则停止训练。在测试片段中，我们还会更新奖励表和转移表以使用环境中的所有数据。

我们来看代码。首先，导入使用的包并定义常量：

然后定义Agent类，该类包括上述表以及在训练循环中用到的函数：

在类构造函数中，创建将用于数据样本的环境，获得第一个观察结果，并定义奖励表、转移表和价值表。

此函数用于从环境中收集随机经验，并更新奖励表和转移表。请注意，我们无须等片段结束就可以开始学习。只需要执行N步，并记住它们的结果。这是价值迭代法和交叉熵方法的区别之一，后者只能在完整的片段中学习。

下一个函数将根据转移表、奖励表和价值表计算从状态采取某动作的价值。我们将其用于两个目的：针对某状态选择最佳动作，并在价值迭代时计算状态的新价值。图5.8说明了其逻辑。

执行以下操作：

1）从转移表中获取给定状态和动作的转移计数器。该表中的计数器为dict形式，键为目标状态，值为历史转移次数。对所有计数器求和，以获得在某状态执行某动作的总次数。稍后将使用该值将个体计数器数值变为概率。

2）然后，对动作所到达的每个目标状态进行迭代，并使用Bellman方程计算其对总动作价值的贡献。此贡献等于立即奖励加上目标状态的折扣价值。将此总和乘以转移概率，并将结果汇总到最终动作价值。

图5.8举例说明了状态s下采取动作a时的价值的计算。想象一下，根据经历，我们已经执行了此动作很多次（c1+c2），并以s1或s2这两种状态之一结束。我们在转移表中记录了这些状态转移的次数，格式为dict {s1：c1,s2：c2}。

然后，状态和动作的近似价值Q(s, a)将等于每个状态的概率乘以状态价值。根据Bellman方程，它也等于立即奖励和折扣长期状态价值之和。

下一个函数将使用刚刚描述的函数来决定某状态可采取的最佳动作。对环境中所有可能的动作进行迭代并计算每个动作的价值。动作价值最大的获胜，并返回该动作。这个动作选择过程是确定性的，因为play_n_random_steps()函数引入了足够的探索。因此，智能体将在近似值上表现出贪婪的行为。

play_episode()函数使用select_action()来查找要采取的最佳动作，并在环境中运行一整个片段。此函数用于运行测试片段，在这里我们不想打乱用于收集随机数据的主要环境的当前状态。因此，将第二个环境用作参数。逻辑很简单，你应该很熟悉：一个片段中只需遍历一遍状态来累积奖励。

Agent类的最后一个方法是价值迭代实现，得益于前面的函数，它非常简单。所需要做的只是循环遍历环境中的所有状态，然后为每个该状态可到达的状态计算价值，从而获得状态价值的候选项。然后，用状态可执行动作的最大价值来更新当前状态的价值。

上面就是智能体全部的方法，最后一部分代码是训练循环和监控。

我们创建了用于测试的环境、Agent类实例，以及用于TensorBoard的SummaryWriter。

前面代码片段中的两行是训练循环中的关键部分。首先，执行100个随机步骤，使用新数据填充奖励表和转移表，然后对所有状态运行价值迭代。其余代码使用价值表作为策略运行测试片段，然后将数据写入TensorBoard，跟踪最佳平均奖励，并检查训练循环停止条件。

好了，我们来运行程序：

我们的解决方案是随机的，并且实验通常需要12～100次迭代才能找到解决方案，但是，在80%的情况下，它可以在1秒内找到一个好的策略来解决该环境的问题。如果你还记得使用交叉熵方法需要多少小时才能达到60%的成功率，那么你就可以理解这是一个重要的进步。这有几个原因：

首先，动作的随机结果，加上片段的持续时间（平均6～10步），使交叉熵方法很难理解片段中什么是正确的动作以及哪一步是错误的。价值迭代作用于状态（或动作）的价值个体，通过估计概率并计算期望值自然地给出了动作的概率性结果。因此，价值迭代更加容易进行，并且所需的环境数据要少得多（在RL中称为样本效率）。

第二个原因是价值迭代不需要完整的片段即可开始学习。在极端情况下，仅从一个例子就可以开始更新价值。然而，对于FrozenLake，由于奖励的结构（仅在成功到达目标状态后才得到奖励1），仍然需要至少成功完成一个片段才能从有用的价值表中进行学习，这在更复杂的环境中可能会有一定挑战性。例如，你可以尝试将现有代码转换为较大版本的FrozenLake（其名称为FrozenLake8x8-v0）。较大版本的FrozenLake可能需要150～1 000次迭代才能解决，根据TensorBoard图，大多数情况下，需要等待第一个片段成功，然后就会很快收敛。图5.9显示了在FrozenLake-4x4上训练的奖励动态，图5.10则是针对8x8版本的。

现在，是时候将刚刚讨论过的学习状态价值的代码与学习动作价值的代码进行比较了。