Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards

Aquí presento un resumen técnico detallado del artículo "Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards" (Brazos Múltiples con Recompensas Sustitutas Generadas por Aprendizaje Automático), estructurado según los puntos solicitados.

1. El Problema

El problema central abordado es la optimización de la toma de decisiones secuenciales bajo incertidumbre en el marco de los Brazos Múltiples (Multi-Armed Bandits - MAB). Tradicionalmente, los algoritmos de MAB dependen exclusivamente de datos en línea (recompensas observadas al "tirar" un brazo), lo que a menudo resulta en una escasez de datos durante la fase inicial de exploración.

En muchos escenarios prácticos (como ensayos clínicos, selección de modelos de lenguaje o recomendación de videos), existe una gran cantidad de datos auxiliares offline (históricos) y variables de covariables (características de usuarios, parámetros de configuración) disponibles antes de iniciar la fase online. Sin embargo, las recompensas verdaderas no están disponibles en esta fase offline.

El desafío específico de este trabajo es cómo utilizar modelos de aprendizaje automático (ML) pre-entrenados para convertir estas variables auxiliares en recompensas sustitutas (surrogate rewards) que guíen la decisión.

• El Dilema: Las recompensas sustitutas generadas por ML suelen estar sesgadas (sus medias no coinciden con las medias de las recompensas verdaderas) y pueden requerir extrapolación a entornos no vistos.
• La Oportunidad: A pesar del sesgo, las recompensas sustitutas suelen estar correlacionadas con las recompensas verdaderas. El objetivo es explotar esta correlación para reducir la varianza de la estimación de la recompensa media, sin necesidad de conocer la magnitud del sesgo ni la matriz de covarianza exacta.

2. Metodología: Algoritmo MLA-UCB

Los autores proponen el algoritmo MLA-UCB (Machine Learning-Assisted Upper Confidence Bound), que integra la inferencia potenciada por predicción (Prediction-Powered Inference - PPI) en el contexto dinámico de los MAB.

A. Estimador de Media Asistido por ML

El núcleo del método es un estimador de la media de recompensa $\mu_k$ para cada brazo $k$ que combina:

1. Datos Online: Pares de recompensas verdaderas ($R$) y sustitutas ($\hat{R}$) observados durante la interacción.
2. Datos Offline: Un conjunto estático de recompensas sustitutas ($\hat{R}^{off}$) generadas por el modelo ML.

El estimador se define como:
$$\hat{\mu}^{MLA}_{k,n} = \bar{R}_{k,n} - \hat{\lambda}_{k,n} (\bar{\hat{R}}_{k,n} - \bar{\hat{R}}^{off}_{k})$$
Donde $\hat{\lambda}_{k,n}$ es un coeficiente de regresión estimado (plug-in) que minimiza la varianza. Este enfoque es equivalente a un estimador de mínimos cuadrados ordinarios (OLS) donde la recompensa verdadera se regresa contra la sustituta, utilizando la diferencia entre la media online y offline de la sustituta para corregir el sesgo.

B. Construcción de Límites de Confianza

A diferencia de los UCB clásicos que asumen varianza conocida o usan estimadores simples, MLA-UCB construye límites de confianza superiores (UCB) invirtiendo una prueba t de una muestra con una estimación de varianza novedosa.

• Utiliza la distribución exacta de los residuos de la regresión.
• No requiere conocimiento previo de la varianza de las recompensas verdaderas ni de la matriz de covarianza entre recompensas verdaderas y sustitutas.
• El límite de confianza se ajusta dinámicamente según el tamaño de la muestra online ($n$) y offline ($N$).

C. Extensión a Recompensas Agrupadas (Batched)

Para escenarios donde las decisiones se toman en lotes (batches) y las recompensas individuales pueden no seguir una distribución Gaussiana, los autores extienden el método utilizando desviaciones moderadas auto-normalizadas (self-normalized moderate deviation bounds). Esto permite mantener garantías de confianza válidas bajo distribuciones generales (sub-Gaussianas) sin asumir normalidad estricta.

3. Contribuciones Clave

1. Nuevo Marco de MAB con Sustitutos: Introducen un setting donde los sustitutos pueden tener un sesgo arbitrario (incluso desalineado en el ordenamiento de los brazos) pero deben ser computables tanto offline como online.
2. Algoritmo MLA-UCB: Desarrollan un algoritmo que es aplicable a cualquier modelo de predicción ML y cualquier forma de datos auxiliares, sin necesidad de parámetros de varianza conocidos.
3. Análisis Teórico Riguroso:
   • Demuestran que bajo un modelo Gaussiano bivariado, el algoritmo mejora la cota de arrepentimiento (regret) en comparación con el UCB clásico.
   • La mejora es proporcional a $(1 - \rho_k^2)$, donde $\rho_k$ es la correlación entre la recompensa verdadera y la sustituta.
   • Establecen que el algoritmo es asintóticamente óptimo dentro de una amplia clase de políticas, incluso cuando el sesgo es grande.
   • Derivan cotas inferiores (lower bounds) que coinciden con las cotas superiores, confirmando la optimalidad.
4. Robustez a No-Gaussianidad: Extienden la teoría a entornos con recompensas agrupadas y distribuciones no Gaussianas, proporcionando garantías computables.

4. Resultados

Resultados Teóricos

• Reducción de Arrepentimiento: El término principal de la cota de arrepentimiento esperado $E[Reg_T]$ se reduce en un factor de $(1 - \rho_k^2)$ comparado con el UCB estándar.
• Independencia del Sesgo: La reducción del arrepentimiento se logra mediante la reducción de la varianza, no mediante la agregación directa de datos sesgados. Por lo tanto, el algoritmo funciona incluso si la media de la recompensa sustituta es completamente incorrecta, siempre que exista correlación.
• Tamaño de Muestra Offline: Se demuestra que se requiere un tamaño de muestra offline polilogarítmico ($N_k = \Omega((\log T)^{4/3})$) para alcanzar la optimalidad asintótica.

Resultados Empíricos (Simulaciones y Casos Reales)

• Simulaciones Gaussianas: Muestran reducciones significativas en el arrepentimiento acumulativo a medida que aumenta la correlación $\rho$ y el tamaño de la muestra offline $N$.
• Modelos ML No Lineales: Se probaron con modelos reales (Regresión Lineal, SVR, Redes Neuronales, Árboles de Decisión) sobre datos no Gaussianos. A pesar de violar la suposición de normalidad, el algoritmo mantuvo una reducción sustancial del arrepentimiento.
• Estudio de Caso 1: Selección de Modelos de Lenguaje (LLMs):
  • Escenario: Elegir entre modelos propietarios (GPT-4, Claude) usando modelos de código abierto (Llama) como sustitutos baratos.
  • Resultado: MLA-UCB identificó el mejor modelo más rápido que el UCB clásico, aprovechando la correlación entre la precisión del modelo abierto y el cerrado.
• Estudio de Caso 2: Recomendación de Videos:
  • Escenario: Maximizar la tasa de visualización (watch ratio) en una plataforma de videos.
  • Resultado: El uso de predicciones basadas en características de usuarios y videos redujo consistentemente el arrepentimiento en comparación con los métodos baselines.

5. Significado e Impacto

Este trabajo es significativo porque cierra la brecha entre el aprendizaje automático estático y la toma de decisiones secuenciales dinámicas.

• Utilización de Datos Históricos: Permite a los sistemas de recomendación y experimentación aprovechar grandes volúmenes de datos históricos y modelos ML pre-entrenados que anteriormente se consideraban "demasiado sesgados" para usarse directamente en la optimización.
• Eficiencia en Costos: En aplicaciones donde obtener la recompensa verdadera es costoso (ej. ensayos clínicos con seguimiento a largo plazo, llamadas a APIs de LLMs costosas), el uso de sustitutos baratos y rápidos permite una exploración más eficiente.
• Robustez: Al no requerir conocimiento de la matriz de covarianza ni asumir que los sustitutos preservan el ordenamiento de los brazos, el método es aplicable en escenarios del mundo real donde los modelos de ML son imperfectos y los datos sufren cambios de distribución (distribution shift).

En resumen, MLA-UCB ofrece un marco teórico y práctico sólido para integrar la inteligencia artificial generativa y predictiva en la optimización de decisiones secuenciales, logrando una mayor eficiencia en la exploración y una reducción garantizada del arrepentimiento.