Credit assignment is challenging in long-horizon agentic reinforcement learning, where supervision often comes only from final rewards. Existing methods refine trajectory-level signals into step-level credits through step grouping or graph-based advantage estimation, but can overlook meaningful intermediate milestones. We propose MileGPO (Milestone Inference with Local Evidence for Graph-Based Policy Optimization), which derives process-level credit from grouped on-policy rollouts through three designs. Milestone Discovery identifies candidate milestones on successful rollouts and recurring traps on failed ones. Reliability-Calibrated Shaping (RCS) weights these candidates by outcome-based confidence, strengthening reliable milestones and traps while down-weighting uncertain ones. Progress-Contrastive Calibration (PCC) further tests whether a candidate reflects local progress and whether its incoming transition outperforms observed alternatives from the same state. MileGPO requires neither auxiliary models nor additional environment interaction. Experiments on ALFWorld and WebShop show state-of-the-art performance and a small in-distribution to out-of-distribution gap on ALFWorld. Ablations and credit diagnostics indicate that reliability weighting, local progress, and same-state branch evidence complement milestone discovery and resolve ambiguous intermediate credit.
Figures & tables
Figure 1: Trajectory-level and same-state step-level credit for two successful rollouts and one failed rollout. Here, τi is rollout i ; st(i) , at(i) , R(τi) , and AT(τi) denote its state, action, final reward, and trajectory-level advantage. Matching colors mark the same state across rollouts.
Figure 2: Structural ambiguity in early GraphGPO rollouts. Shared states create opportunities for local branch comparison, but final-state-distance ties and mixed outcomes leave progress ambiguous.
Figure 3: Overview of MileGPO. Squares denote canonicalized states, circles denote sampled actions, and check and cross marks indicate success and failure. Here, d is directed shortest-path distance ( ∞ if unreachable); S+ and S− are the milestone and trap sets; ΦR+ and ΦR− are their score-weighted potentials; and δ+ and δ− are the corresponding increases along a transition. MD discovers candidates, RCS weights and propagates them, and PCC adjusts positive scores using local progress and BCC comparisons between branches from the same state.
Method
ALFWorld
WebShop
Pick
Clean
Cool
Look
Heat
Pick2
All
Score
Succ.
Closed-Source Prompting
GPT-4o †
75.3
60.8
31.2
56.7
21.6
49.8
48.0
31.8
23.7
Gemini-2.5-Pro †
92.8
63.3
62.1
69.0
26.6
58.7
60.3
42.5
35.9
Open-Source 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, grouped into closed-source prompting, open-source prompting, and RL-based training. Rows marked with † are reported by GraphGPO 4 , rows marked with ∗ are our reproduced baselines, and the unmarked row denotes MileGPO.
Method
ID ↑
OOD ↑
Gap ↓
GiGPO
92.06\,\mbox{(0.72)}
90.17\,\mbox{(0.09)}
1.89
GraphGPO
95.25\,\mbox{(0.60)}
91.47\,\mbox{(0.51)}
3.78
MileGPO
\mathbf{96.29}\,\mbox{\mathbf{(0.55)}}
\mathbf{94.60}\,\mbox{\mathbf{(0.33)}}
1.69
Table 2: ALFWorld success rates (%) on the ID and OOD.
ALFWorld
WebShop
Method
ID ↑
OOD ↑
Score ↑
Succ. ↑
MileGPO
\mathbf{96.3}\,\mbox{\mathbf{(0.6)}}
\mathbf{94.6}\,\mbox{\mathbf{(0.3)}}
\mathbf{90.3}\,\mbox{\mathbf{(0.8)}}
\mathbf{78.6}\,\mbox{\mathbf{(1.2)}}
w/o PCC
95.9\,\mbox{(0.5)}
90.9\,\mbox{(0.5)}
87.9\,\mbox{(1.9)}
77.2\,\mbox{(2.2)}
w/o PCC, RCS
95.3\,\mbox{(0.0)}
89.7\,\mbox{(0.3)}
87.4\,\mbox{(1.5)}
73.8\,\mbox{(2.2)}
Table 3: MileGPO ablation on ALFWorld and WebShop (%).
Figure 4: WebShop credit-calibration diagnostics. (a) Validation success compares three locally trained methods. (b) Tie-correction rate measures the fraction of opposite-outcome transition pairs with equal GraphGPO credit, where shaped returns rank successful transitions higher. (c) Candidate support partitions success-visited candidates into those with local evidence (positive progress or BCC), successful-path coverage only, and weak candidates. (d) PCC evidence separates positive progress from positive sibling-branch contrast.
Figure 5: Efficiency analysis. (a) Published GraphGPO iteration times; Agg., Adv., Roll., and Upd. denote graph aggregation, graph advantage, rollout, and policy update, respectively. (b) Median single-thread CPU replay time with IQRs over five stored batches; graph construction is shared.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
Group
Hyperparameter
ALFWorld
WebShop
Model and data
Policy model
Qwen2.5-1.5B-Instruct
Qwen2.5-1.5B-Instruct
Training task groups / iteration
16
16
Rollouts per task group ( K )
8
8
Maximum prompt / response tokens
4096 / 512
4096 / 512
History length
2
2
Optimization
Actor learning rate
1×10−6
1×10−6
Appendix
Table 4: Training and evaluation hyperparameters shared by the reported local Qwen2.5-1.5B-Instruct runs on ALFWorld and WebShop. The two environment columns are shown separately for direct comparison.
Figure 6: ALFWorld prompt template. Runtime placeholders are blue and output tags are green.
Figure 7: WebShop prompt template. Runtime placeholders are blue and output tags are green.
Stage
Parameter
Role
ALFWorld
WebShop
Graph return
c
Return scale
10
10
γG
Graph-distance discount
0.20
0.20
γΦ
Potential discount
1.00
1.00
λ
Shaping coefficient
0.25
0.25
MD and RCS
w+,w−
Positive / negative potential weights
1.00 / 0.25
1.00 / 0.25
ws,wm,wf
Success, coverage, failure weights
1 / 1 / 1
1 / 1 / 1
Appendix
Table 5: MileGPO hyperparameters. MD denotes milestone discovery, RCS denotes reliability-calibrated shaping, and PCC denotes progress-contrastive calibration. The environment-specific PCC controls are fixed during training and evaluation, as are the policy-update weights.
Figure 8: WebShop training dynamics of the aligned GiGPO, GraphGPO, and MileGPO runs. From left to right, the panels show mean episode reward and validation success rate. Faint lines show per-checkpoint measurements, and solid lines show the smoothed training trends.
Figure 9: Offline replay on the same GraphGPO WebShop rollout traces We compare success/failure transitions sharing a parent state and tied under GraphGPO’s final-state-distance advantage. We report the correction rate, Ncorrected/Ntie , at each checkpoint with eligible pairs; a correction means that replayed shaping orders the successful transition above the failed one. Step 50 is omitted because it contains no eligible ties. This is a descriptive offline replay, not a causal intervention or a retrained ablation.
Branch
t
Agent action
Environment feedback / observation
rt
Successful
0
search[machine wash men’s dress shirts with polyester heathers, heathers cotton, cotton heather, needle sleeve, classic fit with color: kelly green, and fit type: youth, and size: x-small, and price lower than 40.00 dollars]
Results page 1 (50 products); B09P39QN2W , priced at \16.99$ , is listed.
0
1
click[b09p39qn2w]
Product page for B09P39QN2W ; fit-type, color, and size options are shown.
0
2
click[kelly green]
Confirms kelly green ; product page remains open.
0
3
click[x-small]
Confirms x-small ; selected options are kelly green and x-small.
0
4
click[classic fit]
Product page unchanged; the requested attribute is not an offered button.
0
5
click[needle sleeve]
Product page unchanged; the requested attribute is not an offered button.
0
Appendix
Table 6: Complete paired WebShop rollout for the representative price-constraint correction at training step 30. Both branches share the task and initial observation; all 28 successful and five failed transitions are shown.
Long-horizon LLM agents require reinforcement learning methods that can assign credit to intermediate decisions under sparse and delayed rewards. Existing group-based methods such as GRPO and GiGPO alleviate this issue by comparing rollout returns or repeated anchor states, but they still fail when the compared returns have no variation. We identify this failure mode as zero-credit failure: during early training, many failed rollouts contain useful prefixes, yet existing methods assign them no task-discriminative advantage. To address this issue, we propose Milestone Viability Potential Policy Optimization (MVPO), a potential-routed policy optimization algorithm that learns from viable failure prefixes. MVPO estimates prefix potential over Union-Find viability regions, repairs zero-credit groups with potential-difference advantages, and attenuates the potential branch according to relative performance progress. Experiments with Qwen2.5-1.5B-Instruct show that MVPO outperforms eight strong baselines, including GRPO and GiGPO. Under the same training length, MVPO improves over the GiGPO baseline by +4.4 success points on ALFWorld and +5.3 on WebShop, while adding only 0.16%-0.20% advantage-construction overhead.
Long-horizon LLM agents require reinforcement learning methods that can assign credit to intermediate decisions under sparse and delayed rewards. Recent group-based methods such as GiGPO improve over GRPO by constructing step-level advantages at repeated anchor states. However, we show that such dense credit can be statistically unreliable: under limited rollouts, rare but lucky actions may receive overly large advantages, producing divergent anchor bias and late-stage training oscillation. We propose Evidence-Calibrated Policy Optimization (ECPO), a critic-free policy optimization algorithm that calibrates step-level credit before policy updates. ECPO combines Evidence-Calibrated Action Advantage, which groups rollouts by canonical actions and shrinks low-count estimates, with Variance-Gated Credit Weighting, which suppresses anchor states dominated by within-action noise. Experiments on ALFWorld and WebShop with Qwen2.5-1.5B/7B show that ECPO consistently outperforms strong baselines, improving GiGPO by +5.2/+7.3 success points on ALFWorld/WebShop with Qwen2.5-1.5B while adding only 0.1% additional advantage-computation overhead.
Yuanfan Li, Qi Zhou, Wenjing Duan +1
X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · Faculty of Electronic and Information Engineering, Xi’an Jiaotong University
While long-horizon agentic tasks require language agents to perform dozens of sequential decisions, training such agents with reinforcement learning remains challenging. We identify two root causes: credit misattribution, where correct early actions are penalized due to terminal failures, and sample inefficiency, where scarce successful trajectories result in near-total loss of learning signal. We introduce a milestone-guided policy learning framework, BEACON, that leverages the compositional structure of long-horizon tasks to ensure precise credit assignment. BEACON partitions trajectories at milestone boundaries, applies temporal reward shaping within segments to credit partial progress, and estimates advantages at dual scales to prevent distant failures from corrupting the evaluation of local actions. On ALFWorld, WebShop, and ScienceWorld, BEACON consistently outperforms GRPO and GiGPO. Notably, on long-horizon ALFWorld tasks, BEACON achieves 92.9% success rate, nearly doubling GRPO's 53.5%, while improving effective sample utilization from 23.7% to 82.0%. These results establish milestone-anchored credit assignment as an effective paradigm for training long-horizon language agents. Code is available at https://github.com/ZJU-REAL/BEACON.