acceptodds
Withdrawn from ICLR 2027

Back to the Definition: Estimating Step-Level Advantages via Trajectory Graphs for Agentic Reinforcement Learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Group-based reinforcement learning (RL) methods, such as GRPO and its variants, have become a leading paradigm for training reasoning and agentic large language models (LLMs). While their group-normalized advantage estimation is reliable at the response level, it becomes systematically biased at the step level, since coarse-grained trajectory-level advantages are hard to accurately reflect the contribution of individual steps (*i.e*, failed trajectories may contain valuable steps). Revisiting the foundational RL definition, we notice that GRPO's success on single-turn tasks stems from its advantage estimation strategy, which adheres to the basic definition: the mean reward of multiple actions sampled from the same state constitutes a credible state-value estimate. Extending the faithful estimation to step-level would in principle demand sampling multiple actions from each intermediate state, which is too costly on a per-state basis. To mitigate this issue, we can aggregate similar states across trajectories to better leverage global information. Since each trajectory is a chain of state-action transitions, cross-trajectory information flow requires modeling state-action transitions across trajectories, which naturally forms a directed graph. Building on this insight, we propose a **Gra**ph-based **F**aithful s**T**ep-level credit-assignment framework (**GRAFT**) that grafts all rollout trajectories into a trajectory graph, recovering node state-values via Bellman iteration on the graph, and assigning credit to each edge by the node value difference. Theoretically, the estimated step-level advantage faithfully adheres to the basic advantage definition in RL. To further ensure the reliability of step-level advantage estimation, we further propose Graph GAE, which extends GAE to the trajectory graph for reducing the impact of state-value estimation bias. Experiments across a range of multi-turn agentic benchmarks show consistent gains over GRPO and superior performance compared to recent agentic RL algorithms. Code will be available online.

Primary area:
reinforcement learning
Keywords:
Agentic Reinforcement Learning, Step-level Credit Assignment

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_P5qbOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces GRAFT, which builds a trajectory graph from rollouts, estimates node values via Bellman iteration, and derives step-level advantages from value differences plus a Graph GAE variant, evaluated on ALFWorld, WebShop, and SearchQA against GRPO, GiGPO, and GraphGPO. However, due to various shortcomings of this article, my suggestion is a weak rejection. Below are my thoughts on the strength, weakness, and my question of the paper.

Critical strengths
  1. The proposed approach constructs trajectory graphs from sampled rollouts and estimates step-level advantages. These are achieved through Bellman value iteration and Graph GAE. The algorithmic contribution is demonstrated through many experiments, where GRAFT achieves improvements over existing baselines.
  2. The experiment is quite comprehensive. The article is relatively complete.
  3. The paper is well-written with clear exposition and reasonable experiments.
Critical weaknesses
  1. The core issue has been resolved by GraphGPO, and this article only criticizes its mechanism without proving the existence of residual unresolved problems. GraphGPO has already done "cross trajectory aggregation of states and step level credit allocation using graphs". The difference between the two articles is that GraphGPO uses the shortest path heuristic reward, while this article replaces it with Bellman value iteration+Graph GAE. But the authors have never proven that there is a residual problem after GraphGPO that cannot be solved by GraphGPO and must be solved by Bellman. The author only said that the reward of GraphGPO is heuristic, which is a criticism of the baseline mechanism, not a proof that the problem has not been solved.
  2. Weak theoretical justification. Proposition 1 assumes access to the true value function V^π in a deterministic environment, making the TD residual equal to the true advantage. This oracle result does not establish the accuracy of GRAFT's practical graph-based estimator.
  3. Insufficiently justified Graph GAE. The proposed estimator uniformly averages reachable TD residuals without accounting for policy probabilities. Its claimed bias reduction and interpolation toward Monte Carlo advantages are not rigorously established.
  4. The actual advantage estimator combines Graph GAE with normalization, yet the authors first present the one-step TD estimate as theoretically aligned with the standard advantage definition, before introducing Graph GAE to address its limitations.
  5. In Sec 3.3, there might be some imprecise parts: a) The proposed Graph GAE averages reachable edges without policy-probability weighting, potentially introducing systematic bias; b) Setting μ=0 and σ=|A_t^GAE | effectively yields A≈sign(A_t^GAE), discarding magnitude information without justification; c) Eq. (11) does not clarify whether normalization uses s_t or ϕ(s_t).
Questions for authors

See above.

Reviewer_fxVZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

It is a graph-based approach to work reinforcement learning under agentic environment. The proposed approach is reasonable.

The crucial problem is to find a set of useful of trajectories, and form a group to learn. The cost and the search may be substantial.

Critical strengths

provide a graph-based approach to work reinforcement learning under agentic environment. The numerical results are quite good.

Critical weaknesses

The crucial problem is to form a graph, and measure their similarities. The cost of the construction, expansive ? pairwise calculati

Questions for authors

How to construct a graph efficiently ?

Reviewer_SzQhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper targets step-level credit assignment in agentic RL. The authors argue that group-based methods misassign credit in long-horizon sparse-reward tasks because they normalize by step index or shape rewards with heuristics like shortest paths. Their proposed GRAFT grafts a task's multiple rollouts into a directed graph, where nodes denote canonicalized states, and edges denote actions. GRAFT runs Bellman value iteration to estimate state values, and uses adjacent-value differences as step credit, extended to a multi-hop Graph GAE. The method requires no critic and no process reward model, adds negligible overhead, and across ALFWorld, WebShop, and SearchQA it consistently outperforms baselines including GRPO, GiGPO, GraphGPO, HCAPO, and SALT.

Critical strengths
  1. The method is simple, cheap, and free of any extra critic or process reward model. Its appeal is that it recycles information group sampling already generates: instead of discarding the multiple rollouts of a task, it stitches them into a graph and runs value iteration, exploiting cross-trajectory transitions at almost no cost. This makes it far more engineering-friendly and scalable than approaches that train a separate value model or call an LLM for process scoring.
  2. GRAFT leads multiple strong baselines across three rather different benchmarks, and the results are reported with variance across runs, so the improvements are clearly consistent rather than noise. Further analysis supports the central claim that the graph genuinely aggregates multi-trajectory information.
  3. Reproducibility is strong: graph construction, value iteration, iteration bounds, multi-hop GAE, and the sequence-level importance ratio in the released code all correspond to the paper, with hyperparameters clearly specified.
Critical weaknesses
  1. Proposition 1's zero population error holds only under the true value function, and the graph-estimated value approximates the truth is asserted rather than proven. Moreover, Bellman iteration converges to the truth only under a deterministic, unique-successor structure, yet SearchQA's similarity merging may merge semantically distinct states into one node.
  2. The text describes embedding cosine similarity, while the released code uses a string edit-distance ratio. This is substantive since it directly determines which states get merged and hence the quality of the resulting value estimates.
  3. Comparisons omit more recent and stronger credit-assignment methods such as BEACON [1] and HGPO [2], which weakens the "better than state of the art" claim. In addition, the experiments rely mainly on Qwen2.5, which is now old; validating on a more recent backbone would strengthen generality. [1] Milestone-guided policy learning for long-horizon language agents. [2] Hierarchy-of-groups policy optimization for long-horizon agentic tasks.
Questions for authors
  1. This is the greatest problem. In discrete, templated environments like ALFWorld/WebShop, the rollouts of a task often revisit identical states, so the graph grafts well. But in open state spaces where the same state is almost never revisited, e.g., open-domain research/browsing agents, where each observation is nearly unique, the graph degenerates into disconnected chains, and the cross-trajectory statistics vanish. How much does GRAFT degrade in such low-overlap settings, and does it need additional state abstraction to create overlap?
  2. Merging currently looks only at the state observation regardless of the history, yet the same state can mean very different things across trajectories. For example, "about to retrieve A" may occur where one trajectory has already gathered substantial information about A and another has none; merging them into a single node is not reasonable. Have you considered folding necessary context into the state canonicalization, or can you argue that ignoring it does not materially harm the value estimate?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.