Résumé Technique : Recherche de Graphes au Moment du Test pour l'Apprentissage par Renforcement Conditionné par un Objectif

Énoncé du Problème

L'apprentissage par renforcement conditionné par un objectif (GCRL) hors ligne vise à entraîner des agents à atteindre des objectifs spécifiés par l'utilisateur en utilisant des données précollectées, évitant ainsi les coûts et les risques de sécurité liés à l'interaction en ligne. Bien qu'efficace pour des tâches à horizon modéré, les politiques GCRL hors ligne standard échouent souvent sur des tâches à long horizon. Dans des environnements complexes (par exemple, de grands labyrinthes), les erreurs d'estimation de la valeur s'accumulent, conduisant à des politiques peu fiables incapables de relier des comportements provenant de parties disparates du jeu de données.

Les solutions antérieures à ce problème ont introduit une complexité significative, telle que des planificateurs génératifs intensifs en calcul, l'entraînement d'ensembles de fonctions de valeur distributionnelles, l'utilisation de représentations géométriques spécialisées, ou la dépendance à des données supplémentaires au-delà du jeu de données hors ligne. Ces approches opèrent souvent sous l'hypothèse que les fonctions de valeur conditionnées par un objectif standard sont intrinsèquement trop bruyantes ou peu fiables pour soutenir une planification directe à long horizon.

Méthodologie : Recherche de Graphes au Moment du Test (TTGS)

Les auteurs proposent la Recherche de Graphes au Moment du Test (TTGS), un wrapper de planification léger et sans entraînement conçu pour augmenter des politiques GCRL figées. TTGS opère entièrement au moment du test, ne nécessitant aucune supervision supplémentaire, mise à jour de paramètres ou interaction en ligne.

Composants Principaux

1. Construction du Graphique :

   • Un sous-ensemble d'états est échantillonné à partir du jeu de données hors ligne pour servir de sommets du graphique.
   • Un signal de distance est utilisé pour attribuer des poids d'arêtes entre ces sommets. Ce signal peut être dérivé de :
     • Distances dérivées de la valeur : La fonction de valeur conditionnée par un objectif préentraînée $V(s, g)$ est mappée vers un nombre estimé d'étapes $\hat{d}(s, g)$. L'article fournit des mappings sous forme fermée pour des conventions de récompense courantes (par exemple, récompenses terminales éparses ou pénalités par étape).
     • Distances spécifiques au domaine : Utilisation de métriques géométriques comme la distance euclidienne entre les positions corporelles lorsque disponibles.
   • Mécanisme de Pénalité Douce : Pour résoudre le problème des fonctions de valeur surestimant la connectivité (créant des "trous de ver" à travers des écarts), TTGS emploie une fonction de pénalité superlinéaire $p(\cdot)$ pour les transitions dépassant un seuil de région de confiance $\tau$. Les arêtes avec des distances $D_{ij} < \tau$ conservent leur distance brute, tandis que celles avec $D_{ij} \ge \tau$ se voient attribuer un poids $p(D_{ij})$ (par exemple, $x \cdot 1000^{x/\tau}$). Cela préserve la structure métrique locale tout en orientant le planificateur vers des chaînes de sauts courts et fiables, empêchant le graphique de se fragmenter (comme le ferait un seuil dur) ou permettant des sauts longs non réalisables.

2. Planification au Moment du Test :

   • Recherche du Plus Court Chemin : Étant donné un état de départ $s_0$ et un objectif $g$, l'algorithme localise les sommets les plus proches dans le graphique et calcule un plus court chemin en utilisant l'algorithme de Dijkstra. Ce chemin guide est calculé une fois par épisode.
   • Sélection Adaptative de Sous-Objectifs : Pendant l'exécution, l'agent ne suit pas le chemin aveuglément. Au lieu de cela, il sélectionne un sous-objectif parmi le chemin précalculé basé sur un budget d'étapes $T$. L'agent identifie le point de passage le plus éloigné sur le chemin qui se trouve dans le budget $T$ par rapport à l'état actuel. Si aucun tel point de passage n'existe, il sélectionne le point de passage immédiat suivant pour assurer une progression vers l'avant.
   • Exécution de la Politique : La politique de base figée $\pi(a | s, \tilde{g})$ est invoquée avec l'état actuel et le sous-objectif sélectionné $\tilde{g}$.

Outil de Diagnostic

L'article introduit un rapport de saut maximal ($\rho$) comme diagnostic sans déploiement pour prédire si TTGS sera bénéfique pour une nouvelle tâche. $\rho$ est le rapport du coût d'arête maximal le long du chemin planifié à la distance estimée totale. Un $\rho$ faible indique une couverture suffisante des états intermédiaires (favorable à TTGS), tandis qu'un $\rho$ élevé suggère que le jeu de données manque d'états de liaison, auquel cas TTGS revient par défaut au comportement de la politique de base.

Contributions Clés

1. Réévaluation des Fonctions de Valeur : Les auteurs démontrent que les fonctions de valeur GCRL hors ligne standard, précédemment considérées comme trop peu fiables pour la recherche, encodent une structure géométrique locale suffisante pour une planification robuste à long horizon lorsqu'elles sont traitées avec un nouveau mécanisme de pénalité douce.
2. Cadre Sans Entraînement : TTGS fournit une méthode pour améliorer les performances à long horizon en réutilisant les politiques et fonctions de valeur existantes sans modifier le pipeline d'entraînement, ne nécessitant aucune supervision supplémentaire ni interaction en ligne.
3. Performance avec Surcoût Minimal : Les résultats empiriques montrent que TTGS augmente considérablement les taux de réussite pour des agents GCRL hors ligne de l'état de l'art (HIQL, QRL, GCIQL, SAW, OTA) avec un surcoût computationnel négligeable (temps de planification < 1 seconde par épisode).

Résultats Expérimentaux

La méthode a été évaluée sur le benchmark OGBench, couvrant des tâches de locomotion (pointmaze, antmaze, humanoidmaze) et de manipulation.

• Tâches de Locomotion : TTGS a réalisé des gains substantiels sur des tâches de "raccordement" à long horizon où les politiques de base échouent généralement.
  • Sur pointmaze-giant-stitch-v0, les taux de réussite pour HIQL sont passés de 0,0 % à 80,9 %, et pour GCIQL de 0,0 % à 98,0 %.
  • Sur humanoidmaze-giant-stitch-v0, HIQL est passé de 4,4 % à 78,1 %.
  • Ces améliorations ont souvent égalé ou surpassé des méthodes complexes nécessitant un entraînement auxiliaire ou des modèles génératifs.
• Tâches de Manipulation : Sur des tâches où les objectifs d'évaluation se situent en dehors de la variété des données (par exemple, scene-play-v0), TTGS a apporté des gains minimes (0 à 2 points de pourcentage) mais n'a pas dégradé les performances, revenant correctement à la politique de base lorsque les états intermédiaires manquaient.
• Ablations :
  • Pénalités Douces vs Dures : Le retrait de la pénalité douce (utilisation de distances brutes) ou l'utilisation d'un seuil dur (suppression des arêtes longues) a considérablement dégradé les performances sur les tâches de raccordement en raison de déconnexions du graphique ou de chemins non réalisables.
  • Sélection de Sous-Objectifs : La stratégie adaptative de sélection du point de passage le plus éloigné accessible a surpassé une stratégie plus simple consistant à toujours choisir le point de passage immédiat suivant.
  • Sources de Distance : TTGS a fonctionné efficacement avec des distances dérivées de la valeur et des distances simples de position corporelle euclidienne, démontrant sa flexibilité.

Importance et Revendications

L'article revendique que la complexité supplémentaire souvent supposée nécessaire pour la planification à long horizon est fréquemment inutile. En exploitant la structure géométrique latente déjà présente dans les fonctions de valeur standard et en appliquant une recherche de graphe légère au moment du test, les praticiens peuvent étendre considérablement les capacités des agents GCRL hors ligne existants.

Les auteurs soulignent que TTGS est un wrapper de planification conservateur et sûr : il repose uniquement sur des états récupérés du jeu de données, évitant la synthèse de trajectoires physiquement impossibles courante dans les approches génératives. Lorsque les données hors ligne manquent des états intermédiaires nécessaires pour relier le départ et l'objectif, TTGS revient gracieusement au comportement de la politique de base plutôt que de produire des plans peu fiables. Le travail suggère que les agents GCRL basés sur la valeur laissent souvent une structure géométrique utile inutilisée, et TTGS fournit une recette pour récupérer cette structure pour la planification à long horizon sans réentraînement.