Resumen Técnico: Arrepentimiento Casi Óptimo en Bandidos de Núcleo Adversarios

1. Formulación del Problema

El artículo aborda el problema de los bandidos de núcleo adversarios, una generalización de los bandidos lineales adversarios donde las funciones de pérdida pertenecen a un Espacio de Hilbert de Reproductores de Núcleo (RKHS).

• Configuración: En cada ronda $t \in [T]$, un agente selecciona una acción $x_t$ de un conjunto de acciones finito $\mathcal{X} \subset \mathbb{R}^d$. Simultáneamente, un adversario ciego selecciona un vector $w_t$ en el RKHS $\mathcal{H}$.
• Pérdida: El agente incurre en una pérdida $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$, donde $\Phi: \mathcal{X} \to \mathcal{H}$ es el mapa de características asociado a un núcleo simétrico definido positivo $K$.
• Retroalimentación: El agente observa únicamente la pérdida escalar $\ell_t(x_t)$, no el vector $w_t$ ni la función de pérdida completa.
• Objetivo: Minimizar el arrepentimiento esperado $R_T$ frente a la mejor acción fija $x^*$ a posteriori:
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• Supuestos: El adversario está acotado ($\|w_t\|_{\mathcal{H}} \le B$) y el núcleo está acotado ($K(x,x) \le 1$). Crucialmente, a diferencia de trabajos anteriores de Chatterji et al. [2019], el adversario no está restringido a pérdidas de rango uno (es decir, $w_t$ no necesita ser de la forma $\Phi(z_t)$); $w_t$ puede ser cualquier elemento de $\mathcal{H}$ con norma acotada.

2. Metodología y Algoritmo

Los autores proponen un algoritmo basado en Pesos Exponenciales (Exp2) adaptado para espacios de características de dimensión infinita. El desafío central es que los estimadores ponderados por importancia estándar en bandidos lineales se vuelven ilimitados cuando el mapa de características reside en un RKHS de dimensión infinita debido a los valores propios que se desvanecen del operador de covarianza.

Para superar esto, los autores introducen dos modificaciones clave:

1. Estimador de Importancia Ponderada Regularizado:
   En lugar de invertir el operador de covarianza empírica $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$, el algoritmo utiliza una versión regularizada por ridge $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$. El estimador se define como:
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   Esta regularización asegura que el estimador permanezca acotado incluso cuando $\Sigma_t$ tiene valores propios cercanos a cero. Sin embargo, esto introduce un sesgo sistemático: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$.

2. Término de Corrección de Sesgo Explícito:
   Para compensar el sesgo de la regularización, el algoritmo construye un proxy de pérdida corregido $\hat{\ell}_t(x)$:
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   donde el término de corrección es $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$.

   • Mecanismo: El término de corrección se deriva directamente de la expresión de sesgo en forma cerrada. Actúa como una cota superior puntual del sesgo, asegurando que el proxy de pérdida esperado subestime la pérdida real para el comparador (la mejor acción fija). Esta elección estructural asegura que el residuo del lado del comparador en la descomposición del arrepentimiento sea no positivo, dejando solo un residuo del lado del agente controlable.

3. Estrategia de Exploración:
   El algoritmo mantiene una distribución $p_t$ que es una mezcla de la distribución actual de pesos exponenciales $q_t$ y una distribución de exploración fija $\nu_G$. La distribución de exploración se elige mediante un diseño óptimo G regularizado para asegurar que la dimensión efectiva esté controlada.

3. Contribuciones Clave

• Diseño del Algoritmo: Un algoritmo principado que combina pesos exponenciales con un estimador regularizado y un término de corrección de sesgo explícito. Este enfoque evita la suposición restrictiva de adversario de rango uno requerida por Chatterji et al. [2019].
• Análisis de Arrepentimiento mediante Dimensión Efectiva: Los autores derivan una cota de arrepentimiento dependiente de la dimensión efectiva $d^*(\lambda)$ del núcleo, definida como:
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• Eliminación de la Suposición de Rango Uno: El marco permite pérdidas arbitrarias acotadas en RKHS, ampliando significativamente la aplicabilidad en comparación con trabajos anteriores que dependían de estimadores basados en proyección que requerían restricciones de rango uno.

4. Resultados Principales

El artículo establece una cota de arrepentimiento de la forma:
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
donde $d^*(\lambda)$ captura la complejidad del núcleo. Esta tasa coincide con las tasas óptimas conocidas para el problema de bandidos de núcleo estocástico (hasta factores logarítmicos).

Tasas Específicas para Núcleos:

• Núcleo Matérn$(\nu, d)$: Para un núcleo Matérn con suavidad $\nu$ en $\mathbb{R}^d$, la dimensión efectiva produce una cota de arrepentimiento de:
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  Esto mejora la tasa anterior mejor conocida de $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ de Chatterji et al. [2019] y coincide con la cota inferior de un trabajo concurrente [Iwazaki, 2026] hasta factores logarítmicos. Cabe destacar que la tasa anterior ni siquiera era sublineal cuando $\nu < d/2$, mientras que la nueva cota es siempre sublineal.
• Núcleo Exponencial Cuadrático (SE): La cota recupera la tasa casi óptima $\tilde{O}(\sqrt{T})$, coincidiendo con Chatterji et al. [2019] pero sin la restricción de rango uno.
• Decaimiento General de Valores Propios:
  • Decaimiento Polinómico ($\mu_j \le C j^{-\beta}$): Logra $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$.
  • Decaimiento Exponencial ($\mu_j \le C e^{-\beta j}$): Logra $R_T = \tilde{O}(\sqrt{T})$.

5. Significado y Afirmaciones

El artículo afirma cerrar la brecha entre el rendimiento de los bandidos de núcleo adversarios y estocásticos. Específicamente:

• Optimalidad: Las tasas derivadas coinciden con las tasas óptimas conocidas para bandidos de núcleo estocásticos (por ejemplo, mediante SupKernelUCB o métodos de optimización bayesiana) hasta factores logarítmicos.
• Avance Teórico: Al eliminar la suposición de adversario de rango uno, los resultados se aplican a una clase más general y realista de entornos adversarios donde la función de pérdida es un elemento arbitrario acotado del RKHS.
• Comparación con Trabajos Anteriores: El trabajo mejora a Chatterji et al. [2019] para núcleos Matérn y decaimiento polinómico general, proporcionando cotas más ajustadas que son sublineales en $T$ bajo condiciones donde las cotas anteriores no lo eran.
• Trabajo Concurrente: Los autores reconocen un trabajo concurrente independiente de Iwazaki [2026] que logra resultados similares utilizando un enfoque estrechamente relacionado (pesos exponenciales con estimadores regularizados y corrección de sesgo). El artículo nota diferencias menores en la configuración del problema (por ejemplo, adversario ciego vs. adaptativo, medidas de complejidad específicas) pero afirma que las contribuciones algorítmicas y analíticas centrales son esencialmente equivalentes.

El artículo concluye que el método propuesto proporciona una solución casi óptima al problema de los bandidos de núcleo adversarios, manejando efectivamente los desafíos de los espacios de características de dimensión infinita mediante regularización y corrección explícita de sesgo.