Offline-to-Online Learning in Linear Bandits

Resumen Técnico: Aprendizaje de Offline-to-Online en Bandidos Lineales

Planteamiento del Problema
Este artículo aborda el problema del aprendizaje de offline-to-online dentro del entorno de bandidos lineales estocásticos. El escenario involucra a un aprendiz que selecciona secuencialmente acciones de un conjunto $\mathcal{A} \subset \mathbb{R}^d$ para maximizar las recompensas acumuladas durante un horizonte $n$, contando con acceso a un conjunto de datos offline preexistente $\mathcal{D}$. Los datos offline son recolectados mediante un diseño fijo y no adaptativo (conteos de acciones deterministas) y siguen un modelo de recompensa lineal con ruido subgaussiano.

El desafío central radica en el compromiso entre dos objetivos contrapuestos:

1. Regret Online ($R_n$): Minimizar el regret relativo a la acción óptima $\mu^*$. Los algoritmos online estándar (por ejemplo, LinUCB) dependen del optimismo para explorar, logrando un regret sublineal pero potencialmente sufriendo un alto regret inicial si se ignora el dato offline.
2. Regret Offline ($R_n^{off}$): Minimizar el regret relativo a la media de la recompensa del conjunto de datos offline ($\mu_{off}$). Los algoritmos offline estándar (por ejemplo, LinLCB) dependen del pesimismo para explotar los datos conocidos, asegurando un rendimiento cercano a $\mu_{off}$, pero fallan al explorar, lo que conduce a un regret lineal si el horizonte es largo o si el offline es subóptimo.

Los trabajos existentes han tratado estos regímenes por separado o se han centrado en bandidos multi-brazos (MAB), donde el regret escala con el número de acciones. Este artículo busca cerrar la brecha en entornos estructurados (lineales), donde el regret debería escalar con la dimensión $d$ en lugar del tamaño del espacio de acciones.

Metodología: El Algoritmo LinOtO
Los autores proponen LinOtO (Linear Offline-to-Online), un algoritmo que equilibra dinámicamente la exploración y la explotación mediante la gestión de un presupuesto de exploración. El algoritmo opera cambiando entre dos estrategias basadas en un conjunto de confianza $C_t$ construido a partir de datos tanto offline como online:

1. Conjuntos de Confianza: El algoritmo mantiene un estimador de mínimos cuadrados $\hat{\theta}_t$ y un elipsoide de confianza $C_t$ alrededor del verdadero parámetro $\theta^*$. El radio de este conjunto incorpora la incertidumbre proveniente tanto de los datos offline ($\beta_{off}$) como de las interacciones online ($\beta_t$).
2. Acciones Optimistas vs. Pesimistas:
   • Acción UCB ($U_t$): La acción que maximiza el Límite Superior de Confianza (Upper Confidence Bound) dentro de $C_t$. Esto promueve la exploración y reduce $R_n$, pero corre el riesgo de aumentar $R_n^{off}$.
   • Acción LCB ($L_t$): La acción que maximiza el Límite Inferior de Confianza (específicamente, el máximo de los límites de confianza mínimos a lo largo del tiempo). Esto promueve la explotación de los datos offline, reduciendo $R_n^{off}$, pero potencialmente aumentando $R_n$.
3. Mecanismo de Presupuesto:
   • El algoritmo define una recompensa base segura $r_b$, derivada de un límite inferior en la recompensa de una acción "segura" específica $L_{off}$ (la acción LCB calculada únicamente con datos offline). La Proposición 2 garantiza que $L_{off}$ está cerca de $\mu_{off}$ con alta probabilidad.
   • Se mantiene un presupuesto de exploración $B(t)$, que representa la recompensa excedente acumulada del algoritmo sobre la base $r_b$.
   • Regla de Decisión: Si $B(t) > 0$, el algoritmo selecciona la acción optimista $U_t$ (exploración). Si $B(t) \le 0$, selecciona la acción pesimista $L_t$ (explotación) para acumular presupuesto.
   • Este mecanismo asegura que el algoritmo solo explore cuando se haya "ganado" el derecho a hacerlo manteniéndose seguro respecto a la base offline.

Contribuciones Clave

1. Diseño de Algoritmo: El artículo presenta LinOtO, el primer algoritmo diseñado específicamente para el entorno de bandidos lineales de offline-to-online que equilibra simultáneamente las estrategias UCB y LCB mediante un mecanismo de cambio basado en presupuesto.
2. Garantías Teóricas: Los autores establecen límites de regret de alta probabilidad para ambos métricas:
   • Regret Online ($R_n$): El Teorema 1 muestra que LinOtO logra un regret sublineal respecto a la acción óptima. El límite consiste en un término dependiente del horizonte $n$ (similar a LinUCB) y una constante aditiva dependiente de la calidad de los datos offline. Si los datos offline cubren bien el espacio, el límite mejora.
   • Regret Offline ($R_n^{off}$): El Teorema 2 demuestra que el regret relativo a la referencia offline escala linealmente con $n$, pero disminuye como $O(1/\sqrt{m})$ con el número de muestras offline $m$. Esto iguala el rendimiento de una solución puramente offline (pesimista).
3. Análisis de Compromiso de Pareto: El análisis revela un compromiso ajustable controlado por un parámetro $\alpha$. Aumentar $\alpha$ favorece el rendimiento online (más cercano a LinUCB), mientras que disminuir $\alpha$ favorece el rendimiento offline (más cercano a LinLCB).

Resultados Experimentales
Las evaluaciones empíricas en tareas sintéticas de bandidos lineales (dimensión $d=20$, $|A|=100$) demuestran:

• Sensibilidad al Horizonte: Para horizontes cortos, LinOtO sigue la línea base conservadora de LinLCB. Para horizontes largos, transiciona hacia la exploración, logrando un regret sublineal comparable al de LinUCB.
• Calidad de los Datos Offline:
  • Cuando el conjunto de datos offline excluye la acción óptima, LinOtO logra desviarse del prior offline subóptimo para explorar, superando eventualmente a LinLCB (que sufre un regret lineal) y acercándose al rendimiento de LinUCB a medida que aumenta el tamaño de los datos offline $m$.
  • Cuando el conjunto de datos offline incluye la acción óptima, LinOtO converge rápidamente, desempeñándose de manera comparable a LinUCB y LinLCB.
• Robustez: El algoritmo se desempeña consistentemente entre los extremos de la exploración pura (LinUCB) y la explotación pura (LinLCB), adaptándose a los parámetros del problema.

Significancia y Reivindicaciones
El artículo afirma que LinOtO resuelve eficazmente el compromiso de offline-to-online "poco comprendido" en entornos estructurados. A diferencia de trabajos previos en entornos de MAB (por ejemplo, Sentenac et al., 2025), este enfoque aprovecha la estructura lineal para asegurar que el regret escale con la dimensión $d$ en lugar del número de acciones, lo que lo hace escalable para problemas de alta dimensión.

Los autores señalan modestamente que su marco actualmente asume datos offline de diseño fijo y no tiene en cuenta cambios de distribución entre los datos offline y online o políticas de registro adaptativas. Identifican el abordaje de estas limitaciones, junto con la extensión del marco a entornos no lineales, como direcciones importantes para la investigación futura. El trabajo contribuye a la literatura más amplia sobre el aprovechamiento del conocimiento previo (pistas, datos offline) para guiar los compromisos de exploración-explotación en el aprendizaje online.