🤖 machine learning

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

Dieses Paper schlägt die Group-Graph Policy Optimization (G2PO) vor, einen neuartigen gruppenbasierten Reinforcement-Learning-Algorithmus, der lineare Interaktionstrajektorien in einen globalen Zustandsübergangsgraphen transformiert, um Belohnungsspärlichkeit zu mildern und die Kreditzuweisung zu verbessern, wodurch die Leistung von großen Sprachmodellen bei langfristigen agentischen Aufgaben signifikant gesteigert wird.

Ursprüngliche Autoren: Yunan Wang, Minghui Song, Zihan Zhang, Shaohan Huang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, Qi Zhang

Veröffentlicht 2026-06-23

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Yunan Wang, Minghui Song, Zihan Zhang, Shaohan Huang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, Qi Zhang

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie bringen einem sehr intelligenten, aber unerfahrenen Roboter bei, ein komplexes Rätsel zu lösen, wie zum Beispiel das Finden eines bestimmten Gegenstands in einem riesigen, unordentlichen Lagerhaus oder den Kauf des perfekten Geschenks auf einer Website. Der Roboter muss viele Schritte (Züge) unternehmen, um die Aufgabe zu vollenden, und er erhält erst am Ende ein „Gut gemacht!“ oder ein „Versuch es noch einmal“.

Das Problem mit aktuellen Lehrmethoden ist, dass sie den Weg des Roboters wie eine gerade Linie behandeln. Wenn der Roboter frühzeitig einen großartigen Zug macht, aber später über seine eigenen Füße stolpert, wird die gesamte Reise als Misserfolg gewertet. Der Roboter lernt dann, dass der großartige Zug eigentlich schlecht war, was verwirrend ist und das Lernen verlangsamt.

Dieses Paper stellt eine neue Lehrmethode namens G2PO (Group-Graph Policy Optimization) vor. So funktioniert sie, unter Verwendung einfacher Analogien:

1. Von einer geraden Linie zu einem Netz aus Pfaden

Aktuelle Methoden beobachten den Roboter dabei, wie er einen geraden Pfad vom Start bis zum Ziel geht. Wenn der Roboter stecken bleibt, ist dieser Pfad eine Sackgasse.
G2PO ändert die Perspektive. Anstatt einer geraden Linie baut es ein riesiges Netz (oder einen Graphen) aus allen Pfaden auf, die der Roboter jemals ausprobiert hat.

Die Analogie: Stellen Sie sich vor, der Roboter erkundet eine Höhle. Aktuelle Methoden betrachten nur einen spezifischen Tunnel. G2PO betrachtet die gesamte Höhlenkarte. Es bemerkt, dass der Roboter, obwohl er unterschiedliche Routen genommen hat, oft genau im selben Raum (Zustand) landet.

2. Die „Gruppenumarmung“ für Fehler (Group-Aggregation)

Auf dem alten Weg: Wenn der Robat einen bestimmten Raum betritt und dann scheitert, wird dieser Raum als „Schlecht“ markiert. Wenn er denselben Raum später betritt und Erfolg hat, wird dieser Raum als „Gut“ markiert. Das ist verwirrend, da der Raum selbst sich nicht verändert hat; nur der Pfad danach tat es.
G2PO sagt: „Lass uns uns alle Male ansehen, in denen der Roboter diesen spezifischen Raum betreten hat.“

Die Analogie: Stellen Sie sich einen Lehrer vor, der die Hausaufgaben eines Schülers bewertet. Anstatt eine einzelne Prüfung zu bewerten und zu sagen: „Du hast versagt“, betrachtet G2PO 10 verschiedene Tests, die der Schüler zum selben Thema gemacht hat. Wenn der Schüler die richtige Antwort 7 Mal richtig und 3 Mal falsch hatte, erkennt der Lehrer: „Ah, der Schüler versteht dieses Thema eigentlich gut; die 3 Fehler waren nur Pech.“
Das Ergebnis: Dies verhindert, dass der Roboter für Pech bestraft wird, und belohnt ihn für gute Entscheidungen, selbst wenn das Endergebnis aufgrund späterer Fehler ein Misserfolg war.

3. Den Schritt bewerten, nicht nur das Ziel (Edge-Centric Advantage)

Aktuelle Methoden vergleichen den Zug eines Roboters oft nur mit anderen Zügen, die in genau demselben Raum verfügbar sind.
G2PO betrachtet den Wert des Sprungs selbst. Es fragt: „Wie viel näher hat dieser spezifische Zug den Roboter dem Ziel gebracht, verglichen mit dem Punkt, an dem er gestartet ist?“

Die Analogie: Stellen Sie sich einen Wanderer vor, der einen Berg hinaufsteigt.
- Alte Methode: „Du hast einen Schritt nach oben gemacht. Gut. Aber du hast später noch einen Schritt nach oben gemacht. War dein erster Schritt besser als der zweite?“ (Lokaler Vergleich von Schritten).
- G2PO: „Du hast unten gestartet (niedriger Wert). Du hast einen Schritt gemacht, der dich halb oben am Berg gelandet hat (hoher Wert). Das war ein riesiger Sprung nach vorn! Selbst wenn du später am Abgrund gestürzt bist, war dieser spezifische Schritt brillant.“
Das Ergebnis: G2PO identifiziert die „entscheidenden Sprünge“, die die Aufgabe tatsächlich voranbringen, und gibt ihnen ein Extra-Lob, während es kleine, triviale Schritte ignoriert, die nicht viel ausmachen.

4. Warum es wichtig ist

Das Paper testete dies bei drei schwierigen Aufgaben:

WebShop: Online-Einkäufe tätigen.
ALFWorld: Hausarbeiten in einem simulierten Haus erledigen.
AppWorld: Code schreiben, um Apps zu verwalten.

Das Ergebnis:

Der Roboter lernte viel schneller und machte weniger Fehler.
Er war signifikant erfolgreicher als vorherige Methoden (bis zu 22 % besser in einigen Fällen).
Das Beste daran: Er schaffte dies alles, ohne mehr Rechenleistung zu benötigen. Er hat einfach die Daten, die er bereits hatte, intelligenter organisiert (wie das Umräumen eines unordentlichen Schreibtisches, um Dinge schneller zu finden, anstatt einen größeren Schreibtisch zu kaufen).

Zusammenfassend lässt sich sagen:
G2PO hört auf, die Lernreise des Roboters als eine einzige, zerbrechliche Linie zu behandeln. Stattdessen baut es eine Karte aller Möglichkeiten auf, gleicht das Glück durch den Durchschnitt aus, um die Wahrheit zu finden, und belohnt den Roboter für die spezifischen Schritte, die ihn dem Ziel tatsächlich näher bringen. Es ist wie ein Upgrade von einem GPS, das nur eine Route anzeigt, zu einem intelligenten Navigationssystem, das die ganze Stadt kennt und Ihnen genau sagt, welche Abbiegung die wichtigste war.

Technisches Resümee: Group-Graph Policy Optimization für Long-Horizon Agentic Reinforcement Learning

Problemstellung

Der Übergang von Large Language Models (LLMs) von Chatbots zu autonomen Agenten, die in der Lage sind, komplexe, reale Probleme zu lösen, erfordert eine robuste Entscheidungsfindung über lange Zeithorizonte (long-horizon decision-making). Während Reinforcement Learning (RL) das Denken in Single-Turn-Aufgaben (z. B. Mathematik und Kodierung) erfolgreich verbessert hat, stellt die Anwendung auf Multi-Turn-Agentic-Szenarien eine erhebliche Herausforderung dar.

Bestehende agentische RL-Frameworks sind weitgehend von Trajektorien-Ebene auf Schritt-Ebene (step-level) umgestiegen, um die Kontextexplosion und den Speicherverbrauch zu mildern. Diese Schritt-Ebene-Ansätze leiden jedoch unter zwei kritischen Einschränkungen bei Long-Horizon-Aufgaben:

Hohe Varianz in der Zustands-Wert-Schätzung: Aktuelle Methoden behandeln die Exploration des Agenten oft als eine Sammlung isolierter, linearer Trajektorien. Da unterschiedliche Trajektorien, die vom gleichen Umweltzustand ausgehen, aufgrund von Stochastizität zu völlig unterschiedlichen Ergebnissen führen können, ist die Schätzung des Wertes eines Zustands basierend auf dem Ertrag einer einzelnen Trajektorie unzuverlässig und anfällig für hohe Varianz.
Grobkörnige Kreditzuweisung (Credit Assignment): Bestehende Schritt-Ebene-Methoden (z. B. GiGPO) vergleichen Aktionen typischerweise nur innerhalb einer lokalen Gruppe identischer Zustände. Diese lokale Perspektive erfasst nicht die globale Bedeutung eines Übergangs. Sie kann nicht zwischen einer geringfügigen Verbesserung in einem trivialen Zustand und einer entscheidenden Durchbruchaktion unterscheiden, die den absoluten Fortschritt zum Endziel vorantreibt, was zu einer myopischen (kurzsichtigen) Kreditzuweisung führt.

Darüber hinaus sind Long-Horizon-Aufgaben durch spärliche Belohnungen (sparse rewards) gekennzeichnet, wobei das Feedback oft erst am Ende von Dutzenden von Interaktionsschritten erfolgt, was die zwischenzeitliche Kreditzuweisung erschwert.

Methodik: Group-Graph Policy Optimization (G2PO)

Um diese Engpässe zu adressieren, schlagen die Autoren Group-Graph Policy Optimization (G2PO) vor, einen neuartigen gruppenbasierten RL-Algorithmus, der lineare Interaktionstrajektorien explizit in einen globalen Zustands-Übergangs-Graphen transformiert.

1. Konstruktion des State Group Graph

Anstatt Trajektorien als unabhängige Linien zu behandeln, aggregiert G2PO identische oder ähnliche Umweltbeobachtungen über alle gesampelten Trajektorien hinweg in Zustandsgruppen (Nodes). Die Aktionen des Agenten dienen als gerichtete Kanten (Edges), die diese Knoten verbinden und so einen einheitlichen Zustands-Übergangs-Graphen bilden. Diese Struktur erkennt an, dass verschiedene Trajektorien oft auf dieselben Umweltzustände konvergieren (z. B. dieselbe Webseite oder dieselbe physische Konfiguration).

2. Gruppen-Aggregierte Zustands-Wert-Schätzung

Um die inhärente hohe Varianz bei der Bewertung einzelner Trajektorien zu mildern, führt G2PO einen Gruppen-Aggregationsmechanismus ein:

Mechanismus: Für jede gegebene Zustandsgruppe $G_k$ ist der Wert $V(G_k)$ definiert als der Mittelwert der diskontierten Erträge aller Zwischenschritte, die zu dieser Gruppe gehören, über alle gesampelten Trajektorien hinweg.
Vorteil: Durch die Mittelung der Ergebnisse aus mehreren Trajektorien, die denselben Zustand passieren, schätzt die Methode den intrinsischen erwarteten Wert des Zustands anstatt eines Zufallsergebnisses aus einer einzelnen Stichprobe. Die theoretische Analyse zeigt, dass dies die Varianz der Wertschätzung linear im Verhältnis zur Gruppengröße reduziert.

3. Multi-Granularitäts-Vorteils-Schätzung (Advantage Estimation)

G2PO synthetisiert drei Arten von Advantages, um dichtes, feinkörniges Feedback zu liefern:

Knotenzentrierter Vorteil (Node-Centric Advantage, ANC): Bewertet eine Aktion durch den Vergleich des Wertes des resultierenden Zustands mit dem Mittelwert aller möglichen nächsten Zustände aus dem aktuellen Knoten. Dies erfasst lokale Präferenzen.
Kantenzentrierter Vorteil (Edge-Centric Advantage, AEC): Dies ist die Kerninnovation. Aktionen werden als Übergänge zwischen Zustandsknoten behandelt. Der Vorteil wird basierend auf dem Temporal Difference (TD) Fehler ( $\delta = V_{next} - V_{current}$ ) berechnet, welcher den absoluten Wertgewinn des Übergangs repräsentiert. Entscheidend ist, dass diese TD-Fehler über den gesamten Graphen hinweg global standardisiert werden, anstatt nur lokal innerhalb einer Zustandsgruppe. Dies ermöglicht es G2PO, kritische Übergänge, die substanziellen absoluten Fortschritt vorantreiben, explizit zu identifizieren und zu priorisieren, selbst wenn die spezifische Trajektorie letztlich scheitert.
Episoden-basierter Vorteil (Episode-Level Advantage, AEP): Wird aus dem Standard-GRPO beibehalten, um sicherzustellen, dass der Lernprozess weiterhin mit dem ultimativen Aufgabenziel im Einklang steht.

Der finale Vorteil für einen Schritt ist eine gewichtete Kombination dieser Komponenten:
$A_{ij} = A_{EP}(a_{ij}) + w \cdot (A_{NC}(a_{ij}) + A_{EC}(a_{ij}))$

Hauptbeiträge

Das Paper skizziert vier primäre Beiträge:

G2PO Algorithmus: Ein gruppenbasierter RL-Algorithmus, der speziell für Long-Horizon-Agent-Aufgaben entwickelt wurde und lineare Trajektorien in einen State Group Graph transformiert.
Gruppen-Aggregierte Zustands-Wert-Schätzung: Eine Methode zur Adressierung der hohen Varianz in der Zustands-Wert-Schätzung durch die Aggregation von Ergebnissen über identische Zustände in verschiedenen Trajektorien hinweg.
Kantenzentrierte Vorteils-Schätzung: Eine Strategie, die Aktionen als Übergänge neu definiert und ihren absoluten Beitrag zum globalen Fortschritt mittels global standardisierter TD-Fehler misst, wodurch die Einschränkungen lokaler Gruppenvergleiche überwunden werden.
Empirische Validierung: Umfangreiche Experimente, die zeigen, dass G2PO State-of-the-Art-Baselines mit vernachlässigbarem Rechenaufwand übertrifft.

Experimentelle Ergebnisse

Die Autoren evaluierten G2PO auf drei repräsentativen Long-Horizon-Benchmarks: WebShop (E-Commerce), ALFWorld (verkörperte physische Umgebungen) und AppWorld (komplexe Software-Ökosysteme). Die Experimente wurden mit Qwen-2.5 Modellen (1.5B, 7B und 14B) durchgeführt.

Performance: G2PO übertraf konsistent prompt-basierte Methoden (z. B. ReAct, Reflexion) und RL-Baselines (PPO, RLOO, GRPO, GiGPO).
- Auf WebShop erreichte G2PO eine Verbesserung der Erfolgsrate von bis zu 22,2 % gegenüber GRPO.
- Auf ALFWorld erzielte es eine Verbesserung von 14,4 % gegenüber GRPO.
- Auf AppWorld übertraf GPO alle anderen RL-Trainingsmethoden und demonstrierte eine robuste Generalisierbarkeit auf komplexe API-basierte Aufgaben.
Effizienz: Mit G2PO trainierte Modelle benötigten weniger Interaktionsrunden, um Aufgaben abzuschließen, im Vergleich zu GRPO und GiGPO, was auf eine verbesserte Entscheidungs-Effizienz hindeutet.
Rechenaufwand: Die Graph-Konstruktion und die Advantage-Schätzungs-Pipeline basieren ausschließlich auf CPU-Verarbeitung. Die Autoren berichten, dass G2PO lediglich etwa 1 Sekunde zusätzlichen Overhead pro Trainingsschritt verursacht (ca. 0,4 % der Gesamtzeit), wodurch die hohe Effizienz des zugrunde liegenden GRPO-Frameworks bewahrt bleibt.

Bedeutung und Ansprüche

Das Paper behauptet, dass G2PO eine signifikante Weiterentwicklung des agentischen RL darstellt, indem es die Perspektive von isolierten linearen Trajektorien zu einer globalen Graphstruktur verschiebt. Durch die explizite Modellierung des Zustands-Übergangs-Graphen und die Nutzung der Gruppen-Aggregation löst die Methode effektiv das Problem der Kreditzuweisung in Szenarien mit spärlichen Belohnungen und langen Zeithorizonten, ohne den Rechenaufwand eines gelernten Critic-Netzwerks oder die Annotationskosten von Process Reward Models zu verursachen.

Die Autoren betonen, dass ihr Ansatz der Philosophie entspricht, empirische Mittelwerte zu nutzen (wie bei GRPO gesehen), dies jedoch auf die strukturelle Ebene von Zustandsübergängen erweitert. Die Ergebnisse legen nahe, dass das Erkennen der inhärenten Graphstruktur von Multi-Turn-Interaktionen entscheidend ist, um die Varianz zu reduzieren und kritische Durchbruchsaktionen zu identifizieren, was zu erheblichen Leistungssteigerungen in komplexen agentischen Aufgaben führt.