When and why randomised exploration works (in linear bandits)

Resumen Técnico: Cuándo y por qué funciona la exploración aleatorizada (en bandits lineales)

Configuración del Problema
El artículo aborda el problema de los bandits lineales, un entorno de toma de decisiones secuenciales donde un agente selecciona acciones $X_t$ de un subconjunto cerrado $\mathcal{X}$ de la bola euclídea unitaria en $\mathbb{R}^d$. El agente recibe una recompensa $Y_t$ con media $\langle X_t, \theta^\star \rangle$, donde $\theta^\star$ es un vector de parámetros desconocido. El objetivo es minimizar el arrepentimiento (regret) de $n$ pasos, definido como la diferencia acumulada entre la recompensa de la acción óptima y las acciones tomadas.

Si bien los algoritmos optimistas (por ejemplo, Upper Confidence Bound) han establecido límites de arrepentimiento frecuentistas de $O(d\sqrt{n} \log n)$ para bandits lineales, los algoritmos de exploración aleatorizada como Thompson sampling han sido históricamente más difíciles de analizar en este entorno. Los análisis frecuentistas previos de métodos aleatorizados a menudo dependían de la "optimismo forzado" o la "inflación de la posterior" (posterior inflation): modificar el algoritmo para inflar artificialmente la varianza de la distribución posterior para asegurar el optimismo con alta probabilidad. Estas modificaciones resultaron típicamente en límites de arrepentimiento subóptimos, tales como $O((d \log n)^{3/2}\sqrt{n})$, introduciendo un factor $\sqrt{d}$ adicional en comparación con los algoritmos optimistas. Además, límites inferiores recientes (Hamidi y Bayati, 2023; Zhang, 2022) demostraron que el Thompson sampling sin modificar puede incurrir en un arrepentimiento lineal en configuraciones patológicas específicas, lo que sugiere que la exploración aleatorizada no es universalmente óptima sin supuestos estructurales.

Metodología y Supuestos
Los autores proponen un nuevo marco de análisis que evita modificar el algoritmo aleatorizado (es decir, sin optimismo forzado ni inflación de la posterior). En su lugar, el análisis se basa en propiedades geométricas específicas del conjunto de acciones $\mathcal{X}$.

1. Marco Algorítmico: El artículo considera una clase de algoritmos aleatorizados donde, en cada paso $t$, se muestrea un parámetro $\theta_t$ como $\theta_t = \hat{\theta}_{t-1} + V_{t-1}^{-1/2}\eta_t$, donde $\hat{\theta}_{t-1}$ es la estimación de mínimos cuadrados regularizada, $V_{t-1}$ es la matriz de diseño, y $\eta_t$ es una perturbación rotacionalmente invariante. La acción se selecciona como $X_t = \arg\max_{x \in \mathcal{X}} \langle x, \theta_t \rangle$.
2. Supuestos de Perturbación: Se asume que las perturbaciones $\eta_t$ son variables aleatorias independientes, rotacionalmente invariantes, con momentos de segundo y cuarto orden acotados (por ejemplo, Gaussianas o uniformes en una esfera).
3. Supuestos del Conjunto de Acciones (Suavidad y Convexidad Fuerte): La contribución teórica central reside en el Supuesto 4.2, que requiere que el conjunto de acciones $\mathcal{X}$ sea un subconjunto cerrado y absorbente de la bola unitaria tal que el cuadrado de su función de soporte, $J_{\mathcal{X}}^2$, sea tanto $m$-fuertemente convexo como $M$-suave con respecto a una norma específica $\|\cdot\|_*$.
   • Convexidad Fuerte: Asegura que la función de soporte no tenga regiones "planas", garantizando que pequeños cambios en el espacio de parámetros se traduzcan en cambios significativos en el espacio de acciones.
   • Suavidad: Asegura que el gradiente de la función de soporte (que mapea parámetros a acciones) sea Lipschitz continuo, evitando saltos grandes en el arrepentimiento debido a pequeñas perturbaciones en los parámetros.
   • Ejemplos: Esta clase incluye bolas $\ell_q$ reescaladas para $q \in (1, \infty)$.

Contribuciones Clave y Análisis
El artículo proporciona un análisis de arrepentimiento frecuentista que no depende del marco de "optimismo ante la incertidumbre". En su lugar, analiza directamente la dinámica del proceso de exploración y la evolución de los conjuntos de confianza.

• Descomposición del Arrepentimiento: Los autores descomponen el arrepentimiento esperado en dos componentes: los pasos donde el algoritmo es "optimista" (el parámetro muestreado produce un valor superior al óptimo real) y los pasos donde no lo es.
• Exploración No Optimista: Una idea crítica es que incluso cuando una muestra no es optimista, esta sigue proporcionando información valiosa que reduce el conjunto de confianza. Los autores utilizan una formulación de divergencia de Bregman para el arrepentimiento por paso, $r_t = D_{J_{\mathcal{X}}}(\theta^\star, \theta_t)$, y aprovechan la convexidad fuerte y la suavidad de $J_{\mathcal{X}}^2$ para acotar esta divergencia.
• Crecimiento de la Información: La prueba establece un límite inferior en el crecimiento de la matriz de diseño $V_t al relacionar la ganancia de información esperada$\mathbb{E}_{t-1}[X_t X_t^\top]$ con la geometría de los elipsoides de confianza. Esto conecta el "tamaño" del espacio de parámetros (medido por $V_t^{-1/2}$) con la exploración real realizada.
• Evitar la Inflación: A diferencia de trabajos anteriores, este análisis no requiere inflar la varianza de la distribución de muestreo. Demuestra que la aleatoriedad natural del algoritmo, combinada con las propiedades geométricas de $\mathcal{X}$, es suficiente para impulsar la exploración y controlar el arrepentimiento.

Resultos Principales
Bajo los supuestos establecidos, los autores demuestran que cualquier algoritmo aleatorizado que satisfaga las condiciones de perturbación logra un límite de arrepentimiento frecuentista de:
$$R_n \lesssim O(d\sqrt{n} \log n)$$
Específicamente, el Teorema 4.1 proporciona un límite del orden de $O(d\sqrt{n} \log n)$ (ignorando factores logarítmicos en $n$ y $\delta$). Esto coincide con el límite inferior conocido para los bandits lineales (Rusmevichientong y Tsitsiklis, 2010) salvo por los factores logarítmicos.

Significado y Reivindicaciones
El artículo afirma resolver una pregunta abierta importante sobre la dependencia de la dimensión de Thompson sampling en los bandits lineales.

• Dependencia Óptima de la Dimensión: Demuestra por primera vez que el Thompson sampling sin modificar (sin inflación) puede alcanzar una dependencia de dimensión óptima ($O(d)$) en entornos de bandits lineales estructurados, específicamente cuando el espacio de acciones es suave y fuertemente convexo.
• Mecanismo de Éxito: El trabajo elucida por qué la exploración aleatorizada funciona en estos entornos: las propiedades geométricas del conjunto de acciones aseguran que las perturbaciones en el espacio de parámetros exploren efectivamente el espacio de acciones sin requerir un optimismo artificial.
• Limitaciones y Alcance: Los autores reconocen que sus resultados no contradicen los límites inferiores existentes que muestran un arrepentimiento lineal para Thompson sampling en espacios de acción no suaves o no absorbentes (por ejemplo, aquellos con brazos "trampa"). El éxito del método depende de que el conjunto de acciones cumpla con los supuestos de suavidad y convexidad fuerte. El artículo no pretende que estas condiciones sean necesarias, sino que son suficientes para lograr tasas óptimas sin modificaciones algorítmicas.

En resumen, el artículo establece que para una amplia clase de conjuntos de acciones bien comportados (incluyendo las bolas $\ell_q$), los algoritmos de exploración aleatorizada alcanzan naturalmente tasas de arrepentimiento óptimas, eliminando la necesidad de las técnicas de inflación de varianza ad-hoc que anteriormente se consideraban necesarias para obtener garantías teóricas.