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.
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · FiT, Tencent, Shenzhen, China +2