第7章 使用表格方法规划和学习

第7章 使用表格方法规划和学习#

在本章中，我们将从统一视角来审视强化学习方法，将其分为两类：一类是需要环境模型的方法（即\(\textit{基于模型}\)的强化学习方法），例如动态规划；另一类是无需模型即可使用的方法（即\(\textit{无模型}\)的强化学习方法），例如蒙特卡洛方法和时序差分方法。

基于模型的方法主要依靠\(\textit{规划}\)，而无模型的方法主要依靠\(\textit{学习}\)。尽管这两类方法存在实际差异，但也有许多相似之处：

  • 这两类方法的核心都是计算价值函数。

  • 所有方法都基于对未来事件的前瞻性计算，计算一个回传的价值，并将其作为逼近价值函数的更新目标。

除了对规划与学习方法的统一视角外，本章的第二个主题是以小而渐进的步骤进行规划的益处。这使得规划可以在任何时候被中断或重新定向，而几乎不会浪费计算资源，这似乎是高效地将规划、执行与模型学习交织进行的关键要求。

7.1 模型和规划#

  • \(\textit{模型}\)（环境的模型）：智能体用于预测环境对其动作反应的任何方法或机制，

  • \(\textit{分布模型}\)：生成所有可能情况及其概率的描述。例如，动态规划中使用的模型（即环境转移概率：\(p(r, s' | s, a)\)）

  • \(\textit{采样模型}\)：仅生成根据概率分布采样出的一种可能情况。

  • 这两种模型都可用于\(\textit{模拟}\)环境并生成\(\textit{模拟经验}\)。给定一个起始状态和策略，采样模型可以生成完整的一次轨迹，分布模型则可以生成所有可能轨迹及其概率。

  • \(\textit{规划}\)：任何以\(\textit{模型}\)为输入并生成或改进与建模环境交互策略的计算过程，其形式如下所示：

\[ model \xrightarrow{\text{planning}} policy \]

规划有两种截然不同的方法：

  • \(\textit{状态空间规划 （State-space planning）}\)：在状态空间中搜索最优策略或通往目标的最优路径。动作引起状态之间的转移，价值函数是在状态上进行计算的。

  • \(\star\textit{计划空间规划 （Plan-space planning）}\)：在计划空间中进行搜索。算子将一个计划转化为另一个计划，若定义了价值函数，也是在计划空间上定义的。计划空间方法难以高效应用于强化学习所关注的随机顺序决策问题，因此我们不再进一步讨论此类方法。

  • 统一基于模型与无模型的强化学习方法：学习与规划（状态空间规划）方法的核心都是通过2）回传更新操作来1）估计价值函数。两者的区别在于，规划使用模型生成的模拟经验，而学习方法使用环境生成的真实经验。

    • 规划与学习之间的共同结构可用如下图示表示：

    \[ \text{model} \rightarrow \text{simulated experience} \xrightarrow{\text{backups}} \text{values} \rightarrow \text{policy} \]

    • 规划的示例：\(\textit{随机采样一步表格}\) Q-规划

      Algorithm: One-step Tabular Q-planning

7.2 Dyna：统筹规划、行动和学习#

  • 在线规划智能体：与环境实时交互，并根据新获得的信息更新模型。

    • 下图概括了经验、模型、价值和策略之间可能存在的关系:

      Architecture of a planning agent

    • 根据真实经验的使用方式，强化学习过程可以分为直接强化学习和间接强化学习：

      • \(\textit{直接强化学习}\)：使用真实经验直接改进价值函数和策略。

      • \(\textit{间接强化学习}\)（或称为\(\textit{模型学习}\)）：使用真实经验来改进模型。

      • 注意：间接方法通常能更充分地利用有限的经验，因此在较少的环境交互下获得更优策略。另一方面，直接方法更简单，不受模型设计偏差的影响。（本书并不强调这两者之间的对比，而是更关注它们之间的相似性。）

  • Dyna 智能体：一种在线规划智能体，能够同时执行上述所有过程——规划、行动、模型学习和直接强化学习——并且这些过程会持续进行。

    • 架构：

      Architecture of Dyna agent

    • 解释：

      • 图中左侧的箭头表示直接强化学习，它基于真实经验来改进价值函数和策略。

      • 右侧则是基于模型的过程。模型通过真实经验学习得到，并用于生成模拟经验。

      • 通常，学习真实经验与从模拟经验中进行规划都会使用相同的强化学习方法。

    • 计算时间分配：

      • 通常，执行、模型学习和直接强化学习过程计算量较小，我们假设它们只消耗一小部分时间。

      • 每一步中可以将更多时间用于规划过程，因为规划本质上是计算密集型的。

  • 一种 Dyna 智能体类型：用于估计 \(q_\pi\) 的表格法 Dyna-Q:

    • 算法

      Algorithm: Tabular Dyna-Q

      Note

      • \(Model(s, a)\) 表示对状态-动作对 \((s, a)\) 的预测结果，包括下一状态及所获得的奖励。

      • 直接强化学习和模型学习分别通过步骤 (d) 和 (e) 实现。

      • 整个步骤 (f) 执行规划。

        • \(\textit{搜索控制}\)：步骤 (f) 中的前两步，用于选择用于模型生成模拟经验的起始状态和动作。

        • 注意：规划中的起始状态是随机选择的，不一定是真实的起始状态。

        • 注意：规划只会针对智能体已经积累了真实经验的状态进行。

      • 如果省略步骤 (e) 和 (f)，则剩下的算法就是一步表格法 Q 学习。

    • 讲解示例的视频（从 3:13 开始）：在一个带有障碍物的网格世界中，智能体从左下角的格子出发，前往右上角的终止状态。初始策略 \(\pi\) 为四个动作（左、右、上、下）分配相等的概率。

      Video: The dyna algorithm

  • 示例：Dyna 迷宫

    • 举例说明，规划智能体的学习速度可能比纯学习智能体快得多：

      Video: The Maze example

    • 智能体需要进行多次规划步骤，原因是搜索控制是随机采样状态-动作对的。如果采样到的状态-动作对产生的 TD 误差为 0，那么该次规划更新不会产生任何效果。在这个环境中，这种情况频繁发生，因为所有奖励都是 0，初始值也同样为 0。

    • 在更大的环境中，随机搜索控制的问题会更加严重。但在本例中，规划次数越多，智能体的表现越好。

7.3 当模型错误时#

  • 不准确的模型：模型可能不完整（缺少某些转移信息），或者环境发生了变化（导致模型中存储的转移信息不再准确）。

    • 当模型出错时：我们需要在规划过程中权衡探索与利用：

      • 探索：尝试能够改进模型的动作

      • 利用：根据当前模型采取最优行为

  • 示例：阻塞迷宫 - 当环境变得”更糟”时

    • 描述：最初，从起点到目标有一条穿过障碍物右侧的捷径，如左上角图所示。经过1000个时间步后，这条捷径被”阻塞”，同时在障碍物左侧开辟了一条更长的路径

      The blocking maze example

    • 解释

      • 图表的第一部分显示，两个 Dyna 智能体在1000步内都找到了这条捷径。

      • 当环境发生变化后，图线变得平坦，表明智能体在一段时间内未能获得任何奖励，因为它们一直在障碍物后方徘徊。

      • 不过不久之后，它们找到了新的通道，并形成了新的最优行为策略。

  • 示例：捷径迷宫 - 当环境变得”更好”时

    • 描述：最初，最优路径是绕过障碍物左侧（左上角）。但在3000步之后，右侧开辟了一条更短的路径，同时未影响原来的较长路径

      The shortcut maze example

      Note

      当环境变得”更好”（出现了更优的解）时，更难察觉模型错误，因此在规划过程中需要更多地考虑探索，以保持模型的更新。

  • Dyna-Q+ 智能体 - 鼓励在规划过程中探索

    • 对所有 \(s ∈ S\) 和 \(a ∈ A\) 初始化 \(Q(s,a)\) 和 \(Model(s,a)\)

    • 循环执行以下步骤：

      • (a) \(S \leftarrow\) 当前（非终止）状态

      • (b) \(A \leftarrow \epsilon\)-greedy(\(S, Q\))

      • (c) 执行动作 \(A\)，观察奖励 \(R\) 和下一状态 \(S'\)

      • (d) \(Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma max_a Q(S', a) - Q(S, A)]\)

      • (e) \(Model(S, A)\) \(\leftarrow R, S'\) 并将 \(S\) \(\leftarrow S'\)（假设环境是确定性的）

      • (f) 如果 \(S\) 是终止状态，则将 \(S \leftarrow\) 起始状态并重新开始，否则重复执行 \(n\) 次：

        • \(S \leftarrow\) 随机选择的之前观察过的状态

        • \(A \leftarrow\) 在 \(S\) 中可用的随机动作（不必是之前执行过的）

        • \(R, S' \leftarrow Model(S, A)\)

        • \(R = R + \kappa \sqrt \tau_{S,A,R,S'}\)

        • \(Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma max_a Q(S', a) - Q(S, A)]\)

      Note

      • 修改1：奖励现在变为 \(R + \kappa \sqrt \tau\)，其中 \(\kappa\) 是一个常数，\(\tau\) 表示在真实经验中状态-动作对 \((S,A)\) 到 \((R, S')\) 的转移已经多长时间没有被尝试过。

        • 时间间隔越长，我们可以推测这对转移的动态可能已经发生变化，导致模型不再准确的可能性越大。

        • 注意：\(\tau\) 只会在真实交互中更新，而不会在规划过程中更新。

        • 这种鼓励探索的方式类似于第2章中描述的上置信界动作选择（Upper-Confidence-Bound Action Selection），两者都在一定程度上衡量了不确定性。

      • 修改2：在规划步骤 (f) 中，允许考虑从未在某个状态下尝试过的动作。对于这些动作，初始模型假设它们会导致回到同一状态，并获得0的奖励。

7.4 总结#

  • 思维导图：我们现在的位置

    Mindmap

  • 关键要点

    1. 基于模型与无模型方法的对比

      • 基于模型的方法（如动态规划）利用模型进行规划。

      • 无模型方法（如蒙特卡洛、TD）直接从实际经验中学习。

      • 两者的核心都是通过回传操作计算价值函数，区别在于经验来源的不同（模拟经验 vs 真实经验）。

    2. 模型与规划的本质

      • 模型的作用是预测环境对动作的反应。

        • 分布模型能够提供所有可能的结果及其概率。

        • 采样模型仅生成一个符合概率分布的采样结果。

      • 规划则是利用模型来改进策略的过程。

        • 状态空间规划通过搜索状态转移来寻找最优策略。

    3. Dyna：规划、行动与学习的集成

      • Dyna 架构将直接强化学习、模型学习和规划有机结合。

        • 直接强化学习从真实经验中更新价值函数。

        • 模型学习从真实经验中更新环境模型。

        • 规划则利用模型生成的模拟经验来加速学习过程。

      • 表格型 Dyna-Q 通过在真实经验和模拟经验之间交替学习，显著加快了学习速度。

    4. 应对模型不准确的挑战

      • 当环境发生变化或模型缺乏某些信息时，模型就会变得不准确。

      • 此时，我们需要在规划过程中权衡探索（改进模型）与利用（使用当前模型）之间的关系。

    5. Dyna-Q+：促进探索的有效机制

      • Dyna-Q+ 根据动作未被访问的时间长度，为奖励添加额外的探索奖励。

      • 在规划过程中纳入未尝试过的动作，以促进更广泛的探索。

      • 这种机制帮助智能体能够更快地适应动态变化的环境，并及时检测到环境中的变化。

    6. 实用洞察与建议

      • 采用增量式规划方法能够更灵活地应对环境变化。

      • 基于模型的方法在交互次数较少的情况下通常学习更快，而无模型方法则更为简单，且能够避免模型偏差问题。

      • 有效的规划需要通过搜索控制机制，优先处理那些最有价值的模拟经验。

  • 额外课程视频（可选）: Drew Bagnell：自动驾驶、机器人技术与基于模型的强化学习

Contents