Resumen Técnico: Bandidos Dueling Lineales Robustos con Contexto Post-servicio bajo Retrasos Desconocidos y Corrupciones Adversarias

1. Formulación del Problema

Este artículo aborda un problema de toma de decisiones complejo dentro del marco de los Bandidos Dueling Contextuales Lineales (CDB), centrándose específicamente en entornos volátiles caracterizados por tres desafíos simultáneos:

1. Contextos Post-servicio: A diferencia de los bandidos contextuales estándar donde la utilidad se determina únicamente por las características previas a la acción (p. ej., la demografía del usuario), la utilidad real aquí depende de características latentes que se revelan solo después de realizar la acción (p. ej., el tiempo de entrega, la temperatura de la comida). El aprendiz debe estimar un mapeo $\phi^*$ de los contextos previos al servicio $x_t$ a los contextos post-servicio $y_t$.
2. Retrasos de Retroalimentación Desconocidos: La retroalimentación llega con retrasos $\tau_t$ que son o bien estocásticos (sub-gaussianos) o adversarios. El aprendiz no sabe qué régimen está activo, ni la secuencia específica de retrasos.
3. Corrupción Adversaria: Un adversario puede corromper los resultados de preferencia observados (cambiando 0 por 1 o viceversa) sujeto a un presupuesto acumulativo $C$.

La dificultad central reside en la interacción multiplicativa de estos factores. Los retrasos reducen el tamaño efectivo de la muestra, amplificando la importancia estadística de las señales corrompidas. Además, el aprendiz debe estimar el mapeo post-servicio $\phi^*$ utilizando una retroalimentación que ya está comprometida por retrasos y corrupción, creando un ciclo vicioso de error de estimación.

El objetivo es minimizar el arrepentimiento acumulado (cumulative regret) $R_T$, definido como la brecha de utilidad entre el par de brazos óptimo y el par seleccionado, permaneciendo agnóstico al régimen de retraso específico y a la presencia de corrupción.

2. Metodología: RCDP-UCB

Los autores proponen RCDP-UCB (Robust to Corruption, Delay, and Post-serving UCB), un marco algorítmico diseñado para manejar estos desafíos entrelazados.

Componentes Clave:

• Predicción de Contexto: El algoritmo emplea un aproximador aprendido $\hat{\phi}_t$ (p. ej., una red neuronal) para predecir los contextos post-servicio $y_t$ a partir de los contextos pre-servicio $x_t$ antes de la selección de la acción. El vector de características se construye como $\hat{z}_t = (x_t, \hat{\phi}_t(x_t))$.
• Matrices de Diseño Duales: El algoritmo mantiene dos matrices distintas para desacoplar la selección de la estimación:
  • $\tilde{V}_t$: La Matriz de Historia Completa, construida utilizando todos los contextos cronológicos (tanto los llegados como los pendientes). Esta matriz se utiliza para la selección de brazos y el cálculo de pesos para asegurar el optimismo y la estabilidad.
  • $\hat{W}_t$: La Matriz de Historia Observada, construida únicamente a partir de la retroalimentación que realmente ha llegado en el tiempo $t$. Se utiliza estrictamente para la estimación de parámetros ($\Theta_t$) para asegurar la validez estadística.
• Estrategia de Ponderación Adaptativa: Se introduce un mecanismo de ponderación unificado para mitigar tanto la corrupción como el sesgo inducido por el retraso. Para una muestra $s$, el peso $\omega_s$ se define como:
  $$\omega_s = \min\left(1, \frac{\alpha}{\|\Delta z_s\|_{\tilde{V}_{s-1}^{-1}}}\right)$$
  donde $\alpha$ es un parámetro de robustez. Esta estrategia de "recorte" (clipping) reduce el peso de las muestras con alta importancia estadística (normas grandes), limitando eficazmente la influencia de las observaciones adversariamente corrompidas y de la retroalimentación retrasada que sesga la geometría de la información.
• Minimización del Arrepentimiento: El algoritmo selecciona pares de brazos $(a_t, b_t)$ utilizando una estrategia de Límite de Banda Superior (UCB) basada en $\tilde{V}_t$ y las características predichas, equilibrando la exploración y la explotación mientras tiene en cuenta la incertidumbre tanto en el parámetro de preferencia $\Theta^*$ como en el mapeo post-servicio $\phi^*$.

3. Principales Contribuciones

1. Marco Analítico Unificado: El artículo formaliza el primer entorno de bandidos dueling lineales que incorpora simultáneamente contextos post-servicio, retrasos desconocidos (estocásticos o adversarios) y corrupción adversaria.
2. Diseño del Algoritmo (RCDP-UCB): Introduce un nuevo algoritmo que integra la estimación del mapeo contextual con un mecanismo de recorte adaptativo. Crucialmente, el esquema de ponderación es agnóstico al régimen de retraso, lo que significa que no requiere conocimiento previo de si los retrasos son estocásticos o adversarios para funcionar eficazmente.
3. Garantías Teóricas:
   • Límite Superior: Bajo condiciones de regularidad estándar, el algoritmo logra un límite superior de arrepentimiento de $\tilde{O}(d(\sqrt{T} + C + D))$, donde $d$ es la dimensión de las características, $T$ es el horizonte de tiempo, $C$ es el presupuesto de corrupción y $D$ representa la complejidad del retraso ($D = \max(\sqrt{\Lambda}, \mu_\tau)$).
   • Límite Inferior: Los autores derivan un límite inferior minimax de $\Omega(\sqrt{dT} + dC + D')$ (donde $D' = \max(\sqrt{d\Lambda}, d\mu_\tau)$) en ausencia de contextos post-servicio. Esto confirma que la sobrecarga introducida por los retrasos y la corrupción es información-teóricamente inevitable.
   • Optimidad: El límite superior coincide con el límite inferior hasta un factor de $\sqrt{d}$ para retrasos adversarios, demostrando una eficiencia casi óptima.

4. Resultados Experimentales

Los autores evalúan RCDP-UCB en entornos sintéticos y conjuntos de datos del mundo real (UCI y OpenML) bajo diversas condiciones:

• Entornos Sintéticos: Los experimentos cubren mapeos post-servicio lineales y no lineales (Polinómico, Sinusoidal, Absoluto) con presupuestos de corrupción ($C$) y regímenes de retraso (Estratégico/Adversario y Estocástico) variables.
• Líneas Base: El algoritmo se compara con métodos de vanguardia que incluyen RCDB (robusto a la corrupción), ColSTIM, MaxInP y MaxPairUCB.
• Hallazgos:
  • RCDP-UCB supera consistentemente a las líneas base en arrepentimiento acumulado en todos los regímenes de retraso y niveles de corrupción.
  • El algoritmo demuestra una robustez superior en entornos "latentes" donde los contextos post-servicio son críticos; las líneas base que fallan al modelar estos contextos o que carecen de una ponderación robusta sufren un arrepentimiento significativamente mayor.
  • El mecanismo de ponderación adaptativa neutraliza eficazmente el ruido combinado de la corrupción y el retraso, manteniendo un rendimiento estable incluso cuando la dimensionalidad del contexto ($d$) y el número de brazos ($K$) aumentan.
  • Los experimentos con datos del mundo real confirman la escalabilidad y robustez del algoritmo incluso cuando el supuesto de preferencia lineal es solo una aproximación.

5. Significación y Reivindicaciones

El artículo afirma ser el primer trabajo que aborda simultáneamente los desafíos combinados de las corrupciones adversarias, los retrasos de retroalimentación desconocidos y los contextos post-servicio dentro del marco de los bandidos contextuales dueling.

• Impacto Teórico: Establece que el efecto combinado de estos factores es fundamentalmente multiplicativo pero puede gestionarse mediante una estrategia de ponderación unificada anclada a la geometría de la información completa ($\tilde{V}_t$). Los resultados proporcionan garantías de "lo mejor de ambos mundos" para los regímenes de retraso, adaptándose tanto a entornos estocásticos como adversarios sin detección explícita.
• Relevancia Práctica: El trabajo está motivado por sistemas interactivos modernos, particularmente el Aprendizaje por Refuerzo a partir de Retroalimentación Humana (RLHF) para Modelos de Lenguaje Extensos (LLMs). En tales sistemas, las preferencias del usuario suelen ser relativas (dueling), la retroalimentación es retrasada y los datos pueden ser ruidosos o manipulados. El marco propuesto ofrece un camino hacia la alineación más fiable, robusta y precisa de los sistemas de IA con la intención humana, teniendo en cuenta los factores latentes post-acción y las irregularidades de los datos.

Los autores reconocen limitaciones, señalando que la brecha de $\sqrt{d}$ en el límite inferior de retraso adversario sigue siendo un problema abierto y que extender el marco para manejar contextos post-servicio retrasados es una dirección para investigaciones futuras.