Résumé Technique : Information Induite par la Structure pour la Recherche d'Arbre de Rerooting de Levin

Définition du Problème

Les problèmes de planification discrète complexes dans des environnements déterministes à agent unique restent difficiles à résoudre à grande échelle. Bien que les méthodes de recherche en arbre guidées par politique comme la Recherche d'Arbre de Levin (LTS) et la Recherche Heuristique Guidée par Politique (PHS*) offrent des garanties théoriques sur l'effort de recherche, elles peinent souvent face à des domaines complexes sans guidage structurel supplémentaire.

Une stratégie courante pour y remédier est la décomposition des problèmes en sous-objectifs. Cependant, les méthodes existantes basées sur les sous-objectifs (par exemple, HIPS-$\epsilon$, SGPS) reposent sur la génération et la reconstruction explicites de sous-objectifs. Cela introduit une complexité de modélisation et un surcoût computationnel importants, car la performance de la recherche devient étroitement liée à la qualité de la génération des sous-objectifs. À mesure que la complexité du domaine augmente, le coût de la reconstruction et du raisonnement sur ces sous-objectifs explicites devient un goulot d'étranglement, entravant la scalabilité.

Cet article traite du défi consistant à exploiter la structure de l'espace d'états pour guider la recherche efficacement sans le coût computationnel de la génération explicite de sous-objectifs. Plus précisément, il étudie comment dériver des poids de « rerooting » (re-racinage) efficaces pour l'algorithme $\sqrt{\text{LTS}}$ — une méthode qui démarre implicitement une recherche LTS à chaque nœud de l'arbre — en utilisant des signaux structurels disponibles durant le processus de recherche.

Méthodologie

Les auteurs proposent un cadre qui utilise des Rerooters Induits par la Structure pour allouer l'effort de recherche dans $\sqrt{\text{LTS}}$. Au lieu de générer des sous-objectifs explicites, le cadre dérive des poids de rerooting à partir de la structure de l'arbre de recherche et des heuristiques apprises. L'article présente trois instanciations spécifiques :

1. Rerooting Global Induit par la Structure ($\sqrt{\text{LTS-L}}$)

Cette approche capture une structure globale grossière dans l'espace d'états en utilisant le clustering de Leiden.

• Mécanisme : À mesure que l'arbre de recherche se construit, un sous-graphe induit de l'espace d'états est construit. L'algorithme de Leiden est invoqué périodiquement (sel sur une progression géométrique) pour regrouper les états en fonction de leur connectivité.
• Assignation de poids : Les nœuds se voient assigner une « couleur » correspondant à leur cluster. Le poids de rerooting d'un nœud est inversement proportionnel à la taille de son cluster (approximée par le nombre de nœuds possédant cette couleur).
• Raisonnement : Cela encourage la recherche à concentrer l'effort sur les régions sous-explorées (petits clusters) et à détourner l'effort des régions sur-explorées (grands clusters), traitant ainsi les clusters comme des sous-tâches douces sans reconstruction explicite.

2. Rerooting Local Induit par la Structure ($\sqrt{\text{LTS-H}}$)

Cette approche tire parti des estimations locales du coût pour atteindre le but fournies par une fonction heuristique apprise.

• Mécanisme : Le poids de rerooting est défini comme une fonction exponentielle de la valeur heuristique normalisée : $w_t = \exp(-\alpha \frac{h(n_t)}{h(n_1)})$.
• Raisonnement : Cela crée une hiérarchisation « douce » où les nœuds estimés être plus proches du but (valeurs heuristiques plus faibles) reçoivent des poids plus élevés. La normalisation par l'heuristique de la racine assure l'invariance par rapport à l'échelle absolue de l'heuristique, tandis que la carte exponentielle garantit des poids strictement positifs et lisses permettant d'utiliser des heuristiques imparfaites.

3. Rerooting Hybride Induit par la Structure ($\sqrt{\text{LTS-LH}}$)

Cette méthode combine les signaux globaux et locaux de manière additive.

• Mécanisme : Le poids final est une combinaison linéaire du poids basé sur le clustering et du poids basé sur l'heuristique : $w_t = u_a w_{t, \text{cluster}} + u_b w_{t, \text{heuristic}}$.
• Raisonnement : Le rerooter global fournit une stabilité contre le bruit ou le mauvais calibrage de l'heuristique en identifiant les goulots d'étranglement structurels, tandis que le rerooter local affine les priorités au sein de ces régions en fonction des progrès estimés. Cette approche « du grossier au fin » vise à équilibrer la robustesse et l'adaptativité dirigée vers le but.

Garanties Théoriques

L'article étend les limites théoriques sur le nombre d'expansions de nœuds requises par $\sqrt{\text{LTS}}$. Il fournit une nouvelle garantie pour les rerooters additifs, montrant que la complexité de la recherche est limitée par l'effet synergique de plusieurs rerooters. Plus précisément, si les poids relatifs des composants sont équilibrés, la limite dépend du minimum des limites individuelles, permettant à la recherche de s'appuyer sur le signal le plus informatif dans n'importe quelle région de l'arbre.

Principales Contributions

1. Apprentissage Automatisé des Rerooters : L'article présente des méthodes automatisées pour dériver des poids de rerooting directement de la structure de l'arbre de recherche (via le clustering) et des heuristiques apprises, éliminant le besoin de réseaux de génération et de reconstruction de sous-objectifs séparés et coûteux en calcul.
2. Trois Designs de Rerooters : Il introduit et évalue trois designs distincts : un rerooter global basé sur le clustering, un rerooter local basé sur l'heuristique, et un rerooter hybride additif.
3. Extension Théorique : Il fournit une nouvelle limite théorique pour $\sqrt{\text{LTS}}$ utilisant des rerooters additifs, démontrant comment plusieurs signaux structurels peuvent être combinés pour améliorer l'efficacité de la recherche.
4. Démonstration de Scalabilité : Le travail démontre que le rerooting peut passer à l'échelle dans des environnements complexes là où les méthodes explicites basées sur les sous-objectifs échouent, atteignant une efficacité d'entraînement en ligne de pointe.

Résultats Expérimentaux

Les auteurs ont évalué leurs méthodes sur quatre domaines : BoulderDash, CraftWorld, Sokoban, et une version grille du Problème du Voyageur de Commerce (TSP). Ils ont comparé leurs méthodes à LTS, PHS*, aux variantes basées sur les sous-objectifs (LTS($\pi_{SG}$), PHS*($\pi_{SG}$)) et à l'algorithme A* pondéré.

• Efficacité d'Entraînement : Dans tous les domaines, le rerooter hybride ($\sqrt{\text{LTS-LH}}$) et le rerooter basé sur l'heuristique ($\sqrt{\text{LTS-H}}$) ont considérablement amélioré l'efficacité de l'échantillonnage de l'entraînement en ligne par rapport aux bases sans rerooting et aux méthodes antérieures basées sur les sous-objectifs. Dans des contextes complexes (ex: BoulderDash avec une haute densité de terre), les méthodes basées sur les sous-objectifs (PHS*($\pi_{SG}$)) n'ont pas pu passer à l'échelle ou ont expiré, tandis que les méthodes de rerooting ont terminé l'entraînement avec succès.
• Performance de Test : Malgré un entraînement plus rapide, les méthodes de rerooting ont atteint des performances de test comparables ou supérieures (mesurées par les problèmes résolus, les expansions vers la solution, et la longueur de la solution) aux approches précédentes.
• Robustesse : L'approche hybride s'est révélée la plus robuste, particulièrement dans les domaines avec des structures de blocage (Sokoban, CraftWorld) où le guidage purement heuristique pouvait être instable. Le composant de clustering global a aidé à stabiliser la recherche lorsque les heuristiques étaient peu fiables.
• Échelle de Complexité : Dans l'expérience de mise à l'échelle de la complexité de BoulderDash, les rerooters hybride et heuristique ont maintenu leurs performances à mesure que l'espace d'états augmentait, tandis que les méthodes basées sur les sous-objectifs ont décliné significativement en raison de la difficulté de reconstruire des sous-objectifs pertinents dans des environnements visuellement denses mais non pertinents pour la tâche.

Signification et Revendications

L'article affirme que le rerooting est une abstraction scalable et flexible pour exploiter la structure dans la recherche d'arbre de politique. Sa principale signification réside dans la démonstration que :

• Sous-tâches Implicites : On peut obtenir les avantages de la décomposition en sous-tâches (amélioration de l'exploration et du guidage de la recherche) sans le surcoût computationnel de la génération et de la reconstruction explicites de sous-objectifs.
• Signaux Légers : Même des signaux structurels légers (comme les valeurs heuristiques locales) peuvent suffire à guider un rerooting efficace, surpassant souvent les approches de clustering global plus complexes lorsqu'elles sont utilisées seules.
• Synergie : Combiner des signaux structurels complémentaires (connectivité globale et coût pour atteindre le but local) crée un mécanisme robuste qui s'adapte aux variations de complexité du domaine et de qualité des heuristiques.

Les auteurs concluent que $\sqrt{\text{LTS}}$, avec des transformations structurelles simples des heuristiques classiques, offre une voie hautement efficace pour une recherche d'arbre de politique scalable, évitant les goulots d'étranglement associés à la modélisation explicite des sous-objectifs dans les domaines complexes.