01
引言
强化学习是机器学习中的一个领域，它引入了智能体的概念——智能体必须在复杂环境中学习最优策略。该智能体通过自身行为进行学习，这些行为会根据环境状态产生相应的奖励。强化学习是一个颇具挑战性的课题，与其他机器学习领域存在显著差异。正因如此，它仅适用于其他方法无法解决的特定问题。
强化学习具有惊人的灵活性，相同的算法可使智能体适应完全不同的、未知且复杂的条件。
注：为充分理解本文内容，强烈建议先熟悉本系列文章第一部分介绍的强化学习核心概念。
02
让我们想象我们完美地知道包含 |S| 个状态的环境动态。动作转移概率由策略 π 给出。
基于此，我们可以求解该环境的 V 函数的 Bellman 方程，这实际上将表示一个包含 |S| 个变量的线性方程组 (如果是 Q 函数，则会有 |S| x |A| 个方程)。
该方程组的解即对应每个状态的v值（或每个（状态，动作）对的q值）。
举例
让我们来看一个包含 5 个状态的简单环境例子，其中 T 是一个终止状态。蓝色数字表示转移概率，而红色数字表示智能体获得的奖励。我们还将假设，在状态A中（由概率p=0.6的水平箭头表示），智能体选择的同一动作会以不同概率（p=0.8和p=0.2）导向C或D状态。
由于环境包含 |S| = 5 个状态，为了找到所有 v 值，我们将不得不求解一个由 5 个 Bellman 方程组成的方程组：
由于 T 是一个终止状态，其 v 值始终为 0，因此从技术上讲，我们只需要求解 4 个方程。
若要求解对应的Q函数方程组则更为复杂，因为需要为每个（state,action）对建立方程。
以直接的方式求解线性方程组，就像上面例子中展示的那样，是获得真实 v 值的一种可能方法。
然而，考虑到算法的立方复杂度 O(n³)，其中 n = |S|，这种方法不是最优的，尤其当状态数量 |S| 很大时。
作为替代，我们可以应用迭代策略评估算法：
随机初始化所有环境状态的 v 值（终止状态除外，它们的 v 值必须等于 0）。
使用 Bellman 方程迭代更新所有非终止状态。
重复步骤2，直至前后两次迭代的v值差异小于阈值θ
如果状态数量 |S| 是有限的，那么在数学上可以证明，在给定策略 π 下，通过策略评估算法获得的迭代估计最终会收敛到真实的 v 值！
对状态 s ∈ S 的 v 值进行一次更新，称为期望更新（expected update）。这个名称背后的逻辑在于，更新过程考虑了状态 s 所有可能的后续状态的奖励，而不仅仅是单一的后续状态。
针对所有状态进行一轮完整的更新，被称为一次扫描（sweep）。
注：类似的迭代算法也可以应用于 Q 函数的计算。
为了让大家了解这个算法的强大之处，我们再次强调：
策略评估允许在给定策略 π 下通过迭代来找到 V 函数。
更新变体
策略评估算法中的更新方程可以通过两种方式实现：
双数组法：新的值是从存储在两个独立数组中的未改变的旧值顺序计算得出的。
单数组法：算出的值会立即覆盖原值。因此，同一迭代中后续的更新会使用已覆盖（即已更新）的新值。
实际应用中，单数组覆盖法是更优的更新方式。相较于双数组法，它能即时利用最新计算值进行后续更新，从而使状态值（v值）更快收敛。
该算法没有规定每次迭代中变量的更新顺序，然而这个顺序可以对收敛速度产生很大影响。
举例
为了进一步理解策略评估算法在实践中如何工作，让我们来看看《Reinforcement Learning》书中的例子。我们有一个 4x4 网格形式的环境，智能体在其中每一步都以等概率 (p = 0.25) 向四个方向中的一个（上、右、下、左）迈出一步。
如果智能体位于迷宫边缘并选择走向迷宫周围的墙壁方向，那么它的位置将保持不变。例如，如果智能体位于 D3 并选择向右移动，那么在下一个状态它将停留在 D3。
除位于 A4 和 D1 的两个终止状态（奖励 R=0）外，其他所有移动均产生 R=−1 的奖励。最终目标是为该等概率策略计算对应的状态价值函数（V 函数）。
算法
让我们将所有状态值（V值）初始化为0，然后运行策略评估算法的多次迭代：
当连续两次迭代的V值不再发生变化时，说明算法已收敛至真实状态值。对于这个网格，最终收敛后的等概率策略V函数如最下方图示右侧所示。
04
乍一看可能令人惊讶，但 V 函数和 Q 函数可以用来找到最优策略。为了理解这一点，让我们回顾一下迷宫的例子，我们在其中计算了初始随机策略下的 V 函数。
以B3单元格为例。在随机策略下，智能体从该状态出发有四个等概率移动方向，其可能获得的期望奖励分别为-14、-20、-20和-14。假设我们现在可以修改该状态的策略：为最大化期望奖励，让智能体总是从B3移向A3或B4（即选择邻域中期望奖励最大的单元格，本例中为-14）难道不是合理的选择吗？
这个思路之所以成立，是因为位于A3或B4能让智能体仅需一步即可完成迷宫。因此我们可以为B3单元格制定这条转移规则，从而推导出新策略。但关键在于：这种以最大化期望奖励为目标的转移方式是否永远最优？
事实上，贪婪地转移到具有最大期望奖励组合的后续状态（即选择预期收益最高的动作），确实能产生更优策略。
继续我们的示例，若对所有迷宫状态执行相同操作：
最终我们将得到优于旧策略的新策略。值得一提的是，这个发现可通过策略改进定理推广到其他问题领域——该定理在强化学习中具有至关重要的作用。
策略改进定理
《Reinforcement Learning》书中揭示了这一定理：
要理解该定理的表述，我们假设已获得策略π在当前环境下评估所得的V函数与Q函数。基于此，我们将构建一个新策略π'。该策略与π完全相同，唯一区别在于：对于每个状态，π'都会选择能带来同等或更高收益的动作。此时定理保证：策略π'下的V函数值必然优于原策略π。
借助策略改进定理，我们总能通过贪婪选择（即在每个状态下选取当前策略中能带来最大收益的动作）来推导出更优策略。
05
对于任意初始策略π，我们都可以计算出其对应的V函数。利用该V函数，我们可以将策略改进为π'。基于这个新策略π'，又能计算出其对应的V'函数。如此反复迭代，就能逐步得到更优的策略和价值函数。
在状态空间有限的情况下，这个被称为策略迭代的算法最终必然收敛，从而得到最优策略和最优价值函数。
若将策略迭代算法应用于迷宫示例，最终得到的最优V函数和策略如下图所示：
在这些设定中，利用获得的最优V-函数，我们可以根据最优策略估算到达终点所需的步骤数。
这个案例最引人入胜之处在于：从零开始，我们仅需两次策略迭代就能获得这些最优值（可以观察到图示中的最优策略与我们之前通过贪婪更新V函数得到的策略完全一致）。在某些情况下，策略迭代算法仅需少量迭代即可收敛。
虽然原始的策略迭代算法可用于寻找最优策略，但其运行速度可能较慢——主要瓶颈在于策略评估阶段需要进行多次全状态迭代。更何况，要使得V函数完全收敛，往往需要极其大量的迭代计算。
但事实上，要获得更优策略，我们有时并不需要精确的V函数值。前文的迷宫示例完美印证了这一点：与其等待V函数完全收敛，我们其实只需进行k=3次扫描，基于此时获得的V函数近似值就能构建出与完全收敛后完全一致的优化策略。
这就引出一个关键问题：策略评估过程是否可以在中途终止？事实证明完全可行！更惊人的是，即使在每次策略评估阶段仅执行单次状态扫描，算法依然能收敛至最优策略。这种改进后的算法被称为值迭代。
我们暂不探讨该算法的数学证明，但可以观察到：策略评估与策略改进本质上是两个高度相似的过程——二者都基于贝尔曼方程，唯一的区别在于策略改进阶段会通过max运算选取更优动作。
通过交替执行单次策略评估扫描和单次策略改进扫描，我们能以更快的速度逼近最优解。实际应用中，当连续两次V函数之间的差异小于阈值时，即可终止算法迭代。
异步值迭代算法
在某些情况下，在每一步的价值迭代中只进行一次遍历可能会带来问题，特别是当状态数 |S| 很大时。为了解决这个问题，可以采用异步版本的算法：不是系统性地对所有状态进行更新，而是在任何顺序中只在原地更新一部分状态值。此外，一些状态可以在其他状态被更新之前多次进行更新。
然而，为确保算法最终收敛，所有状态都必须被更新。理论上，要实现收敛，每个状态总共需要被更新无限次，但在实际应用中，这一要求通常可以放宽——因为我们并不总是需要 100% 最优的策略。
异步值迭代存在多种实现方式，在现实问题中，它们能够在算法速度和精度之间进行高效权衡。
其中，最简单的异步版本是：在策略评估阶段，每次仅更新单个状态。
我们已探讨过策略迭代算法，其核心思想可延伸至强化学习中的一个更广泛概念——广义策略迭代（GPI）。
GPI的本质在于：通过策略评估与策略改进两个过程的交替独立执行，最终逼近最优策略。
几乎所有的强化学习算法都可以归类为广义策略迭代（GPI）。
Sutton与Barto曾用一个简易几何图示直观阐释GPI的工作原理：假设存在一个二维平面，其中每个点代表某个价值函数与策略的组合。在此平面上绘制两条曲线：
价值函数线：由环境所有可能的V函数对应的点构成
策略线：由相对于各V函数的贪婪策略对应的点组成
当基于当前V函数计算贪婪策略时，我们会向策略线靠近，同时远离价值函数线——这很合理，因为新策略会使原有V函数失效。反之，当执行策略评估时，我们会向价值函数线的投影点移动，同时偏离策略线，因为新估算的V函数会使当前策略不再最优。该过程循环往复。
随着两个过程不断交替，当前V函数与策略持续改进，最终必然收敛至两条曲线的交点——这个交点即代表最优价值函数与最优策略的完美契合。
在本文中，我们回顾了策略评估和策略改进背后的主要思想。这两个算法的精妙之处在于它们能够相互作用，以达到最优解。这种方法仅适用于智能体在所有状态和动作下的状态转移概率都已知的环境。尽管存在这一局限性，许多其他的强化学习算法仍将广义策略迭代（GPI）方法作为寻找最优策略的基础。
对于状态数量庞大的环境，可以应用一些启发式方法来加速收敛速度，其中之一就是在策略评估步骤中进行异步更新。由于大多数强化学习算法需要大量的计算资源，这一技术显得尤为重要，它能有效实现计算精度与执行速度的平衡优化。
最后，祝大家学习愉快！
点击上方小卡片关注我
添加个人微信，进专属粉丝群！
