El problema del bandido multibrazo es un clásico en el aprendizaje por refuerzo que plantea la situación de un jugador que debe elegir entre varias «palancas» (brazos del bandido), como máquinas tragaperras, cada una con una probabilidad de recompensa desconocida. El objetivo es maximizar la recompensa total obtenida tras un número determinado de tiradas. Entonces, ¿qué es un bandido en este contexto? Un bandido representa cada una de las palancas de la máquina tragaperras, es decir, cada opción disponible para el jugador. Cada bandido ofrece un resultado aleatorio con una distribución de probabilidad propia.
Este problema presenta un dilema fundamental: explorar o explotar. Explorar significa probar diferentes bandidos para encontrar aquel con la mayor probabilidad de recompensa. Explotar implica centrarse en el bandido que se considera mejor en ese momento para maximizar la recompensa. Equilibrar la exploración y la explotación es la clave del problema del bandido multibrazo.
¿Qué es un bandido y por qué es importante este problema? En la práctica, muchos problemas pueden modelarse como un problema del bandido multibrazo. Por ejemplo:
- Publicidad online: ¿Qué banner generará más clics? Cada banner es un bandido, los clics son la recompensa.
- Fijación dinámica de precios: ¿Qué precio optimizará los ingresos o beneficios? Cada precio es un bandido, los ingresos/beneficios son la recompensa.
- Sistemas de recomendación: ¿Qué producto debería recomendarse a un usuario? Cada producto es un bandido, la satisfacción del usuario es la recompensa.
- Ensayos clínicos: ¿Qué tratamiento es más efectivo y con menos efectos secundarios? Cada tratamiento es un bandido, la eficacia del tratamiento es la recompensa.
Para resolver el problema del bandido multibrazo, se han desarrollado numerosos algoritmos, cada uno con su propio enfoque para equilibrar la exploración y la explotación. Algunos algoritmos comunes incluyen:
- Algoritmo ingenuo: Probar cada bandido un número fijo de veces y luego elegir el bandido con la recompensa promedio más alta.
- Algoritmo ε-Greedy: Con una probabilidad ε, elegir un bandido al azar para explorar; con una probabilidad 1-ε, elegir el bandido con la recompensa promedio más alta para explotar.
- Algoritmo UCB (Upper Confidence Bound): Elegir el bandido con el límite superior de confianza más alto, combinando la recompensa promedio y la incertidumbre de la estimación.
- Algoritmo Thompson Sampling: Utilizar una distribución de probabilidad bayesiana para estimar la recompensa de cada bandido y elegir el bandido basándose en la probabilidad de que sea el mejor.
Cada algoritmo tiene sus propias ventajas y desventajas, y su eficacia depende de las características específicas del problema. Comprender qué es un bandido y los algoritmos relacionados permite elegir el método adecuado para optimizar las decisiones en situaciones de incertidumbre.
Video introductorio sobre el funcionamiento de UCB
La elección entre estos algoritmos depende del problema específico y los requisitos de rendimiento computacional. Por ejemplo, Thompson Sampling suele ser más eficaz que UCB en aplicaciones prácticas con grandes conjuntos de datos y requisitos de procesamiento en tiempo real.
