Multi-Armed Bandits

“The greatest enemy of knowledge is not ignorance, it is the illusion of knowledge.” — Daniel J. Boorstin

En módulos anteriores aprendimos a tomar decisiones óptimas cuando conocemos las distribuciones relevantes (Módulo 09 — Teoría de la Decisión) y a estimar cantidades desconocidas mediante muestreo (Módulo 12 — Monte Carlo). Pero ¿qué pasa cuando debemos tomar decisiones y aprender simultáneamente? Cada acción produce dos cosas: una recompensa inmediata y nueva información. Elegir la acción que parece mejor ahora puede impedirnos descubrir una mejor; explorar demasiado desperdicia recompensas acumuladas. Este es el dilema de exploración vs. explotación, y el bandido multibrazo es su formalización más pura. Los algoritmos de este módulo — ε-greedy, UCB1, Thompson Sampling y EXP3 — aparecen en pruebas A/B, ensayos clínicos, sistemas de recomendación y como pieza central de Monte Carlo Tree Search.

Contenido

Materiales y flujo de trabajo

Paso	Material	Colab	Descripción
1	17.1 El dilema	—	Formulación, regret, problemas canónicos
2	17.2 ε-Greedy	—	Exploración aleatoria, media incremental, decaimiento
3	Notebook 01 — Exploración básica		Construir el entorno, calcular regret, explorar sin algoritmo
4	17.3 UCB	—	Hoeffding, UCB1, KL-UCB, variantes
5	Notebook 02 — Algoritmos frecuentistas		Implementar ε-greedy, UCB1 y KL-UCB; comparar
6	17.4 Thompson Sampling	—	Beta, conjugación, muestreo posterior
7	17.5 Comparación	—	Gran experimento, tabla resumen, guía de uso
8	17.6 Adversarial	—	EXP3, espectro estocástico–adversarial
9	Notebook 03 — Bayesianos y comparación		Thompson, EXP3, comparación de todos los algoritmos
10	17.7 Aplicaciones	—	A/B testing, ensayos clínicos, variantes
11	Notebook 04 — A/B Testing		Prueba A/B real: tradicional vs. adaptativa

Objetivos de aprendizaje

Al terminar este módulo podrás:

1. Formular el problema del bandido multibrazo con sus 5 componentes y explicar por qué MEU solo no basta cuando las distribuciones son desconocidas
2. Definir regret acumulado y descomponerlo por brazo: $R_T = \sum_i \Delta_i N_i(T)$
3. Implementar ε-greedy con actualización incremental de la media y comparar esquemas de decaimiento
4. Derivar la fórmula de UCB1 a partir de la desigualdad de Hoeffding y explicar el principio de optimismo ante la incertidumbre
5. Implementar Thompson Sampling usando la conjugación Beta-Bernoulli y Normal-Normal, y explicar el mecanismo de probability matching
6. Comparar ε-greedy, UCB1, KL-UCB, Thompson y EXP3 en regret teórico y empírico sobre los dos problemas canónicos
7. Explicar por qué EXP3 funciona en entornos adversariales donde UCB1 y Thompson fallan
8. Aplicar bandidos a pruebas A/B y cuantificar la ventaja de la asignación adaptativa sobre el split fijo 50/50
9. Clasificar variantes del problema (contextual, no estacionario, combinatorial) e identificar el algoritmo apropiado para cada una

Prerrequisitos

Mapa conceptual

graph TD
    A["Módulo 09: MEU — decidir con distribuciones conocidas"] --> B["Bandidos: decidir con distribuciones desconocidas"]
    C["Módulo 05: Bayes, distribuciones"] --> D["Thompson: posterior Beta/Normal"]
    E["Módulo 12: Monte Carlo, importance sampling"] --> F["EXP3: estimador ponderado por importancia"]
    E --> G["Thompson: muestreo del posterior"]
    H["Módulo 06: Divergencia KL"] --> I["KL-UCB: cota basada en KL"]
    B --> J["ε-greedy: exploración ciega"]
    J -->|"falla: explora brazos malos"| K["UCB1: exploración dirigida"]
    K -->|"falla: no usa distribución completa"| D
    D -->|"falla: asume recompensas estocásticas"| F
    K --> L["UCT → MCTS (módulo futuro)"]
    M["Módulo 15: Árboles de juego"] --> L

Cómo ejecutar el script de imágenes

cd clase/17_multi_armed_bandits
python3 lab_bandits.py

Dependencias: numpy, matplotlib, scipy (ver requirements.txt).