随机奖励机SRMI：处理非马尔可夫与随机奖励的强化学习新框架

1. 项目概述与核心问题

在强化学习领域，我们通常假设智能体所处的环境是“马尔可夫”的——即下一个状态和即时奖励只取决于当前状态和当前动作。这个假设是许多经典算法（如Q-learning、策略梯度）能够有效工作的基石。然而，当你试图将强化学习应用到一些更贴近现实的复杂任务时，比如教一个机器人完成一套组装工序，或者在一个策略游戏中制定长期计划，你会发现一个尴尬的现实：最有意义的奖励往往不是“即时”的，而是“延迟”且“有条件”的。

举个例子，想象一个采矿游戏。智能体的终极目标是“卖出矿石赚钱”。但这个奖励不会在你“挖到矿石”的瞬间发放。正确的流程可能是：1) 找到装备，2) 开采金矿或铂金矿，3) 将矿石安全运送到市场。只有完成这一系列动作后，奖励才会到来。更复杂的是，奖励本身可能还是随机的——金矿的纯度有波动，市场价格也在变化，导致最终卖出的价格在一个区间内随机分布。这就是一个典型的非马尔可夫且**随机（带噪声）**的奖励函数。

传统的“奖励机”正是为了解决非马尔可夫奖励而生的。它本质上是一个有限状态自动机，其状态用于记忆智能体历史中与奖励相关的高层事件（如“已获取装备”、“已开采金矿”）。通过将环境状态与奖励机状态构成联合状态空间，原本非马尔可夫的奖励问题就被转化成了一个扩大的、但符合马尔可夫性质的MDP，从而可以套用标准强化学习算法。这听起来很完美，对吧？

但这里存在一个实践中致命的缺陷：现有奖励机及其学习算法，都假设奖励是确定性的。在上述采矿例子中，这意味着算法期望“卖出金矿”永远精确地奖励1.0，“卖出铂金矿”永远精确地奖励1.1。一旦奖励存在哪怕一点点噪声（比如实际奖励是0.95或1.05），整个学习框架就会崩溃。算法要么找不到任何与所有观测经验一致的奖励机，要么会学出一个极其庞大、过度拟合噪声的奖励机，导致无法收敛或策略性能低下。

因此，本文介绍的工作——随机奖励机及其对应的SRMI算法——的核心价值，就是填补了这一理论与实践的鸿沟。它承认并建模了奖励的随机性，使得奖励机框架能够真正应用于充满噪声的真实世界任务。这不是一个微小的改进，而是让一个强有力的形式化工具有了落地应用的坚实桥梁。

2. 随机奖励机：核心设计思路与原理

2.1 从确定性到随机性：模型的根本性扩展

要理解SRM，首先要彻底理解经典奖励机的局限性。经典奖励机A = (V, v_I, 2^P, δ, σ)中，输出函数σ: V × 2^P → R映射到一个具体的实数值奖励。这意味着对于相同的状态-标签对(v, ℓ)，输出永远是同一个数字。

随机奖励机的关键扩展在于输出空间。在SRM的定义A = (V, v_I, 2^P, O, δ, σ)中，输出函数σ: V × 2^P → O的陪域O不是一个实数集，而是一个累积分布函数的有限集合。简单来说，每个输出不再是一个数字，而是一个概率分布。

注意：这里选择CDF而非概率密度函数是为了数学上的严谨性，它能统一描述离散和连续分布。在实现中，我们通常处理有界的连续分布，例如均匀分布U([a, b])、截断正态分布等。

为什么是分布，而不是简单的“均值+方差”？你可能会想，为什么不直接输出一个带噪声的实数值（比如均值+高斯噪声）？关键在于结构化。奖励机中的每个转移边都对应一个潜在的“语义”。在采矿例子中，“从v3（已获金矿状态）经标签M（到达市场）转移到终止状态vT”这条边，其奖励分布U([0.8, 1.2])封装了“卖出金矿”这一事件的所有可能结果。这个分布是此边固有的属性。如果我们只建模一个全局噪声模型，就丢失了不同语义事件可能具有不同噪声特性（如不同区间、不同分布形状）这一重要信息。SRM显式地将噪声与奖励机的结构耦合，极大地增强了模型的表达能力和可解释性。

2.2 期望等价性：收敛性的理论基石

引入随机性后，一个自然的问题是：我们还需要精确地还原出真实的环境奖励分布吗？答案是否定的，而且过于追求精确反而会带来麻烦。论文中提出的期望等价性概念，是SRMI算法能收敛的理论核心。

定义：两个随机奖励机A和B是期望等价的，当且仅当对于任何可能的标签序列，它们输出的奖励分布序列，其每个位置上的分布的期望值都完全相同。

引理1：如果两个SRM是期望等价的，那么它们在相同环境下会诱导出相同的最优策略。

这个引理非常强大。它意味着，对于寻找最优策略这个终极目标而言，我们不需要完全复现真实的奖励分布D([a, b])，而只需要学习到一个与之期望值相同的分布D'([a', b'])即可。这大大降低了学习任务的难度。例如，真实分布是U([0.9, 1.1])，期望为1.0。我们学到的分布是U([0.8, 1.2])，期望也是1.0。尽管分布形态不同，但根据引理1，它们对于策略学习是“等效”的。

实操心得：在实际实现中，这意味着我们可以将学习目标从“拟合分布”简化为“拟合期望值”，同时维护一个以该期望值为中心、宽度为2ϵ_c的区间（ϵ_c是已知的噪声分散度上界）。这直接将一个复杂的分布估计问题，转化为了一个带约束的均值估计与结构学习问题。

2.3 核心假设：噪声不能完全掩盖信号

为了保证算法能学出正确的结构，论文提出了一个重要的假设1。这个假设有点绕，但用大白话解释就是：环境中不同的奖励分布，如果它们的支撑集（即奖励可能取值的区间）能够被同一个以某个点为中心、半径为ϵ_c的区间所覆盖，那么这些分布的期望值必须相等。

为什么需要这个假设？考虑两个分布：U([0.1, 0.2])和U([0, 1])。假设ϵ_c = 0.6（因为最大区间宽度是1，一半是0.5，取稍大的0.6）。那么，这两个分布的区间[0.1, 0.2]和[0, 1]都能被区间[0.1-0.6, 0.2+0.6] = [-0.5, 0.8]所覆盖。然而，它们的期望值（0.15 vs 0.5）却不同。这就违反了假设1。

如果这个假设被违反，会发生什么？智能体观察到来自这两个分布的奖励样本，由于ϵ_c较大，算法可能会误认为这些样本都来自同一个“大”分布（期望值在0.15和0.5之间的某个值），从而无法区分背后其实是两个不同的语义事件（对应奖励机中两条不同的转移边）。这将导致学习到的奖励机结构错误。

这个假设合理吗？作者认为，在绝大多数实际场景中是合理的。它要求环境的“信号”（不同事件的平均奖励差异）必须大于“噪声”的分散程度。如果噪声大到足以让两个不同含义的事件产生的奖励看起来完全无法区分，那么任何基于奖励差异的学习方法都会失效。这更像是对问题本身“可学习性”的一个基本要求，而非算法的限制。

3. SRMI算法：分步拆解与实操要点

SRMI算法的核心思想是交织进行策略学习和奖励机推断。它从一个初始的假设SRM开始，在交互中不断收集轨迹，一旦发现与当前假设矛盾的轨迹（反例），就尝试修正或重新推断奖励机。

3.1 算法主循环与两种反例

算���1展示了SRMI的主干。我们重点关注其核心逻辑：

1. 运行QRM：使用当前的假设SRMH和对应的Q函数集，在环境中运行一个回合，生成一条轨迹（标签序列λ和奖励序列ρ），并将其加入总轨迹集A。
2. 检测反例：检查当前轨迹(λ, ρ)是否与假设Hϵ_c-一致。即，对于轨迹中的每一步，观察到的奖励r_i是否落在假设SRM在该步输出的分布期望值的±ϵ_c范围内。如果不是，则这是一个反例，加入反例集X。
3. 处理反例：
   • 类型1反例（微调）：如果存在一个与H图同构的SRMZ，仅通过调整其输出分布的期望值（而不改变状态转移结构），就能使其与当前所有反例集X一致。那么，我们就用Z替换H。这相当于“修正”了现有结构的参数。
   • 类型2反例（重构）：如果找不到这样的Z，说明当前假设的结构（状态数量、转移关系）不足以解释新数据。此时，需要调用约束求解器，基于当前所有反例集X，重新推断一个最小且一致的新SRM结构H'。
4. 参数估计：无论通过哪种方式得到新的假设结构H'，都需要用历史轨迹集A中所有与H'一致的轨迹，来重新估计每条转移边输出分布的期望值。这一步通过Estimates函数完成。
5. 重置与继续：更新假设SRM，并重新初始化Q函数（因为环境模型变了），开始新的学习循环。

区分两种反例的实操意义：

• 类型1就像你发现房间温度计读数总是比实际低2度。你不需要换个温度计，只需给它加一个+2度的校准偏移量。在SRM中，这对应着某些转移边的奖励期望需要调整。
• 类型2就像你发现温度计除了读数偏移，还会在潮湿天气完全失灵。这说明温度计的内部结构（可能缺少防潮部件）有问题，必须换一个不同设计的产品。在SRM中，这对应着需要增加新的状态或改变状态间的转移逻辑来捕捉之前未建模的依赖关系。

3.2 约束求解：如何从反例中推断新结构

这是SRMI算法中最具技术挑战性的部分，也是其区别于简单基线方法的关键。当遇到类型2反例时，算法需要解决任务1：给定反例集X和噪声分散度ϵ_c，生成一个与X中所有轨迹ϵ_c一致的最小SRM。

如何将这个问题转化为约束可满足问题？论文的解决方案是对现有JIRP算法约束编码的扩展。对于一个给定的目标状态数n，我们创建以下变量：

• 结构变量 (d_{p,ℓ,q})：布尔变量。为真表示在假设SRM中，从状态p读入标签ℓ后，会转移到状态q。
• 输出变量 (o_{v,ℓ})：实数变量。表示在状态v读入标签ℓ后，输出分布的期望值。
• 运行变量 (x_{λ,v})：布尔变量。为真表示在读取标签序列前缀λ后，假设SRM处于状态v。

然后，我们构建以下约束：

1. 初始状态约束：机器必须从唯一的初始状态开始。
2. 确定性转移约束：对于每个状态和标签，必须有且仅有一个后继状态。
3. 运行一致性约束：这些约束将x变量与d变量联系起来，确保对于反例中的每个前缀，机器的运行路径是唯一且符合转移函数的。
4. ϵ_c一致性约束：这是核心。对于反例中的每一步，如果机器在读取某个前缀后处于状态v，并且接下来看到的标签是ℓ，那么这一步观察到的奖励r必须满足| o_{v,ℓ} - r | ≤ ϵ_c。这确保了假设的输出与观测数据相容。

将这些约束组合成一个公式Φ_{X,ϵ_c}^n。如果这个公式可满足，那么从一个满足解中我们可以直接提取出一个具有n个状态、且与所有反例一致的SRM。为了找到最小的SRM，我们从n=1开始，依次增加n并求解约束问题，直到找到一个可满足的解为止。

提示：在实际使用中，直接求解这种包含布尔和实数变量的混合约束可能很耗时。论文使用了Z3 SMT求解器。对于大规模问题，可能需要设计更高效的启发式方法或利用问题的特殊结构。

3.3 Estimates步骤：为什么用中程数而非算术平均

在Estimates函数（算法2）中，有一个关键选择：对于每个转移边(v, ℓ)，收集所有相关奖励样本到集合r(v, ℓ)后，计算其期望估计值时，使用的是中程数：µ' = (max(r(v,ℓ)) + min(r(v,ℓ))) / 2，而非简单的算术平均。

为什么这么做？根本原因是为了保证修改后的假设SRM仍然与反例集X保持ϵ_c-一致性。

• 算术平均的缺陷：假设我们收集到的样本是{0.9, 1.0, 1.1}，真实分布是U([0.8, 1.2])，ϵ_c=0.2。算术平均是1.0。如果我们设置输出为U([1.0 - 0.2, 1.0 + 0.2]) = U([0.8, 1.2])，这看起来没问题。但现在考虑另一个场景：真实分布是U([0.9, 1.1])，但我们由于采样偏差，只收集到{0.9, 1.1}两个极端样本。算术平均仍是1.0，区间设为[0.8, 1.2]。然而，原始反例中可能包含一个奖励为0.85的样本，它对于真实分布U([0.9, 1.1])是不可能的（超出范围），但对我们估计出的U([0.8, 1.2])却是“一致”的。这可能导致算法错误地接受了原本不一致的假设。
• 中程数的优势：中程数直接由观测样本的极值决定。µ' ± ϵ_c构成的区间必然包含所有已观测到的样本。这提供了一个保守但安全的估计，确保了新假设与所有历史一致轨迹A的相容性。在样本量足够大时，中程数会收敛到真实区间的中点，而对于对称分布，中点就是期望值，因此它也是一个无偏估计。

一个重要的折衷：中程数对离群值敏感。在学习的早期，样本量少，一个异常的极端值可能会使估计区间偏离真实区间。这就是为什么算法还需要依赖持续的探索和反例发现来逐步修正估计。在附录中，论文也讨论了非对称分布的处理，此时需要维护一个辅助假设G来使用算术平均进行无偏的策略学习，同时主假设H仍使用中程数以保持一致性。

4. 实验验证与对比分析

论文通过两个案例研究验证了SRMI的有效性：采矿和收获。

4.1 实验设置与对比基线

• 环境：
  1. 采矿：如前所述，智能体需要按顺序完成“找装备(E) -> 挖矿(P/G) -> 去市场(M)”才能获得随机奖励，并避免陷阱(T)。
  2. 收获：智能体需要执行“种植(P) -> 浇水(W) -> 收获(H) -> 出售(S)”的序列。奖励取决于收获时环境的“状态”（好G、中M、差B），该状态按MDP动态变化（见图4b），奖励均值因此不同且随机。
• 对比算法：
  1. SRMI：本文提出的算法。
  2. 基线算法：一种朴素的处理噪声的方法。当遇到反例时，暂停QRM，并重复执行该轨迹多次（例如20次），收集足够样本以平均掉噪声，得到近似的期望奖励，然后再用传统的确定性奖励机推断方法（如JIRP）学习。
  3. JIRP：经典的（确定性）奖励机推断算法。它完全忽略噪声，试图直接从带噪声的奖励中学习一个确定性奖励机。
• 评���指标：最近100回合的平均累积奖励（学习曲线）。

4.2 结果解读与深度分析

采矿环境结果分析（图3a）：

• SRMI：成功学习并快速收敛到接近最优的奖励（~1.0）。其学习曲线平滑上升，表明算法能稳定地识别出奖励结构并优化策略。
• 基线算法：性能明显差于SRMI，收敛速度慢。其根本缺陷在于需要重复执行轨迹以获取样本。在动态或随机环境中，完全复现一条轨迹并非总是可行（例如，下一状态由概率转移函数决定）。即使可行，这种“重放”也极其低效，浪费了大量本可用于探索的交互次数。
• JIRP：完全失败，最终超时。因为它试图为每一个略有不同的奖励样本创建新的状态或转移，导致推断出的奖励机规模爆炸（过度拟合噪声），无法收敛到一个简洁有效的模型。

收获环境结果分析（图5a）：

• 这个环境更凸显了基线算法的弱点。由于环境动态是随机的（状态在G/M/B之间随机转移），智能体几乎不可能两次看到完全相同的轨迹。因此，基线算法要求“重复执行轨迹”的前提经常无法满足，导致其陷入不断尝试收集样本但屡屡失败的困境，学习完全停滞。
• SRMI则不受此影响，因为它不依赖轨迹重放，而是直接利用单次轨迹中的奖励信息，通过约束求解来更新假设，从而成功学习。

非随机环境下的表现（图3b, 5b）：

• 当奖励是确定性的时候，SRMI、基线算法和JIRP表现相当。这证明了SRMI的通用性：即使在无噪声的理想情况下，它也不会引入额外的性能开销或复杂度。SRMI在遇到噪声时能优雅降级（degrade gracefully）为处理确定性的情况。

与深度强化学习方法的对比（图6）：

• 论文还将SRMI与DDQN（输入过去200个标签的历史）和DHRL（基于奖励机结构的深度分层RL）进行了对比。
• SRMI显著优于这两种方法。这强调了利用问题结构先验知识（以SRM形式）的重要性。纯粹的端到端深度方法（如DDQN）需要从高维历史中艰难地提取出非马尔可夫依赖关系，而SRMI通过学习一个显式的、可解释的自动机模型，极大地降低了学习难度，加速了收敛。

5. 实现细节、常见问题与避坑指南

5.1 关键参数选择与调优

1. 噪声分散度上界 (ϵ_c)：这是最重要的先验知识。ϵ_c需要大于等于真实奖励分布支撑集宽度的一半。如果设得太小，算法会变得非常敏感，将正常的奖励波动误认为是结构性反例，导致频繁重构奖励机，不稳定。如果设得太大，算法会过于宽容，可能无法区分期望值不同但区间有重叠的分布，导致学习到错误的结构。建议：如果对任务有领域知识，应尽量给出一个紧致的估计。也可以通过初步探索，观察奖励的波动范围来设定。
2. 探索策略：论文使用了标准的ϵ-greedy策略。在奖励机学习中，探索尤为重要，因为需要收集到足够多样、能触发不同奖励机状态转移的轨迹。可以结合一些基于好奇心的探索机制，鼓励智能体覆盖更多样的标签序列。
3. 约束求解器调用频率：每次遇到类型2反例都调用求解器是昂贵的。可以设置一个阈值，例如积累一定数量的类型2反例后再进行重构，或者在连续多次遇到类型1反例（表明参数需要调整）后，再考虑是否结构有问题。

5.2 典型问题与排查思路

问题1：学习过程震荡，奖励机假设频繁在几个结构之间切换。

• 可能原因1：ϵ_c设置过小，导致算法将采样噪声误判为结构性矛盾。
  • 排查：检查反例集中奖励偏差是否普遍只略大于ϵ_c。如果是，适当增大ϵ_c。
• 可能原因2：环境奖励分布的非对称性较强，而算法使用了对称分布假设（中程数估计）。
  • 排查：实现附录B中针对非对称分布的扩展版本（使用辅助假设G和算术平均）。
• 可能原因3：早期样本过少，Estimates步骤的估计极不准确。
  • 排查：在早期学习阶段，可以引入一个“冻结期”，在收集到足够多的轨迹（如100条）之前，只进行类型1反例的修正（参数调整），不触发类型2重构。

问题2：学习停滞，累积奖励不再提升。

• 可能原因1：学习到的奖励机结构陷入局部最优，无法表示真实的最优策略所需的结构。
  • 排查：这是结构化探索的固有问题。可以尝试定期注入一些“结构性探索”噪声，例如以很小概率强制假设奖励机跳转到一个随机状态，或者尝试合并/拆分状态，看看是否能带来性能提升。
• 可能原因2：ϵ_c设置过大，导致算法无法分辨两个本应不同的奖励分布，学到的奖励机过于简单，丢失了关键信息。
  • 排查：手动检查学到的SRM，看其是否过于简单。与任务的最优策略所需逻辑进行对比。如果怀疑是此原因，需调小ϵ_c并重新学习。

问题3：约束求解耗时过长，影响学习效率。

• 可能原因：反例集X过大，或设定的最大状态数n搜索上限过高。
  • 优化：
    • 剪枝反例集：维护反例集时，只保留那些“关键”的反例，例如那些导致结构变化的反例，或者覆盖了独特前缀的反例。
    • 增量式求解：不要每次都从头求解。当新增一个反例时，可以尝试在之前求解的基础上添加新约束，看是否仍然可满足。
    • 设定合理的状态数上限：根据任务复杂度，预先设定一个合理的最大状态数，避免无意义的搜索。

5.3 扩展与进阶思考

1. 输出分布的泛化：目前SRM假设输出是区间上的均匀分布。可以扩展为更一般的分布族（如高斯分布、指数分布），只需在约束中修改一致性条件（如|r - µ| ≤ kσ），并在Estimates步骤中估计分布参数（如均值和方差）。
2. 部分可观测性：当前框架假设智能体能完美观测到高层标签ℓ。在部分可观测环境中，标签本身也可能带有噪声或缺失。一个有趣的方向是将SRM与POMDP或信念状态估计结合。
3. 与模型学习的结合：SRMI专注于奖励模型的学习。可以将其与环境动力学模型的学习相结合，形成一个完整的“模型+奖励”学习系统，迈向更强大的模型化强化学习。
4. 利用先验知识：在实际应用中，我们通常对任务结构有一些模糊的先验（如“步骤A必须在步骤B之前”）。可以将这些先验以逻辑约束的形式注入到SRMI的约束求解过程中，引导搜索，加速学习。

在我自己的实现和实验过程中，最大的体会是对ϵ_c的敏感度管理。它不是一个可以随意设置的超参数，而是连接算法假设与现实世界噪声特性的桥梁。花时间理解任务中奖励噪声的来源和量级，并据此仔细设置ϵ_c，往往比调整其他参数更能决定项目的成败。此外，虽然约束求解是核心，但将其与强化学习主循环高效集成，避免成为性能瓶颈，是工程实现上的一个挑战。采用异步学习架构，让约束求解在后台线程运行，而智能体继续用旧假设进行探索，是一个值得考虑的优化方向。