Recherche d'arbres de politique mono-agents avec garanties

Nous présentons deux nouveaux algorithmes de recherche d'arbres qui utilisent une politique pour guider la recherche. Le premier algorithme est une énumération best-first qui utilise une fonction de coût qui nous permet de prouver une limite supérieure sur le nombre de nœuds à développer avant d'atteindre un état cible. Nous montrons que cet algorithme best-first est particulièrement bien adapté aux problèmes de type "aiguille dans la botte de foin". Le second algorithme est basé sur l'échantillonnage et nous prouvons une limite supérieure sur le nombre attendu de nœuds qu'il développe avant d'atteindre un ensemble d'états cibles. Nous montrons que cet algorithme est mieux adapté aux problèmes où de nombreux chemins mènent à un objectif. Nous validons ces algorithmes de recherche arborescente sur 1 000 niveaux de Sokoban générés par ordinateur, où la politique utilisée pour guider la recherche provient d'un réseau neuronal entraîné à l'aide de A3C. Nos résultats montrent que les algorithmes de recherche arborescente de politique que nous introduisons sont compétitifs avec un planificateur indépendant du domaine à la pointe de la technologie qui utilise la recherche heuristique.

Remerciements

Les auteurs souhaitent remercier Peter Sunehag, Andras Gyorgy, Rémi Munos, Joel Veness, Arthur Guez, Marc Lanctot, André Grahl Pereira et Michael Bowling pour les discussions utiles relatives à cette recherche. Le soutien financier de cette recherche a été fourni en partie par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG).