Reinforcement learning for long-horizon agents relies on feedback from sequences of interactions, making credit assignment to individual actions difficult. Existing methods such as GiGPO compare actions at shared states to compute relative advantages, but estimate each action's value from a single sampled continuation. The resulting local credit remains sensitive to decisions made later in the trajectory. To address this problem, we propose ConCal (Continuation Calibration), a recursive continuation-value estimator that incorporates continuation evidence already present in a rollout batch. ConCal matches visits from the same task by their incoming state-action-state transitions, combines shared continuation evidence with each visit's own transition estimate, and propagates calibrated values backward to refine earlier action-value estimates. This reduces dependence on individual sampled continuations and mitigates local credit distortions without additional rollouts. Held-out return diagnostics show lower error in within-group value differences and higher agreement with reference action orderings than estimates based on individual continuations. With Qwen2.5-1.5B-Instruct, ConCal improves success rates over GiGPO by 3.39 and 5.86 percentage points on ALFWorld and WebShop, respectively. Our code is available at https://github.com/Yingjian-Chen/ConCal.
Figures & tables
Figure 1: Comparison of credit assignment strategies. (a) GRPO assigns the same trajectory-level credit to all actions. (b) GiGPO compares actions at shared state anchors based on their own sampled returns. (c) Our proposed ConCal estimates local action values from continuation evidence shared among matched visits across rollouts. Visits from the same task are matched by their preceding state, executed action, and current state.
Figure 2: Credit-conflict rates and centered-value MSE on WebShop and ALFWorld. Credit conflict (%) measures the proportion of repeated-decision groups in which the same recorded decision receives both positive and negative local credit. Centered-value MSE measures group-centered estimation error against held-out returns. For illustration, both estimators are evaluated on the same subset of 1,000 existing rollout trajectories from each benchmark.
Figure 3: Overview of ConCal. (1) ConCal matches visits across same-task rollouts by their preceding state, executed action, and current state to identify shared continuation evidence ( Left ). (2) It recursively combines continuation evidence from matched visits while retaining each visit’s own transition contribution, producing calibrated continuation values for action evaluation. At each recursion depth, all visits are updated using successor estimates from the previous depth ( Right ). (3) Each action is evaluated using its immediate reward and its actual successor’s calibrated continuation value. The resulting action values are compared within state groups to obtain local advantages, which are combined with episode-level advantages for PPO updates ( Bottom ).
Type
Method
ALFWorld
WebShop
Pick
Clean
Cool
Look
Heat
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
Qwen2.5-1.5B-Instruct
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. For ALFWorld, we report per-category and overall success rates (%). For WebShop, we report average task scores and success rates (%). ConCal results report validation means ± sample standard deviations across three runs. ∗ marks the base method on which ConCal builds. Baseline results are taken from prior publications ( Feng et al., 2025 ; Cheng et al., 2026 ) . The best and second-best means are shown in bold and underlined, respectively.
Figure 4: Learning curves of ConCal in green and GiGPO in blue on ALFWorld and WebShop with Qwen2.5-1.5B-Instruct. Training episode success rates are plotted against policy updates, with faint lines showing unsmoothed curves and bold lines showing EMA-smoothed curves with decay 0.95 .
Figure 5: Calibration of relative action values. Agreement and Disagreement indicate whether the estimated action ordering matches or reverses the ordering given by held-out returns. Tie denotes near-equal estimated values. Ordering comparisons exclude action pairs with tied held-out returns. Gap-matched rescales the centered Own-MC values within each group to match the norm of the ConCal estimates while preserving their ordering. MSE measures group-centered value error against held-out returns.
Estimator
ALFWorld
WebShop
All (%)
Score
Succ. (%)
Own-MC
90.89±1.63
88.25±0.80
73.44±2.07
Fully pooled
91.93±2.39
89.79±1.54
78.65±4.51
Single-pass
93.49±1.97
90.25±2.28
78.65±3.16
ConCal
94.27±1.97
90.18±1.27
79.69±3.41
Table 2: Continuation-estimator ablations on ALFWorld and WebShop. We report overall success rate on ALFWorld and task score and success rate on WebShop, as means ± sample standard deviations across three runs. The best and second-best means are shown in bold and underlined, respectively.
Figure 6: Relationship between calibrated value spread and step-advantage magnitude under group-wise and batch-wise normalization on ALFWorld and WebShop. Within each batch, state groups with nonzero value spread are divided into five approximately equal-sized bins by the root mean square (RMS) of their centered action values, from bin 1 with the smallest spread to bin 5 with the largest. The vertical axis shows the step-advantage RMS of each group divided by the corresponding batch-level step-advantage RMS. Boxes show the middle 50% of values, whiskers the 5th–95th percentiles, and lines connect medians.
Figure 7: Computational cost and coverage of ConCal. (a) Runtime averaged equally over ALFWorld and WebShop. Blue bars denote common training stages, and green bars denote our visit matching and recursive calibration. The x-axis is broken. (b) Direct coverage denotes actions whose next visits have matches in other trajectories. Indirect coverage denotes additional actions reached through recursive propagation of calibrated continuation values. Gray segments indicate uncovered actions, and brackets show total coverage.
Figure 8: Case study in WebShop. Both panels evaluate the same two trajectories. Both gaps subtract the estimate for repeating Zest from that for selecting 5X. Green dashed links indicate shared continuation evidence; two of the three matched visits are shown. Webpages are reconstructed from recorded states using the official interface.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
ALFWorld
WebShop
Training updates
150
150
Tasks per update
16
16
Trajectories per task
8
8
Retained interaction steps
2
2
Maximum environment steps
50
15
Maximum input tokens
2,048
5,120
Appendix
Table 3: Training and evaluation hyperparameters for ConCal.
Figure 9: Training dynamics of ConCal and GiGPO with Qwen2.5-1.5B-Instruct. The top two rows show ALFWorld, and the bottom two rows show WebShop. Faint lines show raw training metrics, and bold lines show exponential moving averages with decay 0.95 . Validation success is shown at the recorded evaluation updates without smoothing.
Group-based reinforcement learning such as GRPO trains LLM agents by comparing rollouts sampled for each task, without a learned critic. In long-horizon settings, these rollouts revisit shared anchor states, offering cross-rollout evidence for step-level credit. Ideally, step-level credit should incorporate evidence beyond the realized suffixes observed at an anchor while aggregating alternative continuations according to their empirical frequencies. Visit-local averaging pools realized suffix returns at shared anchors and respects observed frequencies, but does not recursively propagate evidence across rollouts, whereas shortest-path estimators have global reach but allow a rarely observed route to dominate an anchor's value. We introduce Cross-Rollout Bellman Closure (CRBC), which merges each rollout group into a finite empirical process with absorbing success and failure boundaries and evaluates its behavior-policy Bellman fixed point with one linear solve. This fixed point uses the same empirical action and transition frequencies to propagate evidence through shared anchors and aggregate alternative continuations. Backing up the resulting state values through observed transitions yields action values, whose gain over the corresponding state value provides step-level credit. A corresponding finite-depth family recovers visit-local return averaging at zero depth and converges to the exact closure as depth increases. The normalized closure credit is combined with the trajectory-level group advantage for policy optimization, without additional environment rollouts. Across ALFWorld, WebShop, and Sokoban benchmarks with multiple model scales, CRBC consistently improves final performance and learning efficiency. For example, CRBC outperforms the strongest evaluated baseline by 5.59 percentage points on ALFWorld with Qwen2.5-1.5B-Instruct.
Yangyang Ren, Haodong Zhu, Linlin Yang +3
Beihang University · Zhongguancun Academy · Communication University of China +2
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
Long-horizon language-model agents trained with reinforcement learning oftenreceive sparse outcome rewards that do not reveal which decisions along a tra-jectory deserve credit. Episode-level advantages provide coarse trajectory-widecredit, while step-level comparisons offer finer resolution with context-dependentestimation noise. We propose Granularity-Adaptive Credit Assignment (GACA),a critic-free method that adaptively mixes episode- and step-level credit for eachdecision during policy optimization. GACA normalizes the sampled response'smean per-token negative log-likelihood (NLL) within each trajectory and uses theresulting criticality score to determine the step-specific mixture. The computationreuses rollout log-probabilities without additional training rollouts or model eval-uations. Our analysis characterizes optimal score-dependent mixing and derivesconditions linking expected NLL to a lower bound on the preferred step-levelweight. Across ALFWorld and WebShop with 1.5B and 7B backbones, GACAachieves the highest reported mean success rates among the compared methods,while introducing negligible additional computation.
Taoran Liang, Yang Liu, Shang Luo +10
Nankai University · Peking University · Supply Chain Tech Team Y, JD.com +2