Self-Concordant Perturbations for Linear Bandits

Resumen Técnico: Perturbaciones Autoconcordantes para Bandidos Lineales

Configuración del Problema
El artículo aborda el problema de los bandidos lineales adversarios, un entorno de optimización en línea donde un agente selecciona secuencialmente acciones $a_t$ de un cuerpo convexo $K \subset \mathbb{R}^d$. En cada ronda, el agente sufre una pérdida $\langle y_t, a_t \rangle$ determinada por un vector de pérdida desconocido $y_t$, recibiendo únicamente este feedback escalar. El objetivo es minimizar el regret (arrepentimiento), definido como la diferencia entre la pérdida acumulada del agente y la pérdida acumulada de la mejor acción fija con conocimiento previo (in hindsight).

Existen dos familias algorítmicas primarias para este escenario: Follow-the-Regularized-Leader (FTRL) y Follow-the-Perturbed-Leader (FTPL). Mientras que un marco unificado (GBPA) conecta ambos en el entorno de información completa, la distinción es crítica en los bandidos: FTRL requiere mecanismos de exploración estocástica explícitos, mientras que FTPL es inherentemente estocástico, seleccionando acciones de los puntos extremos del conjunto de acciones. Los algoritmos con tasas óptimas existentes suelen depender de esquemas de preprocesamiento o exploración complejos y específicos del dominio (por ejemplo, elipsoides de expansión o spanning ellipsoids) en lugar de surgir naturalmente del marco de barreras autoconcordantes utilizado en el algoritmo SCRIBLE. SCRIBLE logra un regret de $O(d^{3/2}\sqrt{n \ln n})$ en cuerpos convexos generales y $O(d\sqrt{n \ln n})$ en la bola $\ell_2$, pero sufre de una varianza de exploración suboptimal en el hipercubo.

Metodología: El Marco SC-FTPL
Los autores introducen BANDITS-GBPA, un marco unificador que extiende el GBPA de información completa al entorno de bandidos. Este marco separa el algoritmo en una función de potencial $\Phi$, un esquema de muestreo $S$ y un esquema de estimación $E$.

Dentro de este marco, el artículo propone el algoritmo Self-Concordant Follow-the-Perturbed-Leader (SC-FTPL). La innovación central es la introducción de perturbaciones autoconcordantes.

• Definición: Una distribución de probabilidad $D$ sobre $\mathbb{R}^d$ es una perturbación $\vartheta$-autoconcordante para un cuerpo convexo $K$ si existe una barrera $\vartheta$-autoconcordante $R$ sobre $K$ tal que el gradiente de la conjugada de Fenchel de $R$ es igual a la esperanza del gradiente de la función de soporte de $K$ bajo la perturbación:
  $$\nabla R^*(\theta) = \mathbb{E}_{\xi \sim D}[\nabla \phi_K(\theta + \xi)]$$
  Esta definición asegura que la distribución de perturbación $D$ "replica" las propiedades geométricas de la barrera autoconcordante $R$ dentro de un contexto de FTPL.

• Algoritmo: SC-FTPL mantiene una estimación acumulativa de las pérdidas $\hat{Y}_{t-1}$. En cada paso, se muestrea una perturbación $\xi_t \sim D$ y se selecciona la acción:
  $$a_t = \arg \min_{a \in K} \langle a, \eta \hat{Y}_{t-1} - \xi_t \rangle$$
  El vector de pérdida se estima utilizando el estimador estándar de segundo momento inverso $\hat{y}_t = Q_t^{-1} a_t \langle y_t, a_t \rangle$, donde $Q_t = \mathbb{E}_{t-1}[a_t a_t^\top]$.

Contribuciones Clave

1. Marco Unificado (BANDITS-GBPA): Los autores formalizan un marco que engloba tanto los enfoques FTRL como FTPL para bandidos lineales, extendiendo el análisis de GBPA de información completa a la retroalimentación de bandidos. A diferencia del entorno de información completa, FTPL no es estrictamente un subconjunto de FTRL aquí, pero el marco permite una estructura analítica común.
2. Perturbaciones Autoconcordantes: El artículo identifica y analiza una familia de distribuciones de perturbación que replican las propiedades de las barreras autoconcordantes. Esto cierra la brecha entre las propiedades de regularización de SCRIBLE y la exploración inherente de FTPL.
3. Construcciones Explícitas: Los autores construyen perturbaciones autoconcordantes específicas para dos conjuntos de acciones canónicos:
   • Hipercubo $[-1, 1]^d$: Utilizando la barrera entrópica, derivan una perturbación con marginales independientes.
   • Bola $\ell_2$ ($B_d$): Utilizando la barrera logarítmica, construyen una perturbación basada en una distribución $t$ multivariante escalada.

Resultados y Límites de Regret
El artículo proporciona garantías de regret para SC-FTPL en el hipercubo y la bola $\ell_2$, asumiendo tasas de aprendizaje y condiciones de horizonte apropiadas ($n/\ln n$ suficientemente grande respecto a la dimensión).

• Hipercubo: SC-FTPL logra un límite de regret de $O(d\sqrt{n \ln n})$.

  • Esto coincide con el límite inferior minimax establecido por Dani et al. (2007) salvo por factores logarítmicos.
  • Representa una mejora de $\sqrt{d}$ respecto al algoritmo SCRIBLE (que logra $O(d^{3/2}\sqrt{n \ln n})$ en el hipercubo).
  • La mejora proviene de que el esquema de muestreo de FTPL se concentra en los puntos extremos, lo que reduce la varianza del estimador del vector de pérdida en la norma local en comparación con el muestreo de elipsoide de Dikin utilizado por SCRIBLE.
  • La complejidad computacional por ronda es $O(d)$.

• Bola $\ell_2$: SC-FTPL logra un límite de regato de $O(d\sqrt{n \ln n})$.

  • Esto iguala el rendimiento de SCRIBLE en la bola $\ell_2$.
  • El análisis para este caso es más complejo porque la norma local del estimador no admite una cota casi segura uniforme independiente de la estimación de la pérdida acumulada. Los autores emplean un argumento novedoso que involucra un supermartingala y argumentos de tiempo de parada (usando la desigualdad de Ville) para controlar el crecimiento del estimador acumulado y manejar la falta de cotas uniformes.
  • La complejidad computacional por ronda también es $O(d)$.

Significancia y Reivindicaciones
El artículo sostiene que SC-FTPL proporciona un enfoque unificado, basado en perturbaciones, para los bandidos lineales que recupera los beneficios de la regularización autoconcordante sin requerir los mecanismos de exploración explícitos y a menudo complejos de los métodos basados en FTRL.

• Optimalidad en el Hipercubo: La principal significancia radica en alcanzar la tasa óptima en el hipercubo sin esquemas de muestreo específicos del dominio, mejorando el algoritmo de vanguardia SCRIBLE por un factor de $\sqrt{d}$.
• Puente Teórico: El trabajo demuestra que FTPL puede analizarse rigurosamente utilizando la maquinaria de las barreras autoconcordantes, siempre que las perturbaciones se elijan para replicar la geometría de la barrera.
• Modestia sobre la Generalización: Los autores señalan que, aunque construyen perturbaciones para el hipercubo y la bola $\ell_2$, la existencia de perturbaciones autoconcordantes para cuerpos convexos generales sigue siendo una cuestión abierta. También reconocen que el límite de regret en la bola $\ell_2$ iguala a SCRIBLE pero no lo mejora, y que el análisis requirió maquinaria técnica adicional (tiempos de parada) no necesaria para el caso del hipercubo.

El artículo concluye identificando direcciones abiertas, incluyendo determinar si la tasa $O(d\sqrt{n \ln n})$ es ajustada para FTPL en la bola $\ell_2$ para cualquier esquema de perturbación, e investigar si la barrera entrópica (una barrera autoconcordante universal) admite una distribución de perturbación correspondiente para cuerpos convexos generales.