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.
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
It is argued that the right resolution is state-dependent, and GACA, a critic-free estimator whose granularity follows an uncertainty-based criticality proxy is proposed, improves task success over GRPO and GiGPO at both 1.5B and 7B scales.
Tao Liang, Yang Liu, Shang Luo et al.· 3 citations
AdaStep is proposed, an Adaptive Step-credit weighting method that controls how strongly each group-derived local advantage modifies the trajectory-level signal, and an optimal per-state shrinkage coefficient is derived.
X. Wang, Wen-Hao Wu, Meng-Hao Zhang et al.· 0 citations
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
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.· arXiv.org· 0 citations
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· news.mit.eduNov 17, 2026
By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.
Microsoft Research Blog· microsoft.comNov 16, 2026
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.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026