💻 computer science

Neurosymbolic Reasoning with Incremental Knowledge for Sample Efficient Hierarchical Reinforcement Learning

Cet article propose un cadre d'apprentissage par renforcement hiérarchique neurosymbolique qui intègre la Connaissance Incrémentale (InK) et la Recherche par Arbre de Monde de Croyance pour permettre une planification symbolique actualisable et un apprentissage neuronal à récompense façonnée, améliorant ainsi considérablement l'efficacité d'échantillonnage dans les tâches de navigation à horizon long et à récompenses éparses.

Auteurs originaux : Subrat Prasad Panda, Blaise Genest, Arvind Easwaran

Publié 2026-08-05

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Subrat Prasad Panda, Blaise Genest, Arvind Easwaran

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous enseigniez à un robot comment naviguer dans un labyrinthe géant et changeant. Dans le monde de l'intelligence artificielle, c'est un défi classique connu sous le nom d'apprentissage par renforcement (Reinforcement Learning ou RL). Voyez cela comme l'entraînement d'un chien : vous lui donnez une friandise (une récompère) lorsqu'il fait quelque mieux, et il apprend à répéter cette action. Mais attention : si le labyrinthe est immense et que les friandises sont cachées très loin, le chien pourrait errer pendant un million d'années avant de trouver accidentellement le chemin. C'est le problème de la « l'efficacité d'échantillonnage » (sample efficiency) : combien d'essais l'IA a-t-elle besoin pour apprendre ?

Pour corriger cela, les scientifiques utilisent souvent l'« Apprentissage par Renforcement Hiérarchique » (Hierarchical Reinless Learning ou HRL). Au lieu qu'un robot essaie de comprendre chaque petit pas à la fois, vous lui donnez un patron et un ouvrier. Le patron (le planificateur de haut niveau) décide des grands objectifs, comme « aller à la cuisine », tandis que l'ouvrier (le contrôleur de bas niveau) détermine les minuscules mouvements musculaires pour y parvenir. Généralement, le patron est une carte rigide, préprogrammée, qui ne change jamais. Mais que se passe-t-il si le labyrinthe possède des murs secrets qui n'apparaissent que lorsqu'on les heurte ? Un patron rigide continuerait d'essayer de traverser un mur qui vient de surgir, perdant ainsi son temps. Cet article explore une méthode plus intelligente : un robot qui apprend la carte pendant qu'il se déplace, mettant à jour la carte de son patron en temps réel en fonction de ce que l'ouvrier découvre.

La grande idée de l'article : Un robot qui apprend au fur et à mesure

Les auteurs, Subrat Prasad Panda et son équipe, proposent un nouveau système appelé Neurosymbolic HRL with Incremental Knowledge (InK). Décomposons le nom : « Neurosymbolique » signifie qu'ils mélangent deux types de cerveaux. La partie « neurale » est un cerveau flexible et apprenant (comme un réseau de neurones profonds) qui gère les mouvements physiques. La partie « symbolique » est un cerveau logique, basé sur des règles, qui gère la planification, comme un joueur d'échecs qui réfléchit à l'avance.

Dans les systèmes traditionnels, le cerveau logique construit une carte parfaite du monde avant que le robot ne commence à bouger. C'est comme essayer de mémoriser toute la carte du métro de Londres avant de quitter sa maison. Si une ligne de train est fermée ou qu'une nouvelle station ouvre, votre carte est inutile jusqu'à ce que vous recommenciez tout. Les auteurs soutiennent que cela est inefficace. Au lieu de cela, leur robot utilise la Connaissance Incrémentale (InK). Il part d'une page blanche ou d'une estimation approximative. À mesure que le robot « ouvrier » tente de se déplacer et heurte un mur, il dit au « patron » : « Hé, il y a un mur ici ! ». Le patron met immédiatement à jour sa carte et recalcule le meilleur chemin. C'est comme avoir un GPS qui met à jour votre itinéraire dès que vous tombez sur un embouteillage, plutôt que de rester bloqué en attendant qu'une nouvelle carte soit imprimée.

Le « Monde de Croyance » et la Recherche d'Arbre

L'article introduit une astuce ingénieuse pour gérer l'incertitude. Imaginez que vous soyez dans une pièce sombre et que vous sachiez qu'il y a exactement un mur quelque part, mais vous ne savez pas où. Vous pourriez deviner qu'il est à gauche, ou à droite, ou au milieu. Le robot ne choisit pas seulement une supposition ; il garde un « ensemble de croyances » (belief set) — une liste mentale de tous les mondes possibles où le mur pourrait se trouver.

Pour prendre des décisions dans ce brouillard d'incertitude, les auteurs ont développé un algorithme appelé Belief World Tree Search (BWTS). Imaginez un arbre géant qui pousse dans votre esprit. Le tronc est votre emplacement actuel. Chaque fois que vous devez choisir une direction, l'arbre se ramifie. Mais voici la particularité : au lieu de simplement deviner un chemin, le BWTS simule des milliers de futurs possibles simultanément. Il demande : « Si le mur est ici, quel est le meilleur mouvement ? Si le mur est là, quel est le meilleur mouvement ? ». Il choisit ensuite le mouvement qui fonctionne le mieux en moyenne à travers toutes ces possibilités.

L'article s'oppose explicitement aux méthodes de devinettes « aléatoires » classiques (comme certains anciens algorithmes qui lancent simplement des dés pour voir ce qui arrive). Les auteurs ont constaté que les devinettes aléatoires dans un labyrinthe font souvent tourner le robot en rond, gaspillant du temps. Au lieu de cela, le BWTS utilise des « déploiements stratégiques » (strategic rollouts) — il simule des chemins en utilisant des stratégies intelligentes et pré-planifiées (comme « toujours balayer vers la gauche si vous heurtez un mur ») pour trouver rapidement la meilleure route sans se perdre.

Ce qu'ils ont trouvé : Vitesse et Intelligence

L'équipe a testé leur idée dans des simulations informatiques de labyrinthes, allant de grilles simples à des environnements 3D complexes avec un robot « fourmi » possédant de nombreuses articulations.

Gains de vitesse massifs : Comparée à l'ancienne méthode de construction de la carte d'abord (appelée RGL dans l'article), la nouvelle méthode InK est incroyablement plus rapide pour apprendre. Dans un labyrinthe de type « Four Rooms », l'ancienne méthode avait besoin d'environ 2 080 étapes pour atteindre le but pour la première fois en partant de zéro. La nouvelle méthode InK n'a eu besoin que de 64,9 étapes. C'est environ 30 à 100 fois moins d'essais.
Économies de temps : La différence de temps est encore plus frappante. L'ancienne méthode a pris plus de 96 secondes juste pour comprendre le premier chemin. La nouvelle méthode l'a fait en 0,02 seconde.
Le pouvoir des connaissances préalables : Lorsque le robot recevait un indice sur le monde (comme « il y a un mur quelque part, mais je ne sais pas où »), l'algorithme BWTS excellait. Dans ces cas, il a utilisé la moitié du nombre d'échantillons (essais) par rapport au planificateur standard, bien qu'il ait nécessité un peu plus de temps de calcul pour effectuer les mathématiques complexes.
Environnements complexes : Le système a fonctionné même sur l'« Ant-Maze U-Room », un défi de haute dimension avec 29 dimensions de mouvement. L'ancienne méthode avait besoin d'environ 10 000 étapes pour construire sa carte, tandis que la nouvelle méthode a atteint le but en environ 1 507 étapes (ou même 1 134 étapes avec le planificateur BWTS).

Ce qu'ils n'ont pas trouvé (et ce qu'ils ont rejeté)

L'article précise avec soin ce qui ne fonctionne pas bien dans ce configuration spécifique. Ils ont testé un algorithme populaire appelé BAMCP, qui tente de gérer l'incertitude en supposant que chaque partie du labyrinthe est indépendante (comme supposer que le mur dans la cuisine n'a rien à voir avec le mur dans la chambre). Les auteurs ont constaté que cette approche échouait lamentablement dans leurs tests de labyrinthe. Comme les murs étaient structurellement liés (s'il y a un mur ici, il ne peut pas y en avoir un là), l'hypothèse d'indépendance a conduit à de mauvaises décisions et à une perte de temps. BAMCP a pris en moyenne 28 à 40 étapes là où la nouvelle méthode a pris 21 à 23, et elle tournait beaucoup plus lentement.

Les auteurs notent également que, bien que leur méthode soit plus rapide, l'algorithme BWTS est lourd en termes de calcul. Si vous n'avez aucune connaissance préalable sur le monde, le planificateur « D* » plus simple (un planificateur incrémentiel standard) est en fait plus rapide et suffisant. Vous n'avez besoin de la recherche d'arbre complexe BWTS que si vous avez des indices structurels spécifiques sur le monde à exploiter.

En résumé

Cet article suggère qu'en mélangeant un cerveau apprenant flexible avec un planificateur logique qui met à jour sa carte en temps réel, les robots peuvent apprendre à naviguer dans des mondes complexes et inconnus beaucoup plus rapidement qu'auparavant. Ils n'ont pas seulement simulé un robot ; ils ont montré que dans ces scénarios de labyrinthe spécifiques, la nouvelle méthode surpasse systématiquement l'ancienne approche consistant à « tout apprendre d'abord », économisant des quantités massives de temps et d'efforts. C'est un pas vers des robots capables d'explorer une nouvelle maison, d'apprendre où se trouve le mobilier et de trouver la cuisine sans avoir besoin d'un manuel pour chaque pièce.

Résumé Technique : Raisonnement Neurosymbolique avec Connaissance Incrémentale pour l'Apprentissage par Renforcement Hiérarchique à Haute Efficacité d'Échantillonnage

1. Énoncé du Problème

Les agents d'Apprentissage par Renforcement Profond (DRL) peinent dans les environnements caractérisés par des récompenses éparses et un raisonnement à long horizon, souffrant souvent d'une complexité d'échantillonnage prohibitive. Bien que l'Apprentissage par Renforcement Hiérarchique (HRL) atténue ce problème en décomposant les tâches à travers différents niveaux d'abstraction, les approches standard reposent généralement sur des paradigmes de connaissance non incrémentale (non-InK). Dans ces méthodes, telles que SoRB et RGL, le planificateur symbolique de haut niveau nécessite la construction préalable d'un modèle de monde abstrait complet et statique par une exploration exhaustive avant que tout comportement dirigé vers un but ne puisse commencer. Cela crée une inefficacité fondamentale : l'agent doit explorer l'intégralité de l'environnement, quel que soit le but spécifique.

De plus, dans le HRL neurosymbolique, un fossé sémantique existe souvent entre le planificateur symbolique de haut niveau et le contrôleur neural de bas niveau. Le planificateur de haut niveau suppose que certaines actions sont réalisables, mais la politique neurale de bas niveau (souvent entraînée indépendamment ou dans un environnement différent) peut échouer à les exécuter en raison de contraintes dynamiques, de stochasticité ou d'obstacles non modélisés. Les approches neurosymboliques existantes manquent de mécanismes pour mettre à jour le modèle de monde de haut niveau basé sur le feedback d'exécution de bas niveau. Inversement, les approches classiques de connaissance incrémentale (InK) en robotique (ex. : SLAM actif, D*) mettent à jour les modèles de monde pendant l'exécution, mais supposent généralement des composants symboliques aux deux niveaux, échouant ainsi à traiter la dynamique dépendante de la politique des contrôleurs neuraux de bas niveau.

Enfin, lorsqu'un savoir a priori structurel existe (ex. : « il y a exactement un mur à un emplacement inconnu »), les algorithmes de planification actuels comme D* ou les solveurs de BAMCP (Bayesian Adaptive MDP) sont sous-optimaux. D* replanifie sur la base des observations actuelles mais ignore l'ensemble des mondes possibles (ensemble de croyance) pour optimiser la performance en moyenne. BAMCP suppose l'indépendance entre les transitions état-action, ce qui échoue à capturer les contraintes structurelles où l'emplacement d'un obstacle contraint les possibilités des autres.

2. Méthodologie

Les auteurs proposent le HRL Neurosymbolique avec Connaissance Incrémentale (InK), un cadre qui intègre la planification symbolique au contrôle neural tout en mettant à jour continuellement le modèle de monde basé sur les traces d'exécution.

2.1 HRL Neurosymbolique avec InK

Le cadre emploie une hiérarchie à deux niveaux :

Haut Niveau (Symbolique) : Maintient un modèle de monde abstrait mis à jour ( $M$ ) représentant l'environnement comme un ensemble d'états et d'actions symboliques. Il effectue la planification à l'aide d'un planificateur incrémental (ex. : D*) pour générer des sous-buts. Crucialement, ce modèle est mis à jour en temps réel sur la base du feedback de l'exécution de bas niveau.
Bas Niveau (Neural) : Une politique neurale conditionnée par un but ( $\pi_l$ ) exécute le contrôle de mouvement continu pour atteindre les sous-buts fournis par le haut niveau. Elle agit comme un capteur ; ses succès et échecs fournissent les traces d'exécution ( $\rho$ ) nécessaires pour mettre à jour le modèle de haut niveau.
Coordination : Le planificateur de haut niveau dirige l'agent de bas niveau vers un sous-but. Si l'agent de bas niveau échoue (ex. : heurte un mur inattendu), le moniteur le détecte, et le modèle de haut niveau est mis à jour pour refléter la nouvelle contrainte. Le planificateur replanifie ensuite. Cela élimine le besoin d'une exploration exhaustive préalable, permettant un comportement dirigé vers un but dès le premier épisode.

2.2 Recherche en Arbre de Croyance de Monde (BWTS - Belief World Tree Search)

Pour remédier aux limites des planificateurs incrémentaux standards (comme D*) qui n'exploitent pas le savoir a priori structurel sur un ensemble de mondes possibles ( $W_0$ ), les auteurs introduisent la Recherche en Arbre de Croyance de Monde (BWTS).

Formulation du Problème : L'agent opère dans un monde vrai $W_{true} \in W_0$ , où $W_0$ est un ensemble fini de mondes possibles encodant des priors structurels (ex. : « un mur existe, emplacement inconnu »). L'objectif est de trouver une politique $\pi$ qui minimise le coût moyen sur tous les mondes de $W_0$ .
Structure de l'Arbre : BWTS construit un arbre de recherche avec deux types de nœuds :
- Nœuds de Décision : Représentent le choix d'action de l'agent.
- Nœuds de Chance : Représentent le résultat d'une action (ex. : si un chemin est bloqué par un mur ou non), divisant l'ensemble de croyance $W$ en sous-ensembles ( $W^-$ où le mur existe, $W^+$ où il n'existe pas).
Rollouts Stratégiques : Contrairement à la recherche arborescente de Monte Carlo (MCTS) standard qui utilise des rollouts aléatoires, BWTS emploie des rollouts stratégiques. Il évalue des stratégies fixes et déterministes (ex. : « balayer à gauche », « balayer à droite », « aller vers le but ») à travers tous les mondes de l'ensemble de croyance actuel pour estimer la valeur des nœuds. Cela réduit la variance et évite les boucles communes dans les rollouts stochastiques.
Sélection et Expansion : L'algorithme utilise une formule de type UCB (Upper Confidence Bound) pour équilibrer l'exploration et l'exploitation. Il donne la priorité à l'expansion des branches possédant de plus grands ensembles de croyance, car celles-ci nécessitent plus d'exploration pour lever l'incertitude.
Convergence : Théoriquement, BWTS converge vers la politique optimale pour le problème InK à mesure que le nombre d'itérations augmente, à condition que l'arbre soit entièrement déployé.

3. Contributions Clés

HRL Neurosymbolique avec InK : La proposition d'un cadre hiérarchique où un planificateur de haut niveau symbolique maintient un modèle de monde mis à jour, guidé par un contrôleur neural de bas niveau. Cette approche comble le fossé sémantique en utilisant le feedback d'exécution de bas niveau pour affiner les abstractions de haut niveau, permettant un apprentissage efficace en termes d'échantillonnage sans exploration préalable exhaustive.
Recherche en Arbre de Croyance de Monde (BWTS) : Le développement d'un algorithme de planification qui optimise la performance moyenne sur un ensemble de mondes possibles avec des dépendances structurelles. BWTS adapte MCTS pour gérer des dynamiques entièrement observables mais inconnues avec des priors structurels, dépassant les hypothèses d'indépendance de BAMCP et l'absence d'utilisation de l'ensemble de croyance de D*.
Validation Empirique : Démonstration que l'InK HRL surpasse significativement les bases non-InK (spécifiquement RGL) en efficacité d'échantillonnage à travers diverses tâches de navigation, incluant le contrôle continu de haute dimension (Ant-Maze).

4. Résultats Expérimentaux

Les auteurs ont évalué leur approche sur des tâches de navigation utilisant des environnements Point-Maze (Four Rooms, Medium Maze, Hard Maze) et un Ant-Maze U-Room de haute dimension.

InK vs. Non-InK (RGL) :
- Efficacité d'Échantillonnage : InK a nécessité de 30 à 100 fois moins d'échantillons que RGL pour atteindre un but en partant de zéro (sans connaissance préalable). Par exemple, dans le Hard Maze, InK a atteint le but en ~209 étapes contre ~17 456 étapes pour RGL.
- Efficacité d'Entraînement : Même après que RGL a terminé sa phase d'entraînement intensive (100k+ échantillons), InK (après avoir atteint seulement 75 buts pour construire sa base de connaissances) est resté plus efficace, nécessitant 18 % d'échantillons en moins et 20 fois moins de temps par but.
- Contrôle de Haute Dimension : Dans l'Ant-Maze (29 dimensions), InK a atteint le but en ~1 500 étapes (avec D*) ou ~1 134 étapes (avec BWTS), tandis que la base non-InK nécessitait ~10 000 étapes pour construire un modèle abstrait complet.
Comparaison des Planificateurs Symboliques (D vs. BWTS vs. BAMCP) :*
- BWTS vs. D :* Dans des mondes de grille synthétiques avec des priors structurels (ex. : un mur horizontal unique), BWTS a obtenu un coût attendu plus faible (ex. : amélioration de 15,7 % par rapport à D*) en exploitant l'ensemble de croyance pour éviter les retours en arrière coûteux. Cependant, dans des scénarios complexes sans avantages structurels clairs (ex. : types de murs mixtes), la surcharge de temps de calcul de BWTS était significative pour des gains marginaux.
- BWTS vs. BAMCP : BAMCP a mal performé (souvent >28 étapes contre ~24 étapes pour D*) et s'est montré instable en raison de sa dépendance aux rollouts stochastiques et de son incapacité à modéliser les dépendances structurelles (ex. : « si mur en A, pas de mur en B »). Les rollouts stratégiques de BWTS et la modélisation explicite des contraintes structurelles ont produit des performances supérieures.
- Connaissance A Priori : Lorsque le savoir a priori était disponible (ex. : un ensemble de trois types de labyrinthes connus), l'approche InK-BWTS a réduit de moitié le nombre d'échantillons par rapport à InK-D*, bien qu'elle ait engendré un temps de calcul plus élevé durant la phase de planification.

5. Signification et Revendications

L'article affirme que le HRL Neurosymbolique avec InK offre une approche pratique pour un apprentissage efficace en termes d'échantillonnage dans des environnements complexes à récompenses éparses. En combinant le raisonnement structurel des planificateurs symboliques à l'adaptabilité des contrôleurs neuraux, le cadre permet aux agents d'agir avec une connaissance partielle et d'affiner leurs décisions à mesure qu'ils acquièrent de nouvelles informations, imitant ainsi le raisonnement humain.

Les auteurs soulignent que :

Efficacité d'Échantillonnage : L'approche produit des gains dépassant 100 000 étapes d'environnement par rapport aux méthodes non-InK de pointe dans les environnements Point Maze.
Optimalité sous Incertitude : BWTS offre une méthode pour planifier de manière optimale en moyenne sur des mondes de croyance, comblant un vide laissé à la fois par les replanificateurs incrémentaux (qui ignorent les priors) et les planificateurs bayésiens (qui supposent l'indépendance).
Polyvalence : Le cadre est applicable aux problèmes de contrôle continu de basse et haute dimension, à condition qu'une politique de bas niveau conditionnée par un but puisse être pré-entraînée ou apprise.

Le travail conclut que bien que BWTS introduise une surcharge de calcul, le compromis est justifié lorsque le savoir a priori structurel est disponible, et que le cadre InK lui-même offre des gains d'efficacité substantiels même sans tels priors par rapport au HRL traditionnel. Des travaux futurs sont suggérés pour étendre l'InK aux tâches de manipulation et pour unifier les priors structurels et probabilistes dans un algorithme unique.