Resumen: Estudiamos una implementación eficiente de la búsqueda de árboles de Monte-Carlo basada en Bandit (MCTS) basada en múltiples brazos (MAB) para la planificación clásica. Una debilidad de los MCT es que pasa un tiempo significativo decidiendo qué nodo expandirse a continuación. Si bien la selección de un nodo de una lista abierta con $ n $ nodos tiene $ O (1) $ complejidad de tiempo de ejecución con colas de prioridad basadas en matriz tradicionales para claves enteras densas, la lista abierta basada en árboles utilizada por MCTS requiere $ O ( log n) $, que corresponde aproximadamente a la profundidad de búsqueda $ D $. En la planificación clásica, $ D $ es arbitrariamente grande (por ejemplo, $ 2^K-1 $ en $ K $ -Disk Tower-of-Hanoi) y el tiempo de ejecución de la selección de nodos es significativo, a diferencia de la búsqueda en el árbol de juego, donde el costo es descuidado en comparación con la evaluación de nodos (despliegue) porque $ D $ está inherentemente limitado por el juego (por ejemplo, $ D LEQ 361 $ en Go). Para mejorar este cuello de botella, proponemos una modificación bilevel a MCTS que ejecuta una búsqueda mejor de cada nodo de hoja seleccionado con un presupuesto de expansión proporcional a $ D $, que logra un tiempo de ejecución de $ O (1) amortizado para la selección de nodos, equivalente a la lista abierta basada en la cola tradicional. Además, presentamos el colapso de los árboles, una mejora que reduce los pasos de selección de acción y mejora aún más el rendimiento.
Publicado Originalme en export.arxiv.org El 12 de agosto de 2025.
Ver Fuente Original
