💻 computer science

Active Reward Machine Inference From Raw State Trajectories

本文提出了一种在缺乏奖励、标签或机器节点观测的情况下，直接从原始状态轨迹中主动学习奖励机器并优化数据效率的方法，并通过网格世界实验验证了其有效性。

原作者： Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

发布于 2026-04-10

📖 1 分钟阅读☕ 轻松阅读

原作者： Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于**“教机器人理解复杂任务”**的有趣故事。

想象一下，你正在训练一只机器狗去执行一个复杂的任务，比如“先去厨房拿杯子，然后去客厅倒水，最后去阳台晒太阳”。

1. 核心难题：机器人只有“眼睛”，没有“说明书”

在传统的机器人训练方法中，人类专家需要给机器人写一本详细的“说明书”（在论文里叫奖励机器 Reward Machine）。这本说明书会告诉机器人：

“如果你看到了杯子（状态），你就进入了‘拿杯子’阶段。”
“如果你看到了水，你就进入了‘倒水’阶段。”
“如果你走到了阳台，任务就完成了。”

问题在于： 在现实世界中，给机器人写这本说明书非常困难。世界太复杂了，人类很难把每一个步骤、每一个触发条件都精确地写出来。如果写错了，机器人就会做出奇怪的行为（比如拿着杯子去倒水，却忘了先拿杯子）。

这篇论文的突破点在于： 我们不再需要人类专家来写这本说明书。我们只需要给机器人看它**“怎么做的”（也就是它走过的路、看到的场景），然后让机器人自己“悟”**出这本说明书是怎么写的。

2. 我们的方法：像侦探一样“逆向推理”

这就好比你在玩一个侦探游戏：

已知线索： 你看到了一只机器狗在房间里跑来跑去。它先去了厨房，拿了东西，又去了客厅。
未知真相： 你不知道它脑子里在想什么（比如它是不是在“拿杯子”？还是“找玩具”？）。
目标： 你要根据它跑路的轨迹，猜出它脑子里的“任务流程图”（奖励机器）和“识别标签”（比如看到什么算作“杯子”）。

难点： 机器人走的每一步路，可能对应着无数种可能的“任务流程图”。就像你看到一个人从 A 走到 B，他可能是去上班，也可能是去买菜，还可能是去约会。怎么确定他到底是在做什么？

3. 解决方案：两个步骤的“魔法”

作者提出了一个聪明的两步走策略：

第一步：用“逻辑锁”缩小范围（SAT 求解）

作者发明了一种数学方法（基于 SAT 求解器），就像给侦探游戏加了很多把“逻辑锁”。

如果机器人走的路 A 和路 B，最后的行为不一样（比如路 A 它停了，路 B 它继续跑），那么这两条路在“任务流程图”里一定属于不同的阶段。
通过收集这些“行为不同”的线索，算法可以排除掉成千上万种错误的“任务流程图”，只留下几种可能的候选者。

第二步：主动出击，只问关键问题（主动学习）

这是论文最精彩的部分。

传统做法（笨办法）： 为了搞清楚真相，侦探把机器人所有可能走的路（哪怕有几亿条）都跑一遍，记录下来，然后慢慢分析。这太慢了，而且电脑内存会爆炸。
作者的做法（聪明办法）： 侦探只问机器人**“最关键”**的问题。
- 算法会想：“如果机器人走这条路，可能会让我排除掉一半的错误猜想；如果走那条路，可能什么都排除不了。”
- 于是，它只让机器人去走那条**“最能排除错误猜想”**的路。
- 这就好比玩“猜词游戏”，你问“是动物吗？”比问“是猫吗？”更能快速缩小范围。

4. 实验结果：又快又省

作者在虚拟的“网格世界”（就像超级玛丽里的地图）里测试了这个方法：

任务 1（仓库搬运）： 机器人需要先去取货，再去送货，还要避开危险区。
任务 2（巡逻）： 机器人需要按顺序 A->B->C->D 巡逻。

结果令人惊讶：

全量搜索（笨办法）： 需要记录几亿条路径，占用 24GB 内存，算了几千秒还没算完。
主动学习（聪明办法）： 只问了很少的问题，只用了 0.15GB 内存，速度快了 2 倍，而且完美还原了正确的任务流程图。

5. 总结：给机器人装上“自我进化”的大脑

这篇论文的核心思想可以总结为：
“不要试图把所有路都走一遍，要学会问对问题。”

以前，我们要教机器人做复杂任务，必须像教小学生一样，把每一步都手把手教好（写死规则）。
现在，我们只需要给机器人看它成功的“背影”（轨迹），它就能通过**“主动提问”和“逻辑推理”**，自己把背后的任务逻辑（奖励机器）和识别规则（标签）给“悟”出来。

这不仅让机器人更聪明，能处理更复杂的任务，还大大节省了计算资源，让未来的机器人能在更复杂的现实世界中（比如真实的工厂、家庭）自主学习和工作。

一句话比喻：
这就好比给机器人一个**“黑盒”，我们不看里面的说明书，只通过观察它“怎么走路”，并“聪明地引导它多走几步关键的路”，就能把里面的说明书“反推”**出来，而且比人工写还要快、还要准。

论文技术总结：从原始状态轨迹进行主动奖励机器推断

1. 研究背景与问题定义

背景：
多阶段任务（Multi-stage tasks）在机器人应用中非常普遍，通常涉及按特定顺序满足中间目标。奖励机器（Reward Machines, RMs）作为一种有限状态自动机，能够有效地编码此类任务的逻辑结构和进度。然而，传统方法依赖人工专家手动定义奖励机器及其标签函数（Labeling Function，将底层状态映射为高层命题），这在复杂环境中既耗时又容易出错。

核心问题：
现有的奖励机器学习方法通常假设已知状态标签、奖励信号或自动机节点。本文旨在解决一个**信息极度匮乏（Information-scarce）**的设定：

输入： 仅包含原始状态轨迹（Raw State Trajectories）和由专家策略诱导的历史策略（History Policy）。
未知： 没有奖励信号、没有状态标签（原子命题）、没有奖励机器的节点结构。
目标： 直接从原始状态轨迹中推断出奖励机器模型（包括状态转移函数 $\delta_u$ ）和标签函数（ $L$ ），使得推断出的策略与观察到的专家策略在行为上等价。

挑战：
这是一个病态问题（Ill-posed problem），因为可能存在多个不同的奖励机器和标签函数组合都能产生相同的策略行为。此外，直接枚举所有可能的轨迹会导致组合爆炸，计算和存储成本极高。

2. 方法论 (Methodology)

论文提出了一套基于**布尔可满足性（SAT）的推断框架，并结合了主动学习（Active Learning）**策略来优化效率。

2.1 形式化定义

历史策略 ( $\pi_h$ )： 定义为 $\pi_h(a|s, \tau) = \pi_{Prod}(a|s, \delta^*_u(u_I, L(\tau)))$ 。它仅基于可观测的状态序列 $\tau$ 来预测动作，隐含了奖励机器的内部状态。
策略等价性： 如果两个标记的奖励机器诱导出的历史策略相同，则称它们是策略等价的。
问题分解：
- (P1) 确定是否存在一个足够的深度 $l^*$ ，使得在该深度下的历史策略足以唯一确定（或缩小到等价类）奖励机器。
- (P2) 在给定深度下，寻找最小节点数的标记奖励机器。

2.2 基于 SAT 的联合推断 (Learning a Labeled RM)

作者将学习 $\delta_u$ 和 $L$ 的问题转化为一个 SAT 问题（Problem 1）：

编码： 将转移函数 $\delta_u$ 和标签函数 $L$ 编码为二进制变量。
负样本约束 (Negative Examples)： 核心约束来源于“负样本”。如果两条状态轨迹 $\tau$ 和 $\tau'$ 在相同状态 $s$ 下导致了不同的动作分布（即 $\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$ ），那么根据引理 1，它们在奖励机器中必须导致不同的节点状态（ $\delta^*_u(u_I, L(\tau)) \neq \delta^*_u(u_I, L(\tau'))$ ）。
约束条件：
1. 函数定义约束（每个输入对应唯一输出）。
2. 锚定约束（消除对称性，如固定初始状态标签）。
3. 兼容性约束： 所有负样本对必须导致不同的节点。
4. 非停滞约束（可选）：防止在同一命题下重复自环，适用于多阶段任务。

2.3 理论保证：充分深度 (Sufficient Depth)

命题 1： 证明了存在一个充分深度 $l^* = |S| \cdot u_{max}^2$ （其中 $|S|$ 是状态数， $u_{max}$ 是奖励机器节点数的上界）。
意义： 如果在该深度下 SAT 问题有解，则对于任何更深的深度，解集不会进一步缩小（即不会引入新的约束）。这为算法的终止提供了理论依据。

2.4 主动扩展算法 (Active Extension)

由于穷举所有深度为 $l$ 的轨迹会导致指数级增长（存储和计算瓶颈），作者提出了主动扩展策略：

核心思想： 不需要检查所有轨迹，只需查询那些能最大程度区分候选解的轨迹对。
算法流程 (Algorithm 1)：
1. 采样： 从当前可行的 SAT 解集中采样一部分候选模型。
2. 生成候选对： 寻找状态轨迹对 $\{\tau, \tau'\}$ ，使得在当前候选模型集中，约有一半模型认为它们到达同一节点，另一半认为到达不同节点（即最大化“节点分裂”或“节点合并”的不确定性）。
3. 质量评估： 计算轨迹对的“质量”，即它能消除多少候选模型。
4. 查询与更新： 向历史策略查询这些高价值轨迹对的真实行为。如果确认为负样本，则将其加入 SAT 约束集，重新求解，从而剪枝解空间。
5. 迭代： 重复直到解空间收敛到单一模型（或等价类）。

3. 实验结果 (Results)

作者在网格世界（Grid World）环境中进行了验证，包括两个任务：pick_n_drop（取货与投递）和 patrolABCD（按顺序巡逻）。

任务 1 (pick_n_drop)：
- 使用深度为 9 的专家历史策略，算法成功恢复了真实的奖励机器结构。
- 主动学习对比： 从深度 $l=3$ 开始（此时解空间超过 15 万），通过主动查询，仅需深度 12 即可在 100% 的试验中收敛到真实解。相比之下，随机基线在深度 20 时仍无法找到有效约束。
任务 2 (patrolABCD)：
- 在深度 $l=9$ 时，穷举法产生的负样本数量高达 4.14 亿 ( $414M$ )，导致内存瓶颈（需 24.76 GB）。
- 主动学习优势： 主动方法仅需查询约 29.2 万 个负样本，内存占用降至 0.147 GB（减少两个数量级）。
- 运行时间： 主动方法的总运行时间约为 3545 秒，而穷举法（受限于 SAT 求解时间）超过 7185 秒，实现了近 2 倍 的加速。
- 收敛性： 在深度 13 时，主动方法（ $N_{active}=200$ ）在 96.6% 的试验中收敛到真实解集（考虑重命名等价）。

4. 主要贡献 (Key Contributions)

信息匮乏设定下的新范式： 首次提出在完全未知奖励、标签和自动机结构的情况下，仅凭原始状态轨迹和历史策略来推断奖励机器和标签函数。
联合推断框架： 提出了一种基于 SAT 的联合推断方法，同时学习奖励机器的转移结构和状态到命题的映射（标签函数）。
理论充分性证明： 证明了存在一个有限的“充分深度” $l^*$ ，在此深度之后，增加更多轨迹数据不会进一步约束解空间，为算法终止提供了理论保证。
主动学习策略： 设计了一种基于“体积消除（Volume Removal）”的主动查询算法，通过选择最具信息量的轨迹对，显著降低了内存需求和计算时间，解决了穷举法无法处理大规模状态空间的问题。
实证有效性： 在网格世界实验中展示了该方法在恢复真实任务结构方面的有效性，并证明了其在内存和计算效率上的巨大优势。

5. 意义与展望 (Significance)

自动化任务设计： 该方法消除了对人工专家手动定义复杂任务逻辑和标签的依赖，使机器人能够从专家演示中自主发现任务的“隐藏”阶段结构。
可扩展性： 通过主动学习解决了状态空间爆炸问题，使得从原始数据推断复杂多阶段任务成为可能，为大规模机器人应用奠定了基础。
记忆结构的理解： 论文从理论角度探讨了序列决策中“记忆”的来源（任务结构 vs. 部分观测），并展示了如何直接从策略数据中揭示这种任务结构记忆。
未来方向： 作者指出当前方法假设离散状态空间和已知最优策略的历史分布。未来的工作包括处理连续状态空间、从感知表示（如图像）直接学习标签函数，以及将框架扩展到部分可观测马尔可夫决策过程（POMDP）的学习中。

总结： 这篇论文通过结合形式化验证（SAT）和主动学习，成功解决了在缺乏先验知识的情况下从原始轨迹中逆向工程奖励机器的问题，为机器人自主任务学习提供了强有力的理论工具和高效算法。