An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction

Resumen Técnico: Un Algoritmo Mejorado para Bandidos de Contexto Lineal Adversarios mediante Reducción

Definición del Problema

El artículo aborda el problema de los bandidos de contexto lineal adversarios (adversarial linear contextual bandits). En este entorno, un adversario desprevenido selecciona una secuencia de vectores de pérdida ocultos $\theta_t \in \mathbb{R}^d$ antes de que comience la interacción. En cada ronda $t$, un conjunto de acciones $A_t \subset \mathbb{R}^d$ se extrae de forma i.i.d. de una distribución fija pero desconocida $\mathcal{D}$ y se revela al aprendiz. El aprendiz debe seleccionar una acción $a_t \in A_t$ e incurre en una pérdida $\ell_t$ con esperanza $\mathbb{E}[\ell_t] = a_t^\top \theta_t$. El objetivo es minimizar el arrepentimiento (regret) frente a la mejor política fija $\pi$, donde una política mapea cualquier conjunto de acciones $A$ a un punto en su envolvente convexa $\text{conv}(A)$.

Este entorno generaliza a los bandidos lineales clásicos al permitir que los conjuntos de acciones (contextos) varíen estocásticamente en el tiempo, mientras que las pérdidas permanecen adversarias. Un desafío crítico es que la distribución $\mathcal{D}$ es desconocida, y el aprendiz no tiene acceso a un simulador que pueda generar muestras gratuitas de $\mathcal{D}$. Además, el número de posibles acciones $K$ puede ser exponencialmente grande en la dimensión $d$ (por ejemplo, en problemas combinatorios como la ruta más corta), lo que hace que los algoritmos con complejidad polinomial en $K$ sean inviables.

Metodología

La contribución central es una reducción computacionalmente eficiente que transforma el problema de los bandidos de contexto lineal adversarios en un problema de bandidos lineales adversarios robustos ante la especificación errónea (misspecification-robust) con un conjunto de acciones fijo.

1. Reducción a Conjuntos de Acciones Fijos:
   Los autores definen un mapeo $\Psi(\pi) = \mathbb{E}_{A \sim \mathcal{D}}[\pi(A)]$, que mapea una política $\pi$ a su acción media. Dado que $\mathcal{D}$ es desconocida, el verdadero conjunto de acciones medias $\Omega = \{\Psi(\pi) \mid \pi \in \Pi\}$ no puede accederse directamente. En su lugar, el algoritmo construye una aproximación empírica $\hat{\Omega}$ utilizando $N$ muestras i.i.d. de conjuntos de acciones extraídos de $\mathcal{D}$.

   • $\hat{\Omega}$ se define como la suma de Minkowski de las envolventes convexas de los conjuntos de acciones muestreados: $\hat{\Omega} = \frac{1}{N} \sum_{i=1}^N \text{conv}(A_i)$.
   • La reducción se basa en el hecho de que para las políticas de clasificadores lineales, la diferencia entre la pérdida esperada en la distribución verdadera y la distribución empírica es pequeña (convergencia uniforme), siempre que $N$ sea suficientemente grande.

2. Manejo de la Discrepancia mediante la Robustez ante la Especificación Errónea:
   Debido a que el aprendiz opera sobre $\hat{\Omega}$ en lugar de $\Omega$, la retroalimentación recibida por el algoritmo de bandido lineal subyacente está "mal especificada". Específicamente, la pérdida esperada observada por el algoritmo de bandido lineal difiere de la verdadera pérdida esperada por un término de error acotado $\epsilon$.

   • Los autores utilizan un algoritmo de bandido lineal adversario $\alpha$-robusto ante la especificación errónea como una caja negra. Este algoritmo garantiza un bajo arrepentimiento incluso cuando la retroalimentación satisface $|\mathbb{E}[c_t] - \langle y_t, \theta_t \rangle| \le \epsilon$.
   • Para ejecutar un punto $y_t \in \hat{\Omega}$ sugerido por el algoritmo de bandido lineal, el aprendiz utiliza una descomposición basada en Frank-Wolfe (Algoritmo 2) para expresar $y_t$ como una combinación convexa de puntos en la frontera de $\hat{\Omega}$. Estos puntos fronterizos corresponden a políticas de clasificadores lineales $\pi_\phi$, que pueden ejecutarse utilizando un oráculo de optimización lineal para los conjuntos de acciones individuales $A_t$.

3. Componentes Algorítmicos:

   • Algoritmo 1: El marco principal que interactúa con el entorno, descompone la sugerencia del bandido lineal en una mezcla de políticas lineales y alimenta la pérdida resultante al algoritmo de bandido lineal.
   • Algoritmo 3 (Pesos Exponenciales Continuos Robustos ante la Especificación Errónea): Una instanciación específica del algoritmo de bandido lineal robusto. Adapta el método de pesos exponenciales continuos recortados (Ito et al., 2020) añadiendo un "término de bono" $b_t$ al estimador de la pérdida. Este bono fomenta la exploración y compensa el exceso de arrepentimiento causado por la especificación errónea.
   • Truco de Doble (Doubling Trick): Para manejar el tamaño de muestra $N$ desconocido, el algoritmo emplea un truco de doble, reiniciando el proceso en épocas $2, 4, 8, \dots$ y utilizando todas las muestras de contexto acumuladas para refinar $\hat{\Omega}$.

Principales Contribuciones

• Algoritmo Eficiente en Oráculos: El artículo presenta el primer algoritmo para bandidos de contexto lineal adversarios con conjuntos de acciones estocásticos que logra cotas de arrepentimiento independientes del número de acciones $K$ en su complejidad computacional. Solo requiere un oráculo de optimización lineal para los conjuntos de acciones individuales en cada ronda.
• Aplicabilidad Combinatoria: El método es el primero en lograr un arrepentimiento de $\text{poly}(d)\sqrt{T}$ en tiempo polinomial para bandidos combinatorios con conjuntos de acciones estocásticos y pérdidas adversarias. Los algoritmos anteriores requerían retroalimentación de semi-bandido o tenían una complejidad computacional que escalaba polinomialmente con $K$ (lo cual es exponencial en $d$ para muchos problemas).
• Reducción Novedosa: El trabajo establece una reducción en tiempo polinomial de los bandidos de contexto lineal adversarios a los bandidos lineales robustos ante la especificación errónea. A diferencia de reducciones previas (por ejemplo, Hanna et al., 2023) que se centraban en entornos estocásticos o carecían de implementaciones en tiempo polinomial, esta reducción opera bajo pérdidas adversarias y es computacionalmente eficiente.

Resultados

El algoritmo logra las siguientes cotas de arrepentimiento (ignorando factores logarítmicos):

• Sin Simulador: $\tilde{O}(\min\{d^2\sqrt{T}, \sqrt{d^3 T \log K}\})$.
  • Esto resuelve una pregunta abierta de Liu et al. (2023) sobre si es posible lograr un arrepentimiento de $\text{poly}(d)\sqrt{T}$ en tiempo polinomial independiente de $K$.
  • La complejidad computacional es $\text{poly}(d, T)$ más $\text{poly}(d, T)$ llamadas al oráculo de optimización lineal.
• Con Simulador: Si el aprendiz tiene acceso a un simulador que puede generar contextos gratuitos, la cota de arrepentimiento mejora a $\tilde{O}(d\sqrt{L^*})$, donde $L^*$ es la pérdida acumulada de la mejor política. Esta es una cota de primer orden que se adapta a la dificultad de la instancia del problema.

Significado y Reivindicaciones

Los autores afirman que este trabajo proporciona un marco general que amplía significativamente la aplicabilidad de los bandidos de contexto lineal adversarios a problemas con espacios de acciones exponencialmente grandes (por ejemplo, ruta más corta, flujo, emparejamiento bipartito) sin requerir el conocimiento de la distribución del contexto o un simulador.

El artículo señala explícitamente que, si bien la cota $\tilde{O}(d^2\sqrt{T})$ es una mejora respecto a los resultados previos en tiempo polinomial dependientes de $K$, sigue siendo una pregunta abierta si se puede lograr la cota casi óptima $\tilde{O}(d\sqrt{T})$ sin un simulador en tiempo polinomial. Los autores también destacan que su enfoque elimina la hipótesis poco realista de distribuciones de contexto log-cóncavas requerida por algunos trabajos previos (Olkhovskaya et al., 2023) cuando se especializa a ciertas formulaciones. Finalmente, sugieren que el marco de reducción puede ser aplicable a otros entornos, como los MDP lineales con transiciones fijas y pérdidas adversarias.