The Reinforcement Learning (RL) paradigm has achieved remarkable success in enhancing the reasoning capabilities of Large Language Models (LLMs). However, when applied to long-horizon tasks, it faces severe challenges: i) Due to the high task complexity, the model struggles to sample enough successful trajectories, resulting in slow convergence. ii) Relying solely on sparse final rewards causes all steps to be updated indiscriminately, encouraging redundant step generation. When both the quantity and quality of successful trajectories become difficult to guarantee, the performance is severely constrained. This dilemma stems from the limitations: existing RL paradigms rely entirely on the reasoning capability of base models, lacking the ability to actively optimize trajectories. To address the above issues, we propose a novel trajectory evolution paradigm with hindsight credit assignment, termed TrajEvolve. TrajEvolve not only relies on the trajectory inferred by the model but also generates ``evolutionary trajectories'' by refining low-quality steps in historical trajectories, thereby exposing the policy to high-quality compositions that lie within the base model's support but are rarely sampled within practical training budgets. Furthermore, TrajEvolve reformulates step-level continuous credit assignment as a binary classification task, whether each step is necessary for task completion. This simplification not only reduces the learning difficulty but also enables step labels to be obtained through counterfactual verification, achieving precise identification of redundant steps. Extensive experiments on two datasets demonstrate the superiority of the proposed method.
Figures & tables
Figure 1: Overview of the TrajEvolve training framework. Left: Training pipeline with hindsight verification and trajectory evolution module. Right: Three trajectory evolution strategies.
Type
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Closed-Source Model
Prompting
GPT-4o
81.3
25.0
36.3
38.5
40.7
23.1
45.3
30.8
18.8
Prompting
Gemini-2.5-Pro
83.3
42.9
48.6
54.5
64.7
42.9
57.8
42.8
26.6
Qwen2.5-1.5B-Instruct
Prompting
Qwen2.5
11.1
0.0
7.1
0.0
0.0
7.7
5.5
22.4
5.5
Table 1: Performance Comparison on ALFWorld and Webshop benchmarks. Results are averaged over 3 random seeds. For ALFWorld, we report the success rate (%) for the results. For WebShop, we report both the average score and the success rate (%).
Figure 2: Validation success rate during training on ALFWorld and WebShop dataset.
Figure 3: Effect of integrating the trajectory evolution module with different RL baselines. The shaded area indicates the performance gain from adding our evolution module.
Model
ALFWorld
WebShop
Avg. Steps
Succ. Steps
Avg. Steps
Succ. Steps
PPO
17.45
10.63
8.94
8.61
RLOO
15.20
10.06
7.98
7.11
GRPO
15.36
11.26
10.97
12.61
GiGPO
11.58
8.76
6.16
5.33
Ours
9.63
7.91
5.89
5.15
Table 2: Redundancy analysis on ALFWorld and WebShop. “Avg. Steps” denotes mean steps across all trajectories. “Succ. Steps” measures mean steps for successful trajectories only. Lower values indicate more efficient execution.
Figure 4: Ablation study on ALFWorld and Webshop benchmarks. Qwen2.5-1.5B-Instruct serves the base models.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Training curves on ALFWorld with Llama-3.2-3B-Instruct. Left: validation success rate. Right: Average episode length. Our method consistently achieves a higher success rate and shorter, more efficient trajectories than all baselines.
Figure 6: Training curves on Webshop with Llama-3.2-3B-Instruct. Left: validation success rate. Right: Average episode length. Our method consistently achieves a higher success rate and shorter, more efficient trajectories than all baselines.
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
PPO
57.14
25.00
29.17
27.78
21.05
41.67
37.50
86.25
62.50
GRPO
57.14
25.00
20.83
33.33
21.05
41.67
36.72
82.66
65.63
RLOO
94.29
62.50
95.83
66.67
52.63
87.50
81.25
79.81
66.41
GIGPO
65.71
37.50
66.67
77.78
52.63
58.33
62.50
83.04
63.28
Ours
97.14
62.50
100.00
88.89
89.47
91.67
92.19
88.13
76.56
Appendix
Table 3: Performance comparison on ALFWorld and WebShop with Llama-3.2-3B-Instruct, the best result in each column is highlighted in bold.
Figure 7: Training accuracy of our discriminator on ALFWorld (top) and WebShop (bottom), reporting overall, success, and failure accuracy across training iterations.
Figure 8: Per-step time overhead of each training stage on ALFWorld (left) and WebShop (right).
Method
IID
OOD
GRPO
92.19
86.72
GiGPO
92.97
87.50
Ours
95.31
89.06
Appendix
Table 4: Final success rate (%) on ScienceWorld with Qwen2.5-7B-Instruct after 150 iterations. IID: seen task variants; OOD: unseen variants within seen categories.
Figure 9: Mean KL divergence (left) and clip fraction (right) during training on ALFWorld and WebShop, indicating stable policy updates.
Figure 10: Mean KL divergence (left) and clip fraction (right) during the trajectory evolution stage on ALFWorld and WebShop.
Step
Action
Observation
Credit
Dep(t)
0
go to drawer 1
The drawer 1 is closed.
Redundant
{1}
1
open drawer 1
The drawer 1 is open. In it, you see nothing.
Redundant
∅
2
go to drawer 2
The drawer 2 is closed.
Redundant
{3}
3
open drawer 2
The drawer 2 is open. In it, you see a spoon 1.
Redundant
∅
4
go to countertop 1
On the countertop 1, you see …a knife 1 …(and 18 other objects).
Necessary
{5,7,9}
5
take knife 1 from countertop 1
You pick up the knife 1 from the countertop 1.
Necessary
{7,9}
Appendix
Table 5: Case study of counterfactual credit analysis on a successful ALFWorld trajectory. The agent is asked to put a clean knife in sidetable . Each step t is removed from the trajectory (together with steps already identified as redundant) and the remaining actions are replayed in the environment: t is labeled Necessary if the task then fails, and Redundant otherwise. Dep(t) is the set of later steps whose actions become inexecutable ( “Nothing happens.” ) in this replay. When t is redundant, all steps in Dep(t) are marked redundant as well without further replay ( † ). Steps 0–3 are unsuccessful drawer searches and are all redundant; steps 4–9 form the necessary chain ( locate → grasp → clean → deliver ). These labels supervise the training of our step discriminator.
Figure 11: The prompt template of ALFWorld agents.
Figure 12: The prompt template of WebShop agents.
Figure 13: The think-only prompt template used during the trajectory evolution phase in ALFWorld. The predetermined action is provided and the model is asked to generate only the reasoning.
Figure 14: The think-only prompt template used during the trajectory evolution phase in WebShop. The predetermined action is provided and the model is asked to generate only the reasoning.
Reinforcement learning (RL) has become a dominant paradigm for enhancing LLMs' reasoning capabilities. Yet long-horizon autoregressive rollouts introduce a fundamental limitation: local policy mismatch can compound into severe state distribution shift over trajectories. Existing LLM RL methods, such as GRPO and GSPO, control policy mismatch at the token or sequence level, but overlook this trajectory-induced shift, causing training instability and eventual collapse as the horizon grows. To close the state distribution gap, we propose Trajectory-Aware Policy Optimization (TAPO), a principled framework that theoretically derives the state-distribution correction from the off-policy policy gradient and incorporates it into the RL objective. TAPO further employs a geometric-mean estimator for variance reduction, together with a length-aware dynamic clipping that prevents overly deviated updates across the trajectory. Extensive experiments demonstrate that TAPO significantly surpasses existing LLM RL algorithms across eight competition-level benchmarks, achieving up to 48% and 12% improvement over GRPO on mathematical reasoning and algorithmic coding, with substantially enhanced training stability.
Zhicheng Cai, Hanlin Wu, Weinan Dai +4
Institute for AI Industry Research (AIR), Tsinghua University SIA-Lab of Tsinghua AIR and ByteDance Seed
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
Recent advances in Reinforcement Learning (RL) have underscored its potential for incentivizing reasoning capabilities of Large Language Models (LLMs). However, existing step-level efforts suffer from costly annotations that limit domain coverage, while scalar scores further impose an information bottleneck, offering insufficient semantic bandwidth to improve intermediate decisions. Alternative language-critique approaches, which rely on frozen or external critics, provide richer textual feedback but lack the scalability needed for sustained policy improvement. In this work, we propose language-driven stepwise trajectory redirection, termed as STRIDE, a novel training framework that shifts process supervision from scalar rewards to learnable stepwise language feedback. Specifically, we co-train a generator and a generative verifier using only outcome-based rewards, eliminating external annotations, while delivering sustained policy improvement through jointly aligned verifier training. The verifier's stepwise language critiques explicitly localize and explain failures, enabling the generator to redirect reasoning trajectories at intermediate steps toward alternative decisions. The trajectory redirection design guarantees harmless policy improvement, even under noisy or suboptimal verifier feedback. Experiments on diverse reasoning benchmarks show that STRIDE significantly outperforms state-of-the-art baselines, as well as achieving breakthroughs on zero-pass-rate problems where scalar methods yield no learning signal in our ablation studies, demonstrating the effectiveness of learnable stepwise language feedback for enhancing LLM reasoning.
Junjie Zhang, Guozheng Ma, Shunyu Liu +5
Generative AI Lab, College of Computing and Data Science, Nanyang Technological University, Singapore 639798 · Tongyi Lab, Alibaba Group