Resumen Técnico: Dueling Bandits Lineales y Neuronales con Retroalimentación Retrasada

1. Definición del Problema

El artículo aborda el problema de los Dueling Bandits Contextuales (CDB) bajo Retroalimentación Estocástica Retrasada. En los escenarios estándar de CDB, un agente selecciona un par de brazos (candidatos) y recibe retroalimentación binaria inmediata de preferencia (por ejemplo, $x_1 \succ x_2$) para aprender una función de recompensa latente. Sin embargo, en aplicaciones del mundo real como la alineación de Modelos de Lenguaje Grande (LLM), la optimización de prompts y la publicidad programática, la retroalimentación a menudo es asíncrona.

El escenario específico formalizado en este trabajo asume:

• Retrasos Estocásticos: La retroalimentación para una acción tomada en la ronda $s$ llega después de un retraso aleatorio $D_s$.
• Umbral Rígido: Existe una ventana de observación máxima $M$. Si $D_s > M$, la retroalimentación se trata como perdida (censurada).
• Probabilidad de Observación: La probabilidad de que la retroalimentación llegue dentro de la ventana es $\rho = P(D_s \le M)$.
• Desafío de Sesgo: A diferencia de los bandits lineales donde los estimadores tienen soluciones de forma cerrada (por ejemplo, regresión ridge), los dueling bandits dependen de la Estimación de Máxima Verosimilitud (MLE) bajo el modelo Bradley-Terry-Luce (BTL). Esta falta de soluciones de forma cerrada significa que las adaptaciones ingenuas de las técnicas estándar de retroalimentación retrasada (como la imputación simple o ignorar los datos faltantes) introducen un sesgo sistemático que no puede ser fácilmente acotado o corregido.

2. Metodología

Los autores proponen dos algoritmos novedosos diseñados para manejar estos retrasos sin imputación heurística: Dueling Bandits Lineales con Retroalimentación Retrasada (LDB-DF) y Dueling Bandits Neuronales con Retroalimentación Retrasada (NDB-DF).

Mecanismo Central: Ponderación por Probabilidad Inversa (IPW)

La innovación central es la integración de un mecanismo de Ponderación por Probabilidad Inversa (IPW) directamente en la función de pérdida.

• Estrategia de Ponderación: Para una instancia de retroalimentación $y_s$ observada en la ronda $t$ (donde $s < t$), el algoritmo asigna un peso $\omega_{s,t} = \frac{1}{\rho} \cdot \mathbb{I}\{D_s \le \min(M, t-s)\}$.
• Corrección Insesgada: Al escalar la contribución de la retroalimentación observada por $1/\rho$, el gradiente esperado de la pérdida sustituta se convierte en un estimador insesgado del gradiente verdadero, neutralizando efectivamente el sesgo introducido por el mecanismo de observación estocástica y los datos faltantes.

Algoritmo 1: LDB-DF (Entorno Lineal)

• Modelo: Asume una función de recompensa lineal $f(x) = \theta^\top \phi(x)$.
• Estimación: Minimiza una pérdida logística regularizada con IPW utilizando únicamente la retroalimentación "llegada".
• Exploración: Utiliza una estrategia de Límite Superior de Confianza (UCB). El primer brazo se selecciona de manera codiciosa basándose en la estimación actual $\theta_t$. El segundo brazo se selecciona para maximizar el UCB de la diferencia de preferencia en relación con el primer brazo, incorporando un radio de confianza $\beta_t$ que tiene en cuenta tanto el ruido estocástico como la incertidumbre inducida por los retrasos.
• Matriz de Información: Se actualiza inmediatamente utilizando los vectores de características de los pares seleccionados, independientemente de la latencia de la retroalimentación.

Algoritmo 2: NDB-DF (Entorno Neuronal)

• Modelo: Aproxima la función de recompensa no lineal utilizando una red neuronal totalmente conectada $h(x; \theta)$ con activaciones ReLU.
• Estimación: Entrena la red en línea utilizando la misma pérdida de entropía cruzada ponderada con IPW, aprendiendo únicamente del subconjunto de retroalimentación que ha llegado dentro de la ventana válida.
• Marco Teórico: El análisis se realiza en el régimen del Kernel Tangente Neuronal (NTK). El algoritmo asume que la red es suficientemente ancha ($m$) de modo que se comporta aproximadamente como una función lineal en el espacio de características del gradiente en la inicialización.
• Exploración: Similar al caso lineal, emplea una estrategia UCB. La bonificación de exploración se deriva del espacio de características NTK, cuantificando la incertidumbre epistémica en la diferencia de preferencia.

3. Contribuciones Teóricas

El artículo proporciona límites de arrepentimiento rigurosos para ambos escenarios, caracterizando explícitamente el impacto de los parámetros de retraso ($M$ y $\rho$).

• Límite de Arrepentimiento Lineal: El arrepentimiento acumulado para LDB-DF se establece como $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} d \sqrt{T}\right)$.

  • El término $\frac{M}{\rho}$ actúa como una penalización multiplicativa. Una probabilidad de observación $\rho$ más pequeña (menos muestras) y un umbral $M$ más grande (retrasos potenciales más largos) aumentan linealmente el arrepentimiento.
  • Cuando $\rho=1$ y $M=1$ (sin retraso), el límite recupera el estado del arte $\tilde{O}(d\sqrt{T})$ para los dueling bandits lineales estándar.

• Límite de Arrepentimiento Neuronal: El arrepentimiento acumulado para NDB-DF se establece como $\tilde{O}\left(\frac{M}{\rho \kappa_\mu} \tilde{d} \sqrt{T}\right)$, donde $\tilde{d}$ es la dimensión efectiva de la matriz NTK.

  • La prueba se basa en una técnica novedosa de descomposición "suma y resta" para separar el ruido de la martingala del sesgo sistemático inducido por los retrasos.
  • El análisis confirma que la dureza fundamental del problema (compensación entre la probabilidad de observación y la magnitud del retraso) persiste incluso con aproximadores de funciones no lineales complejos.

4. Resultados Experimentales

Los autores evalúan LDB-DF y NDB-DF frente a líneas base que ignoran los retrasos o utilizan imputación heurística.

• Líneas Base:
  • Ignorar: Utiliza la misma arquitectura de modelo pero descarta la retroalimentación pendiente hasta su llegada sin ponderación.
  • Heurística: Imputa la retroalimentación faltante utilizando la preferencia predicha por el modelo actual (proxy sesgado).
• Conjuntos de Datos:
  • Sintético: Funciones de recompensa lineales, cuadráticas y cúbicas con retrasos geométricos estocásticos.
  • Mundo real: Optimización automatizada de prompts utilizando el benchmark InstructZero (29 tareas de inducción de instrucciones).
• Hallazgos:
  • Ambos algoritmos propuestos superan significativamente a las líneas base en términos de arrepentimiento acumulado.
  • En entornos no lineales, la línea base Heurística a menudo converge a regiones subóptimas debido a errores de predicción de refuerzo mutuo (alucinaciones), mientras que la línea base Ignorar sufre de escasez de datos.
  • LDB-DF y NDB-DF demuestran robustez ante la latencia de la retroalimentación, navegando efectivamente por el espacio de búsqueda en tareas de optimización de prompts.

5. Significado y Afirmaciones

El artículo afirma cerrar una brecha crítica en el aprendizaje basado en preferencias al proporcionar el primer marco unificado que maneja simultáneamente:

1. Retroalimentación de Preferencia (Dueling): Resultados relativos binarios en lugar de recompensas absolutas.
2. Aproximación No Lineal (Neuronal): Paisajes de recompensa complejos mediante redes neuronales.
3. Retrasos Estocásticos/Datos Faltantes: Latencia de retroalimentación realista y censura.

Los autores enfatizan que su enfoque se aparta de la imputación heurística, ofreciendo una solución principista e insesgada mediante IPW. El análisis teórico establece los primeros límites de arrepentimiento para este escenario específico, demostrando que la degradación del rendimiento es predecible y depende linealmente de las características del retraso ($M/\rho$). El trabajo se posiciona como un paso fundamental para mejorar el aprendizaje de preferencias asíncrono en sistemas con humanos en el bucle, particularmente para la alineación de LLM y la optimización de prompts.