Reinforcement Learning with Symbolic Reward Machines

本文提出了符号奖励机（SRMs）及其配套算法 QSRM 和 LSRM，通过利用符号公式直接处理环境观测而非依赖人工标注，克服了传统奖励机在适用性和可扩展性上的局限，同时实现了与现有方法相当的性能并保留了任务的可解释性。

要点

这篇论文介绍了一种让机器人（或 AI 智能体）更聪明、更独立地学习新任务的新方法。为了让你轻松理解，我们可以把强化学习（RL）想象成教一个小孩学骑自行车，而这篇论文的核心就是解决“如何给这个小孩制定最合适的奖励规则”的问题。

1. 以前的难题：需要一位“翻译官”

在传统的强化学习中，环境（比如骑自行车的路况）只告诉 AI 两件事：“你现在在哪”和“你刚才做得好不好（给个分数）”。

但是，很多任务不是只看当下的。比如任务要求：“先拿苹果，再拿香蕉，最后去厨房”。

• 传统方法（Reward Machines, RMs）的痛点：
  以前的方法（叫 RM）需要一个人工编写的“翻译官”（Labeling Function）。
  • 想象一下，你教小孩骑车，但你不能直接说“保持平衡”，你必须给小孩戴上一个特制的头盔，头盔上有个传感器，只有当小孩身体倾斜角度正确时，头盔才会亮绿灯（发出一个高级信号）。
  • 问题：每换一个新环境（比如从平地换到坡道），或者每换一个任务（从拿苹果变成拿橘子），你就得重新设计并安装这个“头盔”和“传感器”。这需要专家手动写代码，非常麻烦，而且一旦环境稍微变复杂，这个“翻译官”就失效了。

2. 新方案：符号奖励机（SRM）—— 让 AI 直接“看”懂世界

这篇论文提出了符号奖励机（SRM），它不需要那个麻烦的“翻译官”头盔。

• 核心比喻：
  以前的 RM 像是听指令行事：只有当“翻译官”大喊“现在去拿苹果！”时，AI 才知道该拿苹果。
  现在的 SRM 像是拥有逻辑推理能力的向导：AI 直接看着眼前的世界（比如看到桌子上有个红苹果），它脑子里的公式会直接判断：“哦，那个红色的东西就是苹果，符合我的规则，我可以去拿了。”

• SRM 是怎么工作的？
  SRM 内部有一张“任务地图”（状态机），地图上的每一条路（转换）都挂着逻辑公式作为路标（Guard）。

  • 比如路标上写着：x > 5 且 y < 10。
  • AI 不需要别人告诉它“你到了位置 A"，它自己计算坐标，发现符合公式，就自动走到下一步。
  • 好处：不需要人工写“翻译官”代码，直接利用环境原本的数据（坐标、速度等），让 AI 在标准环境下就能学会复杂的、有先后顺序的任务。

3. 两大新算法：QSRM 和 LSRM

作者基于 SRM 开发了两个新算法，分别对应两种学习场景：

A. QSRM：如果你知道任务长什么样（“有地图的导游”）

• 场景：你作为人类，已经画好了任务地图（SRM），你知道任务分几步走。
• 作用：QSRM 就像是一个超级导游。它拿着你给的地图，直接教 AI 怎么走。
• 优势：它比以前的方法（QRM）更灵活，因为它不需要“翻译官”头盔，直接看环境数据就能跑。实验证明，它学得和以前一样快，甚至更好，而且不需要额外的人工干预。

B. LSRM：如果你连地图都没有（“从零开始的探险家”）

• 场景：你不仅不知道任务怎么做，连任务地图（SRM）长什么样都不知道。你只给 AI 一个环境和一个目标（比如“最后给 100 分”）。
• 作用：LSRM 是一个会自己画地图的探险家。
  1. 它先瞎猜一个任务地图（比如“先拿苹果再拿香蕉”）。
  2. 它带着 AI 去试跑。
  3. 如果 AI 跑错了（比如拿了香蕉没拿苹果，但环境却给了分，或者没给分），LSRM 就会记录这个“错误案例”（反例）。
  4. 它利用这些错误案例，像拼图一样自动修正它猜的地图，直到猜出的地图能完美解释所有的奖励规则。
• 两大模式：
  • LSRM-GF：你给它一些可能的“逻辑积木”（比如它知道可以用 x > 5 这种公式），它负责组装。
  • LSRM-FT（更厉害）：你什么都不用给，它自己发明“逻辑积木”（比如它自己发现需要设定一个范围 2 < x < 5），完全端到端地学会任务。

4. 为什么这很重要？（实验结果）

作者在“办公室世界”（机器人要在房间里按顺序去不同房间）和“山地车”（连续控制）等环境中做了测试：

1. 比传统方法强：传统的 AI（像 Q-Learning）因为记不住历史，面对这种“先做 A 再做 B"的任务时，就像无头苍蝇，学不会。
2. 和旧方法一样好，但更省事：SRM 方法的效果和以前需要人工写“翻译官”的 RM 方法一样好，甚至更好，但完全不需要人工写那个讨厌的“翻译官”代码。
3. 可解释性：这是最酷的。LSRM 学完后，不仅学会了怎么骑车，还把“任务地图”画了出来。人类可以看到它学到的规则（比如“当 x 在 5 到 6 之间时，奖励是 1"）。这就像 AI 不仅学会了开车，还给你写了一份驾驶说明书，告诉你它是怎么理解这个任务的。

总结

这篇论文就像是在说：

“以前教 AI 做复杂任务，我们需要给它戴个特制的‘翻译头盔’，每换任务就得换头盔，太麻烦了。
现在我们发明了一种自带逻辑眼镜的 AI（SRM）。它不需要头盔，直接看世界就能理解规则。
甚至，如果我们连规则都没告诉它，它还能自己观察、自己猜、自己修正，最后不仅学会了任务，还把规则总结成人类能看懂的说明书交给我们。”

这让强化学习在现实世界（比如机器人控制、自动驾驶）中的应用变得更容易、更通用，也更容易让人类理解 AI 到底在想什么。

技术摘要

基于符号奖励机器的强化学习技术总结

1. 问题背景 (Problem)

在强化学习（RL）中，传统的奖励函数通常是**马尔可夫（Markovian）的，即奖励仅取决于当前的状态和动作。然而，许多现实世界的任务具有非马尔可夫（Non-Markovian）**特性，即奖励取决于状态历史（例如：必须先收集木材，然后才能放入机器）。

现有的解决方案**奖励机器（Reward Machines, RMs）**虽然能有效处理非马尔可夫奖励，但存在显著局限性：

1. 依赖标签函数（Labeling Function）： RM 需要环境输出高层事件（标签），这要求用户为每个环境和任务手动设计标签函数。
2. 破坏标准交互协议： 标准 RL 框架通常只输出状态和奖励，引入标签函数需要修改环境接口，导致通用性差。
3. 可解释性受限： 标签通常是抽象的符号，难以直接反映环境状态的具体数值特征。

核心挑战： 如何在不修改标准环境接口（即不使用外部标签函数）的情况下，让智能体学习非马尔可夫奖励函数，并自动推断出可解释的任务结构？

2. 方法论 (Methodology)

本文提出了**符号奖励机器（Symbolic Reward Machines, SRMs）**及其配套的算法 QSRM 和 LSRM。

2.1 符号奖励机器 (SRMs)

SRM 是 RM 的扩展，其核心创新在于输入机制：

• 输入： 直接接收环境的原始状态（State），而非高层标签。
• 转换条件（Guards）： 使用符号公式（Symbolic Formulas）（如线性实数算术 LRA）作为状态转换的守卫条件。
• 机制： 当环境状态 $s$ 满足某个公式 $\phi$（即 $s \models \phi$）时，SRM 发生状态转移并输出奖励。
• 优势： 无需标签函数，直接处理原始状态，且公式具有可解释性（例如 $x \ge 5 \land y < 10$）。

2.2 学习算法

论文提出了两种主要算法：

A. QSRM (已知 SRM 的情况)

• 功能： 当用户已知 SRM 结构时，用于学习最优策略。
• 原理： 类似于 QRM，但将 SRM 的状态与 RL 的状态进行笛卡尔积，构建扩展 MDP。它利用多步更新（Multi-update）机制加速收敛。
• 特性： 尊重标准 RL 交互接口，无需标签函数。理论上保证了在标准 Q-Learning 条件下收敛到最优策略。

B. LSRM (自动推断 SRM)

• 功能： 在完全未知 SRM 结构的情况下，端到端地学习策略和 SRM。
• 流程：
  1. 初始化一个假设的 SRM（通常只有一个状态）。
  2. 使用 (D)QSRM 训练策略。
  3. 一致性检查： 比较环境实际奖励与假设 SRM 输出的奖励。如果不一致，将当前轨迹作为反例（Counterexample）。
  4. SRM 推断： 利用反例集，通过**约束满足问题（CSP）**编码，使用 SMT 求解器（如 Z3）生成一个新的、与所有反例一致的 SRM 假设。
  5. 重复上述过程直到收敛。
• 两种变体：
  • LSRM-GF (Given Formulas)： 用户给定一组可能的公式集合，算法从中选择并组合。
  • LSRM-FT (Formula Templates)： 用户仅提供公式模板（如 $x \ge b_1 \land x < b_2$），算法自动推断模板中的参数（$b_1, b_2$），完全无需用户干预。

3. 关键贡献 (Key Contributions)

1. 提出符号奖励机器 (SRMs)： 消除了对标签函数的依赖，使非马尔可夫奖励学习能够直接应用于标准 RL 环境。
2. 开发端到端学习算法 (LSRM)： 实现了从标准环境输出直接学习策略和可解释的奖励结构（SRM），无需人工先验知识。
3. 理论保证： 证明了 QSRM 的收敛性，并证明了 LSRM 在无限次观测下能以概率 1 学习到与真实奖励机器等价的 SRM（Almost Surely Equivalent）。
4. 可解释性： 学习到的 SRM 以符号公式形式呈现，为用户提供了任务结构的直观解释（例如：任务分几步，每一步的数值条件是什么）。

4. 实验结果 (Results)

实验在离散（有限状态）和连续（无限状态）环境中进行，包括修改版的"Office World"和"Mountain Car"。

• 性能对比 (RQ1 & RQ2)：

  • 基线方法： 标准 Q-Learning 和 DQN（即使使用帧堆叠）在复杂非马尔可夫任务上表现较差，无法有效学习历史依赖。
  • SRM 方法： (D)QSRM 与现有的 (D)QRM 性能完全一致，均能收敛到最优策略，且优于基线方法。
  • 结论： SRM 在不牺牲性能的前提下，移除了标签函数的限制。

• 端到端学习 (RQ3 & RQ4)：

  • 策略学习： LSRM-GF 和 LSRM-FT 在离散环境中成功收敛到最优策略；在连续环境中虽未达理论最优，但获得了极高的性能值。
  • SRM 推断：
    • LSRM-GF 学习到的 SRM 与真实 SRM 在逻辑上几乎必然等价（结构可能略有不同，但行为一致）。
    • LSRM-FT 学习到的 SRM 结构高度接近真实 SRM。虽然在连续空间中由于数值精度问题可能存在微小差异，但足以支撑智能体获得高性能。
  • 可解释性验证： 实验可视化显示，学习到的 SRM 公式准确捕捉了任务的关键数值边界（如坐标范围），验证了其作为任务解释工具的有效性。

5. 意义与影响 (Significance)

• 通用性提升： 该方法使得非马尔可夫奖励学习能够直接应用于现有的标准 RL 库（如 Gymnasium），无需修改环境代码或设计复杂的标签函数。
• 降低门槛： 通过 LSRM-FT，即使是非专家用户也能让智能体自动发现复杂的任务逻辑和奖励结构，无需提供领域知识。
• 可解释 AI (XAI)： 学习过程不仅产出策略，还产出人类可读的符号规则（SRM），揭示了“智能体是如何理解任务目标”的，增强了 RL 系统的透明度和可信度。
• 未来方向： 为处理更复杂的连续控制任务和自动化任务规范生成提供了新的技术路径。

总结： 本文通过引入符号逻辑直接处理环境状态，成功解决了传统奖励机器依赖人工标签的痛点，提出了一套从标准环境端到端学习非马尔可夫任务的高效、可解释框架。