Avancemos a este paso a paso.
Un “bandido armado”, desde un punto de vista matemático, es cualquier distribución de probabilidad sobre un conjunto de números reales. A veces solo consideramos una distribución de probabilidad sobre dos resultados posibles: 0 y 1, pero en general se puede usar cualquier distribución.
Un bandido de brazos múltiples es un conjunto de bandidos de un brazo, llamados “brazos” del bandido de brazos múltiples. Por lo general, consideramos un conjunto finito.
- ¿Cómo funcionan los sockets web?
- ¿Puede la polaridad de un imán ser una alternativa a algunos de los componentes de una computadora eléctrica moderna?
- ¿Qué es pseudo streaming y qué sitios lo usan?
- ¿Vale la pena tomar CS 161 (sistemas operativos) en Harvard?
- Con respecto al problema de factorización, ¿podría P = NP si lo piensa un poco diferente?
En Machine Learning, un problema de bandido multi-armado consiste en un bandido multi-armado donde no conocemos las distribuciones de probabilidad de cada uno de los brazos. Es posible que tengamos algunos datos sobre resultados pasados para algunos o todos los brazos, y podemos usar esto para aproximar las distribuciones. Queremos averiguar qué brazo tiene el mayor valor esperado. Esto es similar a un conjunto de máquinas de apuestas en un casino: tiene cierta cantidad de dinero y desea apostar en las máquinas que tienen más probabilidades de obtener un mayor rendimiento.
En Machine Learning, llamamos a una configuración de problemas “en línea” si obtenemos un único punto de datos a la vez. Esencialmente, obtenemos una única instancia de problema, hacemos una predicción y luego observamos algún resultado; y repetir. Para el problema del bandido multi-armado, esto significa que comenzamos sin datos, y luego apostamos 1 (seleccione 1 brazo del bandido), observe el resultado, actualice nuestro modelo, seleccione otro brazo (o el mismo brazo nuevamente si lo deseamos), observar el resultado, y así sucesivamente.
Una estrategia para un bandido multi-armado es una forma específica de elegir armas dependiendo del modelo actual, para cualquier dato que hayamos observado en el camino.
Tenga en cuenta que muchos problemas diferentes se pueden modelar como un problema de bandido multi-armado. Un ejemplo típico es: debe seleccionar qué anuncio mostrar en su sitio y se le paga por cada usuario que hace clic en el anuncio. No sabe qué anuncios serán los más populares y desea maximizar sus retornos esperados. Aquí cada anuncio posible es un brazo del bandido, y las distribuciones de probabilidad están dadas por cuántas personas hacen clic en cada uno de los anuncios.
Una de las dificultades clave es el equilibrio entre la exploración (probar armas donde nuestro modelo aún es muy incierto) y la explotación (probar armas que creemos que son mejores según nuestro modelo actual).
Una de las mejores estrategias se conoce como el algoritmo UCB. Utiliza una combinación inteligente de la media de cada brazo, más algún factor multiplicado por la desviación estándar de ese brazo. El factor aumenta lentamente con el tiempo a una velocidad específica. Esto garantiza que cada brazo se seleccionará “suficientes” veces, al mismo tiempo que se explota el brazo “mejor” actual. Es una estrategia muy inteligente, y muchas estrategias se han basado en esto.
