原文towardsdatascience.com/reinforcement-learning-part-2-policy-evaluation-and-improvement-59ec85d03b3a简介强化学习是机器学习的一个领域它引入了代理的概念代理必须学习在复杂环境中的最优策略。代理从其行动中学习这些行动在给定环境状态的情况下产生奖励。强化学习是一个困难的话题与机器学习的其他领域有显著差异。这就是为什么它只应该在给定问题无法以其他方式解决时使用。强化学习的惊人灵活性在于相同的算法可以用来使代理适应完全不同、未知和复杂的环境。注意. 要完全理解本文中包含的思想强烈建议熟悉本文系列的第一部分中介绍的强化学习的主要概念。第一部分。强化学习第一部分简介和主要概念关于本文在第一部分本文基于由理查德·S·萨顿和安德鲁·G·巴特罗撰写的著名书籍强化学习的第三章我强烈推荐给所有对深入研究感兴趣的人。我们介绍了强化学习的主要概念框架、策略和价值函数。递归建立价值函数之间关系的贝尔曼方程是现代算法的骨架。我们将通过学习如何用它来找到最优策略来理解其力量。本文基于由理查德·S·萨顿和安德鲁·G·巴特罗撰写的书籍强化学习的第四章。我非常感谢作者们的努力他们为这本书的出版做出了贡献。解决贝尔曼方程让我们设想我们完美地了解了包含*|S|个状态的动态环境。动作转移概率由策略π给出。在这种情况下我们可以为这个环境的 V 函数求解贝尔曼方程这实际上将代表一个包含|S|个变量在 Q 函数的情况下将有|S| x |A|*个方程的线性方程组。该方程组的解对应于每个状态或每个*(状态动作)*对的 q 值的 v 值。示例让我们看看一个具有 5 个状态的环境的简单例子其中T是一个终止状态。蓝色数字表示状态之间的转移概率红色数字表示代理收到的奖励。我们还将假设代理在状态A由概率p 0.6的水平箭头表示选择的相同动作以不同的概率导致C或D概率p 0.8和p 0.2。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/7c6773b13a078e304facf40c378965ef.png示例的转移图。蓝色数字表示状态之间的转移概率红色数字定义相应的奖励。由于环境包含|S| 5个状态为了找到所有 v 值我们将不得不解决由5个贝尔曼方程组成的方程组https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/150106cef7b215c338693bfe2e8ee4e3.pngV 函数的贝尔曼方程组。由于 T 是一个终止状态其 v 值始终为 0因此技术上我们只需要解决4个方程。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/cc8abed83bd1e336ff667b441271a966.png方程组的解解决 Q 函数的类似系统会更困难因为我们需要为每一对(状态动作)解一个方程。政策评估以如上例所示的直接方式解决线性方程组是获取真实 v 值的一种可能方法。然而考虑到立方算法复杂度O(n³)其中n |S|它不是最优的尤其是在状态数量|S|较大时。相反我们可以应用迭代政策评估算法随机初始化所有环境状态除了终止状态的 v 值必须等于 0的 v 值。通过使用贝尔曼方程迭代更新所有非终止状态。重复步骤 2直到前一次和当前 v 值之间的差异太小≤ θ**)**。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/a595912dbbcb7871f5c8ddf79c2f3d10.png政策评估伪代码。来源强化学习。简介。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗如果状态数量|S|是有限的那么可以数学上证明在给定策略π**下政策评估算法获得的迭代估计最终会收敛到真实的 v 值状态 s ∈ S 的 v 值的单次更新称为期望更新。这个名字背后的逻辑是更新过程考虑了 s 的所有可能后续状态的奖励而不仅仅是单一的一个。对所有状态进行的一次更新迭代称为扫描。注意. 类似的迭代算法也可以应用于 Q 函数的计算。为了再次强调这个算法的神奇之处让我们再次突出它策略评估允许迭代地找到一个给定策略π下的 V 函数。更新变化策略评估算法中的更新方程可以以两种方式实现通过使用两个数组新值是从存储在两个单独数组中的未更改的旧值中顺序计算出来的。通过使用一个数组计算出的值会立即被覆盖。因此在相同迭代过程中的后续更新将使用覆盖后的新值。在实践中覆盖 v 值是执行更新的首选方式因为新信息一旦可用就被用于其他更新与两个数组方法相比。因此v 值往往收敛得更快。该算法不对每次迭代中应该更新的变量的顺序施加规则然而顺序可以极大地影响收敛速度。示例描述为了进一步了解策略评估算法在实际中的工作方式让我们看看萨顿和巴特奥的书中的示例 4.1。我们得到一个环境形式为4 x 4的网格在每一步智能体以等概率p 0.25在四个方向之一上、右、下、左移动一步。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/70d14dc3b545bbc1ee4c098f55b39dc1.png智能体从一个随机的迷宫单元格开始可以向四个方向之一移动每一步获得奖励 R -1。A4 和 D1 是终端状态。图片由作者改编。来源强化学习。入门。第二版 | 理查德·S·萨顿和安德鲁·G·巴特奥如果一个智能体位于迷宫的边缘并且选择进入迷宫周围墙壁的方向那么它的位置将保持不变。例如如果智能体位于D3并且选择向右移动那么在下一个状态它将保持在D3。除了位于A4和D1的两个终端状态其奖励为 R 0 之外每次移动到任何单元格都会得到R -1的奖励。最终目标是计算给定等概率策略的 V 函数。算法让我们将所有 V 值初始化为 0。然后我们将运行策略评估算法的多次迭代https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/52e90c96ebc67332670200c5c53ac35f.png不同策略评估迭代中的 V 函数。图片由作者改编。来源强化学习导论。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗在某个时候连续迭代中的 v 值之间将不再发生变化。这意味着算法已经收敛到真实的 V 值。对于迷宫在等概率策略下的 V 函数显示在最后一张图行的右侧。解释假设一个根据随机策略行动的智能体从单元格C2开始其期望奖励为 -18。根据 V 函数的定义-18 是智能体在游戏结束时收到的总累积奖励。由于迷宫中的每一步都会使奖励减少 1我们可以将 18 的 v 值解释为智能体到达终端状态之前需要采取的预期步数。策略改进初看可能会觉得惊讶但V 函数和 Q 函数可以用来找到最优策略。为了理解这一点让我们参考迷宫示例其中我们已经计算了起始随机策略的 V 函数。例如让我们以单元格B3为例。给定我们的随机策略智能体可以从该状态以相等的概率向四个方向移动。它可以收到的可能期望奖励是 -14、-20、-20 和 -14。假设我们有一个修改该状态策略的选项。为了最大化期望奖励不是逻辑上应该总是从B3向A3或B4移动即向邻居中期望奖励最大的单元格移动在我们的例子中是 -14吗https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/13eebb906e3c67e61d6699059f1c4fdb.png从单元格 B3 出发的最优动作可以导向 A3 或 B4那里的期望奖励达到最大值。这个想法是有道理的因为位于A3或B4的智能体有机会一步完成迷宫。因此我们可以为B3包含这个转换规则以推导出新的策略。然而是否总是通过最大化期望奖励进行这样的转换是最优的事实上贪婪地过渡到具有最大期望奖励的组合动作的状态将导致更好的策略。为了继续我们的例子让我们对迷宫的所有状态执行相同的程序https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c4b8cfc9321e2a81716fe0fec5e5f3e8.png示例中的收敛 V 函数及其对应的贪婪策略。图片由作者改编。来源强化学习导论。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗因此我们推导出了一种比旧策略更好的新策略。顺便说一句我们的发现可以通过策略改进定理推广到其他问题这个定理在强化学习中起着至关重要的作用。策略改进定理公式萨顿和巴特罗的书籍中的公式简洁地描述了定理设 π 和 π’ 是任何一对确定性策略对于所有 s∈Shttps://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/e214d06af687b3cd06dc3880f6c80b80.png来源强化学习。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗然后策略 π’ 必须与 π 相当好或者更好。也就是说它必须从所有状态 s∈S 中获得更大的或相等的期望回报https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8f398193135d87b6b4e2d843ae8c92b1.png来源强化学习。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗逻辑为了理解定理的公式让我们假设我们能够访问在策略π下评估的给定环境的 V 和 Q 函数。对于该环境我们将创建另一个策略π’。这个策略将绝对与π相同唯一的区别是对于每个状态它将选择导致相同或更大奖励的动作。然后定理保证在策略π’下的 V 函数将比策略π的那个更好。通过策略改进定理我们可以通过贪婪地选择当前策略中导致每个状态获得最大奖励的动作始终推导出更好的策略。策略迭代给定任何初始策略π我们可以计算其 V 函数。这个 V 函数可以用来改进策略到π’。使用这个策略π’我们可以计算其 V’-函数。这个过程可以重复多次以迭代地产生更好的策略和值函数。在有限状态的数量下这个被称为策略迭代的算法在极限情况下收敛到最优策略和最优值函数。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4cdfa001767f6e82c319fc03dbf8a32c.png策略评估E和策略改进I之间的迭代交替。图片由作者改编。来源强化学习。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗如果我们将策略迭代算法应用于迷宫示例那么最优的 V 函数和政策将看起来像这样https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2f197ce7a582810af1054bcc6ebfb04f.png迷宫示例的最佳 V 函数和政策。图片由作者改编。来源强化学习。简介。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗在这些设置中有了获得的最优 V 函数我们可以轻松地估计到达终端状态所需的步数根据最优策略。这个例子如此有趣的原因在于我们只需要进行两次策略迭代就可以从头开始获得这些值我们可以注意到从图像中看最优策略与我们在贪婪地将其更新到相应的 V 函数之前的情况完全相同。在某些情况下策略迭代算法只需要很少的迭代次数就可以收敛。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/da58461ed932f7a1b41f65df3e6e370a.png一个更复杂迷宫环境的最佳 V 函数和策略示例。值迭代尽管原始的策略迭代算法可以用来找到最优策略但它可能很慢主要是因为在策略评估步骤中执行了多次扫描。此外完全收敛到精确的 V 函数可能需要很多次扫描。此外有时并不一定需要得到精确的 v 值才能得到更好的策略。前一个例子完美地展示了这一点我们本可以只进行k 3次扫描然后基于获得的 V 函数近似值构建策略。这个策略将与我们计算出的 V 函数收敛后的策略完全相同。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4200653e16488128c7eb69343743cf4a.pngV 函数和政策评估的前三次迭代。我们可以看到从第三次迭代开始策略没有变化。这个例子表明在某些情况下没有必要运行所有策略迭代的迭代次数。图片由作者改编。来源强化学习。简介。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗通常情况下我们是否可以在某个点停止策略评估算法结果是肯定的此外在每次策略评估步骤中只需执行一次单次遍历结果仍然会收敛到最优策略。这种描述的算法被称为值迭代。我们不会研究这个算法的证明。然而我们可以注意到策略评估和策略改进是两个非常相似的过程它们都使用贝尔曼方程除了策略改进使用max操作来产生更好的动作。通过迭代执行策略评估的单次遍历和策略改进的单次遍历我们可以更快地收敛到最优解。实际上一旦连续的 V 函数之间的差异变得微不足道我们就可以停止算法。根据理论状态值可以按顺序更新和覆盖无需使用其他状态的更新值使用先前值不会阻止算法找到最优策略。这种技术被称为自举。异步值迭代在某些情况下在值迭代的每一步只执行单次遍历可能会出现问题特别是当状态数量|S|很大时。为了克服这一点可以使用算法的异步版本不是在整个遍历过程中系统地更新所有状态而是在任何顺序中只更新状态值的一个子集。此外某些状态可以在其他状态更新之前多次更新。然而在某个时刻所有状态都必须更新以便算法能够收敛。根据理论所有状态必须总共无限次更新才能达到收敛但在实践中这个方面通常被省略因为我们并不总是对获得 100% 最优策略感兴趣。异步值迭代存在不同的实现方式。在实际问题中它们使得在算法的速度和精度之间进行有效权衡成为可能。其中一种最简单的异步版本是在策略评估期间只更新单个状态。广义策略迭代我们已经研究了策略迭代算法。其思想可以用来指代强化学习中更广泛的一个术语称为广义策略迭代 (GPI)。GPI 的核心是通过独立交替进行策略评估和策略改进过程来寻找最优策略。几乎所有的强化学习算法都可以被称为 GPI。Sutton 和 Barto 提供了一个简化的几何图形直观地解释了 GPI 的工作原理。让我们想象一个二维平面其中每个点代表一个值函数和策略的组合。然后我们将画两条线第一行将包含与一个环境的不同 V 函数相对应的点。第二行将表示与相应 V 函数相关的贪婪策略集。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/a9a84b92b2955364f66f24d3cd6b930e.png政策改进向最优点的几何可视化。图片由作者改编。来源强化学习。简介。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗每当我们为当前的 V 函数计算贪婪策略时我们就会接近策略线同时远离 V 函数线。这是合乎逻辑的因为对于新计算出的策略先前的 V 函数不再适用。另一方面每当我们执行策略评估时我们就会向 V 函数线的点投影移动因此我们就会远离策略线对于新估计的 V 函数当前策略不再是最佳的。整个过程会再次重复。由于这两个过程相互交替当前的 V 函数和政策都会逐渐改进并在某个时刻达到一个最优点这将代表 V 函数和政策线的交点。结论在本文中我们探讨了策略评估和策略改进背后的主要思想。这两个算法的美丽之处在于它们能够相互交互以达到最优状态。这种方法仅在完美环境中有效其中代理的概率转移对所有状态和动作都是已知的。尽管存在这种限制但许多其他强化学习算法将 GPI 方法作为寻找最优策略的基本构建块。对于具有众多状态的环境可以应用几种启发式方法来加速收敛速度其中之一包括在策略评估步骤中进行异步更新。由于大多数强化算法需要大量的计算资源这项技术变得非常有用并允许在速度和精度之间进行有效权衡。我们在这里讨论的策略迭代算法是基于称为“动态规划”的方法它指的是一种问题其中代理完全了解环境的动态转移概率p(s’ r | s, a))。代理使用这些信息根据其先前估计计算价值函数和政策并用新值替换它们。资源强化学习。简介。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗除非另有说明所有图片均为作者所有。