Reinforcement learning (RL) has become a common approach for training large language model (LLM) agents on long-horizon tasks. However, learning from sparse terminal rewards makes credit assignment and exploration difficult. We approach these challenges through a policy-induced capability region, the set of states from which the current policy can reliably complete a task. Near its boundary, an agent may need only a few actions to reach a more solvable state, even when the goal remains distant. This reduces long-horizon learning to two coupled subproblems of reaching that state and completing the task from there. We address them with paired advantages and a progressive reverse-to-forward curriculum. The advantages provide separate signals for reaching more solvable states and completing the task from them, while the curriculum expands the capability region backward along successful reference trajectories and then into off-reference states through on-policy exploration. On ALFWorld and WebShop, our method outperforms competitive agentic RL methods at both model scales, achieving success rates of 90.1%/96.1% and 80.2%/82.6% with Qwen2.5-1.5B/7B-Instruct, respectively.
Figures & tables
Figure 1: The three curves show Pass@1 at checkpoints 20, 40, 60 in reverse curriculum training , as the training start moves backward along a successful reference trajectory from near the goal toward the original task start. Defining the capability region on this trajectory as starting positions with Pass@1 above 80% , we observe that this region also expands toward the original start. By ckp60, its new boundary reaches approximately 60% remaining steps.
Type
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Closed-Source Models
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
1.5B
Prompting
Qwen2.5
5.9
5.5
3.3
9.7
4.2
0.0
4.1
23.1
5.2
Prompting
ReAct
17.4
20.5
15.7
6.2
7.7
2.0
12.8
40.1
11.3
Table 1: Performance on ALFWorld and WebShop. We report success rates (%) for ALFWorld and task scores and success rates (%) for WebShop. Subscripts denote standard deviations where available. For our method, they are computed over three evaluation seeds using a fixed checkpoint. Baseline results are taken from GiGPO ( Feng et al., 2025 ) and CRPS ( Zhang and Yang, 2026 ) . Bold indicates the best mean in each column within a model scale.
Figure 2: Prefix endpoint coverage during ALFWorld training with Qwen2.5-7B-Instruct. In two panels, the left bar of each pair represents PA and the right bar represents GRPO. Both methods are initialized from the same model checkpoint and trained on the same dataset. PA samples exactly two suffixes from each unique endpoint, whereas GRPO observes one continuation for each prefix reaching that endpoint, so its suffix count is determined by m(e) . (a) Bars show the mean number of distinct prefix endpoints per training step, grouped by value V(e) .Curves show the mean number of suffixes per endpoint. (b) Endpoint counts restricted to those reached by exactly one prefix, m(e)=1 . PA’s two suffixes can reveal mixed outcomes V(e)=0.5 at these singleton endpoints.
Figure 3: Distribution of the number of unique prefix endpoint contexts ∣E∣ reached per training on Webshop.
Curriculum
Rev. PA
Fwd. PA
Succ. (%)
Reverse only
–
–
68.8
Reverse + Forward
–
–
74.7
Reverse + Forward
✓
–
76.6
Reverse + Forward
✓
✓
80.2
Table 2: Ablation study on WebShop using Qwen2.5-1.5B-Instruct.
Figure 4: (a) Validation success against cumulative model-generated environment steps. (b) Environment steps consumed per training step for each arm.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Config
ALFWorld
WebShop
train_batch_size
32
32
n_samples_per_prompt
8
8
ppo_mini_batch_size
16
16
ppo_micro_batch_size_per_gpu
2
1
ppo_max_token_len_per_gpu
12288
15360
log_prob_max_token_len_per_gpu
12288
15360
Appendix
Table 3: Hyperparameters of ALFWorld and WebShop.
Figure 5: Prompt template used for the WebShop agent.
Figure 6: Prompt template used for the ALFWorld agent.
Figure 7: Illustration of a WebShop shopping task through multi-turn interaction.
Figure 8: Illustration of an ALFWorld household task through multi-turn interaction.
Training LLMs as interactive agents for multi-turn decision-making remains challenging, particularly in long-horizon tasks with sparse and delayed rewards, where agents must execute extended sequences of actions before receiving meaningful feedback. Most existing reinforcement learning (RL) approaches model LLM agents as flat policies operating at a single time scale, selecting one action at each turn. In sparse-reward settings, such flat policies must propagate credit across the entire trajectory without explicit temporal abstraction, which often leads to unstable optimization and inefficient credit assignment. We propose HiPER, a novel Hierarchical Plan-Execute RL framework that explicitly separates high-level planning from low-level execution. HiPER factorizes the policy into a high-level planner that proposes subgoals and a low-level executor that carries them out over multiple action steps. To align optimization with this structure, we introduce a key technique called hierarchical advantage estimation (HAE), which carefully assigns credit at both the planning and execution levels. By aggregating returns over the execution of each subgoal and coordinating updates across the two levels, HAE provides an unbiased gradient estimator and provably reduces variance compared to flat generalized advantage estimation. Empirically, HiPER achieves state-of-the-art performance on challenging interactive benchmarks, reaching 97.4% success on ALFWorld and 83.3% on WebShop with Qwen2.5-7B-Instruct (+6.6% and +8.3% over the best prior method), with especially large gains on long-horizon tasks requiring multiple dependent subtasks. These results highlight the importance of explicit hierarchical decomposition for scalable RL training of multi-turn LLM agents.
Jiangweizhi Peng, Yuanxin Liu, Ruida Zhou +4
University of Minnesota · Northwestern University · Amazon AGI +2
Reinforcement learning (RL) for large language model (LLM) agents remains challenging in long-horizon tasks with sparse outcome rewards, where assigning credit to individual actions is difficult. Methods such as GRPO assign the same trajectory-level advantage to all actions, while critic-based methods require learning an additional value function that can be costly and unstable. We introduce LLM Value Function RL (LVRL), which uses the pretrained knowledge and in-context learning ability of an LLM to estimate policy-aware state values without finetuning a separate critic. LVRL conditions the value model on group context and calibrates its predictions using known values at the initial and terminal states, enabling step-level credit assignment from estimated value differences. We further extend this idea to learning from an expert policy through on-policy distillation (OPD), introducing LLM Value Function OPD (LVOPD), which focuses teacher supervision on actions associated with decreases in estimated value. We evaluate our approach across diverse agentic benchmarks: AppWorld, BabyAI, and SWE-bench Verified. Across policy scales (4B to 32B), LVRL consistently and substantially outperforms both GRPO and PPO. On AppWorld and SWE-bench Verified, LVRL yields absolute improvements of up to 13.6 and 8.6 percentage points over GRPO. Notably, on tasks requiring extended exploration like BabyAI, LVRL bridges the gap from total failure to 75.0% success. Furthermore, LVOPD yields consistent improvements over standard distillation baselines on AppWorld. Finally, Monte-Carlo analysis confirms that our frozen critic accurately identifies semantic pitfalls and recoveries, proving that LVRL extracts robust, policy-aware step-level credit from sparse terminal outcomes.
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.