Resumen Técnico: Un Algoritmo Conjuntamente Eficiente y Óptimo para Bandidos GLB Heterocedásticos con Corrupciones Adversarias

1. Configuración del Problema

El artículo aborda el problema de los Bandidos de Modelos Lineales Generalizados (GLB) Heterocedásticos en presencia de corrupciones adversarias. Este entorno unifica tres aspectos desafiantes de la toma de decisiones secuencial:

1. Modelos Lineales Generalizados (GLM): La recompensa esperada para un brazo $x_t \in \mathbb{R}^d$ sigue un GLM, $E[r_t|x_t; \theta^\star] = \mu(\langle x_t, \theta^\star \rangle)$, donde $\mu$ es una función de enlace inversa conocida y $\theta^\star$ es un parámetro desconocido. Este marco abarca bandidos lineales logísticos, de Poisson y gaussianos.
2. Heterocedasticidad: La varianza de la recompensa no es constante, sino que varía entre brazos y pasos de tiempo. Específicamente, $\text{Var}[r_t|x_t, \tau_t; \theta^\star] = g(\tau_t) \dot{\mu}(\langle x_t, \theta^\star \rangle)$, donde $g(\tau_t)$ es un parámetro de dispersión que puede variar exógenamente en el tiempo (por ejemplo, en bandidos gaussianos) o ser determinado endógenamente por la elección del brazo (por ejemplo, en bandidos logísticos o de Poisson).
3. Corrupciones Adversarias: Un adversario adaptativo manipula la recompensa observada en cada paso $t$ añadiendo una corrupción $c_t$, de tal manera que el aprendiz observa $\tilde{r}_t = r_t + c_t$. El adversario opera bajo una restricción de presupuesto total $\sum_{t=1}^T |c_t| \le C$.

El objetivo es minimizar el pseudo-regrete acumulado, definido como la diferencia entre la recompensa esperada del brazo óptimo y el brazo elegido a lo largo de $T$ rondas.

2. Metodología: HCW-GLB-OMD

Los autores proponen HCW-GLB-OMD (Hessian-Confidence Weighted GLB-OMD), un algoritmo diseñado para ser tanto computacionalmente eficiente como estadísticamente óptimo. El algoritmo integra dos componentes primarios:

A. Estimador de Descenso de Gradiente en Línea (OMD)

A diferencia de enfoques previos que dependen de la Estimación de Máxima Verosimilitud (MLE) por lotes, lo cual crea un desajuste de índice temporal entre los pesos locales y las estimaciones globales, HCW-GLB-OMD utiliza un estimador OMD en línea. La actualización del parámetro en el paso $t$ se define como:
$$\theta_{t+1} \leftarrow \arg \min_{\theta \in \Theta} \left[ \langle \nabla \tilde{\ell}_t(\theta_t), \theta - \theta_t \rangle + \frac{1}{2} \|\theta - \theta_t\|^2_{\nabla^2 \tilde{\ell}_t(\theta_t)} + \frac{1}{2\eta} \|\theta - \theta_t\|^2_{H_t} \right]$$
donde $\tilde{\ell}_t$ es una verosimilitud negativa ponderada. Este enfoque en línea asegura que el estimador, el brazo y los pesos estén alineados en el mismo paso de tiempo local, facilitando un análisis riguroso de los impactos de la corrupción.

B. Pesos de Confianza Basados en el Hessiano

Para lograr robustez contra las corrupciones, el algoritmo asigna un peso de confianza $w_t$ a cada observación basándose en el Hessiano local (curvatura) de la función de enlace y el parámetro de dispersión:
$$w_t = \min \left\{ 1, \frac{\alpha g(\tau_t)}{\|x_t\|_{H_t^{-1}}} \right\}$$
Aquí, $\|x_t\|_{H_t^{-1}}$ cuantifica la incertidumbre en la dirección de $x_t$.

• Mecanismo: Si una dirección de brazo es altamente incierta (norma grande en el inverso del Hessiano) en relación con la dispersión, el peso $w_t$ se reduce ($<1$). Esto penaliza las observaciones de direcciones vulnerables a la manipulación adversaria.
• Conciencia de la Curvatura: A diferencia de los métodos de bandidos lineales que utilizan una matriz de diseño, este método utiliza el Hessiano $\nabla^2 \tilde{\ell}_t$, que incorpora la pendiente local $\dot{\mu}$. Esto permite que el algoritmo se adapte a la geometría específica del GLM (por ejemplo, la saturación en bandidos logísticos).

C. Secuencias de Confianza Robustas a la Corrupción

Los autores construyen un conjunto de confianza $C_t(\delta)$ que da cuenta tanto del error de estimación como de la corrupción adversaria. El radio de este conjunto incluye un término aditivo proporcional al presupuesto de corrupción $C$:
$$C_t(\delta) \equiv \{ \theta \in \Theta : \|\theta - \theta_t\|_{H_t} \le \beta_t(\delta) + 2\eta\alpha C \}$$
La prueba de esta secuencia se basa en un argumento de supermartingala aplicado a una razón de verosimilitud ponderada, utilizando la concavidad del mapeo $x \mapsto x^{w_t}$ para manejar los casos donde $w_t < 1$.

3. Principales Contribuciones y Resultados

A. Cota Superior de Regrete

El artículo establece una cota superior de regrete para HCW-GLB-OMD bajo el supuesto de que la función de enlace $\mu$ es autoconcordante (Supuesto 3). Con una probabilidad de al menos $1-\delta$, el regrete está acotado por:
$$\text{Reg}(T) \lesssim \log d \left( \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + d^2 g_{\max} \kappa + d(g_{\max} + \kappa)C \right)$$
Donde:

• $\dot{\mu}_{t,\star} = \dot{\mu}(\langle x_{t,\star}, \theta^\star \rangle)$ es la pendiente de la función de enlace en el brazo óptimo.
• $g_{\max} = \max_t g(\tau_t)$ es la dispersión máxima.
• $\kappa = (\min_{x,\theta} \dot{\mu}(\langle x, \theta \rangle))^{-1}$ es el parámetro de curvatura.
• $C$ es el presupuesto total de corrupción.

Significancia de la Cota:

• Optimalidad Caso por Caso (Instance-Wise): El término principal $\sqrt{\sum g(\tau_t) \dot{\mu}_{t,\star}}$ depende de la pendiente real en el brazo óptimo, en lugar de la peor curvatura $\kappa$. Esto coincide con el límite inferior minimax para los GLB libres de corrupción.
• Robustez a la Corrupción: El término de corrupción escala linealmente con $C$ (específicamente $d(g_{\max} + \kappa)C$), lo cual es minimax óptimo salvo por un factor de curvatura $\kappa$.
• Unificación: La cota recupera simultáneamente resultados de vanguardia para bandidos lineales heterocedásticos, bandidos logísticos y bandidos de Poisson.

B. Límite Inferior de Regrete Unificado

Los autores demuestran un límite inferior unificado para cualquier GLB heterocedástico autoconcordante con corrupciones adversarias:
$$\Omega \left( d \sqrt{\sum_{t=1}^T g(\tau_t) \dot{\mu}_{t,\star}} + dC \right)$$
Este límite inferior:

• Subsume los límites inferiores específicos existentes para bandidos logísticos, bandidos lineales heterocedásticos y bandidos lineales corrompidos.
• Confirma que el término principal del algoritmo es minimax óptimo caso por caso.
• Demuestra que el término de corrupción $dC$ es inevitable, aunque la cota superior incluye actualmente un factor $\kappa$ adicional en el término de corrupción ($d\kappa C$).

C. Eficiencia Computacional

Una contribución crítica es la eficiencia del algoritmo. Al utilizar la actualización OMD en línea y actualizaciones recursivas del Hessiano, HCW-GLB-OMD logra una complejidad de espacio y tiempo de $O(1)$ por iteración. Esto contrasta con los algoritmos de robustez a la corrupción previos para GLM (por ejemplo, CR-Eluder-UCB, GAdaOFUL) que a menudo requieren una complejidad de $O(t)$ debido al procesamiento por lotes o a la construcción de conjuntos de confianza complejos.

4. Significancia y Reivindicaciones

El artículo afirma proporcionar el primer algoritmo conjuntamente eficiente y óptimo para los GLB heterocedásticos bajo corrupciones adversarias. Su principal significancia radica en:

1. Cerrar la Brecha: Resuelve el compromiso entre la eficiencia computacional y la optimalidad estadística en los GLB corrompidos. Los trabajos previos o bien lograban la optimalidad con un alto costo computacional, o bien la eficiencia con cotas de regrete subóptimas (que a menudo escalan con la peor curvatura $\kappa$).
2. Optimalidad Caso por Caso: El algoritmo logra cotas de regrete que se adaptan a la dificultad específica de la instancia (vía $\dot{\mu}_{t,\star}$) en lugar de depender de supuestos de peor caso, incluso ante la presencia de corrupciones.
3. Marco Unificado: Ofrece un único marco teórico que cubre un amplio espectro de problemas de bandidos (lineales, logísticos, de Poisson, heterocedásticos) sin requerir modificaciones algorítmicas específicas para cada problema.

Los autores señalan una brecha restante: el término de corrupción en la cota superior escala con $d\kappa C$, mientras que el límite inferior es $dC$. Conjeturan que el factor $\kappa$ en el término de corrupción es un artefacto del análisis y que es posible alcanzar una cota $O(dC)$, pero esto sigue siendo un problema abierto. Además, el análisis actual asume que el parámetro de dispersión $\tau_t$ es conocido por el aprendiz; el manejo de un $\tau_t$ desconocido se identifica como una dirección futura.