Prior Diffusiveness and Regret in the Linear-Gaussian Bandit

Planteamiento del Problema
El artículo aborda el problema de los bandidos lineales gaussianos, un entorno de toma de decisiones secuenciales donde un jugador selecciona acciones $A_t \in \mathcal{A} \subset \mathbb{R}^d$ para maximizar las recompensas acumuladas. La recompensa en el tiempo $t$ se genera mediante $R_{t+1} = \theta_\star^\top A_t + W_{t+1}$, donde $\theta_\star$ es un vector de parámetros desconocido y $W_{t+1}$ es un ruido gaussiano i.i.d. con varianza $\sigma^2$. El objetivo es minimizar el arrepentimiento bayesiano (Bayesian regret), definido como la diferencia esperada entre la recompensa de la acción óptima y la acción elegida a lo largo de un horizonte $T$, asumiendo una distribución previa $\rho$ sobre $\theta_\star$. Específicamente, los autores se centran en el caso donde $\theta_\star \sim \mathcal{N}(\mu_0, \Sigma_0)$ y el conjunto de acciones es una bola $\ell_2$ escalada de radio $r$.

Metodología
Los autores analizan el muestreo de Thompson (Thompson sampling), un algoritmo de muestreo de la posterior que extrae una estimación del parámetro $\hat{\theta}_t$ de la distribución posterior dada la historia $H_t$ y selecciona la acción que maximiza la recompensa esperada bajo $\hat{\theta}_t$.

Para derivar los límites de arrepentimiento, los autores emplean una descomposición del arrepentimiento instantáneo en dos términos:

1. Término (I): El arrepentimiento incurrido cuando el parámetro muestreado $\hat{\theta}_t$ está cerca del parámetro real $\theta_\star$ (dentro de un evento de alta probabilidad definido por la matriz de precisión de la posterior).
2. Término (II): El arrepentimiento incurrido cuando el parámetro muestreado está lejos del parámetro real.

La innovación técnica central reside en el análisis del Término (I). Los autores introducen un lema de potencial elíptico generalizado (Lema 3). A diferencia de los lemas de potencial elíptico estándar utilizados en la literatura de bandidos lineales (por ejemplo, Abeille & Lazaric, 2017; Dani et al., 2008), que típicamente requieren que la matriz de precisión inicial esté acotada lejos de cero (por ejemplo, $V_0 \succeq I$) y acotan errores cuadráticos, este nuevo lema:

• Permite que la matriz de precisión inicial $V_0$ sea arbitrariamente pequeña (o incluso cero en el límite), acomodando distribuciones previas difusas.
• Introduce un exponente flexible $p \in [0, 1]$ en la sumatoria de las normas.
• Separa explícitamente el límite en un término de determinante logarítmico (que captura la ganancia de información a largo plazo) y un término de traza que involucra la matriz de precisión inicial (que captura el costo inicial de "calentamiento" o burn-in).

El análisis del Término (II) se basa en desigualdades de concentración estándar para distribuciones gaussianas para acotar la probabilidad de grandes desviaciones entre $\hat{\theta}_t$ y $\theta_\star$.

Contribuciones Clave y Resultados
La contribución principal es un nuevo límite de arrepentimiento bayesiano para el muestreo de Thompson en el entorno lineal-gaussiano que desacopla el término de "calentamiento" dependiente de la previa de la tasa de minimax.

1. Límite de Arrepentimiento Mejorado: Los autores demuestran que el muestreo de Thompson logra un arrepentimiento de:
   $$\text{Reg}(T) = \tilde{O}\left( \sigma d \sqrt{T} + d r \sqrt{\text{Tr}(\Sigma_0)} \right)$$
   Aquí, $\sigma d \sqrt{T}$ representa la tasa minimax asintótica, mientras que $d r \sqrt{\text{Tr}(\Sigma_0)}$ representa el costo inicial de reducir la incertidumbre desde la escala de la previa hasta la escala del ruido.

2. Desacoplamiento de Términos: Los límites previos (por ejemplo, Kalkanli & Özgür, 2020) exhibían una dependencia multiplicativa, tal como $\tilde{O}(d \sqrt{T(\sigma^2 + r^2 \text{Tr}(\Sigma_0))})$, donde la difusividad de la previa $\sqrt{\text{Tr}(\Sigma_0)}$ escalaba toda la tasa minimax. El nuevo resultado muestra que, hasta factores logarítmicos, la difusividad de la previa solo añade una constante aditiva al arrepentimiento, independiente del horizonte de tiempo $T$.

3. Límites Inferiores: El artículo establece un límite inferior para cualquier política en este entorno, demostrando que el término de calentamiento $d r \sqrt{\text{Tr}(\Sigma_0)}$ es inevitable para distribuciones previas gaussianas. Esto confirma que la estructura aditiva del límite superior es ajustada (hasta factores logarítmicos) y que la difusividad de la previa no puede eliminarse totalmente del arrepentimiento.

4. Generalización: Los autores señalan que sus resultados pueden extenderse a distribuciones con log-concavidad fuerte y distribuciones de ruido, no limitándose estrictamente al caso gaussiano.

Significado
El artículo afirma que sus resultados resuelven una imprecisión en los límites de arrepentimiento existentes para el muestreo de Thompson. Al demostrar que el término dependiente de la previa es aditivo en lugar de multiplicativo, el trabajo clarifica el papel de la difusividad de la previa: actúa como un costo de "calentamiento" de una sola vez requerido para reducir la incertidumbre al nivel del ruido de observación, tras lo cual el rendimiento del algoritmo está gobernado únicamente por la varianza del ruido $\sigma$ y la dimensión $d$. Esto proporciona una caracterización más precisa de la eficiencia del algoritmo, particularmente en regímenes donde la previa es altamente difusa (gran $\text{Tr}(\Sigma_0)$), mostrando que tal difusividad no degrada permanentemente la tasa de convergencia asintótica. La introducción del lema de potencial elíptico generalizado se presenta como una herramienta que permite un análisis más flexible de problemas de optimización estocástica donde la incertidumbre inicial puede ser ilimitada.