Algoritmo del bandido de brazos múltiples para encontrar el mejor bandido en el menor número de ensayos

Question

Me pregunto si existe un algoritmo que minimice la pérdida posterior esperada para el bandido de mejor rendimiento, donde el arrepentimiento se calcula como el número de ensayos para alcanzar un umbral de pérdida posterior.

Ejemplo: Supongamos que realizamos una prueba AB para comparar las tasas de clics de 3 creatividades diferentes. Para cada usuario, podemos decidir qué creatividad recibirá. Como estamos fingiendo que esto es un escenario del mundo real, no ganamos nada con el clic, pero tenemos que pagar por cada impresión lo mismo. ¿Existe una manera (un algoritmo) de encontrar la creatividad que mejor funcione en el menor número de impresiones (pruebas)?

Answer 1

La configuración que buscas se llama Mejor identificación del brazo . En este escenario, no se tiene ninguna noción de arrepentimiento, sino que sólo se pretende identificar el mejor brazo lo más rápido posible (digamos en $\tau$ pasos) y con una probabilidad al menos igual a $1-\delta$ , para $\delta\in(0,1)$ .

Se han propuesto muchos algoritmos para resolver este problema. Un algoritmo demostrable (asintóticamente para $\delta \to 0$ ) el algoritmo óptimo es propuesto por Garivier y Kaufmann pero hay muchos otros algoritmos (véase Audibert et al. o Jamieson et al. ).