Hindsight Credit Assignment for Long-Horizon LLM Agents

Hui-Ze Tan; Xiao-Wen Yang; Hao Chen; Jie-Jing Shao; Yi Wen; Yuteng Shen; Weihong Luo; Xiku Du

cs.LGMar 7, 2026

Hindsight Credit Assignment for Long-Horizon LLM Agents

Authors: Hui-Ze Tan, Xiao-Wen Yang, Hao Chen, Jie-Jing Shao, Yi Wen, Yuteng Shen, Weihong Luo, Xiku Du,

Organizations: State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · FiT, Tencent, Shenzhen, China · School of Data Science, City University of Hong Kong, Hong Kong, China ·

Abstract

Large Language Model (LLM) agents often face significant credit assignment challenges in long-horizon, multi-step tasks due to sparse rewards. Existing value-free methods, such as Group Relative Policy Optimization (GRPO), encounter two fundamental bottlenecks: inaccurate step-level Q-value estimation and misaligned value baselines for intermediate states. To address these limitations, we introduce HCAPO, the first framework to integrate hindsight credit assignment into LLM agents. HCAPO leverages the LLM itself as a post-hoc critic to refine step-level Q-values through hindsight reasoning. Furthermore, HCAPO's multi-scale advantage mechanism effectively supplements the inaccurate value baselines at critical decision states. Evaluations across three challenging benchmarks, including WebShop and ALFWorld, demonstrate that HCAPO consistently outperforms state-of-the-art RL methods. Notably, HCAPO achieves a 7.7% improvement in success rate on WebShop and a 13.8% on ALFWorld over GRPO using the Qwen2.5-7B-Instruct model. These results indicate that HCAPO significantly enhances exploration efficiency, promotes concise decision-making, and ensures scalability in complex, long-horizon tasks.

Figures & tables

Figure 1: From trajectory-level to step-level: hindsight credit assignment for long-horizon agents. $\rho$ is the hindsight ratio.

Panel of Figure 2 — Figure 2: The HCAPO framework. (a) Illustrates the generative verification process: for a candidate action $a_{t}$ , the LLM acts as a critic to compute the hindsight score $\rho_{t}$ by conditioning on the state $s_{t}$ and hindsight information $s_{final}$ . (b) Shows the full optimization loop where a group of $G$ trajectories is evaluated via Hindsight Q-values to produce the final group-based advantage $A_{i,t}$ .

Closed-Source Model
Type	Method	ALFWorld							WebShop
Type	Method	Pick	Look	Clean	Heat	Cool	Pick2	All	Score	Succ.
Prompting	GPT-4o	75.3	60.8	31.2	56.7	21.6	49.8	48.0	31.8	23.7
Prompting	Gemini-2.5-Pro	92.8	63.3	62.1	69.0	26.6	58.7	60.3	42.5	35.9
Qwen2.5-1.5B-Instruct
Prompting	Qwen2.5	5.9	5.5	3.3	9.7	4.2	0.0	4.1	23.1	5.2

Table 1: Performance on ALFWorld and WebShop. Results are averaged over 3 random seeds. For ALFWorld, we report the average success rate (%) for each subtask as well as the overall result. For WebShop, we report both the average score and the average success rate (%). We compare our proposed HCAPO with GRPO and GiGPO. Best results are bolded .

Base Model: Qwen2.5-3B-Instruct
Type	Method	Single-Hop QA			Multi-Hop QA				Avg.
Type	Method	NQ $\dagger$	TriviaQA $\star$	PopQA $\star$	HotpotQA $\dagger$	2Wiki $\star$	MuSiQue $\star$	Bamboogle $\star$	Avg.
RL Training	R1-Instruct	27.0	53.7	19.9	23.7	29.2	7.2	29.3	27.1
RL Training	Search-R1	34.1	54.5	37.8	32.4	31.9	10.3	26.4	32.5
RL Training	ZeroSearch	41.4	57.4	44.8	27.4	30.0	9.8	11.1	31.7
RL Training	StepSearch	–	–	–	34.5	32.0	17.4	–	34.4

Table 2: Performance on search-augmented QA tasks.

\dagger

and

\star

indicate in-domain and out-of-domain datasets, respectively. Bold indicates the best performance in each category.

Figure 3: LEFT: Proportion of redundant actions during training in webshop task. RIGHT: Path-shortening effect of HCAPO vs. GRPO in webshop task.

Figure 4: Computational cost breakdown during training. The hindsight audit pass accounts for only 8.3% of total training time.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Success Rate during training

Qwen2.5-1.5B-Instruct
Type	Method	ALFWorld
Type	Method	Pick	Look	Clean	Heat	Cool	Pick2	All
RL Training	GRPO	85.3 $\pm$ 1.5	53.7 $\pm$ 8.0	84.5 $\pm$ 6.8	78.2 $\pm$ 7.9	59.7 $\pm$ 5.0	53.5 $\pm$ 5.6	72.8 $\pm$ 3.6
RL Training	GiGPO	94.4 $\pm$ 5.9	67.5 $\pm$ 4.6	94.8 $\pm$ 3.8	94.4 $\pm$ 7.8	79.8 $\pm$ 4.7	76.4 $\pm$ 5.4	86.7 $\pm$ 1.7
RL Training	HCAPO w/o Smooth	88.6 $\pm$ 7.0	75.0 $\pm$ 0.0	97.6 $\pm$ 1.8	90.7 $\pm$ 6.9	84.2 $\pm$ 0.0	74.2 $\pm$ 6.9	87.0 $\pm$ 4.1
RL Training	HCAPO w Smooth	93.3 $\pm$ 5.4	70.8 $\pm$ 5.9	93.1 $\pm$ 2.0	90.7 $\pm$ 6.9	86.0 $\pm$ 2.5	76.4 $\pm$ 1.0	87.2 $\pm$ 3.7

Appendix

Table 3: Performance on ALFWorld with temporal smoothing. Results are averaged over 3 random seeds. For ALFWorld, we report the average success rate (%) for each subtask as well as the overall result. We compare our proposed HCAPO with GRPO and GiGPO.

$\omega$	Pick	Look	Clean	Heat	Cool	Pick2	All
0	85.3 $\pm$ 1.5	53.7 $\pm$ 8.0	84.5 $\pm$ 6.8	78.2 $\pm$ 7.9	59.7 $\pm$ 5.0	53.5 $\pm$ 5.6	72.8 $\pm$ 3.6
0.2	89.5 $\pm$ 8.8	45.8 $\pm$ 11.8	77.8 $\pm$ 5.2	87.0 $\pm$ 6.9	78.9 $\pm$ 0.0	73.6 $\pm$ 8.6	79.7 $\pm$ 3.4
0.5	91.4 $\pm$ 6.1	79.2 $\pm$ 5.9	93.1 $\pm$ 2.0	83.3 $\pm$ 15.6	88.9 $\pm$ 0.0	80.7 $\pm$ 1.0	84.4 $\pm$ 4.8
1.0	88.6 $\pm$ 7.0	75.0 $\pm$ 0.0	97.6 $\pm$ 1.8	90.7 $\pm$ 6.9	84.2 $\pm$ 0.0	74.2 $\pm$ 6.9	87.0 $\pm$ 4.1

Appendix

Table 4: Ablation on ALFWorld with different

\omega

values. Results are averaged over 3 random seeds.

Credit Assignment in RL

Credit assignment in reinforcement learning studies how to trace rewards and failures back to the actions, states, or agents that caused them.

See all 212 papers

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents
Sep 28, 2026Haodong Zhu, Yangyang Ren, Changbai Li +4Credit Assignment in RL Step-Level Credit Assignment in RL
Beihang University · Zhongguancun Academy · Communication University of China +1
LLM Value Functions for Credit Assignment in Agentic RL
Oct 11, 2026Kaijie Zhu, Weixiang Yan, Omar Attia +3RL for LLM Agents Agentic RL
Apple
HiPER: Hierarchical Reinforcement Learning with Explicit Credit Assignment for Large Language Model Agents
Feb 18, 2026Jiangweizhi Peng, Yuanxin Liu, Ruida Zhou +4RL for LLM Agents Hierarchical RL
University of Minnesota · Northwestern University · Amazon AGI +2

Sep 28, 2026J/K move · Enter open · S save

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

Haodong Zhu, Yangyang Ren, Changbai Li, Sheng Xu+3

Beihang University · Zhongguancun Academy · Communication University of China+1

Credit Assignment in RL Step-Level Credit Assignment in RL Model-Free RL Long-Horizon LLM Agents Policy Learning RL for LLM Agents

Open paper AskPDF 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.

Abstract

Credit Assignment in RL

Explore similar work

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

LLM Value Functions for Credit Assignment in Agentic RL

HiPER: Hierarchical Reinforcement Learning with Explicit Credit Assignment for Large Language Model Agents