GRAFT Estimates Step-Level Advantages for Agentic Reinforcement Learning

Summary

Group-based reinforcement learning methods such as GRPO estimate advantages reliably at the response level, but their coarse trajectory-level rewards can misrepresent the value of individual steps. A failed trajectory may still contain useful actions, creating biased step-level credit assignment. The paper introduces GRAFT, which merges rollout trajectories into a graph, estimates node state values through Bellman iteration, and assigns each edge a credit based on the value difference between its nodes. This extends the basic reinforcement-learning definition of advantage without requiring multiple action samples from every intermediate state, which would be expensive. The authors also propose Graph GAE, an adaptation of generalized advantage estimation for trajectory graphs that reduces the effect of state-value estimation bias. Experiments across multiple multi-turn agentic benchmarks report consistent gains over GRPO and better performance than recent agentic reinforcement-learning methods. Code is planned for release on GitHub.