Stochastic Linear Bandits with Parameter Noise

Resumen Técnico: Banditos Lineales Estocásticos con Ruido de Parámetros

Definición del Problema
Este trabajo investiga el modelo de banditos lineales estocásticos con ruido de parámetros. En este escenario, un agente interactúa con un entorno durante un horizonte temporal $T$ seleccionando acciones $a_t$ de un conjunto de acciones $\mathcal{A} \subseteq \mathbb{R}^d$. A diferencia del modelo de ruido aditivo estándar, donde la recompensa es $X_t = a_t^\top \theta^\star + \eta_t$ (con $\theta^\star$ fijo y ruido $\eta_t$), el modelo de ruido de parámetros asume que la recompensa viene dada por $X_t = a_t^\top \theta_t$, donde $\theta_t$ se muestrea de forma i.i.d. desde una distribución fija y desconocida $\nu$ con media $\theta^\star$ y matriz de covarianza $\Sigma$.

El artículo destaca una distinción clave: en el modelo de ruido de parámetros, el agente puede influir en la varianza de la recompensa. Específicamente, $\text{Var}(X_t) = a_t^\top \Sigma a_t$, whereas en el modelo de ruido aditivo, la varianza está determinada únicamente por el entorno. Los autores señalan que, aunque el modelo de ruido de parámetros es una relajación del modelo de banditos lineales adversarios (donde $\theta_t$ es elegido por un adversario), presenta propiedades estructurales únicas que permiten cotas de arrepentimiento potencialmente más ajustadas que las del modelo de ruido aditivo en ciertos contextos geométricos.

Metodología y Algoritmos
Los autores proponen dos algoritmos adaptados a diferentes geometrías de conjuntos de acciones:

1. VASE (Eliminación Sucesiva de Diseño Óptimo Consciente de la Varianza):

   • Objetivo: Conjuntos de acciones finitos generales (y conjuntos infinitos mediante argumentos de recubrimiento).
   • Mecanismo: Un algoritmo de eliminación sucesiva que aprovecha la información de la varianza. En cada fase, calcula un diseño G-óptimo $\pi_\ell$ para seleccionar acciones. Estima explícitamente la varianza de las acciones en el soporte del diseño utilizando un algoritmo de regla de parada (SR).
   • Innovación Clave: El algoritmo utiliza las varianzas estimadas de dos maneras: para reducir el número de muestras requeridas para la exploración y como pesos en un estimador de mínimos cuadrados ponderados. Este ponderado asegura que la covarianza del estimador permanezca controlada incluso con menos muestras, lo que conduce a cotas de arrepentimiento dependientes de la varianza.

2. VALEE (Exploración-Explotación Lineal Consciente de la Varianza):

   • Objetivo: Bolas unitarias $\ell_p$ donde $p \in (1, 2]$ (y sus normas duales $q \ge 2$).
   • Mecanismo: Un algoritmo simple de exploración-explotación.
     • Exploración: El algoritmo juega vectores de la base estándar $e_i$. Estima el vector medio $\theta^\star$ coordenada a coordenada utilizando la técnica de Mediana de Medias (MoM). Si la matriz de covarianza $\Sigma$ es desconocida, primero estima las varianzas de los vectores de la base.
     • Explotación: Una vez que el error de estimación es suficientemente pequeño en relación con la varianza y el horizonte temporal, el algoritmo se compromete con una acción $\hat{a}$ derivada de la media estimada $\hat{\theta}$, específicamente $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • Innovación Clave: El análisis explota la geometría de la bola $\ell_p$ y la estructura del ruido de parámetros. Los autores demuestran que explorar vectores de la base produce un error de estimación proporcional a $\sqrt{\sigma^2(e_i)}$, lo cual es más ajustado que la cota estándar $\epsilon$ en modelos de ruido aditivo. Esto permite al algoritmo alcanzar cotas de arrepentimiento óptimas que dependen de la estructura de varianza de la distribución de recompensas.

Resultados Clave
El artículo establece tanto cotas superiores como inferiores, demostrando que los algoritmos propuestos son óptimos minimax (hasta factores logarítmicos) para configuraciones específicas.

• Conjuntos de Acciones Finitos Generales ($K$ acciones):

  • Cota Superior: VASE alcanza un arrepentimiento de $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$, donde $M_\sigma$ es una cantidad dependiente de la varianza acotada por $\max_a \sigma^2(a)$.
  • Cota Inferior: Se prueba una cota inferior de $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, mostrando que la cota superior es ajustada hasta factores logarítmicos cuando $\log(K) \approx d$.

• Bolas Unitarias $\ell_p$ ($p \le 2$):

  • Covarianza Conocida: VALEE alcanza un arrepentimiento de $\tilde{O}(d + \sqrt{dT \sigma^2_q})$, donde $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. Esto se demuestra óptimo mediante una cota inferior coincidente de $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$.
  • Covarianza Desconocida: VALEE incurre en un término aditivo adicional, resultando en un arrepentimiento de $\tilde{\O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$. Los autores señalan que este término aditivo surge de la fase de estimación de la varianza.

• Bolas Unitarias $\ell_p$ ($p > 2$):

  • El artículo proporciona una cota inferior de $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$, coincidiendo con las cotas inferiores conocidas para el escenario adversario en estas geometrías.

Significado y Afirmaciones
El artículo afirma resolver un "caso curioso" respecto a los banditos lineales, donde el modelo de ruido aditivo a menudo produce cotas de arrepentimiento peores ($d\sqrt{T}$) que el modelo adversario ($\sqrt{dT}$) para conjuntos de acciones específicos como la bola unitaria $\ell_2$. Los autores demuestran que el modelo de ruido de parámetros se alinea más estrechamente con la intuición de que los modelos estocásticos deberían ser más fáciles que los adversarios.

• Cotas Más Ajustadas: Para bolas $\ell_p$ con $p \le 2$, el modelo de ruido de parámetros permite cotas de arrepentimiento del orden $\sqrt{dT \sigma^2_q}$, que pueden ser significativamente menores que la cota $d\sqrt{T}$ típica de los modelos de ruido aditivo cuando la varianza es pequeña.
• Ventaja Estructural: Los resultados destacan que la linealidad de la realización (no solo de la esperanza) y la capacidad del agente para influir en la varianza son cruciales para lograr estas cotas mejoradas.
• Simplicidad: Sorprendentemente, el arrepentimiento óptimo para bolas $\ell_p$ ($p \le 2$) es alcanzable utilizando un algoritmo de exploración-explotación muy simple (VALEE), en contraste con los complejos algoritmos de diseño óptimo a menudo requeridos en configuraciones de ruido aditivo.

Los autores concluyen que, aunque sus resultados para $p \le 2$ son óptimos (hasta logaritmos) cuando la covarianza es conocida, el caso de covarianza desconocida deja una brecha abierta (el término $T^{1/3}$) que trabajos futuros podrían abordar. También dejan como pregunta abierta el diseño de un algoritmo que coincida con la cota inferior para $p > 2$.