PaperlayerView exact revision on arXiv

Source-linked AI summary

Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning

Yunan Wang, Minghui Song, Zihan Zhang, Shaohan Huang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, Qi Zhang

arXiv:2606.22995v2cs.LGcs.AIcs.CL

TL;DR

Existing step-level agentic RL still assigns credit over isolated trajectories, despite shared states connecting paths. G2PO builds a global state-transition graph, aggregates state values, and scores transitions using globally standardized TD errors. Across WebShop, ALFWorld, and AppWorld, it outperforms prompt-based and RL baselines, with up to 22.2% success-rate improvement over GRPO on ALFWorld.

  • Problem

    Existing step-level methods treat exploration as isolated trajectories, leaving high-variance state-value estimates and local action comparisons that miss global importance.

    Source: §1 · p. 2

  • Method

    G2PO builds a state-transition graph, aggregates values for shared observations across trajectories, and globally standardizes edge-level TD errors to estimate advantages.

    Source: §1 · pp. 2–3

  • Results

    Across WebShop, ALFWorld, and AppWorld, G2PO outperforms prompt-based and RL baselines, with up to 22.2% success-rate improvement over GRPO on ALFWorld.

    Source: §1 · p. 3

  • Takeaways & Limitations

    G2PO reports substantial gains over state-of-the-art RL baselines with almost no additional computational overhead on long-horizon agent tasks.

    Source: §1 · p. 3, §6 · p. 10

    The limitations addressed are those of existing step-level methods: single-trajectory state estimates are high-variance, and local comparisons miss global action importance.

    Source: §1 · p. 2

Abstract

from arXiv · show

Group-based Reinforcement Learning (RL) has significantly enhanced Large Language Models (LLMs) in agentic scenarios. To achieve finer-grained policy updates, recent agentic RL frameworks have shifted from trajectory-level to step-level training. However, long-horizon agentic RL suffers from severe reward sparsity and delay, as feedback is often deferred for dozens of interaction steps. While existing step-level frameworks refine training granularity, their credit assignment remains coarse-grained and still treats agent exploration as isolated, linear trajectories. This oversimplified perspective ignores the inherent graph structure of state transitions, leading to high-variance state-value estimation and myopic, localized credit assignment. To overcome these critical bottlenecks, we propose Group-Graph Policy Optimization (G2PO), a novel group-based RL algorithm tailored for multi-turn agentic tasks. G2PO explicitly transforms linear interaction trajectories into a global state-transition graph. By aggregating identical observations across different trajectories, we introduce group-aggregation state-value estimation that reduces sampling variance and trajectory-dependent bias. Furthermore, we redefine agent actions as transitions between state nodes and propose an edge-centric advantage estimation strategy. By globally standardizing Temporal Difference (TD) errors across the entire graph, G2PO explicitly identifies and prioritizes critical transitions that drive absolute task progress. Extensive experiments on representative long-horizon benchmarks-WebShop, ALFWorld, and AppWorld-demonstrate that G2PO substantially outperforms state-of-the-art prompt-based and RL baselines, achieving remarkable success rate improvements of up to 22.2% over GRPO.

1 Introduction

Long-horizon agentic RL has shifted toward step-level training, yet existing methods still assign credit along isolated trajectories rather than a shared state graph. G2PO builds that graph to estimate state values across trajectories and globally score transitions.

1 Introduction

  • Trajectory-level training causes context growth and memory consumption, while step-level training reduces that burden but retains coarse credit assignment over isolated linear paths.Shared environmental states connect trajectories as graph nodes, with actions serving as transition edges.Source: §1 · pp. 1–2
  • State values estimated from a single sampled trajectory are high-variance because later errors or corrections can change whether that trajectory succeeds.Different continuations from the same state can reach different end states.Source: §1 · p. 2
  • Comparing actions only within a local state misses their global importance, making minor local gains hard to distinguish from breakthroughs that advance the task.Source: §1 · p. 2
  • G2PO reconstructs sampled trajectories as a state-transition graph, aggregates values across identical or similar observations, and globally standardizes edge-level TD errors to prioritize progress-driving transitions.The value aggregation reduces dependence on a single trajectory outcome; edge advantages compare the values of source and destination nodes.Source: §1 · pp. 2–3
  • G2PO improves success rates by up to 14.4% over GRPO on WebShop and 22.2% over GRPO on ALFWorld, while outperforming prompt-based and RL baselines.The experiments cover WebShop, ALFWorld, and AppWorld, with almost no additional computational cost.Source: §1 · p. 3

2 Related work

Prior work spans LLM agents, group-based RL, and interactive-agent optimization, while the paper positions G2PO against limitations in trajectory-level and local credit assignment.

LLM Agents

  • Agentic LLM approaches interleave reasoning and environment actions, as in ReAct, Toolformer, and Reflexion.MetaGPT structures multi-agent collaboration around human procedures.Source: §2 · p. 3

Reinforcement Learning for LLMs

  • RLOO and GRPO use group samples without a separate critic, while process reward models [4] offer step guidance but can require costly annotation and risk reward hacking.The passage describes G2PO as deriving dense advantages from sampling statistics without a learned critic or process-supervision annotation.Source: §2 · p. 3

Reinforcement Learning for LLM Agents

  • RL has emerged as a cornerstone for LLM agents in dynamic, open-ended environments [25] [50] [61], and standard on-policy PPO/AWR [34] proved effective across diverse interactive scenarios.Source: §2 · p. 3
  • RAGEN [49] optimizes whole trajectories, GEPO [59] uses graph centrality and task similarity, and GiGPO compares steps at identical states; G2PO instead aggregates states across sampled trajectories.The passage characterizes GiGPO’s single-trajectory outcomes as susceptible to sampling bias.Source: §2 · p. 4

3 Preliminary

The preliminary section defines delayed-reward, multi-turn agent interaction and reviews GRPO’s group-normalized advantages and clipped policy objective.

3.1 Problem Setup

  • In the problem setup, an agent receives observations and produces actions across a long-horizon trajectory, but receives a scalar reward only upon task completion or reaching the interaction threshold.Intermediate steps receive no immediate rewards, making their actions difficult to score.Source: §3.1 · p. 4

3.2 Group Relative Policy Optimization

  • GRPO estimates each sampled output’s advantage by normalizing its reward against the group mean and standard deviation, then optimizes a clipped objective with a KL penalty toward a reference policy.The importance-sampling ratio compares current-policy and old-policy probabilities; the clipping parameter and KL penalty control the update.Source: §3.2 · p. 4

4 Training LLM Agents with G2PO

G2PO builds a state-group graph from sampled trajectories and averages values across shared observations. It uses graph-based step advantages to provide finer-grained credit assignment for multi-turn agentic RL.

4.1 State Group Graph Construction

  • Similar observations across sampled trajectories form state-group nodes, with agent actions represented as transitions between nodes.The graph supports step-level advantages from both node and edge perspectives.Source: §4.1 · p. 4, Figure 2 · p. 5

4.2 Group-Aggregation State-Value Estimation

  • A state group's value averages the discounted-return values of its constituent steps, reducing sampling variance and later-step noise in state evaluation.Identical states can lead to different outcomes across trajectories, making single-trajectory values unreliable.Source: §4.2 · p. 5

4.3 Multi-Granularity Advantage Estimation

  • Node-centric advantage compares destination-state values among actions from the same state, while G2PO also retains an episode-level advantage to keep learning aligned with the task objective.The combined step-level advantage is scaled by a static weight before being merged with episode-level feedback.Source: §4.3 · p. 6
  • Edge-centric advantage globally standardizes transition TD errors across sampled trajectories to prioritize transitions with larger value gains over locally normalized actions.This approach can preserve positive reinforcement for an impactful action even if later exploratory errors cause its trajectory to fail.Source: §4.3 · p. 6

5 Experiment

Across WebShop, ALFWorld, and AppWorld, G2PO outperforms the reported RL baselines; its ablations and analyses support group-aggregated values and edge-centric advantages, with low added training overhead.

5.1 Experimental Setting

  • Experiments cover WebShop, ALFWorld, and AppWorld, comparing frontier models, prompting agents, and RL methods; main-paper state groups use exact observation-string matching.The paper describes exact matching as an implementation choice rather than an algorithmic requirement.Source: §5.1 · p. 7

5.2 Experimental Results

  • G2PO outperforms the reported baselines on WebShop and ALFWorld, and outperforms RL methods on AppWorld.The reported gains over GRPO reach 22% on WebShop and 14% on ALFWorld; AppWorld results cover complex API-based observations.Source: §5.2 · p. 7, Table 2 · p. 7, Table 1 · p. 8

5.3 Ablation Study

  • Group-aggregation and edge-centric advantages each contribute to performance: aggregation improves WebShop and ALFWorld results, while edge-centric advantages outperform node-centric ones.The ablation attributes aggregation's gains to reduced state-value variance and edge-centric advantages to capturing actions' global, absolute contribution.Source: §5.3 · p. 8, Figure 3 · p. 8

5.4 Analysis

  • On WebShop, success rate and score peak at w = 0.8; lower values approach GRPO, while higher values risk short-sighted optimization.The analysis uses Qwen2.5-1.5B and reports that performance first rises and then falls as w increases.Source: §5.4 · p. 8, Figure 4 · p. 9
  • Across both benchmarks and 1.5B/7B scales, many states have non-zero value variance because identical states can lead to different outcomes.Group aggregation averages outcomes from identical states across trajectories to assign each node a more consistent value.Source: §5.4 · p. 9, Figure 4 · p. 9
  • G2PO uses fewer interaction turns than GRPO on WebShop and ALFWorld, and in most cases fewer than GiGPO.The paper connects fewer turns with lower inference and environment API-call costs.Source: §5.4 · p. 9, Figure 4 · p. 9

5.5 Computational Budget

  • G2PO adds only 1 second of overhead during advantage calculation; its CPU-only advantage-estimation pipeline occupies 0.4% of total RL training time, preserving GRPO’s high efficiency.Source: §5.5 · p. 9

6 Conclusion

The conclusion presents G2PO as a graph-based framework using group-aggregated state values and edge-centric advantages, with gains over RL baselines and almost no added computational overhead. The paper's implementation is limited to verl-agent, with other agentic RL frameworks and rollout settings left for future exploration.

6 Conclusion

  • G2PO restructures trajectories as a state-transition graph, using group-aggregated values and edge-centric advantages to prioritize transition value gains.Experiments report performance gains over state-of-the-art RL baselines with almost no additional computational overhead.Source: §6 · p. 10

A Limitations

  • The implementation is limited to verl-agent; the authors identify other agentic RL frameworks and tree or asynchronous sampling as future directions.The paper chose verl-agent for its lightweight step-level RL and flexible credit-assignment control.Source: A Limitations · p. 14

B Variance Reduction Analysis

G2PO analyzes variance reduction from aggregating values across shared state groups and estimating action advantages from transitions between groups. Its training procedure combines these fine-grained signals with episode-level feedback.

B.1 Value Estimation Variance Reduction

  • When a state group contains more than one sample, group aggregation linearly reduces value-estimation variance relative to a single-trajectory estimate.The derivation assumes sparse terminal rewards, an undiscounted horizon, and independent sampling across trajectories.Source: §B.1 · pp. 14–15

B.2 Advantage Estimation Variance Reduction

  • Trajectory-level advantages depend on a single trajectory outcome, whereas G2PO measures an action using the one-step TD difference between target and source group values.The paper notes that trajectory-level estimates are therefore heavily influenced by subsequent steps.Source: §B.2 · p. 15
  • When both source and target groups contain multiple samples, edge-centric advantage estimation has variance no greater than trajectory-level advantage estimation under the stated assumptions.The analysis attributes this bound to positively correlated source- and target-group value estimates.Source: §B.2 · p. 15

C Pseudo Code

  • G2PO combines edge-centric, node-centric, and episode-level advantages with confidence-aware weights before updating the policy.The training procedure constructs a state-group graph and estimates group values before integrating the three feedback granularities.Source: C Pseudo Code · p. 15

D Group Size Analysis

Training produces repeated state observations across WebShop, ALFWorld, and AppWorld, with group sizes and dynamics varying by benchmark. The section also introduces the benchmark settings and comparison-baseline categories.

D Group Size Analysis

  • Only 11.9% of WebShop steps and 8.1% of ALFWorld steps have group size 1; average group size is around 5 in both benchmarks.WebShop group size initially rises and then falls, while ALFWorld group size rises after reasoning-format learning; the paper attributes the latter trend to repetitive actions.Source: D Group Size Analysis · pp. 15–16, Figure 6 · p. 16, Figure 7 · p. 16

E.1 Descriptions of Benchmarks

  • AppWorld has a mean state-group size of 2.01 and 155.38 state groups per task graph, indicating non-trivial overlap despite less overlap than in WebShop and ALFWorld.The section presents WebShop as a simulated e-commerce task, ALFWorld as embodied household tasks, and AppWorld as API composition and task planning across apps.Source: D Group Size Analysis · p. 16, §E.1 · p. 17

E.2 Comparing Baselines

  • The comparison includes off-the-shelf models, prompt-based methods, and RL approaches, including GiGPO, PPO, RLOO, and GRPO.GiGPO estimates relative advantages at episode and step levels using retrospectively grouped identical states.Source: §E.2 · p. 17

E.3 Training Details

The experiments use benchmark-specific interaction limits and shared training settings, with G2PO trained on WebShop, ALFWorld, and AppWorld. The section also supplies agent prompts and illustrates edge-centric advantage estimation with an ALFWorld case.

E.3 Training Details

  • Training uses 128 total environments; group-based methods sample 16 groups of 8, while episode limits are 15 steps in WebShop and 30 in AppWorld.Qwen2.5-1.5/7B experiments use 4×H100 GPUs for ALFWorld and WebShop; AppWorld Qwen2.5-14B uses 8×H100 GPUs.Source: §E.3 · p. 18

E.4 Prompts

F Case Study

  • For the ALFWorld case, edge-centric advantage assigns 2.1 to the transition toward the fridge, compared with 0.55 under local group comparison.The task is to cool a bowl and put it in a microwave; the source observation describes moving a cup to the microwave, while the destination observation locates the fridge.Source: F Case Study · pp. 18–19, Figure 11 · p. 20

G State Grouping under Observation Noise

The noisy-observation ALFWorld setting with similarity-based grouping preserves overall success relative to exact matching on original observations.

G State Grouping under Observation Noise

  • 95.3% overall success with similarity matching under observation noise compares with 95.0% for exact matching without noise.The noisy variant inserts task-irrelevant sentences and merges observations above a SequenceMatcher similarity threshold of 0.95.Source: G State Grouping under Observation Noise · p. 21, Table 3 · p. 21

H Empirical Comparison with GEPO

G2PO matches or exceeds GEPO on the evaluated ALFWorld and WebShop settings, with lower reported training overhead on WebShop. The section also examines whether edge-centric advantage tracks critical actions and action importance.

H Empirical Comparison with GEPO

  • 95.0% vs. 92.9%: G2PO exceeds GEPO on ALFWorld by 2.1 percentage points with half as many rollouts, and reaches 97.7%, 4.8 points above GEPO, at N = 16.The comparison uses N = 8 for G2PO's 95.0% result and N = 16 for its 97.7% result.Source: Table 4 · p. 21, H Empirical Comparison with GEPO · p. 21
  • At N = 8 on WebShop, G2PO and GEPO differ by only 0.2 percentage points; reported overhead is approximately 0.4% per G2PO training step versus GEPO's approximately 15%.GEPO's reported overhead is approximately 35% at N = 16.Source: Table 5 · p. 21, H Empirical Comparison with GEPO · p. 21

I Diagnostic Validation of the Edge-Centric Advantage

I.1 Advantages of Critical and Non-Critical Actions

The diagnostic evaluates edge-centric advantage against critical actions on shortest paths and against action importance defined by subsequent task success rate.

I.1 Advantages of Critical and Non-Critical Actions

  • Critical actions receive higher average advantages in 91.0% of tasks, with nearly three times the average advantage of non-critical actions and a mean difference of +0.4655.Critical actions are those on a shortest path from the initial state to a success state; the reported advantage is unnormalized, before global standardization.Source: Table 6 · p. 22, §I.1 · p. 22

I.2 Correlation with Action Importance

  • Action importance is defined as the task success rate following an action; the diagnostic compares this measure with episode-, node-, and edge-centric advantages.Source: §I.2 · p. 22
  • The edge-centric signal has approximately 5.1× and 8.3× the Pearson correlation of node-centric and episode-level signals, and 2.6× and 6.9× their Spearman correlation.The absolute correlations are described as modest.Source: Table 7 · p. 22, §I.2 · p. 22

Related papers

Loading 2606.22995v2…