- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3(+1)
Read review
Paper summary
This paper introduces Graph-Hit Group Policy Optimization (GHGPO), a graph-based reward estimation method for agentic RL. By incorporating both the topological distance and the policy-dependent success probability of each action, this paper provides a more comprehensive combination of reward estimation compared with GraphGPO. The empirical results show that GHGPO consistently improves agentic RL performance in various agentic tasks.
Critical strengths
-
The motivation of this idea is clear: previous graph-based reward estimation methods do not consider policy-dependent success. GHGPO incorporates this feature, which makes the soundness of this paper easy to understand.
-
This paper conducts comprehensive experiments, including two text-based and one visual-based agentic environments. In addition, this paper also involves analysis of the motivation and efficiency, broadly showing the benefits of this method.
Critical weaknesses
-
One main concern is that GHGPO is established on an assumption: the policy-dependent success that is characterized by the finite-budget graph-hit probability is helpful for reward estimation. However, the reliability of policy-dependent success highly relies on the performance of the base model. Given a weak base model, the policy-dependent success induced from the sampled trajectories may be unstable for analysis. Further clarification on the reliability of this feature could be helpful.
-
Another main concern is that the contribution of GHGPO is strongly based on graph-based reward estimation. The authors only mention one graph-based reward estimation method (GraphGPO), which suggests that this paper is just a follow-up of a previous method. In addition, GraphGPO also cannot be applied to all agentic tasks (for example, for math and coding tasks, the observations are very stochastic, which introduces significant challenges for state determination for group computation), which also limits the generality of GHGPO.
-
The formulation of Sec. 4 is a little hard to follow, especially in Eq. (8), the matrix and the subscript of . It would be better to further explain or change the representation of this formulation.
-
Minor: In Figure 1, Prefix: visting -> visiting. Besides, using complex formulas in Figure 1 without explicit explanation may decrease readability.
Questions for authors
See main weaknesses
7 comments
Response to Reviewer XKeC (2/4)
W2(a): Another main concern is that the contribution of GHGPO is strongly based on graph-based reward estimation. The authors only mention one graph-based reward estimation method (GraphGPO), which suggests that this paper is just a follow-up of a previous method.
A2: We thank the reviewer for raising this concern. We agree that GHGPO should be more clearly positioned within the broader literature on graph-based credit assignment to better highlight its distinct contributions.
Distinctions from existing graph-based methods. SALT [1] and G2PO [2] both leverage graph structures to aggregate recurring states or transitions across trajectories, enabling cross-trajectory sharing of credit information. Specifically, SALT mainly aggregates trajectory-level outcome advantages over shared transitions, while G2PO aggregates discounted terminal returns within identical state groups and uses the resulting state values to compute process advantages. In contrast, GraphGPO further exploits the multi-step topology of the graph to assign process credit based on shortest-path distances to successful states. GHGPO goes beyond structural distance by explicitly modeling probabilistic success reachability, using empirical transition probabilities and multi-step recursion to estimate the probability of reaching success under the current policy within a finite interaction budget.
Distinct methodological contributions. GHGPO reveals the limitations of structural distance in characterizing success reachability. As demonstrated in Sec. 4.1, states with identical shortest-path distances can have different success probabilities, and a state that is structurally closer to success may even have a lower success probability than a more distant state.
To address this limitation, GHGPO preserves empirical transition frequencies from grouped rollouts to construct a policy-dependent probabilistic transition model. It then computes finite-budget graph-hit probabilities through dynamic programming and visiting-step marginalization. Unlike existing methods that primarily derive process credit through outcome-information aggregation, state-value differences, or structural distances, GHGPO explicitly models success reachability using multi-step probabilistic transitions and the remaining interaction budget. Consequently, even with identical graph topology, different empirical transition frequencies can yield different graph-hit credit, while shortest-path distances remain unchanged. This constitutes a distinct methodological contribution to graph-based process-level credit assignment.
Empirical evidence. The ablation results in Table 3 further validate the effectiveness of graph-hit credit and its complementarity with distance-based credit. On WebShop, achieves 78.65% success, achieves 83.33%, and the full combination reaches 84.63%. On ALFWorld, the corresponding overall success rates are 92.71%, 93.75%, and 96.61%, respectively. These results demonstrate that finite-budget success reachability provides an effective process-credit signal beyond structural distance, and that combining the two can further improve policy optimization.
We will expand the Related Work section to include a comparison with these graph-based credit assignment methods and further clarify GHGPO's distinct contribution in explicitly modeling policy-dependent, finite-budget success reachability.
References
[1] Jiazheng Li et al. SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph. Findings of EACL 2026, pp. 4709–4725.
[2] Yunan Wang et al. Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning. NeurIPS 2026.
Response to Reviewer XKeC (3/4)
W2(b): In addition, GraphGPO also cannot be applied to all agentic tasks (for example, for math and coding tasks, the observations are very stochastic, which introduces significant challenges for state determination for group computation), which also limits the generality of GHGPO.
A3: We thank the reviewer for highlighting the challenges of state identification and merging in complex tasks. While mathematical reasoning and coding tasks involve more diverse state representations, making state aggregation more challenging, this does not preclude the application of graph-based RL to such tasks. In fact, recent studies have explored this direction through both more flexible state-matching and merging strategies and RL algorithms built upon aggregated states, demonstrating encouraging potential.
Specifically, regarding state matching, GraphPO [3] uses semantic summaries of reasoning prefixes and embedding similarity to identify and merge equivalent states across reasoning trajectories. SALT [1] further employs semantic matching in complex environments such as AppWorld, where actions involve free-form code and natural-language instructions, allowing functionally equivalent steps with different surface forms to be merged. Regarding RL algorithms, GraphPO leverages merged reasoning graphs for advantage estimation and demonstrates performance improvements on mathematical reasoning tasks. SALT and G2PO [2] also exploit shared states across trajectories for fine-grained credit assignment, demonstrating effectiveness on complex long-horizon agentic tasks, including AppWorld. Together, these studies suggest that with task-appropriate state-matching mechanisms, state aggregation and graph-based RL have promising potential for more complex tasks.
Adaptation to mathematical reasoning. Inspired by GraphPO's semantic state construction and merging strategy, we conducted an additional experiment using Qwen2.5-7B-Math. Specifically, we divide reasoning trajectories into reasoning segments and represent intermediate states using semantic summaries of their reasoning prefixes. We then encode these summaries into embeddings and use cosine similarity to identify and merge semantically equivalent states across trajectories. This enables intermediate states representing similar reasoning progress to be aggregated despite differences in their textual expressions.
On the resulting state-transition graph, GHGPO preserves empirical transition frequencies and computes finite-budget graph-hit probabilities for process credit assignment. We express the finite interaction budget in reasoning-segment units by dividing the response token budget by the minimum semantic-segment length.
Experimental results.
| Method | AIME24 | AIME25 | MATH500 | LiveCodeBench |
|---|---|---|---|---|
| Qwen2.5-7B-Math† | 13.6 | 6.3 | 54.8 | 5.7 |
| GRPO† | 23.3 | 15.5 | 79.5 | 11.4 |
| GraphPO† | 32.1 | 24.5 | 91.6 | 16.9 |
| GraphGPO | 31.1 ± 1.7 | 20.9 ± 0.9 | 87.8 ± 0.7 | 13.6 ± 0.5 |
| GHGPO | 33.2 ± 1.9 | 23.3 ± 1.1 | 91.9 ± 0.8 | 17.1 ± 0.3 |
† Results are taken from GraphPO [3]. Results for GraphGPO and GHGPO are obtained from our experiments and reported as mean ± standard deviation over three independent random seeds.
GHGPO achieves the best performance on three of the four benchmarks (AIME24, MATH500, and LiveCodeBench), while remaining competitive on AIME25. It consistently outperforms the base model and GRPO across all benchmarks. Compared with graph-based methods, GHGPO outperforms GraphGPO on all four benchmarks and achieves better results than GraphPO on three of them. These results further demonstrate that, with a suitable semantic state-matching and merging mechanism, GHGPO's finite-budget graph-hit credit assignment can be effectively applied to mathematical reasoning, with improvements also observed on the LiveCodeBench coding benchmark. This provides additional empirical support for extending state-aggregation-based graph RL to more complex tasks.
References
[1] Jiazheng Li et al. SALT: Step-level Advantage Assignment for Long-horizon Agents via Trajectory Graph. Findings of EACL 2026, pp. 4709–4725.
[2] Yunan Wang et al. Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning. NeurIPS 2026.
[3] Yuliang Zhan et al. GraphPO: Graph-based Policy Optimization for Reasoning Models. arXiv:2606.18954, 2026.
Response to Reviewer XKeC (1/4)
We thank the reviewer for the thoughtful review and valuable feedback. Below, we address the reliability of graph-hit credit under weak base policies, clarify GHGPO's distinct methodological contributions and generalizability, and provide further explanations to improve the clarity of the paper.
A1: We thank the reviewer for raising this question. GHGPO assigns relative process-level credit by comparing the finite-budget graph-hit probabilities of candidate actions' successor states. Ideally, actions with higher probabilities of eventual task success should receive higher credit. Therefore, reliable credit assignment should preserve action rankings consistent with their underlying success probabilities. To examine whether graph-hit estimates obtained from limited rollouts achieve this, we use a large number of sampled trajectories to estimate empirical success probabilities as a reference and evaluate the consistency of the resulting action rankings.
Experimental setup. We evaluate five checkpoints of Qwen2.5-1.5B-Instruct during training on ALFWorld, representing policies at different training stages and performance levels. Policy Success Rate denotes the task success rate of each checkpoint on the ALFWorld validation set, measuring the policy's overall task-solving ability.
At each checkpoint, we sample 256 trajectories for each of 64 ALFWorld tasks, yielding 16,384 trajectories in total. For each task separately, we estimate the empirical success probability of each observed state s using its corresponding 256 trajectories:
\frac{\\#\text{occurrences of }s\text{ in successful trajectories}} {\\#\text{total occurrences of }s}.$$ This estimate serves as a large-sample Monte Carlo empirical reference for the corresponding task under the same checkpoint policy. We then subsample **$M=8$ trajectories per task**, matching the rollout budget used during training, to construct empirical transition graphs and compute finite-budget graph-hit probabilities. For pairs of candidate actions originating from the same state, we compare the rankings induced by their successor states' graph-hit probabilities with those induced by the empirical success probabilities. **A higher proportion of consistent action-pair rankings indicates that the relative credit ordering induced by finite-sample graph-hit estimates is more consistent with the ordering implied by large-sample empirical success frequencies.** Thus, action-ranking consistency reflects the effectiveness of finite-sample graph-hit estimates in relative credit assignment. We compute **Pairwise Ranking Agreement (PRA)** as the number of action pairs with consistent rankings divided by the total number of compared action pairs, requiring agreement on greater-than, less-than, and equality relations. **Results.** | Training Step | Policy Success Rate | Graph-hit PRA | |---|---:|---:| | 0 | 8.67% | 84.80% | | 40 | 51.83% | 76.57% | | 80 | 78.04% | 84.03% | | 120 | 80.62% | 77.40% | | 150 | 83.94% | 80.14% | **Notably, at the initial checkpoint, the policy achieves only 8.67% task success, while graph-hit already reaches 84.80% PRA.** Across all five checkpoints, despite substantial differences in policy success rates, PRA remains between **76.57% and 84.80%**. These results indicate that, even when the base policy has a low overall task success rate, graph-hit estimates obtained using the training-time rollout budget can still largely preserve action rankings consistent with the large-sample empirical reference. Furthermore, Figure 3 shows favorable early-training validation performance of GHGPO compared with GraphGPO, providing complementary evidence of its effectiveness in policy optimization.