Recherche heuristique guidée par des politiques avec garanties

Résumé

L'utilisation d'une politique et d'une fonction heuristique pour guider la recherche peut être très efficace dans les problèmes adverses, comme l'ont démontré AlphaGo et ses successeurs, qui sont basés sur l'algorithme de recherche PUCT. Bien que l'algorithme PUCT puisse également être utilisé pour résoudre des problèmes déterministes à agent unique, il manque de garanties quant à son effort de recherche et peut être inefficace sur le plan informatique dans la pratique. La combinaison de l'algorithme A* avec une fonction heuristique apprise a tendance à mieux fonctionner dans ces domaines, mais A* et ses variantes n'utilisent pas de politique. De plus, le but de l'utilisation de A* est de trouver des solutions de coût minimum, alors que nous cherchons plutôt à minimiser la perte de recherche (par exemple, le nombre de pas de recherche). LevinTS est guidé par une politique et fournit des garanties sur le nombre d'étapes de recherche qui sont liées à la qualité de la politique, mais il n'utilise pas de fonction heuristique. Dans ce travail, nous présentons Policy-guided Heuristic Search (PHS), un nouvel algorithme de recherche qui utilise à la fois une fonction heuristique et une politique et qui offre des garanties théoriques sur la perte de recherche liée à la fois à la qualité de l'heuristique et de la politique. Nous montrons empiriquement sur le puzzle des tuiles coulissantes, Sokoban, et un puzzle du jeu commercial 'The Witness' que PHS permet l'apprentissage rapide d'une politique et d'une fonction heuristique et se compare favorablement avec A*, A* pondéré, Greedy Best-First Search, LevinTS, et PUCT en termes de nombre de problèmes résolus et de temps de recherche dans les trois domaines testés.