Análisis del arrepentimiento en problemas estocásticos y no estocásticos de bandidos con varios brazos

Título original:

Regret Analysis of Stochastic and Nonstochastic Multi-Armed Bandit Problems

Contenido del libro:

Un problema del bandido de brazos múltiples -o, simplemente, un problema del bandido- es un problema de asignación secuencial definido por un conjunto de acciones. En cada paso de tiempo, se asigna una unidad de recurso a una acción y se obtiene un beneficio observable.

El objetivo es maximizar el beneficio total obtenido en una secuencia de asignaciones. El nombre bandido hace referencia al término coloquial para referirse a una máquina tragaperras (un "bandido manco" en el argot americano). En un casino, se obtiene un problema de asignación secuencial cuando el jugador se enfrenta a muchas máquinas tragaperras a la vez (un "bandido de varios brazos"), y debe elegir repetidamente dónde introducir la siguiente moneda.

Los problemas del bandido de brazos múltiples son los ejemplos más básicos de problemas de decisión secuenciales con un equilibrio de exploración-explotación. Se trata del equilibrio entre quedarse con la opción que dio mayores ganancias en el pasado y explorar nuevas opciones que puedan dar mayores ganancias en el futuro.

Aunque el estudio de los problemas del bandido se remonta a la década de 1930, los equilibrios entre exploración y explotación surgen en varias aplicaciones modernas, como la colocación de anuncios, la optimización de sitios web y el enrutamiento de paquetes. Matemáticamente, un bandido de brazos múltiples se define por el proceso de recompensa asociado a cada opción. En este libro, nos centramos en dos casos extremos en los que el análisis del arrepentimiento es especialmente sencillo y elegante: los resultados independientes e idénticamente distribuidos y los resultados adversos.

Además del escenario básico de acciones finitamente numerosas, también analiza algunas de las variantes y extensiones más importantes, como el modelo de bandido contextual. Esta monografía es una referencia ideal para estudiantes e investigadores interesados en los problemas de bandidos.