mlsanityData to 14 Oct 2026

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents

arXiv 2609.35084 ↗First posted 28 Sep 2026cs.LGcited by 0

On the map: LLM agents and tool use → Reinforcement learning for LLM agents

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use. Builds on 33 of its 40 references that are in the map. First posted on arXiv 28 Sep 2026.

Builds on

33 of 40 references.

Closest ancestors · 7

Same direction, newest first

  1. 2026Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning26 May
  2. 2026Hindsight Credit Assignment for Long-Horizon LLM Agents7 Mar
  3. 2025Harnessing Uncertainty: Entropy-Modulated Policy Gradients for Long-Horizon LLM Agents11 Sep
  4. 2025Group-in-Group Policy Optimization for LLM Agent Training16 May
  5. 2025ToolRL: Reward is All Tool Learning Needs16 Apr
  6. 2024ArCHer: Training Language Model Agents via Hierarchical Multi-Turn RL29 Feb
  7. 2023Reflexion: Language Agents with Verbal Reinforcement Learning20 Mar

Other references · 26

  1. 2023GPT-4 Technical Reportcited by 18,396
  2. 2022Training language models to follow instructions with human feedbackcited by 15,971
  3. 2017Proximal Policy Optimization Algorithmscited by 15,215
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  5. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  6. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  7. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  8. 2025Qwen2.5-VL Technical Reportcited by 5,587
  9. 2024Qwen2.5 Technical Reportcited by 4,942
  10. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,182
  11. 2023Let's Verify Step by Stepcited by 3,789
  12. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
14 more
  1. 2020Learning to summarize from human feedbackcited by 2,588
  2. 2019Fine-Tuning Language Models from Human Preferencescited by 2,150
  3. 2024SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineeringcited by 1,737
  4. 2025Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learningcited by 1,444
  5. 2022WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agentscited by 1,251
  6. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  7. 2020ALFWorld: Aligning Text and Embodied Environments for Interactive Learningcited by 1,205
  8. 2019Advantage-Weighted Regression: Simple and Scalable Off-Policy Reinforcement Learningcited by 782
  9. 2024AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agentscited by 401
  10. 2022CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learningcited by 358
  11. 2023Android in the Wild: A Large-Scale Dataset for Android Device Controlcited by 319
  12. 2024DigiRL: Training In-The-Wild Device-Control Agents with Autonomous Reinforcement Learningcited by 214
  13. 2024Agent Q: Advanced Reasoning and Learning for Autonomous AI Agentscited by 208
  14. 2019Hindsight Credit Assignmentcited by 79

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026TreeHCA: Hindsight-Guided Exploration and Credit Assignment for Multi-Turn LLM Agents
  2. 2026Hindsight-Privileged RLVR: Single-Rollout Token Credit Without Group Sampling
  3. 2026From Reasoning to Agentic: Credit Assignment in Reinforcement Learning for Large Language Models
  4. 2026TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents
  5. 2026TIGPO: Temporal Instance-Graph Policy Optimization for Long-Horizon LLM Agents
  6. 2024Assessing the Zero-Shot Capabilities of LLMs for Action Evaluation in RL
  7. 2026MileGPO: Milestone Inference with Local Evidence for Graph-Based Policy Optimization of Long-Horizon LLM Agents
  8. 2026HISR: Hindsight Information Modulated Segmental Process Rewards For Multi-turn Agentic Reinforcement Learning