1. 项目概述与核心问题在强化学习领域我们通常假设智能体所处的环境是“马尔可夫”的——即未来的状态和奖励只取决于当前的状态和动作与历史无关。这个假设是许多经典算法如Q-learning能够有效工作的基石。然而当你试图将强化学习应用到现实世界的复杂任务时比如教一个机器人完成“拿起螺丝刀、拧紧螺丝、放下工具”这一系列动作或者在一个策略游戏中规划多步战术你会发现一个尴尬的现实奖励往往不是马尔可夫的。一个典型的例子是“采矿”任务智能体需要先找到装备E然后开采矿石金G或铂P最后将矿石运到市场M才能获得奖励。如果你在找到装备前就开采了矿石或者开采后没去市场那么整个过程将一无所获。这里的奖励严重依赖于一长串动作的历史序列这就是“非马尔可夫奖励”。奖励机Reward Machine, RM正是为了解决这个问题而生的。它本质上是一个自动机其内部状态记录了智能体完成了哪些关键子目标从而将非马尔可夫奖励问题“转换”成一个扩展状态空间下的标准马尔可夫决策过程使得传统RL算法得以应用。但奖励机有一个致命的“洁癖”它假设环境给出的奖励信号是绝对干净、无噪声的。这就像要求一个老师每次对学生作业的打分都精确无误毫无主观偏差或笔误。现实中这可能吗传感器会有误差模拟器有随机性人类反馈充满主观噪声。当奖励存在噪声时现有的奖励机学习算法就会彻底失灵要么找不到任何与所有经验一致的奖励机要么学出一个庞大无比、严重过拟合噪声的“怪物”机器完全失去了泛化能力。本文要解决的核心痛点正是这个理论与现实的鸿沟。我们提出了一种名为随机奖励机Stochastic Reward Machine, SRM的新模型以及配套的随机奖励机推理算法SRMI。SRM允许奖励输出是一个概率分布而不仅仅是确定值从而显式地建模了奖励的随机性。SRMI算法则能从一个充斥着噪声的智能体探索轨迹中稳健地推断出背后那个最小、最可能解释数据的SRM结构。我们的目标是让强化学习智能体在充满不确定性的真实世界里依然能学会依赖复杂历史序列才能获得奖励的高阶任务。2. 从奖励机到随机奖励机核心思想演进2.1 经典奖励机为何“怕”噪声要理解SRM的价值我们得先看清经典RM的软肋。一个RM可以看作一个Mealy机它的状态转移由观测到的高层事件标签如“找到装备”、“到达市场”驱动而每次转移会输出一个确定的奖励值。以“采矿”任务为例一个理想的RM可能设计如下状态vI初始等待找到装备。状态v1已找到装备等待开采矿石。状态v2已开采铂金等待前往市场。状态v3已开采黄金等待前往市场。状态vT终止成功交付获得奖励。从v2或v3状态在接收到“到达市场M”标签时会转移到vT并分别输出奖励1.1或1.0。其他错误序列如先开采后找装备、踩到陷阱则输出0奖励。问题来了如果因为矿石纯度或市场价格波动交付铂金的实际奖励是在[0.9, 1.3]区间内均匀随机的交付黄金的奖励是在[0.8, 1.2]区间随机的这个RM模型就完全无法准确描述环境。它会固执地认为每次交付铂金就必须给1.1交付黄金就必须给1.0。当实际奖励是0.95或1.05时这个RM与观测数据就产生了根本性的矛盾。现有基于约束求解的RM学习算法如JIRP会试图寻找一个与所有观测轨迹前缀一致的、最小的RM。在噪声下这会导致两种灾难性后果无解由于噪声导致相同标签序列产生了不同的奖励序列算法找不到任何一个确定的RM能同时满足所有矛盾的数据。过拟合为了强行拟合每一个带噪声的奖励样本算法会发明出大量冗余状态导致RM结构急剧膨胀失去可解释性并且学到的策略无法泛化。2.2 随机奖励机拥抱不确定性SRM的核心革新在于它将输出从标量实数升级为概率分布。形式上一个SRMA是一个六元组(V, v_I, 2^P, O, δ, σ)V,v_I,2^P,δ的定义与经典RM相同分别是状态集、初始状态、输入字母表所有标签的集合和确定性的状态转移函数。O是输出字母表它是一个累积分布函数CDF的有限集合。简单理解每个输出是一个描述奖励随机性的概率分布。σ: V × 2^P → O是输出函数给定当前状态和输入标签它返回一个CDF。回到采矿例子在SRM框架下从状态v2已采铂金在输入M时转移至vT的输出不再是确定值1.1而是一个分布例如均匀分布U([0.9, 1.3])。同样从v3到vT的输出可能是U([0.8, 1.2])。这样做带来了两个根本性优势建模能力SRM可以精确刻画现实世界中奖励的随机性。它不再要求“交付铂金就得1.1分”而是说“交付铂金你会得到一个期望为1.1但在0.9到1.3之间波动的奖励”。这极大地增强了模型对真实环境的表达能力。学习可行性对于学习算法而言目标从“寻找一个输出确定值、与所有数据绝对一致的RM”放松为“寻找一个输出分布、与数据在统计意义上一致的SRM”。这为在噪声数据下进行稳健推理打开了大门。关键洞见对于策略优化而言智能体真正关心的是奖励的期望值。如果两个SRM对所有可能的标签序列产生的奖励序列的期望值都相同那么它们诱导出的最优策略是相同的。我们称之为“期望等价”。这一定理后文详述是SRM学习算法能够收敛的理论基石。3. SRMI算法深度解析如何在噪声中寻找结构有了SRM这个模型接下来最核心的问题就是如何从一个智能体与环境交互产生的、充满噪声的轨迹数据中学习出这个SRM这就是随机奖励机推理SRMI算法要解决的问题。3.1 算法总览与核心循环SRMI算法是一个与强化学习过程交织进行的在线学习算法。它不假设已知SRM而是从零开始一边探索环境、收集数据一边迭代地改进对SRM的假设。其核心流程如算法1所示我们可以将其理解为“假设-检验-修正”的循环初始化从一个初始的假设SRMH可以是一个简单结构如单状态机和对应的Q函数集开始。交互与收集使用当前的假设SRMH运行QRM一种适配RM的Q-learning算法进行一个回合的探索。这会生成一条轨迹包括标签序列λ和对应的奖励序列ρ我们称之为一个迹trace。将此迹加入总经验池A。矛盾检测检查当前迹(λ, ρ)是否与当前假设Hεc-一致。所谓εc-一致是指迹中每个观察到的奖励r_i与H在对应步骤输出的分布d_i的期望值E[d_i]之差的绝对值不超过一个预设的噪声分散界εc即|r_i - E[d_i]| ≤ εc。如果一致继续探索如果不一致该迹就是一个反例counterexample加入反例集X。假设修正类型1反例微调如果存在一个与当前假设H同构即状态和转移结构完全相同的SRMZ且Z与当前所有反例集X都εc-一致。那么我们只需调整H中各个转移输出分布的期望值即“平移”输出就能得到新的假设H Z。这相当于在现有结构框架下修正参数。类型2反例重构如果不存在这样的Z说明当前假设H的结构本身不足以解释新数据。此时我们需要以反例集X为约束重新求解一个新的、最小的、与X一致的SRM结构H。这是一个约束求解问题。参数估计无论是微调还是重构得到新假设H其输出分布的参数期望可能只是满足约束的众多解之一未必是最优估计。因此我们需要一个Estimates步骤用H在所有εc-一致的历史经验A上模拟运行为H的每个转移(v, ℓ)收集所有关联的奖励观测值然后用这些观测值的中程估计(max min)/2来最终确定该转移输出分布的期望。这能有效利用所有一致数据得到更稳健的参数估计。策略重启更新假设SRM为H并重新初始化Q函数然后回到步骤2开始新一轮学习。这个循环持续进行直到假设SRM不再被新的反例推翻并且其参数估计收敛。3.2 核心挑战与精妙设计3.2.1 如何定义“一致性”—— εc 的关键角色εc这个参数是SRMI稳健性的核心。它代表了算法对噪声的“容忍度”。你可以把它理解为已知的传感器误差范围或奖励波动的先验知识。例如如果我们知道市场价格的波动范围是±0.2那么εc可以设为0.2。εc的引入将绝对的一致性要求奖励必须完全相等放松为区间一致性奖励落在以期望值为中心、±εc的区间内即可。这完美匹配了奖励是来自一个有界分布的这一事实。它也是区分类型1和类型2反例的标尺如果通过调整期望值调整区间中心就能让所有观测奖励落入新区间内就是类型1问题如果无论如何调整现有结构下总有些奖励落在所有可能区间之外那就是类型2问题必须改变结构。3.2.2 如何从反例中推断新结构—— 约束求解的威力当遇到类型2反例时SRMI需要解决一个核心的约束满足问题CSP给定反例集X和参数εc找出一个状态数最小、且与X中所有迹都εc-一致的SRM。这是算法中最具技术含量的部分。其基本思想是逐步增加状态数进行搜索假设我们要找一个大小为n的SRM。我们构造一个逻辑公式Φ_{X,εc}^n这个公式的变量定义了状态转移布尔变量d_{p,ℓ,q}表示是否从状态p读入标签ℓ后转移到状态q。输出期望实数变量o_{v,ℓ}表示在状态v读入标签ℓ时输出分布的期望值。运行路径布尔变量x_{λ,v}表示读入前缀λ后SRM是否处于状态v。我们对这些变量施加四类约束初始状态约束空序列后SRM必须在初始状态。确定性转移约束对于每个状态和输入必须有且仅有一个后继状态。路径一致性约束如果读入前缀λ后在状态p且从p经ℓ能到q那么读入λℓ后必须在状态q。这确保了变量x定义的路径与转移函数d自洽。εc-一致性约束对于反例集中每个迹的每个前缀(λℓ, ρr)如果读λ后处于状态v那么该步骤的输出期望o_{v,ℓ}必须与观测奖励r满足|o_{v,ℓ} - r| ≤ εc。将这个复合公式喂给一个SMT/SAT求解器如Z3。如果可满足SAT则从求解器返回的变量赋值中可以构造出一个满足要求的n状态SRM。如果不可满足UNSAT则将n加1重复上述过程。通过从n1开始递增搜索我们最终能得到一个最小的、一致的SRM假设。这种方法保证了学习结果的简洁性有助于避免过拟合和提高可解释性。3.2.3 为何使用中程估计Mid-range Estimator在Estimates步骤中对于每个转移(v, ℓ)我们有一组观测到的奖励样本r(v, ℓ)。一个直观的估计器是算术平均值。然而SRMI选择了中程估计器µ (max(r(v,ℓ)) min(r(v,ℓ))) / 2。这背后有深刻的考量保证一致性算术平均值不一定位于样本区间的中心。假设样本来自区间[0, 10]但大部分集中在9附近平均值可能是8.5。如果我们用8.5作为期望区间设为[8.5-εc, 8.5εc]可能无法覆盖样本最小值0从而破坏了与这个样本集的εc-一致性。中程估计器直接以样本区间的中心作为期望能确保整个样本区间被[µ-εc, µεc]所覆盖只要εc不小于半区间宽度从而始终保持与已观测数据的一致性。无偏性对于对称分布如均匀分布、正态分布样本最大值和最小值的期望之和的一半正好等于总体分布的期望。因此中程估计器在分布对称时是无偏的。应对非对称分布的扩展对于非对称分布论文在附录中给出了扩展方案。核心思想是维护两个假设一个主假设H使用中程估计以保证一致性用于反例检测和结构学习一个辅助假设G使用算术平均估计以获取无偏的期望用于QRM策略学习。两者同步更新兼顾了学习过程的稳健性和策略优化的准确性。3.3 与基线方法的对比为了凸显SRMI的优越性论文设计了一个基线算法作为对比。基线算法的思路很直接既然奖励有噪声那我就对每个产生反例的轨迹进行多次重放采样用大量样本的平均值来“平滑”噪声然后再用传统的确定性RM学习算法如JIRP去学习。基线算法的问题在于成本高昂要求智能体能够“回放”特定轨迹多次。在许多环境中特别是随机环境或与物理世界交互精确回放一条历史轨迹是困难甚至不可能的。效率低下即使可以回放为了获得可靠的均值估计需要大量样本严重拖慢学习进程。不现实它假设对于任何产生矛盾的轨迹我们都能无限次重复实验来获取其统计特性这在实际在线学习中是不切实际的。SRMI完全摒弃了这种“先平均、后学习”的两阶段思路。它通过εc-一致性和约束求解一次性地将噪声纳入模型推理的过程中实现了单次探索、即时利用。智能体在探索中遇到的每个矛盾轨迹都立即被用于修正或重构当前的世界模型SRM学习效率显著更高。4. 实验验证与结果分析理论再优美也需要实验的检验。论文在两个精心设计的案例上验证了SRMI的有效性前文提到的采矿Mining环境和一个新的收获Harvest环境。4.1 实验设置与对比对象环境Mining网格世界智能体需按顺序完成“找装备(E)→采矿(G/P)→到市场(M)”才能获得有噪声的奖励如U([0.8,1.2])错误动作或踩陷阱(T)得0奖励。Harvest模拟耕种循环智能体需按“种植(P)→浇水(W)→收获(H)→出售(S)”顺序行动奖励取决于收获时的土地状态好/中/坏且具有噪声。打破顺序会获得负奖励。对比算法SRMI本文提出的算法。Baseline前述的“重放-平均”基线算法。JIRP经典的确定性奖励机推理算法无法处理噪声。评估指标最近100回合的平均累积奖励学习曲线。在随机和非随机确定性两种奖励设置下分别测试。4.2 结果解读与洞见实验结果图对应论文中的Fig. 3a, 3b, 5a, 5b清晰地展示了SRMI的优势在随机奖励环境中全面领先Mining环境Fig. 3aSRMI最快收敛到接近最优的奖励~1.0。基线算法由于需要大量重放采样学习速度慢于SRMI。而JIRP完全无法处理噪声它试图为每一个略有不同的奖励样本创建新的状态导致假设的RM规模不断膨胀“状态爆炸”最终无法在合理时间内找到一致解学习曲线停滞在低水平。Harvest环境Fig. 5a这个环境的特点是轨迹重复概率低极大地放大了基线算法的弱点。基线算法几乎无法收集到足够多的同轨迹样本来进行平均因此性能极差。JIRP同样因噪声而失败。SRMI则凭借其一次性推理噪声的能力成功学习并收敛到最优策略。在非随机环境中无性能损失当环境奖励是确定性的Fig. 3b, 5bSRMI的表现与基线算法和JIRP一样好。这是一个非常重要的性质说明SRMI的机制是向下兼容的。当没有噪声时εc可以设得很小或为0SRMI退化为一个有效的确定性RM学习器不会因为额外的复杂性而引入性能开销。超越深度强化学习基线论文在附录中还对比了深度双Q网络DDQN和深度分层强化学习DHRL。DDQN通过将长历史序列如过去200个标签作为网络输入来隐式处理非马尔可夫性但这种方法难以学习长期依赖且对噪声敏感。DHRL需要依赖已知的SRM结构来生成选项options。在SRM结构未知且奖励有噪声的情况下SRMI显著优于这两种深度学习方法。实操心得这些实验告诉我们在处理复杂序列任务时显式地建模高级别任务结构如SRM比让神经网络隐式学习要高效得多。尤其是在数据稀缺或噪声大的情况下基于模型的、符号化的方法往往更具样本效率和鲁棒性。SRMI成功地将符号推理的严谨性与机器学习的数据驱动能力结合了起来。5. 理论保证为什么SRMI能收敛到最优策略一个算法光有好的实验结果还不够我们需要知道它为什么有效。SRMI的理论贡献在于它证明了在温和的假设下算法能够收敛。核心定理Theorem 1给定关于环境SRM输出字母表的假设1以及ε-贪婪探索策略SRMI在极限情况下会收敛到一个与真实环境SRM期望等价的SRM。假设1是一个技术性假设它要求环境中不同的奖励分布如果它们的支撑集取值范围可以被同一个长度为2εc的区间覆盖那么它们的期望值必须相等。直观上这是为了避免噪声过大以至于完全掩盖了不同信号之间的区别。例如两个分布U([0, 1])和U([0.9, 1.1])如果εc0.6那么区间[0,1]和[0.9,1.1]都能被[0.2, 1.4]这个εc-区间覆盖。假设1要求这两个分布的期望必须相等否则算法将无法仅凭εc-一致性来区分它们。这个假设在大多数实际场景中是合理的它本质上要求噪声的分散程度εc不能大到让所有奖励看起来都来自同一个“模糊”的分布。收敛性证明的骨架结构收敛首先证明SRMI不会无限循环地访问结构同构的SRM假设Lemma 4。由于状态数有限的SRM其结构种类是有限的因此算法最终会“定居”在一个最终的同构类[H_f]中。参数收敛在定居于最终结构类后算法只会遇到类型1反例微调参数。Estimates步骤中为每个转移(v, ℓ)收集的奖励样本集r(v,ℓ)最终将只包含来自期望值相同的分布的样本Lemma 5。并且中程估计器对这些样本的估计是无偏的Lemma 6。策略最优由于算法收敛到的SRM与真实环境SRM是期望等价的根据Lemma 1它们在任何给定的MDP上会诱导出相同的最优价值函数进而QRM算法能够学习到最优策略。推论Corollary 1SRMI在极限下收敛到一个最优策略。这个理论保证是SRMI区别于许多启发式方法的关键。它不仅仅是一个“好用”的算法而且是一个在数学上有着坚实收敛性保证的严谨方法。6. 实现细节、调参与避坑指南如果你打算在自己的项目中尝试实现或应用SRMI以下是一些从论文和实践中提炼出的关键要点。6.1 关键参数与设置噪声分散界εc这是最重要的先验知识。εc设置过大算法会过于“宽容”可能将本质不同的奖励分布混淆导致学到的SRM结构过于简单无法捕捉真实的任务逻辑。εc设置过小算法会过于“敏感”可能将来自同一分布的噪声奖励误认为是不同信号导致结构过复杂甚至无法找到一致解。建议如果对奖励噪声有先验了解如传感器精度±δ可设εcδ。否则可以从一个保守值开始根据学习过程中反例的数量和类型进行微调。反例过多可能εc太小反例过少且学习慢可能εc太大。探索策略论文使用ε-贪婪策略。探索率ε需要仔细平衡。初期需要较高的探索率以广泛收集各种轨迹尤其是能产生类型2反例结构冲突的关键轨迹。后期可以逐渐降低以利用学到的SRM进行策略优化。约束求解器SRMI的核心是求解布尔和实数混合的约束满足问题。论文使用Z3这是一个强大且通用的SMT求解器。在实际应用中对于状态空间不大的问题Z3表现良好。如果状态数n较大约束公式的变量和子句数量会组合爆炸可能导致求解时间过长。此时可能需要考虑问题特定的简化或设置一个最大状态数上限。初始假设通常从一个单状态的SRM开始是合理的。这个初始机器假设所有标签都产生相同的带噪声的奖励。算法会通过反例逐步增加状态细化结构。6.2 常见问题与排查学习停滞长期没有反例检查εc可能设置过大导致算法认为当前假设与所有经验都一致。尝试减小εc。检查探索探索率ε是否太低智能体可能陷入了当前假设下的局部最优策略无法探索到能推翻假设的新轨迹。增加探索率或引入一些基于好奇心的探索机制。环境复杂性任务可能过于复杂初始策略无法在有限步数内触发出产生反例的关键事件序列。考虑增加回合长度或设计课程学习从简化环境开始。状态数爆炸学习速度极慢检查εc可能设置过小将噪声误认为信号导致为每一个微小的奖励差异都创建新状态。适当增大εc。检查约束求解确认约束公式编码正确。特别是路径一致性约束公式3错误的编码会导致求解器返回不合理的、状态数过多的解。简化标签检查环境提供的标签P是否过于精细或冗余。合并一些语义相近的标签可以显著减少搜索空间。学到的SRM与直觉不符数据不足智能体的探索可能尚未覆盖关键的任务模态。运行更多回合。奖励设计问题环境本身的奖励函数可能非常复杂或存在歧义导致多个SRM都能近似解释数据。需要审视任务本身的奖励设计是否清晰。可视化与调试实现SRM的可视化功能并输出每个反例的具体内容。观察是哪些轨迹导致了结构变化这有助于理解算法的决策过程。6.3 扩展与进阶思考非对称噪声分布论文附录B讨论了如何处理非对称分布如指数分布、截断正态分布。核心是使用双假设机制一个主假设H用中程估计保持一致性一个辅助假设G用算术平均估计保证无偏性QRM基于G学习。这增加了实现复杂度但拓宽了应用范围。与深度RL结合SRMI目前与表格型QRM结合。一个很自然的扩展是将其与深度Q网络DQN或其他深度RL算法结合用神经网络来近似在“环境状态 x SRM状态”这个交叉产品空间上的Q函数以处理高维原始状态如图像。部分可观测性POMDP当前SRM的输入是确定的标签。在部分可观测环境中标签本身可能也是噪声或不确定的。如何将SRM与POMDP模型如使用循环神经网络提取历史特征结合是一个有趣的前沿方向。在线学习与计算效率每次遇到类型2反例都需要调用约束求解器这在在线学习场景中可能成为瓶颈。未来工作可以探索增量式约束求解、缓存机制或利用神经网络来近似SRM的推理过程以提升计算效率。随机奖励机及其学习算法SRMI为处理现实世界中普遍存在的、带噪声的复杂序列任务提供了一套形式化、可证明且有效的工具。它将强化学习从对“干净信号”的依赖中解放出来向应对真实世界的不确定性迈出了坚实的一步。在实际应用中理解其参数含义、掌握其调试方法并思考如何将其与现有的深度强化学习框架融合将是发挥其威力的关键。
随机奖励机：应对噪声奖励的强化学习高阶任务建模新方法
发布时间：2026/5/25 20:13:27
1. 项目概述与核心问题在强化学习领域我们通常假设智能体所处的环境是“马尔可夫”的——即未来的状态和奖励只取决于当前的状态和动作与历史无关。这个假设是许多经典算法如Q-learning能够有效工作的基石。然而当你试图将强化学习应用到现实世界的复杂任务时比如教一个机器人完成“拿起螺丝刀、拧紧螺丝、放下工具”这一系列动作或者在一个策略游戏中规划多步战术你会发现一个尴尬的现实奖励往往不是马尔可夫的。一个典型的例子是“采矿”任务智能体需要先找到装备E然后开采矿石金G或铂P最后将矿石运到市场M才能获得奖励。如果你在找到装备前就开采了矿石或者开采后没去市场那么整个过程将一无所获。这里的奖励严重依赖于一长串动作的历史序列这就是“非马尔可夫奖励”。奖励机Reward Machine, RM正是为了解决这个问题而生的。它本质上是一个自动机其内部状态记录了智能体完成了哪些关键子目标从而将非马尔可夫奖励问题“转换”成一个扩展状态空间下的标准马尔可夫决策过程使得传统RL算法得以应用。但奖励机有一个致命的“洁癖”它假设环境给出的奖励信号是绝对干净、无噪声的。这就像要求一个老师每次对学生作业的打分都精确无误毫无主观偏差或笔误。现实中这可能吗传感器会有误差模拟器有随机性人类反馈充满主观噪声。当奖励存在噪声时现有的奖励机学习算法就会彻底失灵要么找不到任何与所有经验一致的奖励机要么学出一个庞大无比、严重过拟合噪声的“怪物”机器完全失去了泛化能力。本文要解决的核心痛点正是这个理论与现实的鸿沟。我们提出了一种名为随机奖励机Stochastic Reward Machine, SRM的新模型以及配套的随机奖励机推理算法SRMI。SRM允许奖励输出是一个概率分布而不仅仅是确定值从而显式地建模了奖励的随机性。SRMI算法则能从一个充斥着噪声的智能体探索轨迹中稳健地推断出背后那个最小、最可能解释数据的SRM结构。我们的目标是让强化学习智能体在充满不确定性的真实世界里依然能学会依赖复杂历史序列才能获得奖励的高阶任务。2. 从奖励机到随机奖励机核心思想演进2.1 经典奖励机为何“怕”噪声要理解SRM的价值我们得先看清经典RM的软肋。一个RM可以看作一个Mealy机它的状态转移由观测到的高层事件标签如“找到装备”、“到达市场”驱动而每次转移会输出一个确定的奖励值。以“采矿”任务为例一个理想的RM可能设计如下状态vI初始等待找到装备。状态v1已找到装备等待开采矿石。状态v2已开采铂金等待前往市场。状态v3已开采黄金等待前往市场。状态vT终止成功交付获得奖励。从v2或v3状态在接收到“到达市场M”标签时会转移到vT并分别输出奖励1.1或1.0。其他错误序列如先开采后找装备、踩到陷阱则输出0奖励。问题来了如果因为矿石纯度或市场价格波动交付铂金的实际奖励是在[0.9, 1.3]区间内均匀随机的交付黄金的奖励是在[0.8, 1.2]区间随机的这个RM模型就完全无法准确描述环境。它会固执地认为每次交付铂金就必须给1.1交付黄金就必须给1.0。当实际奖励是0.95或1.05时这个RM与观测数据就产生了根本性的矛盾。现有基于约束求解的RM学习算法如JIRP会试图寻找一个与所有观测轨迹前缀一致的、最小的RM。在噪声下这会导致两种灾难性后果无解由于噪声导致相同标签序列产生了不同的奖励序列算法找不到任何一个确定的RM能同时满足所有矛盾的数据。过拟合为了强行拟合每一个带噪声的奖励样本算法会发明出大量冗余状态导致RM结构急剧膨胀失去可解释性并且学到的策略无法泛化。2.2 随机奖励机拥抱不确定性SRM的核心革新在于它将输出从标量实数升级为概率分布。形式上一个SRMA是一个六元组(V, v_I, 2^P, O, δ, σ)V,v_I,2^P,δ的定义与经典RM相同分别是状态集、初始状态、输入字母表所有标签的集合和确定性的状态转移函数。O是输出字母表它是一个累积分布函数CDF的有限集合。简单理解每个输出是一个描述奖励随机性的概率分布。σ: V × 2^P → O是输出函数给定当前状态和输入标签它返回一个CDF。回到采矿例子在SRM框架下从状态v2已采铂金在输入M时转移至vT的输出不再是确定值1.1而是一个分布例如均匀分布U([0.9, 1.3])。同样从v3到vT的输出可能是U([0.8, 1.2])。这样做带来了两个根本性优势建模能力SRM可以精确刻画现实世界中奖励的随机性。它不再要求“交付铂金就得1.1分”而是说“交付铂金你会得到一个期望为1.1但在0.9到1.3之间波动的奖励”。这极大地增强了模型对真实环境的表达能力。学习可行性对于学习算法而言目标从“寻找一个输出确定值、与所有数据绝对一致的RM”放松为“寻找一个输出分布、与数据在统计意义上一致的SRM”。这为在噪声数据下进行稳健推理打开了大门。关键洞见对于策略优化而言智能体真正关心的是奖励的期望值。如果两个SRM对所有可能的标签序列产生的奖励序列的期望值都相同那么它们诱导出的最优策略是相同的。我们称之为“期望等价”。这一定理后文详述是SRM学习算法能够收敛的理论基石。3. SRMI算法深度解析如何在噪声中寻找结构有了SRM这个模型接下来最核心的问题就是如何从一个智能体与环境交互产生的、充满噪声的轨迹数据中学习出这个SRM这就是随机奖励机推理SRMI算法要解决的问题。3.1 算法总览与核心循环SRMI算法是一个与强化学习过程交织进行的在线学习算法。它不假设已知SRM而是从零开始一边探索环境、收集数据一边迭代地改进对SRM的假设。其核心流程如算法1所示我们可以将其理解为“假设-检验-修正”的循环初始化从一个初始的假设SRMH可以是一个简单结构如单状态机和对应的Q函数集开始。交互与收集使用当前的假设SRMH运行QRM一种适配RM的Q-learning算法进行一个回合的探索。这会生成一条轨迹包括标签序列λ和对应的奖励序列ρ我们称之为一个迹trace。将此迹加入总经验池A。矛盾检测检查当前迹(λ, ρ)是否与当前假设Hεc-一致。所谓εc-一致是指迹中每个观察到的奖励r_i与H在对应步骤输出的分布d_i的期望值E[d_i]之差的绝对值不超过一个预设的噪声分散界εc即|r_i - E[d_i]| ≤ εc。如果一致继续探索如果不一致该迹就是一个反例counterexample加入反例集X。假设修正类型1反例微调如果存在一个与当前假设H同构即状态和转移结构完全相同的SRMZ且Z与当前所有反例集X都εc-一致。那么我们只需调整H中各个转移输出分布的期望值即“平移”输出就能得到新的假设H Z。这相当于在现有结构框架下修正参数。类型2反例重构如果不存在这样的Z说明当前假设H的结构本身不足以解释新数据。此时我们需要以反例集X为约束重新求解一个新的、最小的、与X一致的SRM结构H。这是一个约束求解问题。参数估计无论是微调还是重构得到新假设H其输出分布的参数期望可能只是满足约束的众多解之一未必是最优估计。因此我们需要一个Estimates步骤用H在所有εc-一致的历史经验A上模拟运行为H的每个转移(v, ℓ)收集所有关联的奖励观测值然后用这些观测值的中程估计(max min)/2来最终确定该转移输出分布的期望。这能有效利用所有一致数据得到更稳健的参数估计。策略重启更新假设SRM为H并重新初始化Q函数然后回到步骤2开始新一轮学习。这个循环持续进行直到假设SRM不再被新的反例推翻并且其参数估计收敛。3.2 核心挑战与精妙设计3.2.1 如何定义“一致性”—— εc 的关键角色εc这个参数是SRMI稳健性的核心。它代表了算法对噪声的“容忍度”。你可以把它理解为已知的传感器误差范围或奖励波动的先验知识。例如如果我们知道市场价格的波动范围是±0.2那么εc可以设为0.2。εc的引入将绝对的一致性要求奖励必须完全相等放松为区间一致性奖励落在以期望值为中心、±εc的区间内即可。这完美匹配了奖励是来自一个有界分布的这一事实。它也是区分类型1和类型2反例的标尺如果通过调整期望值调整区间中心就能让所有观测奖励落入新区间内就是类型1问题如果无论如何调整现有结构下总有些奖励落在所有可能区间之外那就是类型2问题必须改变结构。3.2.2 如何从反例中推断新结构—— 约束求解的威力当遇到类型2反例时SRMI需要解决一个核心的约束满足问题CSP给定反例集X和参数εc找出一个状态数最小、且与X中所有迹都εc-一致的SRM。这是算法中最具技术含量的部分。其基本思想是逐步增加状态数进行搜索假设我们要找一个大小为n的SRM。我们构造一个逻辑公式Φ_{X,εc}^n这个公式的变量定义了状态转移布尔变量d_{p,ℓ,q}表示是否从状态p读入标签ℓ后转移到状态q。输出期望实数变量o_{v,ℓ}表示在状态v读入标签ℓ时输出分布的期望值。运行路径布尔变量x_{λ,v}表示读入前缀λ后SRM是否处于状态v。我们对这些变量施加四类约束初始状态约束空序列后SRM必须在初始状态。确定性转移约束对于每个状态和输入必须有且仅有一个后继状态。路径一致性约束如果读入前缀λ后在状态p且从p经ℓ能到q那么读入λℓ后必须在状态q。这确保了变量x定义的路径与转移函数d自洽。εc-一致性约束对于反例集中每个迹的每个前缀(λℓ, ρr)如果读λ后处于状态v那么该步骤的输出期望o_{v,ℓ}必须与观测奖励r满足|o_{v,ℓ} - r| ≤ εc。将这个复合公式喂给一个SMT/SAT求解器如Z3。如果可满足SAT则从求解器返回的变量赋值中可以构造出一个满足要求的n状态SRM。如果不可满足UNSAT则将n加1重复上述过程。通过从n1开始递增搜索我们最终能得到一个最小的、一致的SRM假设。这种方法保证了学习结果的简洁性有助于避免过拟合和提高可解释性。3.2.3 为何使用中程估计Mid-range Estimator在Estimates步骤中对于每个转移(v, ℓ)我们有一组观测到的奖励样本r(v, ℓ)。一个直观的估计器是算术平均值。然而SRMI选择了中程估计器µ (max(r(v,ℓ)) min(r(v,ℓ))) / 2。这背后有深刻的考量保证一致性算术平均值不一定位于样本区间的中心。假设样本来自区间[0, 10]但大部分集中在9附近平均值可能是8.5。如果我们用8.5作为期望区间设为[8.5-εc, 8.5εc]可能无法覆盖样本最小值0从而破坏了与这个样本集的εc-一致性。中程估计器直接以样本区间的中心作为期望能确保整个样本区间被[µ-εc, µεc]所覆盖只要εc不小于半区间宽度从而始终保持与已观测数据的一致性。无偏性对于对称分布如均匀分布、正态分布样本最大值和最小值的期望之和的一半正好等于总体分布的期望。因此中程估计器在分布对称时是无偏的。应对非对称分布的扩展对于非对称分布论文在附录中给出了扩展方案。核心思想是维护两个假设一个主假设H使用中程估计以保证一致性用于反例检测和结构学习一个辅助假设G使用算术平均估计以获取无偏的期望用于QRM策略学习。两者同步更新兼顾了学习过程的稳健性和策略优化的准确性。3.3 与基线方法的对比为了凸显SRMI的优越性论文设计了一个基线算法作为对比。基线算法的思路很直接既然奖励有噪声那我就对每个产生反例的轨迹进行多次重放采样用大量样本的平均值来“平滑”噪声然后再用传统的确定性RM学习算法如JIRP去学习。基线算法的问题在于成本高昂要求智能体能够“回放”特定轨迹多次。在许多环境中特别是随机环境或与物理世界交互精确回放一条历史轨迹是困难甚至不可能的。效率低下即使可以回放为了获得可靠的均值估计需要大量样本严重拖慢学习进程。不现实它假设对于任何产生矛盾的轨迹我们都能无限次重复实验来获取其统计特性这在实际在线学习中是不切实际的。SRMI完全摒弃了这种“先平均、后学习”的两阶段思路。它通过εc-一致性和约束求解一次性地将噪声纳入模型推理的过程中实现了单次探索、即时利用。智能体在探索中遇到的每个矛盾轨迹都立即被用于修正或重构当前的世界模型SRM学习效率显著更高。4. 实验验证与结果分析理论再优美也需要实验的检验。论文在两个精心设计的案例上验证了SRMI的有效性前文提到的采矿Mining环境和一个新的收获Harvest环境。4.1 实验设置与对比对象环境Mining网格世界智能体需按顺序完成“找装备(E)→采矿(G/P)→到市场(M)”才能获得有噪声的奖励如U([0.8,1.2])错误动作或踩陷阱(T)得0奖励。Harvest模拟耕种循环智能体需按“种植(P)→浇水(W)→收获(H)→出售(S)”顺序行动奖励取决于收获时的土地状态好/中/坏且具有噪声。打破顺序会获得负奖励。对比算法SRMI本文提出的算法。Baseline前述的“重放-平均”基线算法。JIRP经典的确定性奖励机推理算法无法处理噪声。评估指标最近100回合的平均累积奖励学习曲线。在随机和非随机确定性两种奖励设置下分别测试。4.2 结果解读与洞见实验结果图对应论文中的Fig. 3a, 3b, 5a, 5b清晰地展示了SRMI的优势在随机奖励环境中全面领先Mining环境Fig. 3aSRMI最快收敛到接近最优的奖励~1.0。基线算法由于需要大量重放采样学习速度慢于SRMI。而JIRP完全无法处理噪声它试图为每一个略有不同的奖励样本创建新的状态导致假设的RM规模不断膨胀“状态爆炸”最终无法在合理时间内找到一致解学习曲线停滞在低水平。Harvest环境Fig. 5a这个环境的特点是轨迹重复概率低极大地放大了基线算法的弱点。基线算法几乎无法收集到足够多的同轨迹样本来进行平均因此性能极差。JIRP同样因噪声而失败。SRMI则凭借其一次性推理噪声的能力成功学习并收敛到最优策略。在非随机环境中无性能损失当环境奖励是确定性的Fig. 3b, 5bSRMI的表现与基线算法和JIRP一样好。这是一个非常重要的性质说明SRMI的机制是向下兼容的。当没有噪声时εc可以设得很小或为0SRMI退化为一个有效的确定性RM学习器不会因为额外的复杂性而引入性能开销。超越深度强化学习基线论文在附录中还对比了深度双Q网络DDQN和深度分层强化学习DHRL。DDQN通过将长历史序列如过去200个标签作为网络输入来隐式处理非马尔可夫性但这种方法难以学习长期依赖且对噪声敏感。DHRL需要依赖已知的SRM结构来生成选项options。在SRM结构未知且奖励有噪声的情况下SRMI显著优于这两种深度学习方法。实操心得这些实验告诉我们在处理复杂序列任务时显式地建模高级别任务结构如SRM比让神经网络隐式学习要高效得多。尤其是在数据稀缺或噪声大的情况下基于模型的、符号化的方法往往更具样本效率和鲁棒性。SRMI成功地将符号推理的严谨性与机器学习的数据驱动能力结合了起来。5. 理论保证为什么SRMI能收敛到最优策略一个算法光有好的实验结果还不够我们需要知道它为什么有效。SRMI的理论贡献在于它证明了在温和的假设下算法能够收敛。核心定理Theorem 1给定关于环境SRM输出字母表的假设1以及ε-贪婪探索策略SRMI在极限情况下会收敛到一个与真实环境SRM期望等价的SRM。假设1是一个技术性假设它要求环境中不同的奖励分布如果它们的支撑集取值范围可以被同一个长度为2εc的区间覆盖那么它们的期望值必须相等。直观上这是为了避免噪声过大以至于完全掩盖了不同信号之间的区别。例如两个分布U([0, 1])和U([0.9, 1.1])如果εc0.6那么区间[0,1]和[0.9,1.1]都能被[0.2, 1.4]这个εc-区间覆盖。假设1要求这两个分布的期望必须相等否则算法将无法仅凭εc-一致性来区分它们。这个假设在大多数实际场景中是合理的它本质上要求噪声的分散程度εc不能大到让所有奖励看起来都来自同一个“模糊”的分布。收敛性证明的骨架结构收敛首先证明SRMI不会无限循环地访问结构同构的SRM假设Lemma 4。由于状态数有限的SRM其结构种类是有限的因此算法最终会“定居”在一个最终的同构类[H_f]中。参数收敛在定居于最终结构类后算法只会遇到类型1反例微调参数。Estimates步骤中为每个转移(v, ℓ)收集的奖励样本集r(v,ℓ)最终将只包含来自期望值相同的分布的样本Lemma 5。并且中程估计器对这些样本的估计是无偏的Lemma 6。策略最优由于算法收敛到的SRM与真实环境SRM是期望等价的根据Lemma 1它们在任何给定的MDP上会诱导出相同的最优价值函数进而QRM算法能够学习到最优策略。推论Corollary 1SRMI在极限下收敛到一个最优策略。这个理论保证是SRMI区别于许多启发式方法的关键。它不仅仅是一个“好用”的算法而且是一个在数学上有着坚实收敛性保证的严谨方法。6. 实现细节、调参与避坑指南如果你打算在自己的项目中尝试实现或应用SRMI以下是一些从论文和实践中提炼出的关键要点。6.1 关键参数与设置噪声分散界εc这是最重要的先验知识。εc设置过大算法会过于“宽容”可能将本质不同的奖励分布混淆导致学到的SRM结构过于简单无法捕捉真实的任务逻辑。εc设置过小算法会过于“敏感”可能将来自同一分布的噪声奖励误认为是不同信号导致结构过复杂甚至无法找到一致解。建议如果对奖励噪声有先验了解如传感器精度±δ可设εcδ。否则可以从一个保守值开始根据学习过程中反例的数量和类型进行微调。反例过多可能εc太小反例过少且学习慢可能εc太大。探索策略论文使用ε-贪婪策略。探索率ε需要仔细平衡。初期需要较高的探索率以广泛收集各种轨迹尤其是能产生类型2反例结构冲突的关键轨迹。后期可以逐渐降低以利用学到的SRM进行策略优化。约束求解器SRMI的核心是求解布尔和实数混合的约束满足问题。论文使用Z3这是一个强大且通用的SMT求解器。在实际应用中对于状态空间不大的问题Z3表现良好。如果状态数n较大约束公式的变量和子句数量会组合爆炸可能导致求解时间过长。此时可能需要考虑问题特定的简化或设置一个最大状态数上限。初始假设通常从一个单状态的SRM开始是合理的。这个初始机器假设所有标签都产生相同的带噪声的奖励。算法会通过反例逐步增加状态细化结构。6.2 常见问题与排查学习停滞长期没有反例检查εc可能设置过大导致算法认为当前假设与所有经验都一致。尝试减小εc。检查探索探索率ε是否太低智能体可能陷入了当前假设下的局部最优策略无法探索到能推翻假设的新轨迹。增加探索率或引入一些基于好奇心的探索机制。环境复杂性任务可能过于复杂初始策略无法在有限步数内触发出产生反例的关键事件序列。考虑增加回合长度或设计课程学习从简化环境开始。状态数爆炸学习速度极慢检查εc可能设置过小将噪声误认为信号导致为每一个微小的奖励差异都创建新状态。适当增大εc。检查约束求解确认约束公式编码正确。特别是路径一致性约束公式3错误的编码会导致求解器返回不合理的、状态数过多的解。简化标签检查环境提供的标签P是否过于精细或冗余。合并一些语义相近的标签可以显著减少搜索空间。学到的SRM与直觉不符数据不足智能体的探索可能尚未覆盖关键的任务模态。运行更多回合。奖励设计问题环境本身的奖励函数可能非常复杂或存在歧义导致多个SRM都能近似解释数据。需要审视任务本身的奖励设计是否清晰。可视化与调试实现SRM的可视化功能并输出每个反例的具体内容。观察是哪些轨迹导致了结构变化这有助于理解算法的决策过程。6.3 扩展与进阶思考非对称噪声分布论文附录B讨论了如何处理非对称分布如指数分布、截断正态分布。核心是使用双假设机制一个主假设H用中程估计保持一致性一个辅助假设G用算术平均估计保证无偏性QRM基于G学习。这增加了实现复杂度但拓宽了应用范围。与深度RL结合SRMI目前与表格型QRM结合。一个很自然的扩展是将其与深度Q网络DQN或其他深度RL算法结合用神经网络来近似在“环境状态 x SRM状态”这个交叉产品空间上的Q函数以处理高维原始状态如图像。部分可观测性POMDP当前SRM的输入是确定的标签。在部分可观测环境中标签本身可能也是噪声或不确定的。如何将SRM与POMDP模型如使用循环神经网络提取历史特征结合是一个有趣的前沿方向。在线学习与计算效率每次遇到类型2反例都需要调用约束求解器这在在线学习场景中可能成为瓶颈。未来工作可以探索增量式约束求解、缓存机制或利用神经网络来近似SRM的推理过程以提升计算效率。随机奖励机及其学习算法SRMI为处理现实世界中普遍存在的、带噪声的复杂序列任务提供了一套形式化、可证明且有效的工具。它将强化学习从对“干净信号”的依赖中解放出来向应对真实世界的不确定性迈出了坚实的一步。在实际应用中理解其参数含义、掌握其调试方法并思考如何将其与现有的深度强化学习框架融合将是发挥其威力的关键。
