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.
X-LANCE Lab, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China · Faculty of Electronic and Information Engineering, Xi’an Jiaotong University