GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents
作者: Haodong Zhu, Yangyang Ren, Changbai Li, Sheng Xu, Linlin Yang, haiguang liu, Baochang Zhang
分类: cs.LG
发布日期: 2026-09-28
💡 一句话要点
提出GraphHCA以解决长时间跨度LLM代理的信用分配问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 强化学习 信用分配 大型语言模型 无模型方法 贝叶斯法则 状态成功潜力 长时间跨度任务 智能代理
📋 核心要点
- 现有方法在处理稀疏奖励的长时间跨度任务时，未能有效捕捉行动与结果之间的回顾关系，导致信用分配不准确。
- 论文提出GraphHCA，通过消除显式的回顾分布估计，利用贝叶斯法则简化了信用分配过程，提供了逐步信用信号。
- 在ALFWorld和WebShop等基准测试中，GraphHCA在成功率上超过了现有最强基线，展示了其在长时间跨度任务中的有效性。
📝 摘要（中文）
基于组的强化学习（RL）已推动大型语言模型（LLMs）的发展，并逐渐扩展到代理任务中。在这些任务中，稀疏的终端奖励使得逐步信用分配变得至关重要。现有方法通过采样回放中的后续结果来分配信用，但未能明确捕捉其与实现结果的回顾关系。本文提出GraphHCA，一种无模型的HCA实现，消除了显式的回顾分布估计。该方法在确定性转移的终端目标任务中，通过贝叶斯法则将回顾比率简化为连续状态下行为策略成功概率的比率，从而提供逐步信用。GraphHCA在ALFWorld和WebShop等任务上实现了最先进的结果，显著提升了成功率。
🔬 方法详解
问题定义：本文旨在解决长时间跨度任务中，现有强化学习方法在稀疏奖励情况下的信用分配不足问题。现有方法依赖于采样回放，未能有效捕捉行动与结果之间的回顾关系，导致信用分配不准确。
核心思路：论文提出GraphHCA，利用贝叶斯法则将回顾比率简化为行为策略成功概率的比率，从而避免了对回顾分布的显式估计。通过这种方式，GraphHCA能够在不需要额外模型或前向传递的情况下，提供逐步信用信号。
技术框架：GraphHCA的整体架构包括从池化回放中估计状态成功潜力，并通过折扣递归在诱导的转移图上进行计算。该方法在任何有向图上都存在唯一的固定点，确保了稳定性和有效性。
关键创新：GraphHCA的主要创新在于消除了对回顾分布的显式估计，利用状态成功潜力的增量来实现逐步信用分配。这一设计与现有方法的本质区别在于其模型无关性和计算效率。
关键设计：在实现中，GraphHCA采用了折扣递归算法来估计状态成功潜力，确保了计算的高效性和准确性。该方法的参数设置和损失函数设计均旨在优化信用分配的精度和稳定性。
🖼️ 关键图片
📊 实验亮点
在实验中，GraphHCA在ALFWorld上成功率提升了24.6个百分点，相较于GRPO和最强的逐步基线提升了4.7个百分点，展示了其在长时间跨度任务中的显著优势。
🎯 应用场景
GraphHCA的研究成果在多种长时间跨度的强化学习任务中具有广泛的应用潜力，尤其是在需要高效信用分配的复杂环境中。其无模型的特性使得该方法可以被广泛应用于机器人控制、游戏AI和自动化决策等领域，未来可能推动智能代理的发展。
📄 摘要（原文）
Group-based reinforcement learning (RL) has advanced large language models (LLMs) and is increasingly extending to agentic tasks, where sparse terminal rewards make step-level credit assignment essential. Existing methods assign credit from what follows an action in sampled rollouts, but do not explicitly capture its retrospective relation to the realized outcome. Hindsight credit assignment (HCA) instead attributes credit through the ratio of hindsight to behavior-policy probabilities, but estimating the hindsight distribution requires an auxiliary model or an extra pass. To address this estimation bottleneck, we propose GraphHCA, a model-free realization of HCA that eliminates explicit hindsight-distribution estimation. For terminal-goal tasks with deterministic transitions, Bayes' rule reduces the hindsight ratio to a ratio of behavior-policy success probabilities at consecutive states. Taking logs yields a state-wise success potential, whose increment across a transition provides step-level credit. GraphHCA estimates this potential from pooled rollouts through a discounted recursion on the induced transition graph, which admits a unique fixed point on any directed graph. The resulting step-level signal is combined with the trajectory-level advantage, requiring neither a learned hindsight model nor an extra forward pass and recovering GRPO when the step-level weight is zero. Among all compared baselines, GraphHCA achieves state-of-the-art results on ALFWorld and WebShop at both LLM scales, and on Sokoban with a vision-language agent. For example, on ALFWorld it improves overall success rate by up to 24.6 points over GRPO and by up to 4.7 points over the strongest step-level baseline.