Résumé Technique : Optimisation de Politique par Graphe de Groupes pour l'Apprentissage par Renforcement d'Agents à Longue Horizon

Énoncé du Problème

La transition des modèles de langage de grande taille (LLM) de simples agents conversationnels vers des agents autonomes capables de résoudre des problèmes complexes du monde réel nécessite une prise de décision robuste sur de longs horizons. Bien que l'apprentissage par renforcement (RL) ait réussi à améliorer le raisonnement dans des tâches à tour unique (par exemple, les mathématiques et le codage), l'appliquer à des scénarios d'agents multi-tours présente des défis significatifs.

Les cadres d'apprentissage par renforcement agentique existants ont largement délaissé l'entraînement au niveau de la trajectoire pour un entraînement au niveau de l'étape afin d'atténuer l'explosion du contexte et la consommation de mémoire. Cependant, ces approches par étape souffrent de deux limitations critiques dans les tâches à long horizon :

1. Haute Variance dans l'Estimation de la Valeur d'État : Les méthodes actuelles traitent souvent l'exploration de l'agent comme une collection de trajectoires isolées et linéaires. Comme différentes trajectoires partant du même état environnemental peuvent aboutir à des résultats radicalement différents en raison de la stochasticité, l'estimation de la valeur d'un état basée sur le résultat d'une seule trajectoire est peu fiable et sujette à une variance élevée.
2. Attribution de Crédit Grossière : Les méthodes par étape existantes (par exemple, GiGPO) comparent généralement les actions uniquement au sein d'un groupe local d'états identiques. Cette perspective locale ne parvient pas à capturer l'importance globale d'une transition. Elle ne peut pas distinguer une amélioration mineure dans un état trivial d'une action de rupture critique qui conduit à un progrès absolu vers l'objectif final, menant ainsi à une attribution de crédit myope.

De plus, les tâches à long horizon sont caractérisées par des récompenses éparses, où le feedback est souvent différé jusqu'à la toute fin de dizaines d'étapes d'interaction, rendant difficile l'attribution de crédit intermédiaire.

Méthodologie : Optimisation de Politique par Graphe de Groupes (G2PO)

Pour répondre à ces goulots d'étranglement, les auteurs proposent G2PO (Group-Graph Policy Optimization), un nouvel algorithme de RL basé sur des groupes qui transforme explicitement les trajectoires d'interaction linéaires en un graphe de transition d'états global.

1. Construction du Graphe de Groupes d'États

Au lieu de traiter les trajectoires comme des lignes indépendantes, G2PO agrège les observations environnementales identiques ou similaires à travers toutes les trajectoires échantillonnées en groupes d'états (nœuds). Les actions de l'agent servent d'arêtes dirigées reliant ces nœuds, formant un graphe de transition d'états unifié. Cette structure reconnaît que différentes trajectoires convergent souvent vers les mêmes états environnementaux (par exemple, la même page web ou la même configuration physique).

2. Estimation de la Valeur d'État par Agrégation de Groupes

Pour atténuer la haute variance inhérente à l'évaluation par trajectoire unique, G2PO introduit un mécanisme d'agrégation de groupes :

• Mécanisme : Pour tout groupe d'états $G_k$ donné, la valeur $V(G_k)$ est définie comme la moyenne des retours actualisés de toutes les étapes intermédiaires appartenant à ce groupe à travers toutes les trajectoires échantillonnées.
• Avantage : En faisant la moyenne des résultats de multiples trajectoires passant par le même état, la méthode estime la valeur attendue intrinsèque de l'état plutôt qu'un résultat aléatoire issu d'un seul échantillon. L'analyse théorique démontre que cela réduit la variance de l'estimation de la valeur de manière linéaire par rapport à la taille du groupe.

3. Estimation d'Avantage Multi-Granularité

G2PO synthétise trois types d'avantages pour fournir un feedback dense et fin :

• Avantage Centré sur le Nœud (ANC) : Évalue une action en comparant la valeur de l'état résultant à la valeur moyenne de tous les états suivants possibles à partir du nœud actuel. Cela capture les préférences locales.
• Avantage Centré sur l'Arête (AEC) : C'est l'innovation centrale. Les actions sont traitées comme des transitions entre des nœuds d'états. L'avantage est calculé sur la base de l'erreur de Différence Temporelle (TD) ($\delta = V_{next} - V_{current}$), représentant le gain de valeur absolue de la transition. Crucialement, ces erreurs TD sont standardisées globalement à travers l'ensemble du graphe, plutôt que localement au sein d'un groupe d'états. Cela permet à G2PO d'identifier et de prioriser explicitement les transitions critiques qui génèrent un progrès absolu substantiel, même si la trajectoire spécifique finit par échouer.
• Avantage au Niveau de l'Épisode (AEP) : Conservé de GRPO standard pour garantir que le processus d'apprentissage reste aligné avec l'objectif ultime de la tâche.

L'avantage final pour une étape est une combinaison pondérée de ces composantes :
$$A_{ij} = A_{EP}(a_{ij}) + w \cdot (A_{NC}(a_{ij}) + A_{EC}(a_{ij}))$$

Principales Contributions

L'article souligne quatre contributions principales :

1. Algorithme G2PO : Un algorithme de RL basé sur des groupes spécifiquement conçu pour les tâches d'agents à long horizon qui transforme les trajectoires linéaires en un graphe de groupes d'états.
2. Estimation de la Valeur d'État par Agrégation de Groupes : Une méthode pour traiter la haute variance de l'estimation de la valeur d'état en agrégeant les résultats à travers des états identiques dans différentes trajectoires.
3. Estimation d'Avantage Centrée sur l'Arête : Une stratégie qui redéfinit les actions comme des transitions et mesure leur contribution absolue au progrès global via des erreurs TD standardisées globalement, surmontant les limites des comparaisons de groupes locaux.
4. Validation Empirique : Des expériences approfondies démontrant que G2PO surpasse les méthodes de référence de pointe avec un surcoût computationnel négligeable.

Résultats Expérimentaux

Les auteurs ont évalué G2PO sur trois benchmarks représentatifs de long horizon : WebShop (e-commerce), ALFWorld (environnements physiques incarnés) et AppWorld (écosystèmes logiciels complexes). Les expériences ont été menées sur des modèles Qwen-2.5 (1.5B, 7B et 14B).

• Performance : G2PO a systématiquement surpassé les méthodes basées sur le prompting (par exemple, ReAct, Reflexion) et les bases de référence de RL (PPO, RLOO, GRPO, GiGPO).
  • Sur WebShop, G2PO a obtenu une amélioration du taux de réussite allant jusqu'à 22,2 % par rapport à GRPO.
  • Sur ALFWorld, il a obtenu une amélioration de 14,4 % par rapport à GRPO.
  • Sur AppWorld, G2PO a surpassé toutes les autres méthodes d'entraînement par RL, démontrant une robustesse de généralisation aux tâches complexes basées sur des API.
• Efficacité : Les modèles entraînés avec G2PO ont nécessité moins de tours d'interaction pour accomplir les tâches par rapport à GRPO et GiGPO, indiquant une meilleure efficacité de la prise de décision.
• Coût Computationnel : La construction du graphe et le pipeline d'estimation de l'avantage reposent exclusivement sur le traitement CPU. Les auteurs rapportent que G2PO n'introduit qu'environ 1 seconde de surcharge supplémentaire par étape d'entraînement (environ 0,4 % du temps total), préservant la haute efficacité du cadre GRPO sous-jacent.

Signification et Revendications

L'article affirme que G2PO représente une avancée significative dans le RL agentique en déplaçant la perspective des trajectoires linéaires isolées vers une structure de graphe globale. En modélisant explicitement le graphe de transition d'états et en utilisant l'agrégation de groupes, la méthode résout efficacement le problème de l'attribution de crédit dans les scénarios à récompense éparse et à long horizon sans le surcoût computationnel d'un réseau critique appris ou les coûts d'annotation de modèles de récompense de processus.

Les auteurs soulignent que leur approche s'aligne sur la philosophie de l'exploitation des moyennes empiriques (telle que vue dans GRPO) mais l'étend au niveau structurel des transitions d'états. Les résultats suggèrent que la reconnaissance de la structure de graphe inhérente aux interactions multi-tours est cruciale pour réduire la variance et identifier les actions de rupture critiques, menant à des gains de performance substantiels dans les tâches agentiques complexes.