Resumen Técnico: Arrepentimiento Óptimo para Bandits de Índice Único

Definición del Problema

El artículo aborda el problema del Bandit de Índice Único (SIB), un marco de toma de decisiones secuencial donde las recompensas dependen de una proyección unidimensional desconocida de vectores de contexto de alta dimensión a través de una función de recompensa no paramétrica y desconocida.

Formalmente, en cada ronda $t$, el agente observa un conjunto de $K$ vectores de contexto $X_t = \{x_{t,a} \in \mathbb{R}^d\}_{a \in [K]}$. El agente selecciona un brazo $x_{t,a}$ y observa una recompensa estocástica:
$$y_t = f(x_{t,a}^\top \theta^*) + \eta_t$$
donde:

• $\theta^* \in \mathbb{R}^d$ es un vector de parámetros desconocido (la dirección del índice).
• $f: \mathbb{R} \to \mathbb{R}$ es una función de enlace desconocida, continuamente diferenciable.
• $\eta_t$ es ruido de media cero con varianza acotada.

El objetivo es minimizar el arrepentimiento acumulado, definido como la diferencia entre la recompensa esperada del brazo óptimo y el brazo elegido a lo largo de un horizonte $T$.

Contexto y Brecha:
Si bien las tasas de arrepentimiento óptimas están establecidas para bandits lineales ($\tilde{O}(\sqrt{T})$) y bandits lineales generalizados (donde $f$ es conocida), el escenario SIB es más desafiante porque $f$ es desconocida. Trabajos anteriores de Kang et al. [2025] abordaron el caso donde $f$ es desconocida pero monótona, logrando un arrepentimiento óptimo de $\tilde{O}(\sqrt{T})$ utilizando estimadores de Stein. Sin embargo, para el caso general no monótono (asumiendo solo acotación y continuidad Lipschitz de $f$), el límite conocido más preciso era $\tilde{O}(T^{3/4})$. La pregunta central de este trabajo es: ¿Cuál es la escala de arrepentimiento óptima para bandits de índice único generales (no monótonos)?

Metodología: ZoomSIB-UCB

Los autores proponen un algoritmo de dos fases denominado Bandit de Índice Único Ampliado con Límite Superior de Confianza (ZoomSIB-UCB). La idea central es reducir el problema de alta dimensión a una secuencia de problemas de bandits unidimensionales estimando la dirección de proyección $\theta^*$ y luego discretizando el espacio proyectado.

Fase 1: Estimación de Parámetros

El algoritmo dedica las primeras $T_0$ rondas a estimar la dirección desconocida $\theta^*$.

• Exploración: Los brazos se extraen uniformemente al azar.
• Estimación: El algoritmo emplea un estimador de Stein normalizado. Aprovechando la Identidad de Stein, que establece que $E[y S(x)] = E[f'(x^\top \theta^*)] \theta^* = \mu^* \theta^*$ (donde $S(x)$ es la función de puntuación de la distribución del contexto), el algoritmo construye un estimador insesgado para la dirección de $\theta^*$.
• Normalización: Para resolver ambigüedades de escala y signo, el estimador se normaliza utilizando la norma $\ell_1$.
• Calibración: El horizonte de exploración $T_0$ se elige de modo que el error de estimación $\|\hat{\theta}_0 - \theta^*\|_1$ sea suficientemente pequeño (específicamente acotado por $\Delta / 2L$, donde $\Delta$ es el ancho del contenedor y $L$ es la constante Lipschitz del contexto).

Fase 2: UCB Discretizado

Una vez calculado $\hat{\theta}_0$, el algoritmo opera sobre los valores escalares proyectados $z = x^\top \hat{\theta}_0$.

• Discretización: La recta real se divide en $N = O(T^{1/3})$ contenedores de ancho $\Delta = T^{-1/3}$.
• Bandits Durmientes: En cada ronda, solo un subconjunto aleatorio de contenedores está "activo" (contiene al menos un brazo disponible). Esto introduce una estructura de "bandit durmiente" donde el conjunto de brazos disponibles cambia estocásticamente.
• Estrategia UCB: El algoritmo ejecuta un algoritmo UCB sobre los contenedores disponibles. Selecciona el brazo perteneciente al contenedor con el índice de Límite Superior de Confianza más alto.
• Manejo de Sesgo: El algoritmo tiene en cuenta dos fuentes de error:
  1. Sesgo de Discretización: Aproximación de recompensas continuas por los centros de los contenedores (acotado por la continuidad Lipschitz).
  2. Error de Estimación: El desplazamiento del índice verdadero debido al error en la estimación de $\theta^*$.
     Estos errores se absorben en un radio de confianza inflado.

Contribuciones Clave

1. Límite Superior de Arrepentimiento Mejorado

El artículo establece un límite de arrepentimiento de $\tilde{O}(d^2 T^{2/3})$ para bandits de índice único generales no monótonos.

• Esto mejora significativamente el límite anterior más preciso de $\tilde{O}(T^{3/4})$ de Kang et al. [2025].
• El algoritmo logra esto equilibrando el sesgo de discretización ($O(T\Delta)$) y el costo de exploración del problema de bandit 1D ($O(\sqrt{N T})$). Estableciendo $N \sim T^{1/3}$ (y por tanto $\Delta \sim T^{-1/3}$), se minimiza el arrepentimiento total a $O(T^{2/3})$.

2. Límite Inferior Minimax Coincidente

Los autores prueban un límite inferior minimax de $\tilde{\Omega}(T^{2/3})$ para el escenario general no monótono.

• Construcción: Construyen una instancia de problema difícil que involucra una familia de funciones con pequeños "bultos" localizados de altura $\sim T^{-1/3}$.
• Reducción: Reducen el problema SIB a un problema de bandit de $N$ brazos (donde $N \sim T^{1/3}$) asegurando una alta probabilidad de disponibilidad de brazos en cada contenedor.
• Trampa Teórica de la Información: Utilizando la desigualdad de Bretagnolle-Huber, muestran que distinguir entre una hipótesis nula y una hipótesis de "pico" (donde un contenedor específico es óptimo) requiere una exploración masiva, forzando un arrepentimiento de $\Omega(T^{2/3})$.
• Significado: Esto confirma que el límite superior $\tilde{O}(T^{2/3})$ es ajustado y que el algoritmo propuesto es minimax óptimo.

3. Validación Empírica

Extensos experimentos en conjuntos de datos sintéticos y del mundo real (KDD Cup 99, Forest Cover Type) demuestran:

• Rendimiento Superior: ZoomSIB-UCB supera consistentemente a los métodos más avanzados GSTOR (Kang et al. [2025]) y a las líneas base aleatorias, logrando un arrepentimiento acumulado sustancialmente menor.
• Escalado: El algoritmo exhibe un escalado de arrepentimiento sublineal con un exponente empírico de $\approx 0.53$ (Cuarético) y $0.57$ (Zigzag), muy por debajo del techo teórico del peor caso de $2/3$.
• Dimensionalidad: El algoritmo es robusto a contextos de alta dimensión ($d$), ya que opera en el espacio proyectado 1D después de la fase inicial de estimación, evitando efectivamente la maldición de la dimensionalidad que afecta a los métodos basados en kernels.
• Parada Adaptativa: Una regla de parada adaptativa permite al algoritmo terminar la fase de exploración tempranamente cuando la estimación del parámetro se estabiliza, evitando la necesidad de conocimiento previo de $\mu^*$ o $T$.

Significado y Afirmaciones

El artículo afirma resolver un problema abierto en el aprendizaje secuencial al proporcionar la primera caracterización precisa del arrepentimiento para bandits de índice único generales no monótonos.

• Optimalidad: Al proporcionar tanto un límite superior como un límite inferior coincidente, los autores establecen que la escala correcta de arrepentimiento es $\Theta(T^{2/3})$ (ignorando factores logarítmicos).
• Generalidad: A diferencia de enfoques anteriores que dependían de la monotonía o clases específicas de suavidad (como RKHS), este método funciona para cualquier función de recompensa acotada y Lipschitz continua sin requerir conocimiento de la forma de la función ni del parámetro $\mu^*$.
• Practicidad: La introducción de una regla de parada adaptativa hace que el algoritmo sea implementable en la práctica sin requerir que el horizonte de exploración teórico $T_0$ se fije a priori basándose en constantes desconocidas.

El trabajo cierra la brecha entre las estadísticas no paramétricas y la teoría de bandits, demostrando que la estructura de índice único puede explotarse para lograr tasas óptimas incluso cuando la función de recompensa es completamente desconocida y no monótona.