四、价值迭代与策略迭代

type

status

password

date

slug

summary

值迭代(Value iteration)

💡

一个可能令人困惑的问题是（4.1）中的是否是状态价值。答案是否定的。尽管最终会收敛到最优状态价值，但不能保证它满足任何策略的贝尔曼方程。例如，一般情况下，它不满足或。它仅仅是算法生成的一个中间值。此外，由于不是状态价值，所以也不是动作价值。

算法原理

💡

本质上是迭代计算贝尔曼最优方程

定理 3.3 保证了当时，和分别收敛于最优状态价值和最优策略。证明过程

矩阵形式

该算法具体迭代过程包含两个步骤。

策略更新步骤（policy update）。从数学角度来看，其目的是找到一个能够解决以下优化问题的策略：

其中，是在上一次迭代中获得的。具体来说，策略改进步骤分为以下2步

根据策略评估结果，计算动作价值：

根据动作价值，根据策略：

价值更新步骤（value update）。从数学角度来看，计算一个新的值。

其中，将在下次迭代中被使用。

Elementwise形式

上面介绍的价值迭代算法是以矩阵向量形式呈现的。为了实现这个算法，我们需要进一步研究它的 elementwise形式。虽然矩阵向量形式对于理解算法的核心思想很有用，但按elementwise形式对于解释实现细节是必要的。

首先，策略更新步骤的elementwise形式

我们在 3.3.1 节中表明，能够解决上述优化问题的最优策略是

其中。如果有多个解，我们可以任意选择其中一个（这不会影响算法的收敛性）。由于新策略选择具有最大的动作，这样的策略被称为贪心策略。

其次，价值更新步骤的elementwise形式是

将（4.2）代入上述方程可得

算法推导

计算示例

接下来，我们给出一个例子来说明价值迭代算法的逐步实现。这个例子是一个带有一个禁止区域的 2×2 网格（如图 4.2）。目标区域是。奖励设置为以及。折扣率是。

k = 0：随机选择初始值为。

Q 值计算：将代入动作价值函数中，得到如表 4.2 所示的值。

策略更新(Policy update)：通过为每个状态选择具有最大值的动作来得到：

在图 4.2（中间的子图）中，我们随机选择其中任何一个动作。很明显，这个策略不是最优的，因为它在处选择保持不动。

价值更新(Value update)：通过将每个状态的值更新为最大的值来得到：

k = 1：

值计算：将代入动作价值函数（表 4.1）中，得到表 4.3 所示的值。

策略更新(Policy update)：通过为每个状态选择具有最大值的动作来得到：

价值更新(Value update)：通过将每个状态的值更新为最大的值来得到。

值得注意的是，如图 4.2 所示的策略已经是最优的了。因此，在这个简单的例子中，我们只需要运行两次迭代就能得到一个最优策略。对于更复杂的例子，我们需要运行更多次迭代，直到的值收敛（例如，直到小于一个预先指定的阈值）。

Policy iteration

本节介绍另一种重要的算法：策略迭代。与价值迭代不同，策略迭代不是直接求解贝尔曼最优方程。然而，它与价值迭代有着密切的关系，这一点稍后会展示。此外，策略迭代的思想非常重要，因为它在强化学习算法中被广泛应用。

算法原理

矩阵形式

策略迭代也是一种迭代算法。每次迭代有两个步骤。

策略评估步骤（policy evaluation ）。通过计算相应的状态价值来评估给定的策略。也就是求解以下贝尔曼方程：

策略评估

我们在第二章中介绍了两种求解（4.3）中贝尔曼方程的方法。

解析解：

迭代算法：。其中表示的第次估计值。从任意初始猜测开始，可以确保当时，。具体细节可在第 2.7 节中找到。

策略改进步骤（policy improvement）。这一步用于改进策略。具体来说，一旦在第一步中计算出，就可以得到一个新的策略，如下所示：

具体来说，策略改进步骤分为以下2步

根据策略评估结果，计算动作价值：

根据动作价值，根据策略：

有趣的是，策略迭代是一种迭代算法，在策略评估步骤中还嵌入了另一种迭代算法（4.4）。从理论上讲，这个嵌入的迭代算法需要无限多的步骤（即）才能收敛到真实的状态价值。然而，这是不可能实现的。在实践中，当满足一定的标准时，迭代过程就会终止。例如，终止标准可以是小于预先指定的阈值，或者超过预先指定的值。如果我们不进行无限次迭代，我们只能得到一个不精确的值，这个值将在后续的策略改进步骤中使用。这会造成问题吗？答案是否定的。当我们在 4.3 节后面介绍截断策略迭代算法时，原因就会变得清晰。

Elementwise form

首先，策略评估步骤，使用迭代法计算中策略的状态估计值：

其次，策略改进步骤求解出。

其中是策略下的动作估计值。令。那么，贪婪最优策略是：

算法推导

在策略改进步骤中，为什么比更好呢？

💡

引理 4.1（策略改进）。如果，那么。这里，意味着对于所有的，都有。这个引理的证明在方框 4.1 中给出。

引理 4.1（策略改进）证明
由于和是状态价值，它们满足贝尔曼方程：
因为，即当时，最大，所以我们知道：
由此可见：
因此
当时，，并且对于任何，都是一个非负随机矩阵，且其所有行的行和都等于一。

为什么策略迭代算法最终能够找到一个最优策略？

策略迭代算法生成两个序列。第一个是策略序列：。第二个是状态价值序列：。假设是最优状态价值。那么，对于所有的，都有。由于根据引理 4.1，策略在不断改进，我们知道：

由于是单调递增的且始终以为上界，根据单调收敛定理[12]（附录 C）可知，当时，收敛到一个常数值，记为。

💡

定理 4.1（策略迭代的收敛性）。由策略迭代算法生成的状态价值序列收敛于最优状态价值。因此，策略序列收敛于一个最优策略。

定理 4.1 证明
前提条件
下面的分析表明。特别地，为了证明的收敛性，我们引入另一个由生成的序列。
这个迭代算法正是值迭代算法。我们已经知道，当给定任何初始值时，会收敛到。
归纳法证明
对于，对于任何，我们总是可以找到一个使得。
接下来我们用归纳法证明对于所有的都有。根据值迭代算法，会收敛到。
对于，假设。
对于，我们有
由于且是非负的，所以我们有，因此。
所以，我们可以通过归纳法证明对于任何都有。由于收敛于，所以也收敛于。
💡
根据值迭代法，收敛于

计算示例

考虑如图 4.3 所示的一个简单例子。有两个状态，有三种可能的动作：。这三种动作分别代表向左移动、保持不变和向右移动。奖励设置为和。折扣率是。

接下来我们逐步展示策略迭代算法的实现。当时，我们从如图 4.3(a)所示的初始策略开始。这个策略并不好，因为它没有朝着目标区域移动。接下来我们展示如何应用策略迭代算法来获得最优策略。

首先，在策略评估步骤中，我们需要求解贝尔曼方程：

迭代法计算状态价值估计值

其次，在策略改进步骤中，关键是为每个状态-动作对计算。下面的表可以用来展示这样一个过程：

将在前面的策略评估步骤中得到的代入表 4.4，得到表 4.5。

通过寻找的最大值，可以得到改进后的策略。

这个策略如图 4.3(b)所示。很明显，这个策略是最优的。

💡

上述过程表明，在这个简单的例子中，一次迭代就足以找到最优策略。对于更复杂的例子，则需要更多次的迭代。

Truncated policy iteration

接下来我们介绍一种更通用的算法，称为截断策略迭代。我们将会看到价值迭代算法和策略迭代算法是截断策略迭代算法的两种特殊情况。

比较价值迭代和策略迭代

Policy iteration：选择一个任意的初始策略。在第次迭代中，执行以下两个步骤

Policy evaluation (PE)

Policy improvement (PI)

Value iteration：选择一个任意的初始值。在第次迭代中，执行以下两个步骤。

Policy up (PU)

Value update (VU)

可以看出，这两种算法的过程非常相似。让这两种算法从相同的初始条件开始：。这两种算法的过程列在表 4.6 中。在前三个步骤中，由于，所以这两种算法生成相同的结果。在第四步中它们变得不同。在第四步中，Value iteration执行，这是一步计算，而策略迭代算法求解，这需要无限次迭代。如果我们在第四步中明确写出求解的迭代过程，一切就变得清晰了。通过令，我们有……

从上述过程中可以得到以下观察结果。

如果只运行一次迭代，那么实际上就是Value iteration中计算出的。

如果进行无限次迭代，那么实际上就是Policy iteration中计算出的。

如果进行有限次数的迭代（用表示），那么这样的算法被称为截断策略迭代。它被称为“截断”是因为从到无穷大的剩余迭代被截断了。

💡

因此，Value iteration和Policy iteration可以被看作是Truncated policy的两种极端情况：Value iteration在 = 1 时终止，Policy iteration在时终止。需要注意的是，尽管上述比较具有说明性，但它是基于这个条件的。没有这个条件，这两种算法不能直接进行比较。

Truncated policy算法

直观地说，截断策略迭代介于价值迭代和策略迭代之间。一方面，它比价值迭代算法收敛得更快，因为在策略评估步骤中它计算了不止一次迭代。另一方面，它比策略迭代算法收敛得更慢，因为它只计算有限次数的迭代。这种直觉在图 4.5 中得到了说明。以下分析也支持这种直觉。

算法流程（与策略迭代更像）

前提：对于所有的，概率模型和是已知的。策略初始化。

算法流程：搜索最优状态值和最优策略。当第次迭代时，若尚未收敛，则执行以下操作。

Policy evaluation: 初始化，对下式进行次迭代。其中进行随机初始化（因为在使用迭代法计算状态价值的时候，就是随机初始化的）

Policy improvement:：策略动作调整为最大动作价值函数

算法推导

收敛性证明

policy evaluation步骤的收敛性证明

首先，因为、所以

其次，我们假设，所以

其中不等式是由于，将代入（4.5）可得。

值得注意的是，命题 4.1 需要假设。然而，在实际中是不可用的，只有是可用的。尽管如此，命题 4.1 仍然为截断策略迭代算法的收敛性提供了启示。关于这个主题的更深入讨论可以在[2，第 6.5 节]中找到。

Policy improvement：状态价值肯定是提升的

因为policy evaluation以及Policy improvement中的状态价值（或状态价值估计值）都提升了，根据单调收敛定理，可得最终算法会收敛

Q&A

问题：value iteration算法能保证找到最优策略吗？回答：可以。这是因为 value iteration算法恰好是上一章中由收缩映射定理所提出的用于求解贝尔曼最优方程的算法。该算法的收敛性由收缩映射定理保证。

问题：value iteration算法生成的中间值是状态价值吗？回答：不是。这些值不能保证满足任何策略的贝尔曼方程。

问题：policy iteration算法包括哪些步骤？回答：policy iteration算法的每次迭代包含两个步骤：policy evauation和policy improvement。在policy evauation步骤中，该算法旨在求解贝尔曼方程以获得当前策略的状态价值。在policy improvement步骤中，该算法旨在更新策略，使得新生成的策略具有更大的状态价值。

问题：policy iteration算法中是否嵌入了另一种迭代算法？回答：是。在policy iteration算法的policy evauation步骤中，需要一种迭代算法来求解当前策略的贝尔曼方程。

问题：policy iteration算法生成的中间值是状态价值吗？回答：是。这是因为这些值是当前策略的贝尔曼方程的解。

问题：policy iteration算法能保证找到最优策略吗？回答：是。我们在本章中已经给出了其收敛性的严格证明。

问题：truncated policy iteration算法与policy iteration算法有什么关系？回答：顾名思义，truncated policy iteration算法可以通过在policy iteration算法的策略评估步骤中仅执行有限次数的迭代而得到。

问题：truncated policy iteration与value iteration有什么关系？回答：value iteration可以看作是truncated policy iteration的一种极端情况，即在策略评估步骤中只运行一次迭代。

问题：truncated policy iteration算法生成的中间值是状态价值吗？回答：不是。只有在policy evauation步骤中运行无限次迭代，我们才能获得真正的状态价值。如果我们运行有限次数的迭代，我们只能获得真实状态价值的近似值。

问题：在truncated policy iteration算法的policy evauation步骤中，我们应该运行多少次迭代？回答：一般的指导原则是运行几次迭代，但不要太多。在policy evauation步骤中使用少量迭代可以加快整体收敛速度，但运行太多次迭代并不会显著加快收敛速度。

问题：什么是基于模型的强化学习和无模型强化学习？回答：尽管本章介绍的算法可以找到最优策略，但它们通常被称为动态规划算法而不是强化学习算法，因为它们需要系统模型。强化学习算法可以分为两类：基于模型的和无模型的。这里，“基于模型”并非指需要系统模型。相反，基于模型的强化学习使用数据来估计系统模型，并在学习过程中使用这个模型。相比之下，无模型强化学习在学习过程中不涉及模型估计。关于基于模型的强化学习的更多信息可以在[13–16]中找到。