Brazos, Tirones, Recompensas
Una Fila de Máquinas Traganíquelas
Imagina K máquinas traganíquelas alineadas. Cada máquina paga una recompensa promedio diferente, pero no conoces ninguno de los promedios. En cada paso eliges una máquina, tiras de su palanca y observas un pago. Tu objetivo: maximizar la recompensa total a lo largo de muchos tirones.
Esa configuración define un problema de bandit de múltiples brazos. K = número de brazos. Un tirón selecciona un brazo. La recompensa proviene de la distribución oculta de ese brazo. La mean_reward(k) del brazo k rastrea el promedio acumulado a lo largo de los tirones de k.
Exploración vs Explotación
Dos presiones se oponen entre sí:
Explotación tira del brazo con la media_recompensa observada más alta. Avariciosa. Riesgo: un brazo que parecía genial después de 2 tirones podría retroceder a una media verdadera más baja.
Exploración tira de un brazo menos probado para reducir la incertidumbre. Riesgo: el tiempo gastado explorando cuesta recompensa que podrías haber recolectado de un brazo conocido bueno.
Una buena política mezcla ambas. La explotación pura fija los ganadores tempranos para siempre. La exploración pura nunca recolecta una recompensa.
Los Brazos de ANDREA = Fuentes de Datos
ANDREA enmarca el entrenamiento como un bandido. Cada fuente de datos (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, etc.) actúa como un brazo. Cada paso de entrenamiento tira de un brazo: carga un documento de esa fuente, ejecuta una pasada hacia adelante, observa la reducción de pérdida. La recompensa media por fuente rastrea cuánto mejora esa fuente la pérdida en promedio.
Por qué encaja esto: las necesidades del modelo cambian durante el entrenamiento. Los pasos tempranos se benefician de una exposición amplia (muchas fuentes). Los pasos posteriores se benefician de un pulido dirigido (unas pocas fuentes de alta recompensa). Un bandido se adapta; una proporción de muestreo fija no puede.
Nombrando las Piezas
La Puntuación UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer y colegas publicaron UCB1 en 2002 como una política de bandidos de tiempo finito con un límite de arrepentimiento de O(log N). UCB1 selecciona un brazo combinando su recompensa promedio actual con un bono de exploración que se reduce a medida que se tira del brazo.
La Fórmula
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Término por término:
- mean_reward(k): recompensa promedio observada para el brazo k en sus n_k tiradas. Término de explotación.
- N: tiradas totales en todos los brazos hasta ahora. Crece en cada paso.
- n_k: tiradas del brazo k específicamente. Crece solo cuando se elige k.
- C: constante de exploración. Valor estándar de los libros de texto: 1.4 (sqrt(2)). ANDREA usa C=0.5.
- sqrt(ln(N) / n_k): radio de confianza. Un brazo poco tirado tiene pequeño n_k y recibe un gran bono; un brazo bien tirado tiene gran n_k y recibe un pequeño bono.
Por qué funciona la fórmula
ln(N) crece lentamente (logarítmicamente), por lo que el numerador sube suavemente con la experiencia total. n_k en el denominador reduce el término a medida que se acumula evidencia para un brazo específico. La raíz cuadrada suaviza la respuesta, lo que evita que un solo brazo poco explorado domine para siempre.
Seleccionar por argmax_k UCB(k) en cada paso equilibra automáticamente ambas presiones. Sin parámetro epsilon, sin horario, sin temperatura. Las matemáticas lo manejan.
Calcular una puntuación UCB
Por qué C=0.5 en lugar de 1.4
El valor del libro de texto
Auer, Cesa-Bianchi & Fischer derivan un límite de arrepentimiento asumiendo que las recompensas están en [0, 1]. El límite se cumple para C = sqrt(2) approx 1.414. La mayoría de los libros de texto enseñan C=1.4 como un valor predeterminado seguro.
Magnitudes de recompensa de ANDREA
ANDREA reporta mejoras en la pérdida por paso como recompensa. Las mejoras crudas rondan 0.001 (la pérdida baja de 4.521 a 4.520). Después del factor de escalado 1000x (cubierto en la actividad 78, atribución de recompensas), las recompensas escaladas caen cerca de 1.0 en magnitud. Las recompensas medias a lo largo de la historia de un brazo se estabilizan en una banda de 0.5 a 3.0.
Ahora considera el bono de exploración con C=1.4, N=10000, n_k=100:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 se encuentra dentro de la banda de recompensa. Tolerable. Ahora n_k=10 (un brazo raro):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 se encuentra POR ENCIMA de la mayoría de las mean_rewards observadas. La exploración domina: el brazo raro gana independientemente de su media real. Con muchas fuentes y corridas de entrenamiento largas, esto inunda el schedule con brazos de baja media.
La Solución: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 se sitúa por debajo de la mayoría de las medias de recompensa. La exploración aún ocurre (los brazos raros aún reciben un bono), pero mean_reward lidera. ANDREA explota más, explora menos, y evita el dominio de la exploración.
Ajuste como Ingeniería, No Teoría
El límite del libro de texto asume recompensas en [0, 1]. Las recompensas de ANDREA viven aproximadamente en [0, 5]. Escalar la constante adapta la constante a la magnitud de la recompensa. Mismo algoritmo, entorno calibrado.
Dominancia de Exploración: Diagnóstico
Próximo
Lo Que Tienes
UCB1 elige el brazo con el mayor límite superior de confianza. El límite combina mean_reward (explotar) con sqrt(ln(N) / n_k) escalado por C (explorar). ANDREA ajusta C=0.5 porque las recompensas por paso están en una banda de 0.5 a 3.0, & el 1.4 del libro de texto inunda el horario con brazos de baja media.
Lo que queda
Vanilla UCB1 elige un brazo a la vez. ANDREA elige varios brazos de enfoque por fase, mezcla brazos aleatorios primero, y mantiene cada fase durante 7 a 42 pasos. Esa estructura (actividad 77: fases de dados) evita que UCB se comprometa en exceso con ganadores tempranos mientras aún le permite concentrar el esfuerzo.
La atribución de recompensas (actividad 78) muestra de dónde viene realmente mean_reward(k). Los pisos y penalizaciones de época (actividad 79) agregan reglas protectoras sobre la salida de UCB.
Referencia
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- Whitepaper de ANDREA, secciones 3.1 y 3.4.