Résumé Technique : APEX (Exploration Autonome des Politiques pour les Agents LLM Auto-Évolutifs)

1. Énoncé du Problème : Effondrement de l'Exploration chez les Agents Auto-Évolutifs

Bien que les agents basés sur les Grands Modèles de Langage (LLM) aient démontré leur compétence dans des tâches complexes à long horizon, une limitation critique persiste : ils ne peuvent pas apprendre en temps réel lors des tests sans mettre à jour les poids du modèle. Les agents auto-évolutifs existants tentent de surmonter cela en accumulant de la mémoire et en effectuant une réflexion entre les épisodes. Cependant, les auteurs identifient un phénomène nommé effondrement de l'exploration.

À mesure qu'un agent accumule de l'expérience, son comportement a tendance à se concentrer autour de routines familières à haute récompense. Bien que les rendements moyens puissent rester stables ou même augmenter, la diversité exploratoire de l'agent diminue, le conduisant à se stabiliser dans des schémas comportementaux étroits. Par conséquent, l'agent échoue à découvrir des stratégies qualitativement différentes et supérieures qui se situent en dehors de son espace actuel « connu ». L'article soutient que les mécanismes de mémoire et de réflexion existants fournissent une guidance locale mais échouent à maintenir un espace de stratégies persistant et explicite, laissant l'agent inconscient des choix qu'il n'a pas encore essayés.

2. Méthodologie : Le Cadre APEX

Pour remédier à l'effondrement de l'exploration, les auteurs proposent APEX (Exploration Autonome des Politiques). L'innovation centrale réside dans le maintien d'une Carte de Stratégie explicite, un graphe acyclique dirigé (DAG) qui structure les connaissances de l'agent et guide l'exploration.

2.1 La Carte de Stratégie

La carte de stratégie $G = (V, E, \theta)$ est un DAG où :

• Nœuds ($V$) : Représentent des jalons, définis comme des sous-objectifs discrets décrits en langage naturel avec des actions clés associées (par exemple, « récupérer la lanterne en laiton »).
• Arêtes ($E$) : Encodent les dépendances de prérequis (par exemple, le nœud $u$ doit être atteint avant le nœud $v$).
• Statistiques ($\theta$) : Chaque nœud suit le nombre de visites ($n$), la récompense moyenne ($\bar{r}$) et la variance de la récompense ($Var$).

Cette carte transforme l'espace d'actions ouvert en un problème de planification structuré, où l'état de l'agent est l'ensemble des jalons atteints.

2.2 Composants Principaux

APEX fonctionne via un cycle de quatre mécanismes distincts :

1. Sélection de Politique (Exploration au Niveau de l'Épisode) :
   Pendant un épisode, l'agent sélectionne le jalon suivant parmi l'ensemble des jalons éligibles (ceux dont les prérequis sont satisfaits). Cela est formulé comme un problème de bandit à plusieurs bras. Les auteurs évaluent trois stratégies :

   • Échantillonnage de Thompson (Par défaut) : Échantillonne à partir d'une distribution a posteriori basée sur la moyenne et la variance. Il favorise naturellement les jalons à forte incertitude (sous-explorés) sans nécessiter de réglage d'hyperparamètres.
   • UCB (Borne de Confiance Supérieure) : Ajoute une prime d'optimisme basée sur les nombres de visites.
   • $\epsilon$-Greedy : Explore aléatoirement avec une probabilité $\epsilon$.
   • Mécanisme : La sélection est séquentielle ; si un jalon échoue, l'agent réévalue les jalons éligibles plutôt que d'être verrouillé dans une séquence prédéterminée.

2. Raffinement de la Carte (Correction des Connaissances) :
   Périodiquement (tous les $N$ épisodes), un LLM analyse des résumés structurés des épisodes récents pour mettre à jour la carte existante. Il affine les actions clés, corrige les arêtes de dépendance erronées et élague les nœuds dupliqués sur la base de faits observés. Cela garantit que la carte reste fidèle à la mécanique de l'environnement.

3. Propagation du Retour (Attribution du Crédit) :
   Fonctionnant également de manière périodique, ce composant met à jour les statistiques ($\theta$) des jalons. En utilisant un passage topologique inverse sur le DAG, il propage les récompenses depuis les jalons en aval vers leurs prérequis. Cela garantit que les jalons facilitateurs (par exemple, « trouver la clé ») reçoivent le crédit pour déverrouiller les successeurs à haute récompense (par exemple, « ouvrir le coffre »), même si le jalon facilitateur lui-même ne génère aucune récompense immédiate.

4. Découverte de Fourches (Expansion de l'Espace de Stratégies) :
   C'est le mécanisme principal pour prévenir l'effondrement de l'exploration. Contrairement au Raffinement, qui corrige les chemins connus, la Découverte de Fourches étend activement le front de la carte. Un LLM analyse les résumés d'épisodes pour identifier des actions ou des directions qui ont été observées ou disponibles mais jamais poursuivies. Il propose de nouveaux jalons et arêtes de dépendance pour encoder ces possibilités inexplorées, forçant efficacement l'agent à considérer des stratégies qu'il n'a jamais tentées.

3. Contributions Clés

• Identification de l'Effondrement de l'Exploration : L'article démontre empiriquement que les agents auto-évolutifs (comme Reflexion) convergent souvent vers des routines comportementales étroites, manquant des stratégies supérieures que des agents statiques non apprenants découvrent parfois par la simple diversité.
• Espace de Stratégies Explicite : APEX introduit le premier cadre pour les agents auto-évolutifs qui maintient une carte explicite et structurée de l'espace de stratégies (jalons et dépendances), plutôt que de compter uniquement sur une mémoire non structurée ou une réflexion.
• Exploration en Double Boucle : Le cadre sépare l'expansion au niveau de la carte (Découverte de Fourches) de la sélection au niveau de l'épisode (Sélection de Politique), créant une boucle fermée où de nouveaux territoires sont continuellement ouverts et systématiquement visités.
• Attribution de Crédit Robuste : La propagation du retour basée sur le DAG garantit que les actions facilitatrices sont correctement valorisées, résolvant le problème des récompenses clairsemées dans les tâches complexes.

4. Résultats Expérimentaux

Les auteurs ont évalué APEX sur deux benchmarks : Jericho (9 jeux d'aventure textuelle) et WebArena (812 tâches d'interaction web réalistes).

• Performance : APEX a constamment surpassé tous les modèles de référence (Statique, Mémoire, Reflexion, EvoTest, ACE) dans tous les environnements.
  • Dans Jericho, APEX a obtenu les scores Final-5 les plus élevés sur les 9 jeux. Notamment, dans les jeux nécessitant des stratégies diversifiées (par exemple, Ztuu), APEX a nettement surpassé Reflexion, qui convergeait souvent vers des maxima locaux sous-optimaux.
  • Dans WebArena, APEX a mené dans les 5 catégories (Shopping, Reddit, GitLab, CMS, Carte), avec des gains particulièrement importants sur Reddit et GitLab où des séquences multi-étapes et non évidentes sont requises.
• Études d'Ablation :
  • DAG vs Liste Plate : La structure de dépendance (DAG) était cruciale ; une liste plate de jalons a performé nettement moins bien, confirmant que le raisonnement sur les prérequis est essentiel.
  • Découverte de Fourches : La suppression de la Découverte de Fourches a entraîné une baisse significative de la performance, en particulier dans les jeux complexes, prouvant que l'expansion active de l'espace de stratégies est nécessaire pour éviter l'effondrement.
  • Sélection de Politique : L'échantillonnage de Thompson a surpassé UCB et $\epsilon$-Greedy, soulignant l'importance de l'exploration consciente de la variance.
  • Propagation du Retour : La propagation de crédit basée sur le DAG a surpassé la propagation basée sur les chemins séquentiels, garantissant une estimation précise de la valeur pour les jalons facilitateurs.
• Généralisation : APEX a démontré une forte généralisation inter-tâches sur WebArena, transférant les connaissances des tâches vues vers les tâches non vues sans priors spécifiques à la tâche.
• Coût : Malgré les composants de réflexion supplémentaires, le coût API d'APEX était comparable à celui des autres méthodes en raison de la nature concise des prompts guidés par les jalons.

5. Signification et Revendications

L'article revendique qu'APEX résout efficacement le problème de l'effondrement de l'exploration chez les agents LLM auto-évolutifs en passant d'un apprentissage implicite basé sur la mémoire à une exploration explicite basée sur la carte.

• Signification : Le travail démontre que pour que les agents améliorent leurs performances au fil du temps, ils ne doivent pas seulement réfléchir sur ce qu'ils ont fait, mais aussi construire et naviguer activement dans une carte de ce qu'ils n'ont pas fait.
• Modestie : Les auteurs reconnaissent les limites : la qualité de la carte de stratégies est bornée par la capacité du LLM à identifier des jalons et à inférer des directions inexplorées. Des mécanismes de jeu profondément cachés ou des stratégies entièrement en dehors des connaissances passées de l'agent peuvent toujours être manqués. De plus, l'approche actuelle repose sur des tâches qui se décomposent naturellement en jalons discrets, suggérant que les environnements continus ou moins structurés pourraient nécessiter des adaptations de la définition des jalons.

En conclusion, APEX fournit un cadre robuste pour une exploration soutenue, permettant aux agents auto-évolutifs de découvrir des stratégies supérieures que les méthodes traditionnelles basées sur la réflexion échouent à trouver.