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

Technical Summary: Group-Graph Policy Optimization for Long-Horizon Agentic Reinforcement Learning

Problem Statement
The paper addresses the challenges of applying Reinforcement Learning (RL) to Large Language Model (LLM) agents in long-horizon, multi-turn agentic scenarios. While group-based RL methods like GRPO have improved reasoning in single-turn tasks, agentic tasks require dozens of interaction steps, leading to severe reward sparsity and delay. Existing step-level agentic RL frameworks, while reducing context length compared to trajectory-level methods, suffer from two critical limitations:

1. High Variance in State-Value Estimation: Treating agent exploration as isolated, linear trajectories means that identical environmental states encountered in different trajectories are evaluated based on single, stochastic outcomes. This leads to unreliable value estimates where a promising state might be undervalued due to subsequent errors, or a poor state overvalued due to lucky corrections.
2. Coarse-Grained Credit Assignment: Current methods (e.g., GiGPO) rely on local group comparisons, evaluating actions only against other actions available at the same state. This lacks a global perspective, failing to distinguish between minor improvements in trivial states and critical breakthrough actions that significantly advance task progress.

Methodology: Group-Graph Policy Optimization (G2PO)
To overcome these bottlenecks, the authors propose G2PO, a novel group-based RL algorithm that transforms linear interaction trajectories into a global state-transition graph. The methodology consists of three core components:

1. State Group Graph Construction:
   The algorithm samples $N$ complete trajectories for a given task. It partitions all intermediate observations into disjoint state groups by clustering identical observations. These state groups form the nodes ($V$) of a graph, while agent actions serve as directed edges ($E$) representing transitions between state nodes. This structure captures the inherent graph nature of state transitions, connecting different trajectories that share common states.

2. Group-Aggregation State-Value Estimation:
   Instead of relying on the reward of a single trajectory, G2PO aggregates intermediate steps with identical observations across all trajectories into state groups. The value of a state group $G_k$ is defined as the mean of the discounted returns of all steps within that group:
   $$V(G_k) = \frac{1}{|G_k|} \sum_{o^i_j \in G_k} v^i_j$$
   This approach reduces sampling variance and trajectory-dependent bias by averaging out future-step noise, providing a more robust estimate of a state’s intrinsic expected value.

3. Multi-Granularity Advantage Estimation:
   G2PO synthesizes three types of advantages to provide dense feedback:

   • Node-Centric Advantage ($A^{NC}$): Compares the value of the next state against the mean value of all possible next states from the current node, capturing local preferences.
   • Edge-Centric Advantage ($A^{EC}$): Redefines actions as transitions between state nodes. It calculates the 1-step Temporal Difference (TD) error ($\delta = V(G_{next}) - V(G_{current})$) and globally standardizes these errors across the entire graph. This explicitly prioritizes critical transitions that drive substantial absolute progress toward the goal, regardless of the local context.
   • Episode-Level Advantage ($A^{EP}$): Retains the standard GRPO advantage based on final trajectory rewards to ensure alignment with the ultimate task objective.

   The final advantage for each step is a weighted combination: $A^i_j = A^{EP}(a^i_j) + w \cdot (A^{NC}(a^i_j) + A^{EC}(a^i_j))$.

Key Contributions

• G2PO Framework: A new group-based RL algorithm tailored for long-horizon agent tasks that explicitly reconstructs sampled trajectories into a state-transition graph.
• Variance Reduction: Introduction of group-aggregation state-value estimation to mitigate the high variance inherent in single-trajectory value estimates.
• Global Credit Assignment: An edge-centric advantage estimation strategy that measures the absolute contribution of each step toward the global goal by globally standardizing TD errors.
• Efficiency: The method achieves performance gains with almost no additional computational cost, as the graph construction and advantage calculation are performed on the CPU and occupy a negligible portion of training time.

Experimental Results
The authors evaluate G2PO on three long-horizon benchmarks: WebShop (e-commerce), ALFWorld (embodied physical environments), and AppWorld (complex software ecosystems). Experiments are conducted using Qwen-2.5 models (1.5B, 7B, and 14B).

• Performance: G2PO consistently outperforms state-of-the-art baselines, including prompt-based methods (ReAct, Reflexion) and RL baselines (PPO, RLOO, GRPO, GiGPO).
  • On WebShop, G2PO achieves a success rate of 71.2% (Qwen-2.5-1.5B), outperforming GRPO by 14.4%.
  • On ALFWorld, G2PO achieves an overall success rate of 95.0% (Qwen-2.5-1.5B), outperforming GRPO by 22.2%.
  • On AppWorld, G2PO achieves the highest success rate (27.6%) and score (21.7) among all RL methods.
• Ablation Study: Results confirm that both group-aggregation state-value estimation and edge-centric advantage estimation are indispensable. Removing either component leads to performance degradation, highlighting their roles in reducing variance and capturing global importance, respectively.
• Efficiency: G2PO reduces the number of inference steps required to complete tasks compared to GRPO and GiGPO, indicating improved decision-making efficiency. The additional computational overhead for advantage calculation is minimal (~1 second per training step).

Significance
The paper claims that G2PO significantly enhances the capability of LLM agents in long-horizon tasks by addressing the credit assignment problem through a global graph perspective. By moving beyond isolated linear trajectories, G2PO provides finer-grained, more stable, and globally aware policy updates. This allows agents to better identify critical actions that drive task progress, leading to substantial improvements in success rates across diverse and complex environments without incurring significant computational costs.