Laplacian Representations for Decision-Time Planning

Énoncé du Problème
L'apprentissage par renforcement (RL) fondé sur des modèles offre des avantages potentiels en termes d'efficacité d'échantillonnage, de généralisation et d'adaptation par rapport aux approches sans modèle (model-free). Cependant, un défi central demeure : la planification avec un modèle appris dans des environnements nécessitant une approximation de fonction est entravée par le problème de l'erreur de composition. Lorsqu'un agent simule de longues trajectoires à l'aide d'un modèle imparfait, de petites erreurs de prédiction s'accumulent, provoquant une divergence significative des trajectoires imaginées par rapport à la réalité. Ce problème est particulièrement aigu lors de la planification au moment de la décision, où les représentations d'état doivent simultanément supporter le calcul de coûts locaux et préserver les structures temporelles à long terme. Bien que la planification hiérarchique puisse découpler les actions de bas niveau des objectifs à long terme, elle nécessite un espace latent capable de représenter les distances de l'espace d'état à travers plusieurs échelles de temps pour décomposer efficacement les tâches en sous-objectifs.

Méthodologie
L'article propose que la représentation Laplacienne fournit un espace latent efficace pour la planification au moment de la décision. Cette représentation intègre les états dans un espace défini par les vecteurs propres du Laplacien de graphe induit par la dynamique de l'environnement. Les propriétés clés de cette représentation incluent :

• Structure multi-échelle : Les vecteurs propres sont ordonnés par échelle de temps ; les premiers vecteurs propres encodent la structure globale (ex. : régions), tandis que les suivants capturent les distinctions locales.
• Accessibilité et géométrie : La distance euclidienne dans l'espace Laplacien mis à l'échelle approxime la Distance de Temps de Commutation (CTD), qui mesure le nombre d'étapes attendues pour voyager entre deux états et revenir via une marche aléatoire. Cela rend l'espace isométrique à la CTD, fournissant une géométrie bien adaptée à la planification.
• Découverte de sous-objectifs : La représentation partitionne naturellement l'environnement en régions bien connectées, ce qui la rend idéale pour le clustering spectral afin d'identifier des sous-objectifs aux goulots d'étranglement.

S'appuyant sur ces propriétés, les auteurs introduisent ALPS (Augmented Laplacian Planning with Subgoals), un algorithme de planification hiérarchique au moment de la décision. ALPS opère en deux phases :

1. Pré-entraînement :
   • Apprentissage Laplacien : Utilise l'Objectif Laplacien de l'Augmented Lagrangian (ALLO) pour apprendre les vecteurs propres et les valeurs propres à partir d'un jeu de données hors ligne, évitant le coût computationnel en $O(|S|^3)$ de la décomposition en valeurs propres exacte.
   • Modèle de propagation (Forward Model) : Apprend un modèle de propagation auto-régressif multi-étapes dans l'espace d'état original pour réduire l'accumulation d'erreurs.
   • Prior de comportement : Apprend une politique déterministe conditionnée par l'objectif ($\pi_{prior}$) pour biaiser l'échantillonnage des actions, accélérant ainsi la convergence.
   • Graphe de clusters : Effectue un clustering k-means dans l'espace Laplacien mis à l'échelle ($\psi$-space) pour définir des sous-objectifs (centres de clusters) et construit un graphe de transitions entre clusters.
2. Planification au moment de la décision :
   • Haut niveau : Étant donné un état de départ et un état cible, l'algorithme identifie leurs clusters respectifs et utilise l'algorithme de Dijkstra sur le graphe de clusters pour trouver un chemin de sous-objectifs.
   • Bas niveau : Pour chaque sous-objectif, un planificateur par la Méthode de l'Estimation de Cross-Entropie (CEM) génère une séquence d'actions. Le CEM est initialisé par le prior de comportement et optimisé en minimisant une fonction de coût basée sur la distance dans l'espace $\psi$ (approximant la CTD) et l'amplitude de l'action.

Contributions Clés

• Représentation Laplacienne pour la Planification : L'article démontre que la représentation Laplacienne capture efficacement les distances de l'espace d'état à plusieurs échelles de temps, décomposant naturellement les problèmes à long horizon en sous-objectifs et atténuant les erreurs de composition.
• Algorithme ALPS : Un nouvel algorithme de planification hiérarchique qui intègre l'identification de sous-objectifs basée sur le Laplacien avec l'optimisation de trajectoire par modèle (CEM) et un prior de comportement.
• Validation Empirique : Les auteurs évaluent ALPS sur l'OGBench (Offline Goal-Conditioned RL Benchmark), une suite de tâches précédemment dominées par des méthodes sans modèle (model-free).

Résultats
Les expériences ont été menées sur les environnements Maze2D—PointMass et un ensemble diversifié de tâches OGBench impliquant la locomotion (pointmaze, antmaze, humanoidmaze) et la manipulation (cube, scene) avec des observations basées sur l'état et sur les pixels.

• Performance : ALPS surpasse significativement les bases de référence couramment utilisées sans modèle (incluant GCBC, les variantes d'IQL, QRL, CRL et HIQL) sur la plupart des tâches OGBench, avec une signification statistique ($p < 0,001$).
• Robustesse : ALPS démontre une robustesse face à la taille du labyrinthe et à la qualité du jeu de données hors ligne. Il excelle particulièrement dans les jeux de données "explore" contenant des données de faible qualité mais à haute couverture, où la décomposition hiérarchique permet au planificateur de haut niveau de compenser un horizon de bas niveau limité.
• Comparaison avec PcLast : Sur les tâches Maze2D, ALPS (utilisant la représentation Laplacienne) surpasse PcLast (utilisant des états latents contrastifs), soulignant l'utilité de la métrique Laplacienne tant pour l'estimation de la distance que pour l'identification de sous-objectifs.
• Limites : L'article note qu'ALPS éprouve des difficultés avec les labyrinthes à "téléportation" où la symétrisation inhérente à l'objectif Laplacien fait que les entrées et sorties de téléporteurs sont regroupées, pouvant potentiellement mener l'agent dans des régions inaccessibles. De plus, les performances se dégradent sur les tâches de manipulation multi-objets (ex. : double-cube) en raison de la nature globale de la représentation Laplacienne qui ne parvient pas à capturer l'indépendance conditionnelle entre les états des objets.

Signification
L'article affirme que la représentation Laplacienne sert de bloc de construction utile pour une planification réussie avec des modèles appris, répondant au défi central des erreurs de composition dans les tâches à long horizon. En fournissant un espace latent qui capture intrinsèquement la structure temporelle et la connectivité, ALPS permet une planification hiérarchique efficace dans des espaces d'états continus et de haute dimension en utilisant uniquement des jeux de données pré-collectés hors ligne. Ce travail suggère que l'exploitation des propriétés spectrales de la dynamique de l'environnement peut surmonter la difficulté historique d'appliquer des méthodes basées sur des modèles à des problèmes complexes de RL conditionnés par l'objectif à long horizon.