acceptodds
Under review as a conference paper at ICLR 2027

Structure-Guided Policy Optimization for Long-Horizon Language Agents

Abstract

Large language models (LLMs) have shown promise as sequential decision-makers, yet they still struggle in long-horizon tasks where sparse terminal rewards provide limited guidance for intermediate actions. Existing optimization methods mainly densify supervision through trajectory-level aggregation or local scalar proxies, often treating multi-turn interactions as flat sequences. As a result, they lack an explicit coordinate system for measuring task progress, making it difficult to distinguish redundant local exploration from structural transitions that genuinely advance the task. We propose Structure-Guided Policy Optimization (SGPO), a framework that grounds policy learning in the empirical topology of agent-environment interactions. SGPO aggregates self-generated trajectories into a frequency-weighted state transition graph and partitions it into topological regions that capture latent task structure. Anchored by successful outcomes, this recovered structure induces hierarchical guidance signals: an inter-regional signal that encourages progression across structural bottlenecks toward the target region, and an intra-regional signal that guides efficient local navigation toward preferred exits. These normalized structural signals are integrated at the advantage level with group-based outcome supervision, providing dense stepwise feedback while preserving task success as the primary optimization objective. Extensive experiments on ALFWorld, WebShop and Sokoban show that SGPO improves performance and training stability across diverse LLM scales. The source code is available in the supplementary.

Primary area:
reinforcement learning
Keywords:
LLM agents, Policy Optimization, Reinforcement Learning

Reviews

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

This paper proposes Structure-Guided Policy Optimization (SGPO) to improve credit assignment in long-horizon language-agent reinforcement learning. The method aggregates on-policy trajectories into a frequency-weighted state-transition graph, partitions the graph into regions using Leiden clustering, and derives inter-regional and intra-regional guidance from graph distances to successful outcomes. These signals are added to the trajectory-level GRPO advantage to provide step-level supervision. Experiments on ALFWorld, WebShop, and Sokoban show improvements over GRPO and generally over GiGPO. However, the main contribution is not yet fully established, as the paper does not directly compare against closely related graph-based credit assignment methods or isolate the benefit of regional abstraction itself.

Critical strengths

The paper addresses a meaningful problem, since assigning credit to individual actions from sparse terminal rewards is a genuine challenge in long-horizon agent training. The proposed distinction between global task progression and local navigation is intuitive, and the graph-based formulation provides an interpretable way to construct additional learning signals without introducing a separate reward model.

The experiments cover several environments and model scales, and the ablations provide some evidence that both guidance signals contribute to the reported gains.

I also appreciate the additional analyses of state canonicalization and success-scarce graph construction, which address practical limitations of the approach. The reported computational overhead is small compared with rollout sampling, making the method relatively easy to incorporate into existing group-based RL pipelines.

Critical weaknesses
  1. The novelty over existing graph-based credit assignment methods is not sufficiently established. The closest related work is GraphGPO (ICML 2026), which also aggregates rollout trajectories into a state-transition graph and uses changes in graph distance to the goal for step-level credit assignment. SGPO adds Leiden-based regional abstraction and separates global progression from local navigation, but the paper does not clearly establish how much this additional hierarchy contributes beyond direct graph-distance guidance. Although the related-work section cites methods such as GEPO and SALT, the distinction from these graph-based approaches remains underdeveloped. A direct comparison with GraphGPO under matched training budgets, state representations, and evaluation settings is needed to establish the actual methodological advance.
  2. The current ablation does not isolate the contribution of regional abstraction. Figure 4 removes the inter-regional or intra-regional guidance signal, showing that both are useful within the proposed framework. However, these experiments do not establish that Leiden clustering is necessary. A natural baseline would construct the same empirical graph but calculate progress directly on the original state graph, without partitioning it into regions. This would help determine whether the improvement comes from the hierarchical abstraction or simply from adding graph-based distance signals to GRPO. Adding more substantial evidence would significantly enhance the rigor of the paper’s argumentation.
  3. The role of edge frequency in the distance-based guidance is unclear. Section 4.1 emphasizes that transition edges are weighted by their empirical frequency. However, the abstract graph in Section 4.2 retains an edge whenever at least one transition connects two regions, and the inter-regional distance is then computed using reverse BFS. Thus, a region-to-region transition observed once can have the same effect on shortest-path distance as one observed frequently. This matters because a rare transition caused by an unusual trajectory or imperfect state matching could introduce a shortcut and change the structural advantage assigned to multiple actions. Although edge frequencies influence community detection, their role in the subsequent distance calculation is limited. Could the authors clarify this design choice?
  4. The statistical evidence is insufficient to establish the reliability of the reported improvements. The experiments use three random seeds, but no paired significance tests or confidence intervals are reported. While SGPO generally outperforms GiGPO, the gains are relatively small in some settings. For example, on Sokoban, SGPO achieves 82.1 ± 2.8%, compared with 81.0 ± 3.6% for the strongest GiGPO variant. Given the reported variability, it is unclear whether such improvements are consistent across runs.
Questions for authors

See above.

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

The paper identifies sparse rewards and the lack of an explicit structural basis for measuring task progress as challenges in long-horizon agentic tasks. Structure-Guided Policy Optimization (SGPO) aggregates rollouts collected for the same task into a frequency-weighted empirical transition graph and partitions its states into regions based on connectivity. It uses these regions and the bottlenecks between them to assess how individual actions advance the task.

SGPO constructs inter-regional guidance from reductions in distance to the success region and intra-regional guidance from reductions in distance to preferred exits within each region. These signals are normalized separately and added as weighted corrections to the standard GRPO outcome advantage to obtain step-level advantages. Experiments with Qwen2.5-1.5B/7B-Instruct on ALFWorld and WebShop, and Qwen2.5-VL-3B-Instruct on Sokoban, report improvements in average performance over the evaluated baselines.

Critical strengths

1. The method combines established graph algorithms with low computational overhead.   SGPO constructs action-level learning signals through graph partitioning and reverse BFS-based distance computation without training an additional model. Appendix B.1 reports that the additional graph-side computation is small relative to rollout sampling and policy updates, making the method a practical addition to existing RL training.

2. The paper reports performance gains across multiple environments and model scales.   SGPO achieves higher mean success rates than GRPO and GiGPO at both model scales on ALFWorld and WebShop, as well as on the visual Sokoban benchmark.

Critical weaknesses

1. The presentation and placement of key methodological details and experiments need improvement.

  • Canonicalization determines the nodes and connectivity of the graph, but the main text introduces it primarily through an abstract function ϕ\phi and a list of possible matching approaches. This makes it difficult to understand which states are actually treated as equivalent. Drawing on the context-augmentation details in Appendix A, the main text should briefly summarize the state representations, comparison keys, and matching rules used in each environment. For the Search experiments in Appendix B.4, the inputs to the Ratcliff–Obershelp similarity calculation and the procedure for merging states also need clearer explanations.

  • The organization of the experimental results could be improved. Figure 3 occupies substantial space in the main text, yet there is little discussion of the main observations from these learning curves or their implications. Meanwhile, the context-augmentation and success-scarce graph-construction experiments in Appendix A are important for assessing the method's effectiveness and applicability. Summarizing these key results in the main text and connecting the figures more closely to the analysis would make the method's strengths and limitations easier to assess.

 

2. The added value of region partitioning and inter-/intra-regional guidance is not sufficiently isolated.

  • The paper should more clearly explain how SGPO differs from prior graph-based credit-assignment methods, such as GraphGPO [1] and SALT [2] , and what advantages it offers over them. In particular, the paper emphasizes the limitations of treating multi-turn interactions as flat sequences, but does not sufficiently distinguish the benefits of aggregating experience into a graph from those of further partitioning that graph into regions.

  • The inter-/intra-regional ablations in Section 5.3 support the usefulness of combining the two signals in the evaluated setting. However, both variants retain the region partitioning and remove only one guidance signal. It therefore remains unclear why the hierarchical formulation is preferable to using distances to success directly on the same graph without region partitioning. Such a comparison would help establish the paper's central additional contribution more directly.

References

[1] Xin Cheng, Shuo He, Lang Feng, HaiYang Xu, Ming Yan, Lei Feng, and Bo An. Beyond Trajectory-Level Attribution: Graph-Based Credit Assignment for Agentic Reinforcement Learning. arXiv preprint arXiv:2605.26684, 2026.

[2] Jiazheng Li, Yawei Wang, David Yan, Yijun Tian, Zhichao Xu, Huan Song, Panpan Xu, and Lin Lee Cheong. SALT: Step-level advantage assignment for long-horizon agents via trajectory graph. arXiv preprint arXiv:2510.20022, 2025.

Questions for authors

1. What advantages do region partitioning and inter-/intra-regional guidance provide over a single graph-distance signal?

  • I have considered the inter-/intra-regional ablations in Section 5.3. Do you have results comparing SGPO with a variant that uses the same state representation and empirical transition graph, but omits region partitioning and relies only on reductions in distance from each state to the success node? Please also clarify the differences from prior graph-based methods, to help assess the added value of the hierarchy beyond graph aggregation itself.

 

2. How do changes in the graph affect the actual learning signals during early and late training?

  • Appendix C.1 shows decreases in the number of nodes, the number of regions, and the number of nodes per region over training. Are these changes accompanied by a decrease in the mean number of interaction steps in successful trajectories? Please explain how the graph-size changes relate to shorter execution paths, greater overlap across rollouts, or other factors.
  • Appendix A.5 also states that structural guidance is disabled for groups with no successful rollout. How frequently does this fallback occur early in training, and how does the proportion of transitions receiving inter-/intra-regional guidance change over training?
  • Later in training, rollouts may concentrate on similar successful paths, potentially reducing the diversity of distance reductions. If all signals within a normalization set take the same value, the normalized correction can become zero. Have you examined whether this happens more frequently later in training? Reporting the distributions of raw distance reductions and normalized corrections at different training stages would help clarify whether useful learning signals are maintained as the graphs become smaller.

 

3. How are cycles that cannot reach a preferred exit handled?

  • How are dintrad_{\mathrm{intra}} and rintrar_{\mathrm{intra}} computed when a region has no preferred exit, or when a particular state has no path to any preferred exit? The main text describes a negative signal for entering regions that cannot reach success in the empirical graph, but the treatment of cycles within such regions is unclear.
  • Please clarify how Algorithm 1 handles these cases, including whether the relevant transitions are masked or assigned a separate value, and whether they are included in the normalization statistics.
Reviewer_ECnZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SGPO introduces hierarchical graph-based guidance for long-horizon agent training. It aggregates sampled trajectories into a frequency-weighted state-transition graph, discovers regions using Leiden clustering, and augments GRPO advantages with normalized progress toward successful regions and preferred regional exits. Experiments on ALFWorld, WebShop, and Sokoban, supplemented by search QA experiments and ablations, report improvements over GRPO and GiGPO.

Critical strengths
  • The guidance mechanism is interpretable and practical. Success-oriented regional distances and preferred exits provide explicit step-level feedback without requiring a learned critic or an additional reward model, making the approach straightforward to integrate into group-based training.

  • The evaluation provides meaningful initial evidence. Results cover multiple model scales and both text and visual environments; for example, ALFWorld success improves from 90.2% to 93.8% at 7B. Context-augmentation controls, success-scarcity experiments, and measured computational overhead further strengthen the empirical investigation.

Critical weaknesses
  • The distinctive contribution is insufficiently isolated. Although the manuscript cites SALT [1] and GEPO [2], which already exploit trajectory or state-transition graphs for credit assignment, it provides no experimental comparison with them. The component ablations also omit an unpartitioned shortest-path baseline using identical canonical states. Consequently, the evidence does not establish whether discovered regions add value beyond graph-based dense guidance.

  • The reliability of the broader superiority claims remains uncertain. On Sokoban, SGPO achieves 82.1±2.8 versus 81.0±3.6 for the strongest GiGPO variant, based on three seeds. Moreover, the seven SGPO scores in Table 8 average 42.7, rather than the reported 44.1, reducing the average gain over GiGPO to approximately 0.6 points. Corrected aggregates and uncertainty estimates are needed to assess these gains.

Questions for authors
  • Contribution clarification: Are matched-budget comparisons with SALT [1], GEPO [2], or unpartitioned shortest-path guidance available under the same state canonicalization? These results would materially affect the assessment of regional abstraction.

  • Result clarification: How is the Table 8 average computed, and can the apparent discrepancy be resolved? Can paired per-seed results or confidence intervals clarify the gains over the strongest baselines?

  • Implementation clarification: How are intra-regional scores defined in the target region, which has no strictly closer preferred exit? How are unreachable distances and inactive signals handled during normalization?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.