引言
强化学习 是机器学习中的一个领域，引入了一个署理（agent）的概念，这个署理必须在复杂环境中学习最优策略。署理通过其举动从环境中得到嘉奖，从而学习如何办法。强化学习是一个非常复杂的主题，与其他机器学习领域有很大不同。因此，它应该只在其他方法无法解决问题时才被利用。
强化学习的奇妙之处在于，雷同的算法可以用来让署理适应完全不同的、未知的和复杂的条件。
注意：为了完全明白本文中的观点，强烈建议你先阅读本文系列的 第一部门，其中介绍了强化学习的主要概念。
关于本文
在 第一部门，我们介绍了强化学习的主要概念：框架、策略和价值函数。贝尔曼方程（Bellman Equation）通过递归建立价值函数之间的关系，是当代算法的焦点。我们将在本文中通过学习如何利用它来找到最优策略，来明白它的强大之处。
本文基于 Richard S. Sutton 和 Andrew G. Barto 合著的闻名书籍 《强化学习》 的第四章。我非常感谢作者为出书这本书所付出的努力。
解决贝尔曼方程
假设我们完全了解环境的动态特性，该环境包罗 (|S|) 个状态，办法转移概率由策略 (\pi) 给出。在这种环境下，我们可以为该环境的 V 函数求解贝尔曼方程，这实际上是一个包罗 (|S|) 个变量的线性方程组（假如是 Q 函数，则会有 (|S| \times |A|) 个方程）。
这些方程的解对应于每个状态的 v 值（或每对 ((状态, 办法)) 的 q 值）。
示例
让我们来看一个简单的环境示例，其中包罗 5 个状态，T 是终止状态。蓝色数字表现转移概率，赤色数字表现署理得到的嘉奖。我们假设署理在状态 A 中选择的雷同办法（用程度箭头表现，概率 (p = 0.6)）会导致 C 或 D 的不同概率（分别为 (p = 0.8) 和 (p = 0.2)）。
示例的转移图。蓝色数字表现状态之间的转移概率，赤色数字表现相应的嘉奖。
由于环境包罗 (|S| = 5) 个状态，为了找到所有 v 值，我们需要解一个包罗 5 个贝尔曼方程的方程组：
V 函数的贝尔曼方程组。
由于 T 是终止状态，其 v 值始终为 0，因此实际上我们只需要解 4 个方程。
方程组的解。
假如要解类似的 Q 函数方程组，难度会更大，由于我们需要为每对 ((状态, 办法)) 解一个方程。
策略评估
直接解线性方程组（如上例所示）是一种可能的方法，用于得到真实的 v 值。然而，由于算法复杂度为 (O(n^3))，其中 (n = |S|)，这种方法并不高效，尤其是当状态数 (|S|) 很大时。相反，我们可以应用 迭代策略评估算法：
- 随机初始化所有环境状态的 v 值（终止状态的 v 值必须为 0）。
- 利用贝尔曼方程迭代更新所有非终止状态。
- 重复步调 2，直到前后 v 值的差异富足小（≤ (\theta)）。
策略评估伪代码。来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
假如状态数 (|S|) 是有限的，那么可以数学证明：在给定策略 (\pi) 下，通过策略评估算法得到的迭代估计值终极会收敛到真实的 v 值！
对某个状态 (s \in S) 的 v 值进行单次更新称为 盼望更新。之所以如许命名，是由于更新过程考虑了 (s) 的所有可能后续状态的嘉奖，而不仅仅是一个。
对所有状态进行一次完备的更新迭代称为一个 扫描。
注意：算法并未规定在每次迭代中更新变量的顺序，但顺序可能会对收敛速度产生很大影响。
更新变体
策略评估算法中的更新方程可以用两种方式实现：
- 利用 两个数组：从两个独立的数组中依次计算新值，旧值保持稳定。
- 利用 一个数组：立即覆盖计算出的值。因此，在同一次迭代中，后续更新会利用已覆盖的新值。
在实践中，覆盖 v 值是一种更优的更新方式，由于新信息一旦可用就会被用于其他更新，与利用两个数组的方法相比，v 值的收敛速度会更快。
算法并未规定在每次迭代中更新变量的顺序，但顺序可能会对收敛速度产生很大影响。
示例
形貌
为了更好地明白策略评估算法在实际中的工作方式，让我们来看一个来自 Sutton 和 Barto 的书 的 4.1 节的例子。我们有一个 (4 \times 4) 的网格环境，署理在每一步中以相等的概率（(p = 0.25)）向四个方向（上、右、下、左）之一移动一步。
署理从随机的迷宫单元格开始，并在每一步中向四个方向之一移动，每步的嘉奖 (R = -1)。A4 和 D1 是终止状态。图片由作者改编，来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
假如署理位于迷宫的边缘，并选择向迷宫周围的墙壁方向移动，则其位置保持稳定。例如，假如署理位于 D3 并选择向右移动，则它在下一步中仍保持在 D3。
除了位于 A4 和 D1 的两个终止状态外，每步移动到任何单元格的嘉奖都是 (R = -1)，而终止状态的嘉奖为 (R = 0)。终极目标是计算给定的等概率策略下的 V 函数。
算法
让我们将所有 V 值初始化为 0，然后运行几次策略评估算法的迭代：
不同策略评估迭代中的 V 函数。图片由作者改编，来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
在某个时间，连续迭代之间的 v 值将不再发生变化，这意味着算法已经收敛到真实的 v 值。对于迷宫，给定等概率策略下的 V 函数如末了一个图的右侧所示。
表明
假设署理根据随机策略从单元格 C2 开始，其预期嘉奖为 -18。根据 V 函数的界说，-18 是署理在剧集结束时收到的总累积嘉奖。由于每一步移动都会增加 -1 的嘉奖，我们可以将 v 值 18 表明为 署理到达终止状态所需的预期步数。
策略改进
乍一看，可能会以为有些意外，但 V 函数和 Q 函数可以用来找到最优策略。为了明白这一点，让我们回到迷宫示例，我们已经计算了随机策略下的 V 函数。
例如，我们来看单元格 B3。根据我们的随机策略，署理可以从该状态以相等的概率向 4 个方向移动。它可能得到的预期嘉奖分别是 -14、-20、-20 和 -14。假设我们有机会修改该状态的策略。为了最大化预期嘉奖，难道不是应该总是向 A3 或 B4 移动吗？（在我们的环境下，这两个单元格的预期嘉奖最大，为 -14）。
从 B3 单元格出发的最优办法将导致 A3 或 B4，那边的预期嘉奖到达最大值。
这个想法很有道理，由于位于 A3 或 B4 会让署理有机会在一步之内完成迷宫。因此，我们可以将这条转移规则纳入 B3 的新策略中。然而，总是通过这种方式最大化预期嘉奖是否总是最优的呢？
确实，贪心地转移到预期嘉奖最大的动作所对应的状态，会导致更好的策略。
让我们继承这个例子，对所有迷宫状态执行雷同的步伐：
收敛的 V 函数及其对应的贪心策略。图片由作者改编，来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
因此，我们得到了一个比旧策略更好的新策略。趁便说一下，我们的发现可以推广到其他问题，通过 策略改进定理，它在强化学习中起着至关重要的作用。
策略改进定理
表述
来自 Sutton 和 Barto 的书 的表述简洁地形貌了这个定理：
假设 (\pi) 和 (\pi’) 是恣意一对确定性策略，使得对于所有 (s \in S)，
q π ( s , π ′ ( s ) ) ≥ v π ( s ) q_{\pi}(s, \pi'(s)) \geq v_{\pi}(s) qπ(s,π′(s))≥vπ(s)
来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
那么策略 (\pi’) 必须至少和 (\pi) 一样好，或者更好。也就是说，它必须从所有状态 (s \in S) 得到更大或相等的预期回报：
v π ′ ( s ) ≥ v π ( s ) v_{\pi'}(s) \geq v_{\pi}(s) vπ′(s)≥vπ(s)
来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
逻辑
为了明白定理的表述，假设我们有一个环境，并且我们已经计算了该环境下的 V 函数和 Q 函数，这些函数是根据策略 (\pi) 评估的。对于这个环境，我们将创建另一个策略 (\pi’)。这个策略将与 (\pi) 完全雷同，唯一的区别是对于每个状态，它会选择导致雷同或更大回报的动作。那么定理包管，策略 (\pi’) 下的 V 函数将比策略 (\pi) 下的 V 函数更好。
通过策略改进定理，我们总是可以通过 贪心地 选择当前策略下每个状态的最大回报动作来推导出更好的策略。
策略迭代
给定恣意初始策略 (\pi)，我们可以计算它的 V 函数。这个 V 函数可以用来改进策略到 (\pi’)。有了这个策略 (\pi’)，我们可以计算它的 V’ 函数。这个过程可以重复多次，以迭代地产生更好的策略和价值函数。
在有限状态的环境下，这个算法（称为 策略迭代）终极会收敛到最优策略和最优价值函数。
策略评估（E）和策略改进（I）之间的迭代瓜代。图片由作者改编，来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
假如我们对迷宫示例应用策略迭代算法，那么最优的 V 函数和策略将如下所示：
迷宫示例的最优 V 函数和策略。图片由作者改编，来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
在这个设置中，通过得到最优的 V 函数，我们可以轻松估计根据最优策略到达终止状态所需的步数。
这个例子风趣的地方在于，我们只需要两次策略迭代就可以从头开始得到这些值（我们可以注意到，图片中的最优策略与我们在更新到相应 V 函数之前完全雷同）。在某些环境下，策略迭代算法只需要很少几次迭代就可以收敛。
更复杂迷宫环境的最优 V 函数和策略。
价值迭代
只管原始的策略迭代算法可以用来找到最优策略，但它可能会很慢，主要是由于策略评估步调中需要进行多次扫描。别的，完全收敛到精确的 V 函数可能需要许多次扫描。
别的，有时并不需要得到精确的 v 值就可以产生更好的策略。前面的例子很好地证明了这一点：与其进行多次扫描，我们实在只需要进行 (k = 3) 次扫描，然后根据得到的 V 函数近似值构建策略。这个策略将与我们在 V 函数收敛后计算出的策略完全雷同。
前几次迭代的 V 函数和策略评估。我们可以看到，从第三次迭代开始，策略不再改变。这个例子表明，在某些环境下，没有必要运行策略迭代的所有迭代。图片由作者改编，来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
一般来说，是否可以在某个时间制止策略评估算法呢？事实证明，答案是可以的！而且，甚至可以在策略评估的每一步中只进行一次扫描，效果仍然会收敛到最优策略。这种形貌的算法称为 价值迭代。
我们不会研究这个算法的证明。然而，我们可以注意到，策略评估和策略改进是两个非常相似的过程：它们都利用贝尔曼方程，唯一的区别是策略改进会取 max 操作以产生更好的动作。
通过迭代地进行一次策略评估扫描和一次策略改进扫描，我们可以更快地收敛到最优值。实际上，一旦连续 V 函数之间的差异变得微不敷道，我们就可以制止算法。
异步价值迭代
在某些环境下，每次价值迭代步调中只进行一次扫描可能会有问题，特殊是当状态数 (|S|) 很大时。为了克服这一点，可以利用 异步 版本的算法：不是在整个扫描中体系地更新所有状态，而是 只更新一部门状态值，以恣意顺序就地更新。别的，某些状态可以在其他状态更新之前被多次更新。
然而，终极所有状态都必须被更新，以便算法能够收敛。根据理论，所有状态必须被更新无限多次才能实现收敛，但在实践中，这个方面通常被忽略，由于我们并不总是需要得到 100% 最优的策略。
异步价值迭代存在不同的实现方式。在实际问题中，它们使得在算法的速度和准确性之间高效地进行权衡成为可能。
最简单的异步版本之一是：在策略评估过程中每次只更新一个状态。
广义策略迭代
我们已经研究了策略迭代算法。它的思想可以用来指代强化学习中的一个更广泛的术语，称为 广义策略迭代（GPI）。
GPI 通过独立瓜代进行策略评估和策略改进过程来探求最优策略。
几乎所有强化学习算法都可以归类为 GPI。
Sutton 和 Barto 提供了一个简化的几何图形，直观地表明了 GPI 的工作原理。假设一个二维平面，每个点代表一个价值函数和策略的组合。然后我们画两条线：
- 第一条线包罗对应于环境的不同 V 函数的点。
- 第二条线代表与相应 V 函数相干的贪心策略的聚集。
策略改进向最优性点的几何可视化。图片由作者改编，来源：《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
每次我们为当前 V 函数计算一个贪心策略时，我们都会更接近策略线，同时远离 V 函数线。这是合理的，由于对于新计算出的策略，之前的 V 函数不再适用。另一方面，每次我们执行策略评估时，我们都会向 V 函数线上的点的投影移动，从而远离策略线：对于新估计的 V 函数，当前策略不再是最优的。整个过程会重复进行。
随着这两个过程瓜代进行，当前的 V 函数和策略会渐渐改进，终极在某个时间，它们会到达一个最优性点，这个点代表 V 函数线和策略线的交点。
结论
在本文中，我们探讨了策略评估和策略改进背后的主要思想。这两个算法的美妙之处在于它们能够相互协作以到达最优状态。这种方法只适用于完善环境中，即署理在所有状态和动作下的转移概率都是已知的。只管有这个限定，许多其他强化学习算法仍然将 GPI 方法作为探求最优策略的基础构建块。
对于具有大量状态的环境，可以应用多种启发式方法来加快收敛速度，其中一种方法包括在策略评估步调中进行异步更新。由于大多数强化学习算法需要大量的计算资源，这种技能变得非常有效，它允许在速度和准确性之间进行有效的权衡。
资源
- 《强化学习：导论》第二版 | Richard S. Sutton 和 Andrew G. Barto
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
