Recent advances in multi-turn reinforcement learning (RL) have substantially improved the performance of LLM agents on complex, long-horizon interactive tasks. However, despite progress in fine-grained credit assignment, policy optimization still applies these learning signals through response-specific probability ratios. Different textual responses can induce the same executable effect, yet credit differences arising from subsequent outcomes remain tied to their individual textual realizations. We identify this mismatch as credit-update misalignment. Our analysis reveals that credit-text pairing directly shapes policy-update directions, even when the policy context and executable effect are held fixed. Motivated by this finding, we propose Effect-Marginal Policy Optimization (EMPO), which aligns policy optimization with execution-level equivalence through an effect-level surrogate that couples updates across alternative textual realizations. EMPO preserves the original credit signals, integrates with both trajectory-level and step-level credit estimators, and requires no additional critics or rollouts. Experiments on ALFWorld, WebShop, and Sokoban show that EMPO outperforms strong baselines in both task performance and learning efficiency.
Figures & tables
Figure 1: Execution-equivalent responses may receive different credit and undergo divergent response-wise policy updates despite inducing the same immediate effect. Such within-effect variation can propagate into inconsistent ratio changes and unstable policy updates over training.
Figure 2: Overview of Effect-Marginal Policy Optimization (EMPO). EMPO groups locally comparable responses with the same canonical execution effect and aggregates their response-level policy ratios into a shared effect ratio. The shared ratio is combined with the original advantages to coordinate policy updates across execution-equivalent responses.
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Success
Closed-source models
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
Qwen2.5-1.5B-Instruct
Table 1: Performance comparison on ALFWorld and WebShop benchmarks. Results are reported as mean ± std over 3 random seeds. Δ denotes the change from the corresponding baseline.
Method
ALFWorld SR
WebShop Score
WebShop SR
EMPO-G
83.3
83.1
70.3
w/o Length Normalization
61.7
43.3
27.3
w/o Ratio Sharing
79.7
65.3
55.5
w/o Effect-Based Grouping
78.9
77.5
64.1
EMPO-GiG
94.0
87.9
77.3
w/o Length Normalization
60.2
75.2
43.8
Table 4: Ablation results using Qwen2.5-1.5B-Instruct.
Figure 3: Policy-update analysis on ALFWorld with Qwen2.5-1.5B-Instruct. Panels (a) and (b) show pairwise cosine similarities of response-level objective gradients under GiGPO and EMPO-GiG. Black lines mark effect-cell boundaries and the top strips indicate advantage signs. Panel (c) reports the within-cell dispersion DK of log-probability changes after controlled one-step updates.
Figure 4: Effect-cell size distributions of EMPO-GiG at different training stages. Bars show the proportion of eligible cells in each size range, while response coverage measures the fraction of sampled responses assigned to eligible cells with ∣K∣≥2 .
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
ALFWorld
WebShop
Sokoban
Max. prompt length
2,048
4,096
1,024
Max. environment steps
50
15
15
Groups × trajectories
16×8
16×8
32×8
Actor mini-batch size
256
64
64
Appendix
Table 5: Environment-specific training configurations.
Figure 5: Training curves on ALFWorld, WebShop, and Sokoban.
Figure 6: Training dynamics on ALFWorld with Qwen2.5-1.5B-Instruct. We report token entropy, KL divergence to the reference policy, and gradient norm.
Figure 7: Training dynamics on WebShop with Qwen2.5-1.5B-Instruct. We report token entropy, KL divergence to the reference policy, and gradient norm.
Figure 8: Relative magnitude of the within-effect covariance term on six effect cells from ALFWorld. For each cell K , we report ∥CovK(A^,s)∥/∥GKind∥ under GRPO and GiGPO.
Base
Method
ALFWorld SR
WebShop Score
WebShop SR
GRPO
Advantage Aggregation
80.47
82.1
70.2
EMPO-G
83.3
83.1
70.3
GiGPO
Advantage Aggregation
92.97
83.6
71.1
EMPO-GiG
94.0
87.9
77.3
Appendix
Table 6: Comparison between EMPO and advantage-side aggregation.
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
Group-based reinforcement learning enables large language model agents to learn from sparse outcome rewards in long-horizon tasks. Recent methods derive step-level credit by comparing observation-matched experiences across trajectories. However, identical observations can occur in different contexts, and matched peers are not equally informative for a given decision. Moreover, favorable terminal outcomes can obscure redundant actions or detours within successful trajectories. To address these two challenges, we propose Contextual Credit Policy Optimization (CCPO). For the first, CCPO weights observation-matched peers from other trajectories by contextual similarity, computed from frozen LLM representations and accumulated trajectory statistics, allowing peers from similar contexts to contribute more to a step's baseline. For the second, CCPO pairs historical credit, which compares the realized return against the weighted peer baseline, with future credit, which measures the change in contextual outcome value over a short realized continuation. A step is thus credited for the progress it makes, not only for its trajectory's eventual outcome. Both credits are computed in hindsight from rollouts already collected for training, enabling CCPO to address these challenges without an auxiliary value critic. Across two Qwen2.5-Instruct backbones (1.5B and 7B), CCPO achieves up to 97.4% success on ALFWorld and 79.4% on WebShop and outperforms GRPO by up to 21.6 and 18.5 points. Ablations show that contextual weighting outperforms uniform weighting, and that historical and future credit serve as complementary learning signals.
Huiwen Han, Ziyao Zeng, Zihao Zhu +6
Stanford University · Texas A&M University · Yale University +3
Large Language Model (LLM) agents increasingly solve long-horizon tasks through multi-turn interactions with users and external tools. In these settings, relevant task information often unfolds over time rather than being fully specified at the initial prompt. Service agents make this challenge especially concrete: users may clarify or revise their goals, while tool responses provide information needed for subsequent decisions. Thus, a final reward alone cannot indicate which actions contributed to resolving the task. Recent methods rely on comparative evidence from other trajectories or resampled continuations, or on separately constructed step-level learning signals, to refine credit. However, a completed rollout already records how information and errors flow between agent actions. We introduce Influence-Aware Policy Optimization (IAPO), which represents each rollout as a typed influence-dependency graph over trainable agent actions, with user and tool observations serving as evidence. IAPO converts support-use and failed-use structure into routing weights that redistribute the same trajectory-level advantage. Experiments with Qwen3-4B and Qwen3-8B demonstrate superior performance over multi-turn reinforcement learning (RL) baselines across three service-agent benchmarks: τ2-Bench, UserBench, and AgentChangeBench. BFCL-v4 Multi-Turn further shows that these gains do not compromise multi-turn function-calling performance. This work advances the understanding of credit assignment in multi-turn user interactions and provides a principled approach to training service agents from sparse outcome feedback.