El problema del bandido de varios brazos es un problema de toma de decisiones secuencial de información parcial . La configuración simple se puede describir de la siguiente manera:
- Hay K máquinas tragamonedas. Cada máquina tragamonedas se considera un “brazo” (aludiendo al hecho de que las máquinas tragamonedas a veces se llaman bandidos de un solo brazo).
- La configuración se realiza sobre iteraciones T (por lo tanto, secuencial ).
- Durante cada iteración, el tomador de decisiones elige un brazo para “tirar” y recibe una recompensa por jugar esa acción.
- Cada extracción de brazo da una recompensa aleatoria, y cada brazo tiene una recompensa esperada desconocida pero fija. Por ejemplo, el brazo 1 puede haber esperado una recompensa de 0.3 y cada tirón del brazo 1 dará la recompensa 0 con 70% y la recompensa 1 con 30%.
- El objetivo del tomador de decisiones es maximizar la recompensa total sobre todos los tirones del brazo T.
- El tomador de decisiones solo aprende acerca de las armas tirando de ellas (de ahí la información parcial ).
Una pregunta central en el estudio de los problemas de los bandidos es cómo equilibrar mejor la compensación entre exploración y explotación. Por un lado, el tomador de decisiones puede explotar su experiencia pasada para sacar los brazos que parecen tener una recompensa promedio alta. Sin embargo, los brazos que parecen buenos en realidad pueden ser subóptimos debido a la imprecisión en el conocimiento del tomador de decisiones (es decir, muy pocos tirones para tener una estimación confiable de la recompensa promedio). Para evitar esta situación, el tomador de decisiones debe explorar tirando de otros brazos (aparentemente pobres) para reunir más información sobre ellos.
Por ejemplo, supongamos que hay dos brazos y el tomador de decisiones ha sacado el brazo 1 dos veces y recibió una recompensa promedio de 0.7, y sacó el brazo 2 una vez y recibió una recompensa de 0.5. ¿Debería el tomador de decisiones seguir tirando del brazo 1 o probar el brazo 2? La incertidumbre aquí es que el tomador de decisiones realmente no conoce la recompensa esperada de ninguno de los brazos. Por un lado, el tomador de decisiones tiene alguna evidencia de que el brazo 1 podría ser mejor que el brazo 2. Por otro lado, el brazo 2 solo se ha retirado una vez.
- ¿Cuáles son las variables de factor en el lenguaje R?
- ¿Qué es un diagrama de máquina de Turing y cómo diseño uno?
- ¿Realmente necesito una sólida formación en matemáticas para comenzar a aprender programación?
- ¿Por qué la mayoría de los informáticos tienen un título en matemáticas?
- ¿Pueden los lenguajes naturales ser completamente modelados por las máquinas de Turing?
Como señaló Dhwaj Raj, el MAB se puede utilizar para modelar una serie de aplicaciones, como:
- Publicidad online
- ensayos clínicos
- sistemas de recomendación
Todas estas configuraciones exhiben esta misma propiedad de información parcial en la que solo se aprende sobre cuán buena es una estrategia o acción al probarla. Por ejemplo, la única forma de saber si un determinado anuncio en línea era bueno es mostrándolo a los usuarios web y observando la tasa de conversión de clics. Del mismo modo, la única forma en que aprenderá si cierto tratamiento médico es efectivo es probándolo en pacientes y observando los resultados. Cada una de las decisiones que tome debe equilibrar esta tensión entre la explotación (publicar un anuncio que usted confía es bueno) y la exploración (probar un nuevo anuncio para ver si podría ser mejor).
De hecho, la compensación de exploración / explotación surge en cualquier problema de decisión secuencial con incertidumbre o información parcial. (El MAB también se conoce como el problema del diseño de experimentos secuenciales). De alguna manera, el MAB es un modelo simple de cómo todos nosotros tomamos decisiones a lo largo de nuestras vidas.
El estudio de MAB en la comunidad de ciencias de la computación se centra en el diseño de algoritmos de bandidos (es decir, tomadores de decisiones automatizados) que tienen (probablemente) un buen rendimiento en diversos entornos. Como puede imaginar, esto es extremadamente importante para, por ejemplo, las empresas de publicidad en línea que desean maximizar los ingresos mediante la publicación de buenos anuncios.
Ver también: Sistemas de auto mejora que aprenden a través de la interacción humana