Targeting Pivotal Decisions for Credit Assignment in Agentic Reinforcement Learning
Dongwon Jung, Hemanth Neelgund Ramesh, Yifan Wang, Xiaomin Li, Yuexing Hao, Yu Hu, Muhao Chen, Varun Chandrasekaran, Andrzej Banburski-Fahey, Jaron Lanier
cs.CL, cs.AI
2026-09-29
An LLM judge nominates the segment where successful and failed trajectories diverge; measured success-rate differences set the bonus, beating GRPO by 9.9% (2B) and 7.1% (4B).
GRPO is now the default foundation for RL-trained LLM agents: sample a group of trajectories per task, use the group-mean-centered outcome as the advantage, skip the value model entirely. The cost is that this trajectory-level advantage gets copied onto every policy token, and credit assignment breaks down. An agent episode runs for dozens of turns and one or two decisions may determine the outcome; with uniform credit, mistakes inside successful trajectories get reinforced and useful progress inside failed ones gets punished. Existing fixes each carry a problem. Critics and process reward models score intermediate steps directly, but those scores can be wrong, drift out of date as the policy shifts, and get gamed during optimization. Monte Carlo estimation branches from intermediate states and averages real downstream outcomes, which is trustworthy, but evaluating every candidate state means repeatedly restoring environments and running full continuations, a cost that explodes on long-horizon tasks.
ProVer (Propose, Verify, Credit) separates where to look from how much the credit is worth:
The design point: model judgment only decides where to spend the verification budget, while the numerical credit comes entirely from observed outcomes. A wrong proposal costs a few wasted continuations, not a corrupted reward. The trigger is tight too: only mixed-outcome groups with success rates strictly between 0 and 0.5 enter the pipeline, one successful trajectory per group (the shortest one), and verification happens only at the two boundaries.
With Qwen3.5-2B and 4B across ALFWorld, WebShop, and SearchQA, ProVer takes the best score in four of six settings and the highest average at both scales:
| Method | 2B avg | 4B avg |
| GRPO | 54.07 | 60.12 |
| GiGPO | 55.53 | 59.90 |
| SPO-chain | 50.45 | 60.55 |
| CriticSearch | 54.26 | 62.28 |
| ProVer | 59.43 | 64.40 |
That is a 9.91% relative gain over GRPO at 2B and 7.12% at 4B, positive in all six settings. Two controls carry the argument. Budget-Matched GRPO gets the same extra rollouts but keeps trajectory-level credit, and ProVer beats it everywhere by 5.34% to 22.23%, so the gain comes from targeted verification rather than more sampling. SPO-chain, which evaluates fixed segment boundaries, loses by 43.95% on SearchQA at 2B. On cost, ProVer generates 2.4% (ALFWorld) to 16.8% (SearchQA) more policy tokens per step than GRPO, posts the lowest per-step wall time among the fine-grained methods, and spends 38.4% less on judge API calls than CriticSearch on average.
The judge ablation answers two obvious questions. Replacing the judge with random segment selection but keeping the same verification and credit rules drops the SearchQA acceptance rate to 19.5% versus 58.5% to 72.4% for the four agentic judges, and random segments are longer on average (2.38 vs. 1.03-1.45 turns), so the high acceptance comes from precise localization. A locally served Qwen3.5-9B judge posts the best ALFWorld score, and frontier-scale gpt-5.4 is not the best on any environment. Nomination does not need a frontier model.
For teams already training agents with GRPO, this is a directly portable structure: LLM judgment handles localization, and expensive Monte Carlo verification is spent only at two boundaries. It also offers a pragmatic answer to the debate over whether LLM evaluations can serve as rewards. The evaluation is allowed to be wrong, because it only chooses where to verify; the cost of an error is a few wasted continuations, not a polluted credit signal. Not depending on a frontier judge, with a 9B local model sufficient, matters for budget-constrained teams building their own training pipelines.
Appendix B is candid. Unbiasedness holds only for the raw difference estimate; taking the positive part introduces bias, so even a segment with zero true advantage can earn positive expected credit from finite-sample noise. The full update is not an unbiased estimator of the standard policy gradient, and the boundary comparison yields one number for the whole segment, with no causal separation among the actions inside it. The engineering prerequisites are selective: it needs exact restoration of intermediate states (fine in simulators like ALFWorld and WebShop, unclear for live websites or third-party APIs) and binary terminal rewards. The method only adds positive credit to successful trajectories; mistaken penalties inside failed trajectories go uncorrected. SearchQA evaluation uses gpt-5.4-mini as the semantic judge, the same model as the default proposing judge. Training runs for 100 optimizer steps, so stability over longer horizons is untested.