[Paper] 基于模型的强化学习在离散动作非马尔可夫奖励决策过程中的研究

Source: arXiv - 2512.14617v1

概述

本文介绍了 QR‑MAX，一种基于模型的强化学习算法，能够处理奖励依赖于整个动作历史的任务——而不仅仅是当前状态。通过使用奖励机将转移学习与奖励历史处理分离，作者实现了可证明的近最优性且具有多项式样本复杂度，并进一步将该思想扩展到连续状态问题，提出了 Bucket‑QR‑MAX。

关键贡献

• First PAC‑guaranteed model‑based RL algorithm for discrete‑action NMRDPs – QR‑MAX 学习最优策略，并对所需样本数量提供可证明的上界。
• Factorization via reward machines – 通过奖励机进行因式分解——将非马尔可夫奖励成分从马尔可夫动力学中分离出来，简化学习和分析。
• Extension to continuous state spaces – Bucket‑QR‑MAX 使用基于 SimHash 的离散化方法，在保持因式结构的同时，无需手工网格或神经近似器。
• Empirical validation – 实证验证——在日益复杂的基准测试中，展示了相较于领先的模型基线更高的样本效率和鲁棒性。

方法论

1. Reward Machines (RMs) – 有限状态自动机，用于编码时间奖励规范（例如，“在 5 步内先访问 A 再访问 B”）。RM 记录奖励计算所需的历史信息，而底层环境仍保持马尔可夫性。

2. QR‑MAX Core

   • Transition Model：使用标准表格估计器学习（计数 → 经验概率）。
   • Reward Model：由 RM 管理；每个 RM 状态都有自己的奖励分布，独立于转移模型进行学习。
   • Planning：采用经典 Q‑learning with MAX 的变体（因此得名），在更新转移模型的 Q 值和通过 RM 传播奖励之间交替进行。

3. Bucket‑QR‑MAX for Continuous States

   • 使用 SimHash 将高维连续观测映射到离散的 “bucket”。
   • 哈希函数具备局部敏感性，保留相似性，使相邻状态共享同一 bucket，保持因式分解学习流水线的完整性。

整体流水线保持简洁：收集经验 → 更新转移计数 → 更新 RM 奖励 → 重新计算 Q 值 → 贪婪行动。

结果与发现

• 样本效率：QR‑MAX 在所需环境交互次数上比最佳模型基准少 5‑10 倍，即可达到接近最优的性能。
• 鲁棒性：因子化方法避免了奖励历史信息的灾难性遗忘，使得在不同随机种子下学习曲线更为稳定。
• 可扩展性：Bucket‑QR‑MAX 基于哈希的离散化能够扩展到连续域，无需手动调节网格分辨率。

实际意义

• 生产强化学习中的时序逻辑：工程师可以将复杂的任务规范（例如，“过程 A 必须在 B 之前完成，并在截止时间内”）直接嵌入学习循环，而无需手工设计奖励函数。
• 降低数据收集成本：PAC 保证可以估计实现目标性能所需的回合数，对昂贵的仿真或真实机器人非常有价值。
• 即插即用集成：QR‑MAX 可与任何现成的基于模型的规划器配合使用；唯一额外的组件是奖励机，可从高级规范（例如 LTL 公式）生成。
• 连续状态应用：当需要快速、稳定的学习时，Bucket‑QR‑MAX 提供了相较于深度函数逼近器的轻量级替代方案（例如边缘设备、低延迟控制回路）。

限制与未来工作

• 离散动作假设：当前的理论和保证仅适用于有限动作集合；将其扩展到连续动作需要额外的分析。
• 奖励机构建：虽然论文展示了如何手工构造奖励机，但从自然语言或高级规范自动合成仍是一个未解决的挑战。
• 哈希桶的可扩展性：在极高维空间中，哈希冲突可能会降低性能；自适应哈希或混合神经‑哈希方案被建议作为未来的研究方向。

作者

• Alessandro Trapasso
• Luca Iocchi
• Fabio Patrizi

论文信息

• arXiv ID: 2512.14617v1
• 分类: cs.LG, cs.AI
• 出版时间: 2025年12月16日
• PDF: 下载 PDF