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.20.6] [-0.5, 0.8]所覆盖。然而它们的期望值0.15 vs 0.5却不同。这就违反了假设1。如果这个假设被违反会发生什么智能体观察到来自这两个分布的奖励样本由于ϵ_c较大算法可能会误认为这些样本都来自同一个“大”分布期望值在0.15和0.5之间的某个值从而无法区分背后其实是两个不同的语义事件对应奖励机中两条不同的转移边。这将导致学习到的奖励机结构错误。这个假设合理吗作者认为在绝大多数实际场景中是合理的。它要求环境的“信号”不同事件的平均奖励差异必须大于“噪声”的分散程度。如果噪声大到足以让两个不同含义的事件产生的奖励看起来完全无法区分那么任何基于奖励差异的学习方法都会失效。这更像是对问题本身“可学习性”的一个基本要求而非算法的限制。3. SRMI算法分步拆解与实操要点SRMI算法的核心思想是交织进行策略学习和奖励机推断。它从一个初始的假设SRM开始在交互中不断收集轨迹一旦发现与当前假设矛盾的轨迹反例就尝试修正或重新推断奖励机。3.1 算法主循环与两种反例算1展示了SRMI的主干。我们重点关注其核心逻辑运行QRM使用当前的假设SRMH和对应的Q函数集在环境中运行一个回合生成一条轨迹标签序列λ和奖励序列ρ并将其加入总轨迹集A。检测反例检查当前轨迹(λ, ρ)是否与假设Hϵ_c-一致。即对于轨迹中的每一步观察到的奖励r_i是否落在假设SRM在该步输出的分布期望值的±ϵ_c范围内。如果不是则这是一个反例加入反例集X。处理反例类型1反例微调如果存在一个与H图同构的SRMZ仅通过调整其输出分布的期望值而不改变状态转移结构就能使其与当前所有反例集X一致。那么我们就用Z替换H。这相当于“修正”了现有结构的参数。类型2反例重构如果找不到这样的Z说明当前假设的结构状态数量、转移关系不足以解释新数据。此时需要调用约束求解器基于当前所有反例集X重新推断一个最小且一致的新SRM结构H。参数估计无论通过哪种方式得到新的假设结构H都需要用历史轨迹集A中所有与H一致的轨迹来重新估计每条转移边输出分布的期望值。这一步通过Estimates函数完成。重置与继续更新假设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。然后我们构建以下约束初始状态约束机器必须从唯一的初始状态开始。确定性转移约束对于每个状态和标签必须有且仅有一个后继状态。运行一致性约束这些约束将x变量与d变量联系起来确保对于反例中的每个前缀机器的运行路径是唯一且符合转移函数的。ϵ_c一致性约束这是核心。对于反例中的每一步如果机器在读取某个前缀后处于状态v并且接下来看到的标签是ℓ那么这一步观察到的奖励r必须满足| o_{v,ℓ} - r | ≤ ϵ_c。这确保了假设的输出与观测数据相容。将这些约束组合成一个公式Φ_{X,ϵ_c}^n。如果这个公式可满足那么从一个满足解中我们可以直接提取出一个具有n个状态、且与所有反例一致的SRM。为了找到最小的SRM我们从n1开始依次增加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])ϵ_c0.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 实验设置与对比基线环境采矿如前所述智能体需要按顺序完成“找装备(E) - 挖矿(P/G) - 去市场(M)”才能获得随机奖励并避免陷阱(T)。收获智能体需要执行“种植(P) - 浇水(W) - 收获(H) - 出售(S)”的序列。奖励取决于收获时环境的“状态”好G、中M、差B该状态按MDP动态变化见图4b奖励均值因此不同且随机。对比算法SRMI本文提出的算法。基线算法一种朴素的处理噪声的方法。当遇到反例时暂停QRM并重复执行该轨迹多次例如20次收集足够样本以平均掉噪声得到近似的期望奖励然后再用传统的确定性奖励机推断方法如JIRP学习。JIRP经典的确定性奖励机推断算法。它完全忽略噪声试图直接从带噪声的奖励中学习一个确定性奖励机。评指标最近100回合的平均累积奖励学习曲线。4.2 结果解读与深度分析采矿环境结果分析图3aSRMI成功学习并快速收敛到接近最优的奖励~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 关键参数选择与调优噪声分散度上界 (ϵ_c)这是最重要的先验知识。ϵ_c需要大于等于真实奖励分布支撑集宽度的一半。如果设得太小算法会变得非常敏感将正常的奖励波动误认为是结构性反例导致频繁重构奖励机不稳定。如果设得太大算法会过于宽容可能无法区分期望值不同但区间有重叠的分布导致学习到错误的结构。建议如果对任务有领域知识应尽量给出一个紧致的估计。也可以通过初步探索观察奖励的波动范围来设定。探索策略论文使用了标准的ϵ-greedy策略。在奖励机学习中探索尤为重要因为需要收集到足够多样、能触发不同奖励机状态转移的轨迹。可以结合一些基于好奇心的探索机制鼓励智能体覆盖更多样的标签序列。约束求解器调用频率每次遇到类型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 扩展与进阶思考输出分布的泛化目前SRM假设输出是区间上的均匀分布。可以扩展为更一般的分布族如高斯分布、指数分布只需在约束中修改一致性条件如|r - µ| ≤ kσ并在Estimates步骤中估计分布参数如均值和方差。部分可观测性当前框架假设智能体能完美观测到高层标签ℓ。在部分可观测环境中标签本身也可能带有噪声或缺失。一个有趣的方向是将SRM与POMDP或信念状态估计结合。与模型学习的结合SRMI专注于奖励模型的学习。可以将其与环境动力学模型的学习相结合形成一个完整的“模型奖励”学习系统迈向更强大的模型化强化学习。利用先验知识在实际应用中我们通常对任务结构有一些模糊的先验如“步骤A必须在步骤B之前”。可以将这些先验以逻辑约束的形式注入到SRMI的约束求解过程中引导搜索加速学习。在我自己的实现和实验过程中最大的体会是对ϵ_c的敏感度管理。它不是一个可以随意设置的超参数而是连接算法假设与现实世界噪声特性的桥梁。花时间理解任务中奖励噪声的来源和量级并据此仔细设置ϵ_c往往比调整其他参数更能决定项目的成败。此外虽然约束求解是核心但将其与强化学习主循环高效集成避免成为性能瓶颈是工程实现上的一个挑战。采用异步学习架构让约束求解在后台线程运行而智能体继续用旧假设进行探索是一个值得考虑的优化方向。