Reinforcement learning for long-horizon LLM agents faces a fundamental dilemma: successful experiences are essential for policy improvement, yet limited policy capabilities make such experiences difficult to discover. Sparse outcome rewards compound this challenge, leaving sampled trajectories with little relative feedback for learning. In this paper, we propose TriGRPO, a tree-based reinforcement learning framework that turns scarce successes into exploration and learning signals through hindsight credit assignment within and across rollout trees. TriGRPO constructs rollout trees through hindsight-guided branching: when an ongoing trajectory reaches a matched decision state, a successful action discovered during rollout initiates a sibling branch that continues autonomously, enabling further exploration and parent-sibling comparisons. Three complementary groups organize policy optimization over these trees: root groups capture within-prompt relative returns, node groups assign credit from parent-sibling outcome differences, and cross groups supplement sparse feedback with historical performance on related tasks. Experimental results demonstrate consistent gains in task performance and rollout efficiency across model scales, highlighting structured hindsight credit assignment as an effective approach to long-horizon agent learning.
Figures & tables
Figure 1: TriGRPO enhances agentic RL through hindsight credit assignment. (a) Credit assignment across trees, within a tree, and at branch nodes. (b) Superior Pareto frontier of success versus cost.
Figure 2: Overview of the TriGRPO training pipeline. Tree-structured rollouts generate R root trajectories per prompt, expanded into prefix-sharing trees. During training, successful trajectories populate the hindsight bank in real time. Upon detecting a matched state, TriGRPO creates a guided branch by injecting the hindsight action, forming a node group. Prompts sharing the same task type form a cross group to enable cross-prompt credit assignment, propagating hindsight experience across tasks. Once batch rollouts are completed, a triple-group advantage estimator assigns node, root, and cross credits for policy updates.
Method
pick
look
clean
heat
cool
pick2
All
Tokens
Qwen2.5-1.5B-Instruct
Base (no RL)
5.9
5.5
3.3
9.7
4.2
0.0
4.1
–
GRPO
85.3
53.7
84.5
78.2
59.7
53.5
72.8
0.413B
GiGPO
94.4
67.5
94.8
94.4
79.8
76.4
86.7
0.397B
GSPO
89.3
55.3
87.7
83.2
78.5
54.0
74.7
0.417B
Tree-GRPO
97.1
73.3
95.5
94.4
95.2
50.0
86.7
0.583B
Table 1: Per-type and overall ( All ) peak validation SR (%) on the ALFWorld test split, together with cumulative token consumption up to the peak step ( Tokens ). Bold marks the best value in each column (highest SR, lowest token cost). Base is the untrained instruct model.
Multi-hop
Single-hop
Method
HotpotQA
2Wiki
MuSiQue
Bamboogle
Avg.
NQ
TriviaQA
PopQA
Avg.
Qwen2.5-1.5B-Instruct
Base (no RL)
5.9
4.3
2.6
8.0
5.2
7.1
22.4
9.9
13.1
GRPO
14.6
24.4
2.2
4.0
11.3
39.4
51.0
39.7
43.3
GiGPO
16.7
25.6
3.4
54.8
25.1
16.4
34.8
14.9
22.0
GSPO
15.8
23.7
2.5
4.8
11.7
36.8
48.9
37.3
41.0
Table 2: SearchQA accuracy (%) on four multi-hop and three single-hop benchmarks, with Avg. the unweighted mean over each group. Bold marks the best value per column within a model block; Base is the untrained instruct model.
Method
pick
look
clean
heat
cool
pick2
All
Tokens
TriGRPO (root+cross+node)
96.6
86.7
95.8
100.0
91.3
88.2
93.8
0.338B
root+cross (w/o node)
98.9
73.2
91.4
96.7
78.7
91.0
89.8
0.294B
root+node (w/o cross)
93.1
70.8
90.0
69.9
71.4
80.2
81.9
0.249B
GiGPO+cross
95.0
74.6
94.0
89.8
83.1
87.8
89.5
0.459B
GRPO (root only)
91.4
63.6
70.6
71.4
64.0
76.2
72.9
0.403B
Table 3: Component ablation on ALFWorld (Qwen2.5-3B-Instruct, 150 training steps). Per-type and overall ( All ) peak validation SR (%) are measured on the validation split ( n=128 , t=0.4 ); Tokens is the cumulative token consumption up to the peak step. The GiGPO+cross row replaces TriGRPO’s hindsight-guided node grouping with GiGPO state-prefix grouping while retaining Across .
Figure 3: Autonomous performance by initial task difficulty. (a) Mean unguided success rates throughout training; annotations show TriGRPO–GRPO differences in percentage points. Initial trials define both the groups and the shared starting points. (b) Per-task success counts across four trials at step 150, for very hard tasks ( 0<p^0≤0.05 ) and tasks with no initial success. Segment widths show task proportions; numbers give task counts.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Method
pick
look
clean
heat
cool
pick2
All
Tokens
TriGRPO (prefix-only loss)
96.6
86.7
95.8
100.0
91.3
88.2
93.8
0.338B
+ branch mean aggregation
89.7
87.5
96.2
90.0
68.2
95.7
88.3
0.292B
+ branch max aggregation
100.0
62.5
100.0
88.2
90.0
71.4
88.3
0.389B
+ branch mean agg. w/ shuffle
94.3
80.0
95.0
73.3
73.9
96.0
87.5
0.325B
Appendix
Table 4: Prefix-credit ablation on ALFWorld (Qwen2.5-3B-Instruct); columns follow Table 3 . The default TriGRPO row writes only each trajectory’s own outcome credit into its tokens (branch credit applies solely to tokens after the branch point). The mean variant additionally writes the average on-policy continuation performance from each shared prefix into the prefix tokens’ loss; the max variant instead writes the best continuation observed from each prefix into the prefix tokens’ loss; the shuffle control permutes the real per-prefix credits within each batch without replacement, preserving their mean, variance, extremes, and total gradient scale while breaking the credit–prefix correspondence.
Method
pick
look
clean
heat
cool
pick2
All
Tokens
TriGRPO ( α=0.3 , κ=8 )
96.6
86.7
95.8
100.0
91.3
88.2
93.8
0.338B
fine-only ( κ=0 )
100.0
77.8
93.3
88.2
94.4
78.3
90.6
0.383B
coarse-only (fine EMA off)
96.8
87.5
94.6
91.7
81.5
92.3
91.4
0.375B
no EMA smoothing ( α=1.0 )
96.4
84.6
85.7
84.6
69.6
78.3
83.6
0.417B
Appendix
Table 5: Cross-advantage ablation on ALFWorld (Qwen2.5-3B-Instruct); columns follow Table 3 . All variants keep the full three-level estimator and modify only the historical baseline μ[t] of Across . The default row uses EMA smoothing α=0.3 with coarse-prior shrinkage κ=8 ; κ=0 removes the task-type prior, “coarse-only” removes the fine per-task EMA, and α=1.0 replaces the smoothed history with the raw current-batch mean.
Figure 4: First-turn (no-history) prompt template for the ALFWorld embodied agent.
Figure 5: First-turn (no-history) prompt template for the search QA agent.
Figure 6: Prompt template for the ALFWorld embodied multi-turn agent.
Figure 7: Prompt template for the search-augmented multi-turn QA agent.
Figure 8: Hindsight branch: at training time TriGRPO injects one successful action (empty <think> + a single action span) into the generation prompt of the first step of a hindsight branch. Observation content is unchanged; the injected span is relocated to the response side and receives only behavior-cloning (BC) loss.
Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.
Outcome-supervised group-relative policy optimization (GRPO) assigns the same advantage to every token in an LLM agent trajectory, leaving useful and unhelpful decisions undifferentiated. Hindsight credit assignment (HCA) can refine this feedback, but its estimates rely on trajectories containing informative alternatives at consequential histories. We introduce TreeHCA, which couples hindsight-guided exploration with hindsight credit assignment. TreeHCA uses changes in reference-answer likelihood to revisit intermediate histories and sample alternative continuations, forming a tree of reasoning and tool interactions. Because this exploration changes the distribution of sampled continuations, we derive the corresponding inverse-hindsight importance correction, including an exact finite-pool identity. We use this structure in a normalized tree backup that propagates terminal outcomes into turn-level advantages. This shared hindsight structure is TreeHCA's central design principle, linking informative exploration with hindsight-guided credit assignment. Across seven question-answering benchmarks and three Qwen backbones, TreeHCA outperforms all baselines in aggregate exact match, validating the effectiveness of paired exploration and credit assignment for multi-turn LLM agent training. Our code is available at github.com/TheBlackCat22/TreeHCA.
Debajoy Mukherjee, Jeremy Carleton, Sushil Vemuri +2
Department of Electrical and Computer Engineering, Texas A&M University, College Station, Texas, USA
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.
Hui-Ze Tan, Xiao-Wen Yang, Hao Chen +7
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · FiT, Tencent, Shenzhen, China +2
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.
Haodong Zhu, Yangyang Ren, Changbai Li +4
Beihang University · Zhongguancun Academy · Communication University of China +1