Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards

Resumen Técnico: Optimalidad Asintótica de Thompson Sampling para Bandidos Aversos al Riesgo con Recompensas Sub-Gaussianas

Planteamiento del Problema
El artículo aborda el problema de los Bandidos de Múltiples Brazos (MAB, por sus siglas en inglés) bajo objetivos de aversión al riesgo. A diferencia de los entornos estándar de MAB que maximizan la recompensa esperada, los entornos de aversión al riesgo buscan optimizar funcionales de riesgo generales $\rho$ (por ejemplo, el Valor en Riesgo Condicional (CVaR), media-varianza, la razón de Sharpe o medidas de riesgo de distorsión). El desafío específico abordado es el análisis teórico de $\rho$-NPTS (un algoritmo de Thompson Sampling no paramétrico propuesto por Chang y Tan [2022]). Si bien Chang y Tan demostraron la optimalidad de instancia para un compañero paramétrico ($\rho$-MTS), dejaron como problema abierto la optimalidad del $\rho$-NPTS no paramétrico.

El obstáculo fundamental es que $\rho$-NPTS construye un posterior de Dirichlet donde el tamaño efectivo del alfabeto crece con el número de observaciones ($N_k$). La aplicación directa de los resultados de los límites de cola existentes produce un prefactor super-exponencial de $(N_k)^{N_k/2}$, lo que impide la demostración de límites de arrepentimiento (regret) logarítmicos. Además, los resultados previos a menudo requerían condiciones fuertes como la condición de "dominancia" (para métodos paramétricos) o la continuidad de Lipschitz del funcional de riesgo (para algoritmos de tipo UCB), excluyendo funcionales importantes no Lipschitzianos como la razón de Sharpe.

Metodología
Los autores introducen $\rho$-NPTSSG, una variante sin ancla del algoritmo de Thompson Sampling no paramétrico diseñada para distribuciones con densidad acotada y colas sub-gaussianas ($P(B, \sigma)$). La innovación técnica central es un lema de discretización (y su análogo truncado para colas sub-gaussianas) que proyecta el posterior de Dirichlet de alfabeto creciente sobre una rejilla fija.

1. Discretización y Agregación:
   El artículo define una rejilla fija $G_M$ de tamaño $M$. Para cualquier secuencia de recompensas observadas, la medida empírica se proyecta sobre esta rejilla mediante la agregación de los pesos de Dirichlet correspondientes a las observaciones que caen dentro de la misma celda de la rejilla.

   • Perspectiva Clave: Debido a la propiedad de agregación de la distribución de Dirichlet, los pesos proyectados en las celdas ocupadas siguen una distribución de Dirichlet con una dimensión fija ($M^+ \le M$), independientemente del tamaño de la muestra $N_k$.
   • Consecuencia: Esta proyección limita el prefactor polinomial en los límites de cola en un grado de $(M-1)/2$, el cual es independiente de $N_k$. Esto rompe la barrera super-exponencial que bloqueaba las demostraciones previas.

2. Variantes del Algoritmo:

   • $\rho$-NPTS (Soporte Acotado): Opera sobre distribuciones con soporte en $[0, 1]$ y densidad acotada. Utiliza un ancla fija (el extremo derecho) y una rejilla uniforme.
   • $\rho$-NPTSSG (Sub-Gaussiana): Opera sobre distribuciones en $\mathbb{R}$ con densidad acotada y colas sub-gaussianas. Elimina el ancla fijo (usando inicialización round-robin en su lugar) y emplea un lema de discretización truncada. Este lema utiliza una rejilla centrada en la media empírica con un ancho que se reduce a medida que la muestra crece, mientras trunca las colas para controlar la probabilidad de desbordamiento.

3. Análisis de Arrepentimiento (Regret):
   La prueba sigue una descomposición estándar del arrepentimiento en términos donde el algoritmo extrae un brazo subóptimo con un puntaje de Thompson "alto" frente a uno "bajo".

   • Límite Superior: Utiliza el lema de discretización para aplicar los límites de cola de Chang y Tan [2022] a la proyección de la rejilla fija. La continuidad de $\rho$ (específicamente la continuidad $D_\infty$) asegura que el riesgo de la medida proyectada aproxime el riesgo real.
   • Límite Inferior: Coincide con el límite inferior dependiente de la instancia establecido por Chang y Tan [2022], el cual se basa en el problema de minimización de la divergencia de Kullback-Leibler (KL) $K^\rho_{\inf}$.

Contribuciones Clave

1. Resolución del Problema Abierto: El artículo demuestra que $\rho$-NPTSSG logra un arrepentimiento de optimalidad de instancia de $\sum_{k: \Delta^\rho_k > 0} \frac{\Delta^\rho_k \log n}{K^\rho_{\inf}(\nu_k, r^\rho_1)} + o(\log n)$ para cualquier funcional de riesgo continuo $\rho$ en la clase de distribuciones con densidad acotada y colas sub-gaussianas.
2. Condiciones más Débiles: El resultado requiere únicamente la continuidad del funcional de riesgo $\rho$ (específicamente con respecto a la métrica de Lévy–Prokhorov). Esto es estrictamente más débil que:
   • La condición de "dominancia" requerida para el $\rho$-MTS paramétrico.
   • La condición de Lipschitz requerida para los algoritmos de tipo UCB.
     Esto permite las primeras garantías de optimalidad de instancia para funcionales no Lipschitzianos, como la razón de Sharpe, sin asumir distribuciones de recompensa paramétricas.
3. Lema de Discretización: El artículo introduce un lema técnico que controla un posterior de Dirichlet de alfabeto creciente a una resolución fija. Este lema es de potencial interés independiente para cualquier problema que involucre procesos de Dirichlet con soporte creciente.
4. Extensión Sub-Gaussiana: Los autores extienden los resultados de soporte acotado a la clase más amplia de distribuciones sub-gaussianas (incluyendo brazos gaussianos) mediante un enfoque de discretización truncada, eliminando la necesidad de un intervalo de soporte preespecificado.

Resultados

• Teorema 1 (Soporte Acotado): Establece la optimalidad asintótica para $\rho$-NPTS en $P(B)$ bajo la continuidad únicamente.
• Teorema 2 (Sub-Gaussiano): Establece la optimalidad asintótica para $\rho$-NPTSSG en $P(B, \sigma)$.
• Validación Experimental: El artículo presenta cuatro experimentos que validan la teoría:
  1. $\rho$-NPTS sigue el límite inferior de optimalidad de instancia para CVaR en brazos Beta, superando al baseline Risk-LCB (que tiene una garantía de $\log^2 n$).
  2. $\rho$-NPTS logra un arrepentimiento de $O(\log n)$ para la razón de Sharpe en brazos de normal truncada, un caso donde ningún algoritmo previo proporcionó garantías debido a su naturaleza no Lipschitziana.
  3. El algoritmo maneja funcionales compuestos (por ejemplo, $0.5 \text{CVaR} + 0.5 \text{Sharpe}$) sin modificaciones.
  4. $\rho$-NPTSSG converge al límite inferior de optimalidad de instancia para brazos gaussianos, igualando el rendimiento del algoritmo especializado Normal-Gamma Thompson Sampling (Shah et al. [2025]) sin asumir recompensas gaussianas.

Significancia y Reivindicaciones
El artículo afirma resolver el estatus teórico del Thompson Sampling no paramétrico para bandidos con aversión al riesgo. Demuestra que estos algoritmos no son meramente heurísticas empíricas, sino que son provadamente óptimos asintóticamente.

La significancia radica en la relajación de los supuestos:

• Los profesionales pueden usar observaciones puras sin preespecificar una rejilla de recompensa o ajustar un tamaño de alfabeto.
• El método se aplica a una clase de funcionales de riesgo (incluyendo la razón de Sharpe) y clases de distribución (sub-gaussianas) estrictamente más amplia que los métodos óptimos anteriores.
• El resultado subsume el trabajo concurrente de Shah et al. [2025] al proporcionar una constante de optimalidad de instancia más aguda para la razón de Sharpe sin requerir prioris conjugadas o supuestos paramétricos.

Los autores señalan que el supuesto de densidad acotada es necesario para los límites de probabilidad de las celdas utilizados en la prueba y no se cumple para distribuciones con masas puntuales (por ejemplo, Bernoulli), para las cuales el $\rho$-MTS paramétrico sigue siendo la solución complementaria. Las direcciones de trabajo futuro identificadas incluyen bandidos contextuales, recompensas de cola pesada y distribuciones discretas.