Resumen Técnico: Thompson Sampling con Corrección de Flujo para Bandidos Contextuales No Estacionarios

Formulación del Problema

El artículo aborda el desafío de los bandidos contextuales lineales no estacionarios, un entorno donde la relación entre contextos, acciones y recompensas evoluciona con el tiempo. En los bandidos contextuales clásicos, se asume que el vector de parámetros $w_t$ es estacionario. Sin embargo, en aplicaciones del mundo real (por ejemplo, sistemas de recomendación, fijación de precios dinámica, finanzas), las preferencias de los usuarios y las condiciones del mercado derivan, lo que hace que los datos históricos sean sistemáticamente sesgados si se utilizan de forma ingenua.

La dificultad central reside en el equilibrio entre retener datos históricos para reducir la varianza de la posterior y descartar datos antiguos para evitar el sesgo de modelos desactualizados. Los enfoques existentes —como las ventanas deslizantes, el descuento exponencial y los reinicios periódicos— tratan los datos históricos principalmente como un pasivo que debe gestionarse mediante el descarte uniforme o la reducción de su peso. Los autores argumentan que cuando la no estacionariedad exhibe una estructura predecible (por ejemplo, deriva gradual, periodicidad o regímenes recurrentes), las observaciones históricas contienen información valiosa que puede aprovecharse si se corrigen para los cambios ambientales intervinientes.

Metodología: Thompson Sampling con Corrección de Flujo (FC-TS)

Los autores proponen el Thompson Sampling con Corrección de Flujo (FC-TS), un marco bayesiano que transforma las observaciones históricas en "pseudo-observaciones del tiempo presente" antes de incorporarlas a la posterior. El método desacopla el manejo de la no estacionariedad en dos componentes distintos: un operador de transporte y una regla de ponderación de confianza.

1. Mecanismo Central

En cada ronda $t$, para cada observación pasada $(x_s, a_s, r_s)$, el FC-TS construye una recompensa transportada $\hat{r}_{s \to t}$:
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
donde $\hat{\Delta}_{s \to t}$ estima el desplazamiento en la recompensa media del tiempo $s$ al $t$. Esto efectivamente hace "fluir" la recompensa pasada hacia adelante para alinearla con el modelo de recompensa actual.

Para evitar el ruido derivado de estimaciones de deriva inexactas, a cada observación transportada se le asigna un peso de confianza $\omega_{s,t} \in [0, 1]$. Este peso controla la influencia de la observación en la posterior, inflando su varianza de ruido efectiva si la corrección es incierta.

La actualización de la posterior para una acción $a$ se realiza utilizando estas observaciones ponderadas y transportadas:
$$\Lambda_t^{(a)} = \lambda I + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} x_s x_s^\top$$
$$\eta_t^{(a)} = \lambda m_t^{(a)} + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} \hat{r}_{s \to t} x_s$$
$$\mu_t^{(a)} = (\Lambda_t^{(a)})^{-1} \eta_t^{(a)}$$
La selección de acciones procede mediante el Thompson Sampling estándar utilizando la posterior gaussiana $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$.

2. Instanciaciones Estructuradas

El marco proporciona una plantilla unificada con instancias específicas para tres patrones de no estacionariedad comunes:

• Deriva Lineal (Linear Drift): Asume que los parámetros evolucionan como $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$. El operador de transporte utiliza una estimación de regresión de Ridge en línea $\hat{\delta}_t^{(a)}$ para desplazar las recompensas: $\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$. Los pesos decaen exponencialmente ($\omega_{s,t} = \gamma^{t-s}$) para contabilizar la incertidumbre de la extrapolación.
• Variación Periódica (Periodic Variation): Asume que los parámetros se repiten con un periodo $P$. El operador de transporte es la identidad ($\hat{r}_{s \to t} = r_s$) para observaciones en la misma fase. Los pesos se determinan por la distancia circular entre fases, permitiendo al algoritmo reutilizar datos de ciclos anteriores ($\omega_{s,t}$ depende de la proximidad de fase).
• Regímenes Recurrentes (Recurring Regimes): Maneja entornos que cambian entre un conjunto finito de regímenes. El algoritmo mantiene un banco de posteriores específicos de cada régimen. Tras detectar un punto de cambio (mediante CUSUM sobre los residuales de predicción), recarga la posterior del régimen que está reapareciendo en lugar de reiniciar desde cero.

El marco también admite la composición, permitiendo el manejo simultáneo de deriva lineal y periodicidad mediante la combinación de sus respectivas reglas de transporte y ponderación.

Contribuciones Clave

1. Actualizaciones de la Posterior con Corrección de Flujo: El artículo introduce una visión basada en el transporte de la no estacionariedad, donde las recompensas pasadas se corrigen en pseudo-observaciones del tiempo presente e incorporan mediante actualizaciones bayesianas ponderadas por confianza, en lugar de ser descartadas uniformemente.
2. Diseño de Algoritmo Modular: FC-TS se define por un operador de transporte y una regla de ponderación genéricos, instanciados para deriva lineal, variación periódica y regímenes recurrentes. Esto incluye una variante adaptativa que combina tendencias y múltiples periodicidades.
3. Validación Empírica: Una evaluación extensa a través de cinco casos de estudio (deriva lineal, variación periódica, regímenes recurrentes, no estacionariedad compuesta y selección de cartera semi-sintética) demuestra que FC-TS supera a las líneas base de olvido más avanzadas.

Resultados Experimentales

Los autores evaluaron FC-TS frente a cuatro líneas base: Standard TS (STD-TS), Sliding Window TS (SW-TS), Discounted TS (D-TS) y Restarting TS (R-TS).

• Ganancias de Rendimiento: FC-TS logró el menor arrepentimiento (regret) acumulado en los cinco entornos, con mejoras que oscilan entre el 14.1% y el 59.0% respecto a la línea base más fuerte en cada entorno específico.

• Perspectivas Específicas de cada Caso:

  • Deriva Lineal: FC-TS igualó a SW-TS durante la fase de calentamiento, pero se separó progresivamente a medida que las estimaciones de deriva se estabilizaron, ganando en 8 de 10 semillas.
  • Variación Periódica: FC-TS mostró la mayor ganancia sintética (50.0%) debido a la "memoria de fase", acumulando datos de ciclos previos. El arrepentimiento por ciclo cayó de ~70 a ~4, mientras que las líneas base se estancaron.
  • Regímenes Recurrentes: FC-TS logró una mejora del 59.0% al recargar las posteriores específicas del régimen tras la detección de un cambio, evitando la penalización de "arranque en frío" de los reinicios.
  • No Estacionariedad Compuesta: En entornos con tanto deriva como cambios abruptos, FC-TS combinó con éxito la corrección de deriva (para evolución suave) y los reinicios de régimen (para cambios abruptos), logrando una mejora del 29.5%.
  • Cartera Semi-Sintética: En una tarea financiera con ciclos mensuales/trimestrales superpuestos y deriva de crecimiento hacia valor, la variante adaptativa de FC-TS mejoró el arrepentimiento en un 28.1% respecto a la mejor línea base (D-TS). Los estudios de ablación confirmaron que la corrección de deriva fue el componente dominante de esta ganancia.

• Hallazgos de Ablación:

  • Tamaño de Muestra Efectivo: Retener más datos sin la corrección de transporte (la ablación "sin transporte") resultó en un arrepentimiento mayor que los métodos que descartan datos, confirmando que los datos obsoletos introducen un sesgo sistemático.
  • Valor del Transporte: El operador de transporte por sí solo representó una reducción del arrepentimiento del 47–57% en comparación con la variante sin transporte en varias escalas de deriva, demostiendo que el mecanismo de corrección, y no solo la reconstrucción de la posterior, es lo que impulza el rendimiento.

Significancia y Reclamaciones

El artículo afirma que la no estacionariedad estructurada se aborda mejor corrigiendo y reutilizando la experiencia que mediante el descarte uniforme de la misma.

Los autores enfatizan que cuando la deriva del entorno es predecible (gradual, periódica o recurrente), los datos históricos son un activo en lugar de un pasivo. Al modelar explícitamente el "flujo" de la distribución de recompensa a lo largo del tiempo, FC-TS mantiene un tamaño de muestra efectivo mucho mayor que los métodos basados en el olvido. Los resultados sugieren que la clave de la eficiencia de muestreo en bandidos no estacionarios reside en ponderar y corregir las observaciones históricas basándose en la estructura temporal específica del entorno, en lugar de aplicar una única regla de olvido uniforme.

El artículo concluye modestamente, señalando que el trabajo futuro incluye el aprendizaje de estructuras de deriva en línea con incertidumbre calibrada, la extensión del marco a bandidos lineales generalizados o neuronales, y el desarrollo de salvaguardas para entornos de alto riesgo con cambios de distribución no modelados.