De los bandidos a la búsqueda de árboles de Monte Carlo: El principio optimista aplicado a la optimización y la planificación

Título original:

From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning

Contenido del libro:

From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning cubre varios aspectos del principio de "optimismo ante la incertidumbre" para problemas de optimización a gran escala bajo presupuesto numérico finito. La motivación inicial de la monografía procede del éxito empírico del método denominado "Monte-Carlo Tree Search", popularizado en el juego del Go por ordenador y extendido posteriormente a muchos otros juegos, así como a problemas de optimización y planificación.

Establece los fundamentos teóricos del campo caracterizando la complejidad de los problemas de optimización y diseñando algoritmos eficientes con garantías de rendimiento. La dirección principal seguida en esta monografía consiste en descomponer un problema complejo de toma de decisiones (como un problema de optimización en un gran espacio de búsqueda) en una secuencia de decisiones elementales, donde cada decisión de la secuencia se resuelve utilizando un "bandido de brazos múltiples" estocástico (modelo matemático para la toma de decisiones en entornos estocásticos). Esto define una búsqueda jerárquica que posee la agradable característica de iniciar la exploración mediante un muestreo cuasi uniforme del espacio y centrarse después, a diferentes escalas, en las áreas más prometedoras (utilizando el principio optimista) hasta realizar finalmente una búsqueda local en torno al óptimo global de la función.

Esta monografía considera el problema de la optimización de funciones en espacios de búsqueda generales (como espacios métricos, espacios estructurados, árboles y grafos), así como el problema de la planificación en procesos de decisión de Markov. Su principal contribución es una clase de algoritmos optimistas jerárquicos con diferentes instancias algorítmicas dependiendo de si las evaluaciones son ruidosas o sin ruido y si alguna medida de la ''suavidad'' local de la función alrededor del máximo global es conocida o desconocida.