Paper deep dive
MileGPO: Milestone Inference with Local Evidence for Graph-Based Policy Optimization of Long-Horizon LLM Agents
Bo Qian, Yuting Wu, Shuang Zeng, Huaiyu Wan, Dalin Zhang, Jiqiang Liu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/21/2026, 3:40:56 AM
Summary
The paper introduces MileGPO, a graph-based policy optimization method for long-horizon LLM agents that addresses credit assignment challenges by inferring intermediate milestones and traps from on-policy rollouts. It employs Milestone Discovery to identify candidate states, Reliability-Calibrated Shaping to weight them by outcome confidence, and Progress-Contrastive Calibration to validate local progress and branch superiority, achieving state-of-the-art performance on ALFWorld and WebShop without auxiliary models.
Entities (10)
Relation Signals (9)
MileGPO → evaluatedon → ALFWorld
confidence 100% · Experiments on ALFWorld and WebShop show state-of-the-art performance...
MileGPO → evaluatedon → WebShop
confidence 100% · Experiments on ALFWorld and WebShop show state-of-the-art performance...
MileGPO → usescomponent → Progress-Contrastive Calibration
confidence 95% · Progress-Contrastive Calibration (PCC) further tests whether a candidate reflects local progress...
MileGPO → usescomponent → Milestone Discovery
confidence 95% · MileGPO... through three designs. Milestone Discovery identifies candidate milestones...
MileGPO → usescomponent → Reliability-Calibrated Shaping
confidence 95% · Reliability-Calibrated Shaping (RCS) weights these candidates by outcome-based confidence...
Progress-Contrastive Calibration → includescomponent → Branch-Counterfactual Credit
confidence 90% · its Branch-Counterfactual Credit (BCC) component compares sibling transitions from the same state.
MileGPO → outperforms → GraphGPO
confidence 90% · MileGPO achieves state-of-the-art performance... consistent improvements over reproduced graph-based baselines... smaller than those of... GraphGPO
MileGPO → outperforms →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 ansition outperforms observed alternatives from the same this http URL 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.
Tags
Links
- Source: https://arxiv.org/abs/2608.19803v1
- Canonical: https://arxiv.org/abs/2608.19803v1
Trouble viewing inline? Open PDF directly →
Full Text
73,355 characters extracted from source content.
Expand or collapse full text
MileGPO: Milestone Inference with Local Evidence for Graph-Based Policy Optimization of Long-Horizon LLM Agents Bo Qian Yuting Wu Thanks: Corresponding author. Shuang Zeng Huaiyu Wan Dalin Zhang Jiqiang Liu Affiliation: Beijing Jiaotong University, China Email: ytwu1,hywan,dalin,jqliu@bjtu.edu.cn Affiliation: bobo1398861921@gmail.com, zengs@pku.edu.cn Abstract 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. 1 Introduction Figure 1: Trajectory-level and same-state step-level credit for two successful rollouts and one failed rollout. Here, τi _i is rollout i; st(i)s_t^(i), at(i)a_t^(i), R(τi)R( _i), and AT(τi)A^T( _i) denote its state, action, final reward, and trajectory-level advantage. Matching colors mark the same state across rollouts. In recent years, large language models (LLMs) have evolved from single-turn text generators into capable agents that can reason, invoke external tools, and execute tasks over extended horizons 35; 19; 27. Such agents are increasingly applied to long-horizon tasks such as web navigation and embodied instruction following 6; 39; 24, where successful completion depends on a coherent sequence of interdependent decisions. Reinforcement learning (RL) provides a natural framework for learning to improve such agents from final rewards at the task-level 15; 8; 31. However, when supervision is reduced to a final reward, assigning credit to intermediate decisions becomes challenging. As illustrated in Figure 1, trajectory-level methods assign the same final-reward-derived advantage to all actions in a rollout, while step-level grouping methods compare actions taken under the same state and provide finer-grained credit 32; 21; 7. GraphGPO 4 further organizes grouped on-policy rollouts into a task-local transition graph, where each transition represents a state–action–next-state interaction step, and propagates credit according to each state’s shortest-path distance to a successful final state. Although this graph structure provides dense intermediate supervision, final goal distance primarily captures reachability, rather than reliable progress: states with the same distance can have substantially different probabilities of leading to success, while important intermediate stages may receive weak credit simply because they remain far from the final goal. 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. As shown in Figure 2, in ALFWorld and WebShop, about 74%74\% of the transitions originate from states shared among the rollouts, and most shared states contain multiple observed actions, providing recurring states and sibling branches from which to infer intermediate credit. However, the final-goal distance assigns the same credit to 54.4%54.4\% and 72.7%72.7\% of the same-state action pairs, respectively, while identical transitions can appear in both successful and failed trajectories. Thus, the rollout graph offers useful evidence for finer credit assignment, but exploiting it raises three questions about how to discover, weight, and validate intermediate credit anchors. To address these questions, we propose the MileGPO (Milestone Inference with Local Evidence for Graph-Based Policy Optimization), illustrated in Figure 3, with a sequence of nested credit designs: (1) Milestone Discovery (MD): Not every state on a successful trajectory marks meaningful progress. MD uses final rewards and recurring rollout structures to identify candidate milestones from successful trajectories and recurring traps from failed ones. (2) Reliability-Calibrated Shaping (RCS): Candidate anchors have unequal final-reward evidence. RCS weights their positive or negative influence by empirical reliability, strengthening well-supported candidates while suppressing uncertain ones. (3) Progress-Contrastive Calibration (PCC): Final-reward association alone cannot distinguish genuine progress from incidental correlation. PCC evaluates local advancement, while its Branch-Counterfactual Credit (BCC) component compares sibling transitions from the same state. MileGPO modifies only step-level advantage estimation and requires no external process annotations or auxiliary inference. We evaluate MileGPO on two challenging long-horizon agent benchmarks, ALFWorld and WebShop. MileGPO achieves state-of-the-art performance on both benchmarks, with consistent improvements over reproduced graph-based baselines. Its ALFWorld ID–OOD gap is only 1.691.69 points, smaller than those of GiGPO (1.891.89) and GraphGPO (3.783.78), demonstrating stronger generalization to unseen task configurations. Further analysis shows that milestone discovery alone can introduce noisy credit, whereas reliability weighting recovers outcome-consistent preferences and local progress with the same-state branch evidence resolves distinctions obscured by final-goal distance. These findings attribute MileGPO’s gains to calibrated intermediate credit rather than to indiscriminate milestone propagation. Our main contributions are as follows: • Revealing unreliable intermediate credit. We reveal that final-goal-distance credit leaves many same-state branches indistinguishable and that success-visited states do not necessarily represent reliable progress. • Proposing a rollout-native policy optimization algorithm. We introduce MileGPO, which learns from rollout graphs and on-policy rewards without external annotations, critics, reward models, or auxiliary inference. • Achieving strong empirical performance. MileGPO achieves state-of-the-art performance on ALFWorld and WebShop, while ablations and diagnostics validate its credit-calibration mechanism. 2 Related Work 2.1 Reinforcement Learning for LLM Agents LLM post-training builds on policy-gradient estimators such as REINFORCE, GAE, and PPO 32; 20; 21. RLHF learns human-preference rewards 25; 15; 2, whereas DPO bypasses an explicit reward-model RL loop 18. For verifiable reasoning, RLOO, GRPO, and DAPO compare sampled responses without a value model 11; 1; 22; 36, as exemplified by DeepSeek-R1, while process supervision adds intermediate feedback 8; 12. These objectives extend to agents that interact with search engines, websites, embodied environments, and other agents over multiple turns 40. Reflection, search-guided collection, and hierarchical actor–critic methods use verbal memory, tree search, or learned values 23; 16; 41, while Agent Lightning decouples agent execution from training 13. Recent methods refine credit granularity: GiGPO compares actions at recurring states, HGPO conditions comparisons on interaction history 9, StepPO, BiPACE, and Progress Advantage use step-aligned, action-conditioned, or policy-derived signals 26; 28; 14, and graph-based methods merge grouped trajectories into task-local structures 30. 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+ _R^+ and ΦR− _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. 2.2 Process-Level Credit Assignment Process reward models provide step-level supervision but require process labels and may degrade under distribution shift 12; 29; 38. Annotation-light alternatives estimate intermediate values through search or derive process signals from outcome rewards 3; 5. TreeRPO and TreeRL share prefixes and compare branches through tree-structured rollouts, while GraphPO merges equivalent reasoning states during structured sampling 33; 10; 37. These approaches introduce auxiliary process estimation or alter rollout collection through search and branching. 3 Method MileGPO adds intermediate credit to the final-goal credit used by GraphGPO. It has three steps. MD finds milestone and trap candidates from grouped on-policy rollouts. RCS weights these candidates by their scores and converts changes in graph-distance potentials into positive or negative credit. PCC rechecks positive candidates by measuring local progress and comparing transitions from the same source state. Figure 3 shows the full procedure. All three steps reuse one rollout graph and change only the advantage estimation. 3.1 Preliminaries: Grouped Rollout Graph For each task q, the current policy samples a group of K interaction trajectories q=τii=1KT_q=\ _i\_i=1^K. Each trajectory τi=(si,0,ai,0,…,si,Ti) _i=(s_i,0,a_i,0,…,s_i,T_i) has length TiT_i and a final environment reward RienvR_i^env, and yi=[Rienv>θR]y_i=1[R_i^env> _R] marks success under the task-specific threshold θR _R. Following GraphGPO 4, we merge all trajectories for task q into a directed transition graph q=(q,ℰq)G_q=(V_q,E_q) whose nodes are canonicalized observations and whose edges e=(u,v)e=(u,v) are observed transitions. We write g for the successful final state and d(u,v)d(u,v) for the directed shortest-path distance, setting d(u,v)=∞d(u,v)=∞ when v is unreachable, in which case every distance-decayed term below is zero. GraphGPO then assigns each observed transition a dense return according to the distance from its destination to g: rG(u,v)=cγGd(v,g),r^G(u,v)=c\, _G^d(v,g), (1) where c sets the return scale and γG∈(0,1] _G∈(0,1] controls decay with distance. This return captures reachability but cannot distinguish destinations at the same graph distance; MileGPO preserves it and supplements it with intermediate credit as shown in Figure 3. 3.2 MD: Milestone Discovery MD uses the outcome rewards and transition structure of the rollout group to discover two kinds of intermediate targets. A milestone candidate is a nonfinal state visited by successful trajectories. A trap candidate is a state observed only in failed trajectories that either appears across multiple failures or is revisited. MD first scores these states and then propagates every selected state with equal weight. 3.2.1 Finding Candidates Let q+=τi:yi=1T_q^+=\ _i:y_i=1\ and q−=τi:yi=0T_q^-=\ _i:y_i=0\ be the successful and failed trajectories for task q. For a node v, let (v)T(v) contain the trajectories that visit v (each counted once), with +(v)T^+(v) and −(v)T^-(v) denoting its successful and failed subsets. We compute the group and node-conditional success rates as pq+=|q+||q|,p+(v)=|+(v)||(v)|.p_q^+= |T_q^+||T_q|, p^+(v)= |T^+(v)||T(v)|. (2) To score a milestone candidate v, MD first compares its conditional success rate p+(v)p^+(v) with the rollout-group success rate pq+p_q^+. We retain only positive differences: ℓ+(v)=max(p+(v)−pq+,0). ^+(v)= (p^+(v)-p_q^+,0 ). (3) Thus, ℓ+(v)>0 ^+(v)>0 only when trajectories visiting v have a higher success rate than the average across the rollout group. We separately measure how broadly v appears across successful trajectories: m(v)=|+(v)|max(|q+|,1).m(v)= |T^+(v)| (|T_q^+|,1). (4) Here, m(v)m(v) is the fraction of sampled successful trajectories that visit v. We also define C(v)C(v) as the sum of the in-degree and out-degree of v in qG_q, divided by the largest such sum over success-visited states, so that C(v)∈[0,1]C(v)∈[0,1] measures how central v is among the states that successful trajectories traverse. MD combines these three quantities into the initial milestone score: S0+(v)=wsℓ+(v)+wmm(v)+wcC(v).S_0^+(v)=w_s ^+(v)+w_mm(v)+w_cC(v). (5) wsw_s, wmw_m, and wcw_c weight the success-rate difference, successful trajectory coverage, and graph connectivity, respectively. Let pq−=1−pq+p_q^-=1-p_q^+ be the group failure rate and let p−(v)=|−(v)|/|(v)|p^-(v)=|T^-(v)|/|T(v)| be the failure rate among trajectories that visit v. For a state that no successful trajectory visits, we keep only the amount by which this rate exceeds the group average: ℓ−(v)=max(p−(v)−pq−,0) ^-(v)= (p^-(v)-p_q^-,0). We also compute the fraction of failed trajectories that visit v as f−(v)=|−(v)|/max(|q−|,1)f^-(v)=|T^-(v)|/ (|T_q^-|,1). Finally, L(v)=nre(v)/max(|(v)|,1)L(v)=n_re(v)/ (|T(v)|,1) is the average number of revisits per visiting trajectory, where nre(v)n_re(v) counts visits to v after its first occurrence in each trajectory. MD combines these quantities into the trap score: S−(v)=wfℓ−(v)+wlf−(v)L(v).S^-(v)=w_f ^-(v)+w_lf^-(v)L(v). (6) where wfw_f and wlw_l weight the excess failure rate and the recurrence of v in failed behavior. We denote the selected milestones and traps by +S^+ and −S^-, respectively. 3.2.2 Uniform target propagation MD assigns every selected state unit weight and propagates it through the graph distance. With decay ω∈(0,1]ω∈(0,1], the two potential maps are ΦS+(s)=maxv∈+ωd(s,v),ΦS−(s)=maxv∈−ωd(s,v). array[]rcl _S^+(s)&=& _v ^+ω^d(s,v),\\ _S^-(s)&=& _v ^-ω^d(s,v). array (7) Here, ΦS+(s) _S^+(s) and ΦS−(s) _S^-(s) measure how close s is to the nearest milestone and the nearest trap, respectively, with the maximum retaining the largest distance-decayed target value. RCS next replaces the unit weights with candidate scores. 3.3 RCS: Reliability-Calibrated Shaping RCS uses the same candidates as MD but weights them by their task-wise max-normalized scores S¯0+ S_0^+ and S¯− S^-: ΦR+(s)=maxv∈+S¯0+(v)ωd(s,v),ΦR−(s)=maxv∈−S¯−(v)ωd(s,v). array[]rcl _R^+(s)&=& _v ^+ S_0^+(v)ω^d(s,v),\\ _R^-(s)&=& _v ^- S^-(v)ω^d(s,v). array (8) Thus ΦR+(s) _R^+(s) and ΦR−(s) _R^-(s) are the score-weighted counterparts of ΦS+(s) _S^+(s) and ΦS−(s) _S^-(s), so that higher-scoring targets produce larger potentials. We keep milestones and traps separate because their contributions have opposite signs. RCS next checks whether a transition increases either potential. Writing Φ+ ^+ and Φ− ^- for the positive and negative potentials in use, which are ΦR+ _R^+ and ΦR− _R^- here, a transition from sts_t to st+1s_t+1 discards negative changes: δt+=max(γΦw+Φ+(st+1)−w+Φ+(st),0), _t^+= ( _ w_+ ^+(s_t+1)-w_+ ^+(s_t),0 ), (9) δt−=max(γΦw−Φ−(st+1)−w−Φ−(st),0). _t^-= ( _ w_- ^-(s_t+1)-w_- ^-(s_t),0 ). (10) Here, δt+ _t^+ and δt− _t^- are the discounted increases in milestone and trap potential along the transition, w+w_+ and w−w_- scale these changes, and γΦ _ discounts the next-state potential. The return uses δt+−δt− _t^+- _t^-, rewarding movement toward milestones and penalizing movement toward traps. This is a one-sided credit rule rather than policy-invariant potential shaping. 3.4 PCC: Progress-Contrastive Calibration RCS uses group-level outcome rewards, so a state may score highly even when entering it makes little progress. PCC refines positive candidates with two transition-level scores. BCC compares transitions from the same source state, while local progress measures movement toward the goal and association with success. These scores update candidates rather than add rewards. 3.4.1 Branch-Counterfactual Credit (BCC) At a source state u, grouped rollouts may contain several distinct outgoing edges. We treat each observed edge e=(u,v)e=(u,v) as one sampled branch from u. BCC compares the success rate of this branch with those of the other branches observed from the same state. Let (e)T(e) contain the trajectories that use e, with +(e)T^+(e) and −(e)T^-(e) denoting its successful and failed subsets. Their rates are p+(e)=|+(e)||(e)|,p−(e)=|−(e)||(e)|.p^+(e)= |T^+(e)||T(e)|, p^-(e)= |T^-(e)||T(e)|. (11) Let ℬ(u)B(u) contain these sampled branches. For ei∈ℬ(u)e_i (u), the BCC margin is c~bcc(ei)=p+(ei)−μ+(ei). c_bcc(e_i)=p^+(e_i)-μ^+(e_i). (12) Here, μ+(ei)μ^+(e_i) is the mean success rate of the branches in ℬ(u)∖eiB(u) \e_i\, that is, of the alternatives observed at the same source state ; we set c~bcc(ei)=0 c_bcc(e_i)=0 when eie_i is the only sampled branch. We divide each margin by the largest absolute margin in task q: cbcc(ei)=c~bcc(ei)maxe∈ℰq|c~bcc(e)|.c_bcc(e_i)= c_bcc(e_i) _e _q| c_bcc(e)|. (13) b(v)=maxe=(u,v),cbcc(e)>0+(e)≠∅cbcc(e).b(v)= _ subarrayce=(u,v),\ c_bcc(e)>0\\ T^+(e)≠ subarrayc_bcc(e). (14) Thus, b(v)b(v) records the strongest observed branch preference leading to v, with b(v)=0b(v)=0 when no incoming transition satisfies both conditions; it is not a causal-effect estimate. 3.4.2 Local Progress BCC compares branches but does not capture goal progress. For e=(u,v)e=(u,v), we combine distance reduction Δd(e)=d(u,g)−d(v,g) d(e)=d(u,g)-d(v,g), success-rate gain p+(v)−pq+p^+(v)-p_q^+, and excess failure rate ℓ−(e)=max(p−(e)−μ−(e),0) ^-(e)= (p^-(e)-μ^-(e),0), where μ−(e)μ^-(e) is the mean failure rate of sibling branches in ℬ(u)B(u). Thus, ℓ−(e) ^-(e) is the edge-level counterpart of ℓ−(v) ^-(v) and falls back to max(p−(v)−pq−,0) (p^-(v)-p_q^-,0) when no sibling exists. The progress score is: ψ(e)=αdΔd(e)+αs[p+(v)−pq+]−αfℓ−(e),ψ(e)= _d d(e)+ _s [p^+(v)-p_q^+ ]- _f ^-(e), (15) where αd _d, αs _s, and αf _f weight the three terms. Let ℰpg+(v)E_pg^+(v) contain successful incoming transitions to v with ψ(e)>0ψ(e)>0. PCC takes the largest score and normalizes it over the graph: ψ~(v) ψ(v) =maxe∈ℰpg+(v)ψ(e), = _e _pg^+(v)ψ(e), (16) ψ¯(v) ψ(v) =ψ~(v)maxv′∈qψ~(v′). = ψ(v) _v _q ψ(v ). Here, ψ~(v) ψ(v) is the best progress score among successful incoming transitions and ψ¯(v)∈[0,1] ψ(v)∈[0,1] is its task-wise max-normalized value. Undefined distance changes, empty maxima, and zero normalizers yield zero. 3.4.3 Updating Candidate Scores PCC combines the branch score and the progress score: E(v)=wbcb(v)+wpgψ¯(v).E(v)=w_bcb(v)+w_pg ψ(v). (17) where wbcw_bc and wpgw_pg set their contributions. A retention indicator z(v)z(v) marks candidates with local support: z(v)=1z(v)=1 when ψ¯(v)>0 ψ(v)>0, when coverage m(v)m(v) reaches a threshold θm _m, or when κbc=1 _bc=1 and b(v)>0b(v)>0; otherwise, z(v)=0z(v)=0. The binary switch κbc _bc controls whether branch evidence alone may retain a candidate, and BCC contributes to E(v)E(v) regardless of which condition retains it. PCC updates the score as: Spcc+(v)=S0+(v)[1+wpccE(v)],z(v)=1,ρS0+(v),z(v)=0.S_pcc^+(v)= casesS_0^+(v) [1+w_pccE(v) ],&z(v)=1,\\ ρ S_0^+(v),&z(v)=0. cases (18) Here, wpccw_pcc amplifies retained candidates according to E(v)E(v), while ρ∈[0,1]ρ∈[0,1] shrinks the others. Max-normalization within task q then produces S¯pcc+ S_pcc^+. Method ALFWorld WebShop Pick Clean Cool Look Heat Pick2 All Score Succ. Closed-Source Prompting GPT-4o† 75.375.3 60.860.8 31.231.2 56.756.7 21.621.6 49.849.8 48.048.0 31.831.8 23.723.7 Gemini-2.5-Pro† 92.892.8 63.363.3 62.162.1 69.069.0 26.626.6 58.758.7 60.360.3 42.542.5 35.935.9 Open-Source Prompting Qwen2.5† 5.95.9 5.55.5 3.33.3 9.79.7 4.24.2 0.00.0 4.14.1 23.123.1 5.25.2 ReAct† 17.417.4 20.520.5 15.715.7 6.26.2 7.77.7 2.02.0 12.812.8 40.140.1 11.311.3 Reflexion† 35.335.3 22.222.2 21.721.7 13.613.6 19.419.4 3.73.7 21.821.8 55.855.8 21.921.9 RL-Based Training PPO† 64.864.8 40.540.5 57.157.1 60.660.6 46.446.4 47.447.4 54.454.4 73.873.8 51.551.5 (±3.5)(± 3.5) (±6.9)(± 6.9) (±4.9)(± 4.9) (±6.6)(± 6.6) (±4.0)(± 4.0) (±1.9)(± 1.9) (±3.1)(± 3.1) (±3.0)(± 3.0) (±2.9)(± 2.9) RLOO† 88.388.3 52.852.8 71.071.0 62.862.8 66.466.4 56.956.9 69.769.7 73.973.9 52.152.1 (±3.0)(± 3.0) (±8.6)(± 8.6) (±5.9)(± 5.9) (±8.7)(± 8.7) (±5.5)(± 5.5) (±4.7)(± 4.7) (±2.5)(± 2.5) (±5.6)(± 5.6) (±6.7)(± 6.7) GRPO† 82.8982.89 82.1482.14 73.8673.86 78.5778.57 77.7877.78 71.4371.43 77.8677.86 84.7384.73 71.3571.35 (±3.6)(± 3.6) (±6.4)(± 6.4) (±6.8)(± 6.8) (±0.0)(± 0.0) (±4.5)(± 4.5) (±3.9)(± 3.9) (±1.3)(± 1.3) (±0.5)(± 0.5) (±2.1)(± 2.1) GiGPO† 98.8198.81 95.1695.16 81.4681.46 78.5778.57 94.4494.44 93.6593.65 90.8890.88 87.9487.94 73.8373.83 (±1.7)(± 1.7) (±3.9)(± 3.9) (±0.6)(± 0.6) (±0.0)(± 0.0) (±0.0)(± 0.0) (±5.9)(± 5.9) (±1.0)(± 1.0) (±0.4)(± 0.4) (±2.3)(± 2.3) GraphGPO† 95.1595.15 100.0100.0 85.2685.26 85.7185.71 96.3096.30 93.6593.65 92.7192.71 89.2989.29 78.6578.65 (±1.6)(± 1.6) (±0.0)(± 0.0) (±2.6)(± 2.6) (±5.8)(± 5.8) (±2.6)(± 2.6) (±2.2)(± 2.2) (±1.3)(± 1.3) (±1.5)(± 1.5) (±3.9)(± 3.9) GiGPO∗ 78.5278.52 87.2687.26 98.3198.31 96.2496.24 92.9792.97 92.1592.15 90.1790.17 89.8189.81 76.1776.17 (±3.9)(± 3.9) (±0.7)(± 0.7) (±0.7)(± 0.7) (±1.9)(± 1.9) (±1.8)(± 1.8) (±0.4)(± 0.4) (±0.1)(± 0.1) (±0.9)(± 0.9) (±1.6)(± 1.6) GraphGPO∗ 78.9678.96 91.8291.82 98.6198.61 99.4499.44 89.3189.31 94.1994.19 91.4791.47 88.2488.24 74.8074.80 (±3.8)(± 3.8) (±3.3)(± 3.3) (±0.3)(± 0.3) (±0.8)(± 0.8) (±1.5)(± 1.5) (±2.0)(± 2.0) (±0.5)(± 0.5) (±1.4)(± 1.4) (±2.4)(± 2.4) MileGPO 90.4790.47 93.2993.29 98.3198.31 100.00100.00 90.6690.66 98.0298.02 94.6094.60 90.2990.29 78.5878.58 (±2.8)(± 2.8) (±1.3)(± 1.3) (±0.7)(± 0.7) (±0.0)(± 0.0) (±1.5)(± 1.5) (±0.6)(± 0.6) (±0.3)(± 0.3) (±0.8)(± 0.8) (±1.2)(± 1.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. 3.5 MileGPO Return and Policy Update MileGPO instantiates the Φ+ ^+ of Equations 9 and 10 by inserting the PCC scores into the RCS form: Φ+(s)=maxv∈+S¯pcc+(v)ωd(s,v). ^+(s)= _v ^+ S_pcc^+(v)\,ω^d(s,v). (19) The trap potential remains Φ−=ΦR− ^-= _R^- from Equation 8. Using the resulting increments δt± _t^±, and suppressing the trajectory index on step-level quantities for readability, the MileGPO step return, denoted by rtMr_t^M, is rtM=cγGd(st+1,g)+cλ(δt+−δt−).r_t^M=c\, _G^d(s_t+1,g)+cλ ( _t^+- _t^- ). (20) The first term is the GraphGPO return, and λ scales the milestone and trap correction. Directly normalizing their sum can let a small correction dominate when GraphGPO returns are tied. We instead normalize the graph and MileGPO returns separately. Let Normq,stNorm_q,s_t normalize transitions with the same task and source state, and let rtG=rG(st,st+1)r_t^G=r^G(s_t,s_t+1): A^tG=Normq,st(rtG),A^tmix=Normq,st(rtM). A_t^G=Norm_q,s_t(r_t^G), A_t^mix=Norm_q,s_t(r_t^M). (21) Here, A^tG A_t^G is the step advantage obtained from the GraphGPO return alone, while A^tmix A_t^mix is the step advantage obtained from the shaped MileGPO return. Their difference, A^tres=A^tmix−A^tG A_t^res= A_t^mix- A_t^G, isolates the milestone correction. The episode-level term restores the trajectory index: let Zi=∑ℓri,ℓtokZ_i= _ r_i, ^tok be the trajectory score of τi _i, summing the per-token rewards ri,ℓtokr_i, ^tok that the training framework assigns to its ℓ -th token, and let NormqNorm_q normalize these scores within the rollout group of task q. Each token in action ata_t then receives: At=wstep[A^tG+ηA^tres]+wepisodeNormq(Zi).A_t=w_step [ A_t^G+η A_t^res ]+w_episode\,Norm_q(Z_i). (22) Here, wstepw_step and wepisodew_episode weight step- and episode-level advantages, and η scales the milestone correction. The actor uses the same clipped token-level objective and KL regularization as the group-based baselines. MD, RCS, and PCC use only the rollout graph and on-policy outcome rewards, requiring no external process annotations, critic, reward model, or auxiliary inference. 4 Experiments Method ID ↑ OOD ↑ Gap ↓ GiGPO 92.06(0.72)92.06\, $(0.72)$ 90.17(0.09)90.17\, $(0.09)$ 1.891.89 GraphGPO 95.25(0.60)95.25\, $(0.60)$ 91.47(0.51)91.47\, $(0.51)$ 3.783.78 MileGPO 96.29(0.55)96.29\, $(0.55)$ 94.60(0.33)94.60\, $(0.33)$ 1.691.69 Table 2: ALFWorld success rates (%) on the ID and OOD. ALFWorld WebShop Method ID ↑ OOD ↑ Score ↑ Succ. ↑ MileGPO 96.3(0.6)96.3\, $(0.6)$ 94.6(0.3)94.6\, $(0.3)$ 90.3(0.8)90.3\, $(0.8)$ 78.6(1.2)78.6\, $(1.2)$ w/o PCC 95.9(0.5)95.9\, $(0.5)$ 90.9(0.5)90.9\, $(0.5)$ 87.9(1.9)87.9\, $(1.9)$ 77.2(2.2)77.2\, $(2.2)$ w/o PCC, RCS 95.3(0.0)95.3\, $(0.0)$ 89.7(0.3)89.7\, $(0.3)$ 87.4(1.5)87.4\, $(1.5)$ 73.8(2.2)73.8\, $(2.2)$ Table 3: MileGPO ablation on ALFWorld and WebShop (%). 4.1 Experimental Setup 4.1.1 Benchmarks and Evaluation ALFWorld 24 requires an agent to complete household tasks through text-based navigation and object manipulation, while WebShop 34 requires it to search for and purchase products that satisfy natural-language instructions. They evaluate embodied planning and grounded web interaction, respectively. For ALFWorld, we train on 3,553 tasks and evaluate on both the in-distribution (ID) and out-of-distribution (OOD) splits. For WebShop, we follow the repository’s evaluation protocol. GiGPO and GraphGPO serve as the primary step-group and graph-credit baselines, respectively. We report success rates on both benchmarks and WebShop task scores. For ALFWorld, we additionally include the ID–OOD gap to evaluate generalization. Most results are averaged over 3 random seeds during testing. 4.1.2 Implementation Details All local runs use Qwen2.5-1.5B-Instruct 17 and share the model, rollout, optimizer, and environment configuration. Following the shared agent protocol 7, the policy observes the two most recent interaction steps and generates reasoning within <think> tags followed by an action within <action> tags. Each iteration samples 16 task groups with eight rollouts per group. We train on two NVIDIA H20 GPUs. Since the validation curves of the original GraphGPO and GiGPO implementations under their reported configurations had not converged, we extended training for all local methods to 300 optimization steps and selected the checkpoint with the best validation performance for evaluation. We use maximum horizons of 50 steps on ALFWorld and 30 on WebShop, an actor learning rate of 10−610^-6, a KL coefficient of 0.010.01, and an invalid-action penalty of 0.10.1. More implementation details are provided in Appendix A. 4.2 Main Results Table 1 shows that MileGPO consistently improves over the reproduced baselines. On ALFWorld, it raises overall success by 3.133.13 points over GraphGPO and 4.434.43 points over GiGPO. On WebShop, it improves success by 3.783.78 and 2.412.41 points and task score by 2.052.05 and 0.480.48 points over GraphGPO and GiGPO, respectively. The gains in both strict success and graded task score indicate better task completion as well as higher-quality partial progress. Table 2 further shows that MileGPO reduces the ID–OOD gap to 1.691.69 points, compared with 3.783.78 for GraphGPO and 1.891.89 for GiGPO. This stronger generalization is consistent with MileGPO learning transferable local decision preferences: RCS suppresses milestones with weak or mixed outcome support, while PCC distinguishes competing transitions through local progress and BCC. MileGPO also exhibits lower result variance than the reproduced GraphGPO baseline on both benchmarks. By resolving local credit ties rather than relying only on final-goal distance, MileGPO provides a more discriminative credit signal, offering a plausible explanation for its simultaneous improvements in performance, generalization, and stability. 4.3 Ablation Study Table 3 evaluates PCC and RCS through cumulative removal. Each removal degrades performance across both benchmarks, while the relatively small changes on ALFWorld ID contrast with the larger losses on ALFWorld OOD and WebShop, indicating that the two components primarily improve generalization and task completion rather than fitting the in-distribution evaluation set. Removing PCC decreases ALFWorld OOD success by 3.713.71 points and widens the ID–OOD gap by 3.323.32 points, while reducing WebShop task score and success by 2.382.38 and 1.431.43 points, suggesting that local progress and branch comparisons primarily aid generalization and partial task completion. Further removing RCS causes the largest additional drop in WebShop success (3.323.32 points) and a 1.241.24-point decrease on ALFWorld OOD. PCC and RCS therefore play complementary roles: PCC sharpens local preferences and supports transfer, whereas RCS suppresses weak or inconsistent milestones and stabilizes which intermediate signals are propagated. 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. 4.4 Credit-Calibration Diagnostics To further examine how MileGPO affects the training process, we use WebShop as a representative case because it exhibits a higher rate of final-distance ties than ALFWorld. Figure 4 tracks the evolution of candidate evidence and validation performance during training, as well as whether shaped returns recover preference information obscured by GraphGPO’s final-distance credit. Panel (a) reports validation success throughout optimization, showing the training dynamics of the three methods. Panel (b) shows that RCS corrects a larger fraction of GraphGPO ties than uniform Milestone Discovery, indicating that reliability-weighted shaping recovers more outcome-consistent preferences. Panel (c) partitions success-visited candidates before PCC reweighting. The increasing local-evidence share suggests that more candidate milestones are supported by transition-level evidence. More illustrative examples of how MileGPO resolves ambiguous credit are provided in Appendix B. 4.5 Mechanism Analysis Across Environments Figure 2 and Table 1 show that MileGPO benefits from resolving such ambiguity. ALFWorld and WebShop have nearly identical shared-state transition coverage (73.7%73.7\% versus 73.9%73.9\%), showing that both environments contain enough recurring structure to mine intermediate anchors. The decisive difference is ambiguity within that structure: final-goal distance ties 54.4%54.4\% of same-state action pairs in ALFWorld but 72.7%72.7\% in WebShop. Accordingly, MileGPO produces its clearest gain on WebShop, improving both success and task score. This result distinguishes the source of the gain from graph reuse alone. GraphGPO already aggregates recurring states, yet a distance-based return cannot rank actions that lead to equally distant successors. MileGPO extracts the missing signal from two relationships available in the same rollout group: whether a transition makes local progress and whether it outperforms sibling transitions from the same parent. The larger WebShop improvement, therefore, matches the mechanism precisely: the environment with more unresolved local comparisons benefits more from PCC. 4.6 Efficiency and Computational Cost 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. We reuse the rollout graph and add no environment interactions, model passes, critics, parameters, or activation caches. For a graph with |||V| nodes, |ℰ||E| edges, N transitions, and maximum out-degree Δ , final-distance search costs O((||+|ℰ|)log||)O((|V|+|E|) |V|), candidate statistics cost O(N)O(N), and sibling comparisons cost O(|ℰ|Δ)O(|E| ). The two target potentials add O(||+|ℰ|)O(|V|+|E|) storage, leaving model-scale and rollout complexity unchanged. Figure 5(a) compares post-rollout graph processing with the substantially larger rollout and policy-update costs, while Figure 5(b) reports single-thread CPU replay results on WebShop and ALFWorld. Across both analyses, MileGPO’s post-rollout computation remains lightweight relative to model-level training costs. These results show that MileGPO improves the existing credit signal without additional environment interactions or model inference, while confining its overhead to graph processing. 5 Conclusion We study a central limitation of graph-based credit assignment for long-horizon LLM agents: final-goal distance captures reachability but can leave locally competing actions indistinguishable and cannot determine whether a success-visited state represents reliable progress. We introduce MileGPO, which extracts intermediate credit from grouped on-policy rollouts through milestone and trap discovery, reliability-calibrated shaping, and progress-contrastive calibration with same-state branch evidence, requiring no additional supervision, auxiliary models, or environment interaction. Across ALFWorld and WebShop, MileGPO achieves state-of-the-art performance. Ablations show that milestone discovery alone is insufficient, whereas reliability weighting and local progress and branch evidence provide complementary improvements. Credit-calibration diagnostics and replay profiling further show that these gains align with resolving local credit ambiguity while confining the added computation to lightweight post-rollout graph processing. These results demonstrate that existing rollout groups contain sufficient local evidence to provide useful process-level credit. References Ahmadian et al. (2024) A. Ahmadian, C. Cremer, M. Gallé, M. Fadaee, J. Kreutzer, O. Pietquin, A. Üstün, and S. Hooker Back to basics: revisiting reinforce-style optimization for learning from human feedback in llms. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 12248–12267. Cited by: §2.1. Bai et al. (2022) Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. External Links: 2204.05862, Link Cited by: §2.1. Chen et al. (2024) G. Chen, M. Liao, C. Li, and K. Fan AlphaMath almost zero: process supervision without process. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomczak, and C. Zhang (Eds.), External Links: Link Cited by: §2.2. Cheng et al. (2026) X. Cheng, S. He, L. Feng, H. Xu, M. Yan, L. Feng, and B. An Beyond trajectory-level attribution: graph-based credit assignment for agentic reinforcement learning. In Forty-third International Conference on Machine Learning, Cited by: §1, §3.1, Table 1. Cui et al. (2026) G. Cui, L. Yuan, Z. Wang, H. Wang, Y. Zhang, J. Chen, W. Li, B. He, Y. Fan, T. Yu, Q. Xu, W. Chen, J. Yuan, H. Chen, K. Zhang, X. Lv, S. Wang, Y. Yao, X. Han, H. Peng, Y. Cheng, Z. Liu, M. Sun, B. Zhou, and N. Ding Process reinforcement through implicit rewards. Trans. Mach. Learn. Res. 2026. External Links: Link Cited by: §2.2. Deng et al. (2023) X. Deng, Y. Gu, B. Zheng, S. Chen, S. Stevens, B. Wang, H. Sun, and Y. Su Mind2Web: towards a generalist agent for the web. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), External Links: Link Cited by: §1. Feng et al. (2025) L. Feng, Z. Xue, T. Liu, and B. An Group-in-group policy optimization for llm agent training. External Links: 2505.10978, Link Cited by: §1, §4.1.2. Guo et al. (2025) D. Guo, D. Yang, H. Zhang, J. Song, P. Wang, Q. Zhu, R. Xu, R. Zhang, S. Ma, X. Bi, et al. DeepSeek-r1 incentivizes reasoning in llms through reinforcement learning. Nature 645 (8081), p. 633–638. Cited by: §1, §2.1. He et al. (2026) S. He, L. Feng, Q. Wei, X. Cheng, L. Feng, and B. An Hierarchy-of-groups policy optimization for long-horizon agentic tasks. External Links: 2602.22817, Link Cited by: §2.1. Hou et al. (2025) Z. Hou, Z. Hu, Y. Li, R. Lu, J. Tang, and Y. Dong TreeRL: LLM reinforcement learning with on-policy tree search. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2025, Vienna, Austria, July 27 - August 1, 2025, W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar (Eds.), p. 12355–12369. External Links: Link, Document Cited by: §2.2. Kool et al. (2019) W. Kool, H. van Hoof, and M. Welling Buy 4 REINFORCE samples, get a baseline for free!. In Deep Reinforcement Learning Meets Structured Prediction, ICLR 2019 Workshop, New Orleans, Louisiana, United States, May 6, 2019, External Links: Link Cited by: §2.1. Lightman et al. (2024) H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe Let’s verify step by step. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, External Links: Link Cited by: §2.1, §2.2. Luo et al. (2025) X. Luo, Y. Zhang, Z. He, Z. Wang, S. Zhao, D. Li, L. K. Qiu, and Y. Yang Agent lightning: train any ai agents with reinforcement learning. External Links: 2508.03680, Link Cited by: §2.1. Oh et al. (2026) C. Oh, W. Li, S. Park, S. Yeh, T. Mallick, and S. Li Neglected free lunch from post-training: progress advantage for llm agents. External Links: 2606.26080, Link Cited by: §2.1. Ouyang et al. (2022) L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. Cited by: §1, §2.1. Putta et al. (2024) P. Putta, E. Mills, N. Garg, S. Motwani, C. Finn, D. Garg, and R. Rafailov Agent q: advanced reasoning and learning for autonomous ai agents. External Links: 2408.07199, Link Cited by: §2.1. Qwen et al. (2025) Qwen, :, A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu Qwen2.5 technical report. External Links: 2412.15115, Link Cited by: §4.1.2. Rafailov et al. (2024) R. Rafailov, A. Sharma, E. Mitchell, S. Ermon, C. D. Manning, and C. Finn Direct preference optimization: your language model is secretly a reward model. External Links: 2305.18290, Link Cited by: §2.1. Schick et al. (2023) T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, E. Hambro, L. Zettlemoyer, N. Cancedda, and T. Scialom Toolformer: language models can teach themselves to use tools. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), External Links: Link Cited by: §1. Schulman et al. (2018) J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel High-dimensional continuous control using generalized advantage estimation. External Links: 1506.02438, Link Cited by: §2.1. Schulman et al. (2017) J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov Proximal policy optimization algorithms. Cited by: §1, §2.1. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. K. Li, Y. Wu, and D. Guo DeepSeekMath: pushing the limits of mathematical reasoning in open language models. External Links: 2402.03300, Link Cited by: §2.1. Shinn et al. (2023) N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao Reflexion: language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), External Links: Link Cited by: §2.1. Shridhar et al. (2021) M. Shridhar, X. Yuan, M. Côté, Y. Bisk, A. Trischler, and M. J. Hausknecht ALFWorld: aligning text and embodied environments for interactive learning. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, External Links: Link Cited by: §1, §4.1.1. Stiennon et al. (2020) N. Stiennon, L. Ouyang, J. Wu, D. M. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano Learning to summarize with human feedback. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (Eds.), External Links: Link Cited by: §2.1. Wang et al. (2026a) D. Wang, Q. Li, M. Cheng, J. Ouyang, S. Yu, Q. Liu, and E. Chen StepPO: step-aligned policy optimization for agentic reinforcement learning. External Links: 2604.18401, Link Cited by: §2.1. Wang et al. (2023) G. Wang, Y. Xie, Y. Jiang, A. Mandlekar, C. Xiao, Y. Zhu, L. Fan, and A. Anandkumar Voyager: an open-ended embodied agent with large language models. External Links: 2305.16291, Link Cited by: §1. Wang et al. (2026b) H. Wang, W. Ren, Y. Zhang, D. Cao, Z. Zeng, K. Zeng, and T. Zhao BiPACE: bisimulation-guided policy optimization with action counterfactual estimation for llm agents. External Links: 2606.25556, Link Cited by: §2.1. Wang et al. (2024) P. Wang, L. Li, Z. Shao, R. Xu, D. Dai, Y. Li, D. Chen, Y. Wu, and Z. Sui Math-shepherd: verify and reinforce llms step-by-step without human annotations. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August 11-16, 2024, L. Ku, A. Martins, and V. Srikumar (Eds.), p. 9426–9439. External Links: Link, Document Cited by: §2.2. Wang et al. (2026c) Y. Wang, M. Song, Z. Zhang, S. Huang, H. Huang, F. Wei, W. Deng, F. Sun, and Q. Zhang Group-graph policy optimization for long-horizon agentic reinforcement learning. External Links: 2606.22995, Link Cited by: §2.1. Wang et al. (2025) Z. Wang, K. Wang, Q. Wang, P. Zhang, L. Li, Z. Yang, X. Jin, K. Yu, M. N. Nguyen, L. Liu, E. Gottlieb, Y. Lu, K. Cho, J. Wu, L. Fei-Fei, L. Wang, Y. Choi, and M. Li RAGEN: understanding self-evolution in llm agents via multi-turn reinforcement learning. External Links: 2504.20073, Link Cited by: §1. Williams (1992) R. J. Williams Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, p. 229–256. External Links: Link, Document Cited by: §1, §2.1. Yang et al. (2025) Z. Yang, Z. Guo, Y. Huang, X. Liang, Y. Wang, and J. Tang Treerpo: tree relative policy optimization. arXiv preprint arXiv:2506.05183. Cited by: §2.2. Yao et al. (2022) S. Yao, H. Chen, J. Yang, and K. Narasimhan WebShop: towards scalable real-world web interaction with grounded language agents. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), External Links: Link Cited by: §4.1.1. Yao et al. (2023) S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. R. Narasimhan, and Y. Cao ReAct: synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, External Links: Link Cited by: §1. Yu et al. (2025) Q. Yu, Z. Zhang, R. Zhu, Y. Yuan, X. Zuo, Y. Yue, W. Dai, T. Fan, G. Liu, J. Liu, L. Liu, X. Liu, H. Lin, Z. Lin, B. Ma, G. Sheng, Y. Tong, C. Zhang, M. Zhang, R. Zhang, W. Zhang, H. Zhu, J. Zhu, J. Chen, J. Chen, C. Wang, H. Yu, Y. Song, X. Wei, H. Zhou, J. Liu, W. Ma, Y. Zhang, L. Yan, Y. Wu, and M. Wang DAPO: an open-source LLM reinforcement learning system at scale. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2025, NeurIPS 2025, San Diego, CA, USA, December 2-7, 2025 / Mexico City, Mexico, November 30 - December 5, 2025, D. Belgrave, C. Zhang, L. N. Montoya, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, N. Chen, I. V. M. Ruíz, and A. Loaiza-Bonilla (Eds.), External Links: Link Cited by: §2.1. Zhan et al. (2026) Y. Zhan, X. Tang, J. Li, D. Zheng, W. Chai, J. Chen, J. Zhou, G. Wu, W. Tang, and H. Sun GraphPO: graph-based policy optimization for reasoning models. External Links: 2606.18954, Link Cited by: §2.2. Zhang et al. (2025) Z. Zhang, C. Zheng, Y. Wu, B. Zhang, R. Lin, B. Yu, D. Liu, J. Zhou, and J. Lin The lessons of developing process reward models in mathematical reasoning. In Findings of the Association for Computational Linguistics, ACL 2025, Vienna, Austria, July 27 - August 1, 2025, W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar (Eds.), Findings of ACL, Vol. ACL 2025, p. 10495–10516. External Links: Link, Document Cited by: §2.2. Zhou et al. (2024a) S. Zhou, F. F. Xu, H. Zhu, X. Zhou, R. Lo, A. Sridhar, X. Cheng, T. Ou, Y. Bisk, D. Fried, et al. Webarena: a realistic web environment for building autonomous agents. In International Conference on Learning Representations, Vol. 2024, p. 15585–15606. Cited by: §1. Zhou et al. (2025) Y. Zhou, S. Jiang, Y. Tian, J. Weston, S. Levine, S. Sukhbaatar, and X. Li SWEET-rl: training multi-turn llm agents on collaborative reasoning tasks. External Links: 2503.15478, Link Cited by: §2.1. Zhou et al. (2024b) Y. Zhou, A. Zanette, J. Pan, S. Levine, and A. Kumar ArCHer: training language model agents via hierarchical multi-turn rl. External Links: 2402.19446, Link Cited by: §2.1. Appendix A Implementation and Reproducibility Details A.1 Training Procedure Algorithm 1 summarizes how MileGPO is inserted into the grouped-rollout training pipeline. The rollout and graph-construction stages are shared with GraphGPO; MileGPO changes the computation between graph construction and the policy update. In particular, MD, RCS, and PCC are all computed from the current task-local rollout graph and its observed outcomes. They do not invoke the environment or an auxiliary model. The separate normalization in line 10 is important when several outgoing transitions are tied under final-goal distance: it prevents a numerically small potential correction from replacing the scale of the graph return. The policy update instead adds the normalized residual between the shaped and graph-only advantages, as defined in the main method section. A.2 Shared Training and Evaluation Configuration All locally evaluated methods use Qwen2.5-1.5B-Instruct as the policy. Each training iteration samples 16 task groups with eight rollouts per group. The agent retains the two most recent interaction steps and is limited to 50 environment steps on ALFWorld and 30 on WebShop. We train for 300 optimization steps with an actor learning rate of 10−610^-6, a KL coefficient of 0.010.01, and an invalid-action penalty of 0.10.1. Validation uses stochastic decoding at temperature 0.40.4. Shared model, rollout, optimizer, and environment settings are held fixed across the local comparisons. Method-specific return discounts follow the corresponding baseline and MileGPO recipes. Advantage normalization is a recipe-level setting: ALFWorld uses mean–standard-deviation normalization, whereas WebShop uses mean-only normalization. For each reported method, we run three test evaluations with seeds 123, 456, and 789, and report their mean and population standard deviation. WebShop evaluation uses 512 examples per seed from the official-small split; ALFWorld evaluation uses the full out-of-distribution split of 134 tasks. Table 4 lists settings shared by both environments. The environment-specific settings are 128/256 training-time validation examples, 50/30 maximum environment steps, mean–standard-deviation versus mean-only advantage normalization, 256/64 PPO mini-batch sizes, and 64/4 actor and rollout/reference micro-batch sizes per GPU for ALFWorld/WebShop, respectively. 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−61× 10^-6 1×10−61× 10^-6 KL loss coefficient / type 0.01 / low-variance KL 0.01 / low-variance KL Invalid-action penalty coefficient 0.1 0.1 Optimization steps / validation interval 300 / 5 300 / 5 Rollout and evaluation Tensor model parallel size 2 2 vLLM GPU memory utilization 0.40 0.40 Validation decoding temperature 0.4, sampling enabled temperature 0.4, sampling enabled Training seed 0 0 Test seeds 123, 456, 789 123, 456, 789 Checkpoint selection best validation success rate best validation success rate 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. A.3 Baseline Alignment and Checkpoint Selection Algorithm 1 MileGPO training procedure 0: Policy πθ _θ, task distribution p(q)p(q), group size K, maximum horizon T, graph discount γG _G, shaping coefficient λ, residual correction coefficient η 1: for each training iteration do 2: Set the rollout policy to the current policy 3: Sample task groups q∼p(q)q p(q) and collect K trajectories per task 4: Canonicalize observations and construct one directed rollout graph GqG_q per task 5: Compute final-goal distances and GraphGPO returns rGr^G 6: Mine candidate milestones and traps from visitation and outcome statistics (MD) 7: Weight positive and negative candidates and construct the two target potentials (RCS) 8: Compute local-progress and same-parent branch evidence; retain, amplify, or shrink milestone candidates (PCC) 9: Form the shaped step returns rMr^M from rGr^G and the potential increments 10: Normalize rGr^G and rMr^M within each task–source-state group 11: Combine the graph, residual milestone, and episode-level advantages 12: Update θ with the clipped policy objective and KL regularization 13: end for The locally reproduced GiGPO and GraphGPO baselines use the same policy model, task data, prompt construction, rollout group size, interaction horizon, optimizer settings, validation interval, and hardware allocation as MileGPO. The comparison therefore changes the credit estimator while preserving the agent–environment interface and model-level training workload. We retain method-specific return definitions and recipe-level normalization conventions rather than forcing them into a common estimator. Results marked as reproduced in the main table come from these aligned local runs; results explicitly marked as reported are transcribed from the corresponding source paper and are not treated as controlled local comparisons. All aligned local methods are trained for 300 optimization steps because their validation curves had not converged under the shorter reported schedule. We evaluate the checkpoint with the highest training-time validation success rate. ALFWorld ID and OOD use separate evaluation splits, while WebShop uses the official-small protocol. A.4 Agent Prompt Templates The prompts are shared by MileGPO and the locally reproduced baselines. At each interaction step, placeholders are filled with the task, the two most recent observation–action pairs, the current observation, and the admissible actions. The reasoning and executable action are enclosed by <think> and <action> tags, respectively. 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. A.5 MileGPO Hyperparameters For MileGPO, we use c=10c=10, ω=0.20ω=0.20, γΦ=1 _ =1, and λ=0.25λ=0.25, with γG=0.20 _G=0.20 in both environments. The milestone and trap weights are w+=1w_+=1 and w−=0.25w_-=0.25. Candidate mining uses ws=wm=wf=1w_s=w_m=w_f=1, wc=wl=0.25w_c=w_l=0.25, a minimum node support of one trajectory, and a trap threshold of 0.10.1 with at least two failed-trajectory visits unless a revisit is observed. The PCC stage sets αd=αs=αf=wbc=wpg=wpcc=1 _d= _s= _f=w_bc=w_pg=w_pcc=1 in both environments. The policy update uses wstep=wepisode=1w_step=w_episode=1. ALFWorld uses the selected strict configuration with θm=1.1 _m=1.1, ρ=0ρ=0, η=0.20η=0.20, and progress-only candidate eligibility (κbc=0 _bc=0). Because m(v)≤1m(v)≤ 1, this configuration requires positive progress evidence to retain a milestone; BCC calibrates its strength but cannot establish eligibility by itself. The WebShop run reported in the main table uses θm=0.5 _m=0.5, ρ=0.5ρ=0.5, and η=1η=1, together with the full progress-or-branch eligibility rule (κbc=1 _bc=1) for its more ambiguous shopping-state graph. These are environment-level recipe parameters; the MileGPO mechanism itself is unchanged. Table 5 gives the MileGPO configuration used in the local comparisons. Symbols follow the definitions in the method section. Stage Parameter Role ALFWorld WebShop Graph return c Return scale 10 10 γG _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−w_+,w_- Positive / negative potential weights 1.00 / 0.25 1.00 / 0.25 ws,wm,wfw_s,w_m,w_f Success, coverage, failure weights 1 / 1 / 1 1 / 1 / 1 wc,wlw_c,w_l Centrality and revisit weights 0.25 / 0.25 0.25 / 0.25 Minimum node support Distinct trajectory count 1 1 Minimum trap visits Failed-trajectory support 2 2 Minimum trap score Trap admission threshold 0.10 0.10 ω Milestone/trap propagation discount 0.20 0.20 return_mode Graph and potential composition graph_plus_potential PCC αd,αs,αf _d, _s, _f Distance, success, failure terms 1 / 1 / 1 1 / 1 / 1 wbc,wpgw_bc,w_pg BCC and progress evidence 1 / 1 1 / 1 wpccw_pcc PCC reweighting strength 1 1 θm _m Coverage retention threshold 1.1 0.5 κbc _bc Branch-only retention switch 0 1 ρ Shrink factor for weak candidates 0 0.5 Policy update wstep,wepisodew_step,w_episode Step / episode advantage weights 1 / 1 1 / 1 η Residual milestone correction weight 0.20 1.00 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. Appendix B Theoretical Properties of MileGPO This section establishes three properties of the MileGPO credit estimator on a fixed on-policy rollout graph. The results concern the credit transformation computed from one sampled batch; they do not require assumptions about future rollouts or the environment dynamics. Let the step-level component of the token advantage in Equation 22 be Bt B_t =At−wepisodeNormq(Zi) =A_t-w_episode\,Norm_q(Z_i) (23) =wstep[A^tG+ηA^tres]. =w_step [ A_t^G+η A_t^res ]. We assume wstep≥0w_step≥ 0 and η∈[0,1]η∈[0,1], as in the reported configuration. All normalized advantages below are computed within the same task–source-state group. Proposition 1 (Controlled residual interpolation). Define the GraphGPO and fully shaped step components as BtG=wstepA^tGB_t^G=w_step A_t^G and BtM=wstepA^tmixB_t^M=w_step A_t^mix, respectively. Then MileGPO satisfies Bt=(1−η)BtG+ηBtM,B_t=(1-η)B_t^G+η B_t^M, (24) and its deviation from the GraphGPO step component is |Bt−BtG|=wstepη|A^tmix−A^tG|.|B_t-B_t^G|=w_stepη| A_t^mix- A_t^G|. (25) Consequently, η=0η=0 recovers the GraphGPO step component, η=1η=1 recovers the normalized shaped step component, and intermediate values provide a convex interpolation between them. Proof. By definition, A^tres=A^tmix−A^tG A_t^res= A_t^mix- A_t^G. Substituting this identity into Equation 23 gives Bt=wstep[A^tG+η(A^tmix−A^tG)]=(1−η)BtG+ηBtM. array[]rclB_t&=&w_step [ A_t^G+η( A_t^mix- A_t^G) ]\\ &=&(1-η)B_t^G+η B_t^M. array (26) Subtracting BtGB_t^G and taking absolute values yields Equation 25. Since η∈[0,1]η∈[0,1], the two coefficients in Equation 24 are nonnegative and sum to one. ∎ Proposition 2 (Resolution of graph-distance ties). Consider two observed transitions e1=(s,a1,s1′)e_1=(s,a_1,s _1) and e2=(s,a2,s2′)e_2=(s,a_2,s _2) in the same task–source-state normalization group. If GraphGPO assigns them equal step advantages, then B(e1)−B(e2)=wstepη[A^mix(e1)−A^mix(e2)].B(e_1)-B(e_2)=w_stepη [ A^mix(e_1)- A^mix(e_2) ]. (27) Thus, for wstepη>0w_stepη>0, any strict ordering produced by the normalized shaped advantage becomes the strict ordering of the MileGPO step-level credit. In particular, equal destination-to-goal distances imply equal GraphGPO returns and hence satisfy the premise. Proof. Applying Equation 24 to the two transitions and taking their difference gives the expression below, where ΔG=A^G(e1)−A^G(e2) _G= A^G(e_1)- A^G(e_2) and Δmix=A^mix(e1)−A^mix(e2) _mix= A^mix(e_1)- A^mix(e_2): B(e1)−B(e2)=(1−η)wstepΔG+ηwstepΔmix.B(e_1)-B(e_2)=(1-η)w_step _G+η w_step _mix. (28) The first difference is zero by the premise, which proves Equation 27. Moreover, the GraphGPO return is cγGd(s′,g)c _G^d(s ,g); therefore d(s1′,g)=d(s2′,g)d(s _1,g)=d(s _2,g) gives equal raw graph returns. Applying the same normalization to equal values in the same group preserves equality. ∎ Proposition 3 (Bounded raw shaping correction). Assume the task-wise normalized candidate scores lie in [0,1][0,1], ω,γΦ∈(0,1]ω, _ ∈(0,1], and c,λ,w+,w−≥0c,λ,w_+,w_-≥ 0. Then the one-sided potential increments obey 0≤δt+≤w+,0≤δt−≤w−,0≤ _t^+≤ w_+, 0≤ _t^-≤ w_-, (29) and the raw MileGPO return differs from the GraphGPO return by at most −cλw−≤rtM−rtG≤cλw+.-cλ w_-≤ r_t^M-r_t^G≤ cλ w_+. (30) For the reported values c=10c=10, λ=0.25λ=0.25, w+=1w_+=1, and w−=0.25w_-=0.25, the correction lies in [−0.625,2.5][-0.625,2.5]. Proof. Each positive or negative potential is the maximum of terms of the form S¯(v)ωd(s,v) S(v)ω^d(s,v). The normalized score, distance decay, and their product all lie in [0,1][0,1], so 0≤Φ+(s),Φ−(s)≤10≤ ^+(s), ^-(s)≤ 1. From Equations 9 and 10, 0≤δt+≤γΦw+Φ+(st+1)≤w+,0≤δt−≤γΦw−Φ−(st+1)≤w−. array[]rcl0≤ _t^+&≤& _ w_+ ^+(s_t+1)≤ w_+,\\ 0≤ _t^-&≤& _ w_- ^-(s_t+1)≤ w_-. array (31) Finally, Equation 20 gives rtM−rtG=cλ(δt+−δt−)r_t^M-r_t^G=cλ( _t^+- _t^-). Substituting the increment bounds proves Equation 30; substituting the reported hyperparameters gives the stated numerical interval. ∎ 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. B.1 Full WebShop Training Dynamics Together, these propositions show that MileGPO adds a tunable, tie-resolving, and bounded correction to graph-distance credit on each sampled rollout graph. Figure 8 reports the complete optimization trajectories of the aligned GiGPO, GraphGPO, and MileGPO WebShop runs. MileGPO improves more rapidly during the early and middle stages in both the training and validation views, while the curves become closer near the end of training. These trajectories characterize optimization dynamics rather than final performance; the endpoint comparisons in the main paper follow the independent evaluation protocol described in Section 4. Appendix C Additional Experimental Analyses C.1 Checkpoint-Wise Replay of Distance Ties Figure 9 expands the pooled replay result in Figure 4 by resolving it across checkpoints. We identify sibling transitions that share a parent state, have opposite episode outcomes, and are tied under GraphGPO’s final-state-distance advantage. On the same GraphGPO trajectories, RCS ranks the successful transition above the failed one for 26.5% of the 569 eligible pairs, compared with 17.0% for uniform MD. Figure 9 shows where these corrections occur across checkpoints and also reveals that the number of eligible ties decreases later in training. Because the comparison replays alternative shaping on fixed trajectories, it should be interpreted as descriptive mechanism evidence rather than a causal training ablation. We group transitions by task and canonicalized parent state, label a transition as successful when its trajectory-level episode return is positive, and declare a GraphGPO advantage tie at an absolute difference of at most 10−610^-6. Both replay variants use the same RCS-mined candidate set. Uniform MD assigns unit weight to every mined milestone and trap, whereas RCS retains the mined reliability weights; PCC is disabled in both variants. The replay uses γG=0.20 _G=0.20, ω=0.20ω=0.20, and λ=0.25λ=0.25, matching the reported WebShop recipe. 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/NtieN_ corrected/N_ tie, 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 rtr_t 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\$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 6 click[classic fit] Product page unchanged. 0 7 click[youth] Confirms youth; selected options are youth, kelly green, and x-small. 0 8 click[x-small] Product page unchanged; x-small remains selected. 0 9 click[polyester]; click[heathers]; click[cotton]; click[needle sleeve]; click[classic fit]; click[men]; click[price lower than 40.00 dollars] Product page unchanged; the three valid selections remain active. 0 10 click[x-small] Product page unchanged. 0 11 click[needle sleeve] Product page unchanged. 0 12 click[needle sleeve] Product page unchanged. 0 13 click[classic fit]; click[needle sleeve] Product page unchanged. 0 14 click[kelly green]; click[40.00] Product page unchanged. 0 15 click[polyester heathers]; click[heathers cotton]; click[cotton heathers]; click[lower than 40.00] Product page unchanged. 0 16 click[polyester heathers] Product page unchanged. 0 17 click[x-small] Product page unchanged. 0 18 click[classic fit]; click[price lower than 40.00] Product page unchanged. 0 19 click[x-small] Product page unchanged. 0 20 click[classic fit] Product page unchanged. 0 21 click[x-small] Product page unchanged. 0 22 click[kelly green] Product page unchanged. 0 23 click[x-small] Product page unchanged. 0 24 click[classic fit] Product page unchanged. 0 25 click[kelly green] Product page unchanged. 0 26 click[youth] Product page unchanged. 0 27 click[buy now] success; purchase accepted. 10 Failed 0 search[kelly green, machine wash, polyester heathers, heathers cotton, cotton heathers, needle sleeve, classic fit, youth, x-small, price: $40.00--$50.00] Results page 1 (50 products); B09P39QN2W, priced at $16.99\$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[buy now] Purchase response reports task score 0.90.9 but no binary success; episode terminates as failure. 0 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. C.2 Representative Credit-Assignment Corrections Table 6 makes the aggregate tie correction in Figure 9 concrete through a complete paired trace. The two rollouts start from the same task and exactly the same initial observation, but issue different search actions. The successful branch preserves the requested price ceiling, whereas the failed branch searches in an incompatible price interval. GraphGPO assigns the two first transitions the same advantage (ΔG=0.000 _G=0.000), while RCS favors the successful branch by ΔRCS=+1.533 _RCS=+1.533. Every environment transition in both rollouts is shown. The feedback column reports state changes and denotes repeated product-page observations as “product page unchanged.” This case illustrates the complementary roles of MD and RCS. MD exposes intermediate states as candidate credit anchors, allowing the successful and failed branches to receive distinct intermediate shaping before terminal success is observed. RCS then calibrates these anchors by their outcome support, assigning higher credit to the action that preserves the task constraint. Across all eligible ties, this calibration raises the correction rate from 17.0% with uniform MD to 26.5%. Two additional same-state corrections exhibit the same pattern. On a product page, choosing the listed option click[xnj-tshirt342-black] instead of emitting text outside the action grammar changes the RCS margin by +0.803+0.803. On a compatible loafer page, selecting the requested size with click[12] instead of retreating with click[< prev] changes it by +0.562+0.562. PCC is disabled in this replay and is therefore not illustrated by these paired traces. Its contribution is evaluated separately by the cumulative ablation in Table 3 and the candidate-evidence diagnostics in Figure 4. Adding PCC to RCS increases WebShop success from 77.2% to 78.6% and task score from 87.9% to 90.3%, while the diagnostics show how local progress and same-parent branch evidence are used to retain, strengthen, or suppress candidate milestones.