Résumé technique : Découverte hiérarchique non supervisée des compétences (HiSD)

Énoncé du problème

L'article aborde le défi de la segmentation non supervisée des compétences et de la découverte de structures hiérarchiques dans l'apprentissage par renforcement (RL). Alors que la planification humaine opère de manière hiérarchique — en raisonnant en termes d'objectifs et de sous-tâches plutôt que d'actions primitives — les agents RL actuels dans des environnements de haute dimension (par exemple, Minecraft) peinent à apprendre efficacement de telles structures.

Les approches existantes de découverte de compétences reposent généralement sur une supervision forte, telle que :

• Étiquettes d'actions : Nécessitant l'accès aux actions spécifiques exécutées par un agent.
• Signaux de récompense : S'appuyant sur des structures de récompenses denses ou clairsemées pour définir les frontières des compétences.
• Annotations manuelles : Exigeant une expertise humaine pour définir les décompositions de tâches (par exemple, les réseaux de tâches hiérarchiques).

Ces dépendances limitent l'évolutivité, en particulier lorsqu'il s'agit de données vidéo abondantes non étiquetées où les actions, les récompenses ou les segmentations de vérité terrain sont indisponibles. De plus, de nombreuses méthodes existantes produisent des segmentations « plates » plutôt que des hiérarchies profondes et compositionnelles nécessaires aux tâches complexes à long horizon.

Méthodologie : Découverte hiérarchique des compétences (HiSD)

Les auteurs proposent HiSD, un cadre entièrement non supervisé qui extrait des hiérarchies de compétences réutilisables et multi-niveaux à partir de données purement observationnelles (séquences de pixels bruts ou de caractéristiques). La méthode découple la découverte de structure de l'exécution de la politique et opère en deux étapes distinctes :

1. Identification non supervisée des compétences (Segmentation)

La première étape convertit les trajectoires d'observations continues en séquences discrètes de compétences latentes.

• Entrée : Trajectoires d'observations non étiquetées $T = (X_1, \dots, X_n)$, où $X$ représente des vecteurs de caractéristiques (par exemple, des pixels réduits par PCA ou des embeddings CLIP).
• Algorithme : Le cadre utilise la Segmentation d'actions temporelles (TAS) via l'approche ASOT (Transport Optimal Déséquilibré).
• Mécanisme : ASOT formule la segmentation comme un problème de transport optimal. Il minimise un objectif régularisé qui équilibre :
  • Coût de correspondance visuelle : Dissimilarité entre les caractéristiques d'observation et les prototypes de compétences latentes.
  • Régularité temporelle : Imposée via un composant Gromov-Wasserstein (GW) qui pénalise les changements rapides d'étiquettes dans un rayon temporel, assurant une lisibilité locale.
  • Pénalité marginale : Un terme de divergence KL qui permet des distributions de compétences déséquilibrées (gérant les cas où certaines compétences sont rares).
• Sortie : Une séquence d'indices de compétences discrètes $z_{1:n}$ représentant des unités comportementales atomiques.

2. Abstraction symbolique et induction de grammaire (Découverte de structure)

La deuxième étape induit une structure hiérarchique sur les séquences de compétences discrètes.

• Construction du corpus : Les trames contiguës partageant la même étiquette de compétence sont réduites en symboles atomiques uniques. Toutes les séquences d'épisodes sont concaténées en un corpus unifié, séparées par un jeton de frontière unique $\phi$.
• Algorithme : Un algorithme Sequitur modifié est appliqué au corpus. Sequitur est un algorithme d'induction de grammaire en temps linéaire qui infère une structure hiérarchique en identifiant des motifs récurrents.
• Contraintes :
  • Unicité des digrammes : Aucune paire de symboles adjacents n'apparaît plus d'une fois ; les répétitions sont remplacées par de nouvelles règles non terminales.
  • Utilité des règles : Les règles doivent être utilisées au moins deux fois pour être conservées.
  • Protection des frontières : Le jeton de frontière $\phi$ est interdit dans les règles de production, garantissant que les sous-routines apprises capturent des comportements intra-épisode plutôt que de fusionner la fin d'un épisode avec le début d'un autre.
• Sortie : Une grammaire hors contexte (CFG) $G$ où les nœuds terminaux sont des compétences atomiques et les nœuds internes représentent des sous-routines découvertes (par exemple, « Collecter du bois » + « Fabriquer un établi »).

Contributions clés

1. Cadre non supervisé : Introduction de HiSD, qui intègre la segmentation d'actions temporelles avec l'induction de grammaire pour découvrir des hiérarchies multi-niveaux sans étiquettes d'actions, récompenses ou annotations manuelles.
2. Pipeline basé uniquement sur l'observation : Une méthode adaptée aux démonstrations non étiquetées, découplant la découverte de structure de l'exécution de la politique et permettant l'évolutivité vers de grandes données vidéo.
3. Validation empirique : Démonstration d'une qualité de segmentation supérieure et d'une profondeur d'abstraction accrue par rapport aux bases de référence (CompILE, OMPN) dans des domaines complexes.
4. Utilité en aval : Une preuve de concept montrant que les hiérarchies découvertes accélèrent et stabilisent l'apprentissage dans des tâches RL en aval, même lorsqu'un petit nombre de démonstrations étiquetées par action est disponible pour l'ancrage de la politique.

Résultats expérimentaux

Les auteurs ont évalué HiSD sur deux domaines : Craftax (un environnement 2D déterministe et entièrement observable) et Minecraft (un environnement stochastique, partiellement observable et de haute dimension).

Bases de référence

Des comparaisons ont été effectuées avec CompILE et OMPN, auxquels ont été fournis des ordonnancements de sous-tâches de vérité terrain et des étiquettes d'actions pour garantir qu'ils opéraient dans leurs conditions les plus favorables. HiSD ne nécessitait que le nombre maximum de compétences $K$ comme a priori.

Performance de segmentation des compétences

• Métriques : Moyenne sur les trames (MoF), Score F1 et intersection moyenne sur l'union (mIoU).
• Résultats : HiSD a systématiquement surpassé les bases de référence, en particulier dans les tâches présentant une complexité, une stochasticité et des horizons plus longs.
  • Dans Craftax, HiSD a obtenu des scores mIoU plus élevés, regroupant correctement des comportements perceptuellement distincts mais sémantiquement équivalents (par exemple, s'approcher du bois sous différents angles) en clusters de compétences uniques.
  • Dans Minecraft, malgré l'aliasing perceptuel (par exemple, marcher vers du bois ou de la pierre semblant identique en vue à la première personne), l'a priori de cohérence temporelle de HiSD a permis une segmentation cohérente là où les bases de référence échouaient.

Qualité de la hiérarchie

• Métriques : Arbres uniques (cohérence), profondeur moyenne, taille de l'arbre et facteurs de branchement.
• Résultats :
  • HiSD a produit des décompositions plus cohérentes à travers les épisodes (moins d'arbres uniques) par rapport à OMPN, qui générait souvent une hiérarchie unique pour chaque épisode.
  • Les hiérarchies HiSD étaient généralement plus petites et plus interprétables, avec des facteurs de branchement plus faibles, indiquant une meilleure identification des sous-routines intermédiaires.
  • Dans la tâche bruyante « All » de Minecraft, HiSD a eu du mal à trouver une structure unique cohérente en raison de la stochasticité environnementale, mais a nettement mieux performé dans la tâche « Mapped » (groupée sémantiquement).

Déploiement RL en aval

Les auteurs ont démontré l'utilité des hiérarchies découvertes en entraînant des agents de haut niveau utilisant l'Optimisation de politique proximale masquable (PPO) avec les compétences découvertes en tant qu'options.

• Efficacité : Les agents utilisant les hiérarchies HiSD ont atteint des récompenses quasi optimales significativement plus vite (par exemple, en ~30k étapes dans Craftax) par rapport au PPO d'actions primitives (qui a échoué) et aux agents de compétences plates.
• Efficacité des données : Les agents hiérarchiques ont atteint des performances élevées avec aussi peu que 250 démonstrations étiquetées par action pour l'ancrage de la politique, malgré la découverte initiale de compétences étant entièrement non supervisée.

Importance et revendications

L'article affirme que HiSD offre une voie évolutive vers des agents généralistes capables d'apprendre à partir de données abondantes et non étiquetées. En reliant la segmentation d'actions temporelles de pointe à la compression basée sur la grammaire, la méthode induit des hiérarchies multi-niveaux directement à partir de trajectoires observationnelles brutes.

Les auteurs soulignent que :

• La structure peut être récupérée purement à partir de la cohérence temporelle et de la similarité visuelle, sans avoir besoin de supervision par action.
• Les hiérarchies résultantes sont sémantiquement significatives et réutilisables, fournissant les biais inductifs nécessaires à l'attribution de crédit temporel dans le RL en aval.
• L'approche abaisse la barrière à l'entraînement d'agents capables en éliminant le besoin de supervision dense et d'étiquettes d'actions, facilitant une meilleure interaction humain-IA grâce à des structures transparentes et interprétables.

Le travail est présenté comme une preuve de concept, reconnaissant des limitations telles que la nature déterministe de l'induction de grammaire (qui lutte contre le bruit élevé) et la dépendance à un a priori fixe pour le nombre de compétences $K$. Cependant, les résultats suggèrent que la découverte de structure non supervisée est une stratégie viable et efficace pour des environnements complexes d'apprentissage par renforcement de haute dimension.