Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.35084 · 1 citation · 40 references
Computer Science

TL;DR

GraphHCA is proposed, a model-free realization of HCA that eliminates explicit hindsight-distribution estimation and achieves state-of-the-art results on ALFWorld and WebShop at both LLM scales, and on Sokoban with a vision-language agent.

Abstract

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.

View source

Similar papers

#artificial intelligence Preprint Sep 2026

SHARPO: Segment-Level Credit Assignment for Agentic Reinforcement Learning

Segment-level Hindsight Advantage Reweighting for Policy Optimization (SHARPO), a credit-assignment mechanism that refines Group Relative Policy Optimization at the level of environment-facing segments that outperforms existing baselines on the ALFWorld and WebShop benchmarks.

Xin-Chen Du, Zheng-Ze Zhou, Wen-Hui Zhu et al. · 0 citations
Preprint Aug 2026

TRCA: Transition-wise Rubric Credit Assignment for Long-horizon LLM Agents

Transition-wise Rubric Credit Assignment (TRCA) is proposed, which derives step-level supervision directly from action-induced transitions without learned evaluators or successful anchors for long-horizon tasks with sparse successful anchors.

Huan-Xi Zhang, Ming-Ju Chen, Dongxu Zhou et al. · 7 citations

PACT: From Credit Assignment to Critic Alignment

Policy Aligned Critic Training (PACT), which adopts an Actor-then-Critic update order to apply importance sampling correction to critic training and better align the critic with the updated policy, is developed.

Jia-Yan Fu, Hang Xu, Yong Zhang et al. · 0 citations
Preprint Aug 2026

IAPO: Influence-Aware Policy Optimization for Credit Assignment in Multi-Turn Service Agents

Influence-Aware Policy Optimization (IAPO), which represents each rollout as a typed influence-dependency graph over trainable agent actions, with user and tool observations serving as evidence, is introduced and advances the understanding of credit assignment in multi-turn user interactions.

B. Ren, Yirong Mao, Yi Yang et al. · 1 citation

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.