A Broader View of Thompson Sampling

Resumen Técnico: Una Visión Más Amplia de Thompson Sampling

Enunciado del Problema
Thompson Sampling (TS) es una heurística ampliamente utilizada para el problema de la Banda Multi-Armera (MAB), conocida por su éxito empírico y sus cotas teóricas de arrepentimiento. Sin embargo, a diferencia de los límites de confianza superior (UCB) o las políticas del índice de Gittins, el principio de optimización explícito que gobierna el equilibrio de TS entre exploración y explotación permanece opaco. Mientras que Gittins (1979) formuló el MAB bayesiano como un Proceso de Decisión de Markov (MDP) para derivar una política óptima, ese enfoque se basa en recompensas descontadas de horizonte infinito. Esta formulación conduce a un "aprendizaje incompleto" (fallo en identificar el brazo óptimo infinitas veces), lo cual contradice el objetivo de minimización de arrepentimiento de horizonte finito central en la literatura del MAB (Robbins 1952; Lai y Robbins 1985). El artículo aborda la brecha en la comprensión de TS buscando una formulación estacionaria "fiable" que se alinee con la minimización de arrepentimiento de horizonte finito, manteniendo al mismo tiempo la manejabilidad de la programación dinámica.

Metodología
Los autores proponen un marco de estacionarización fiel para replantear el problema no estacionario de minimización de arrepentimiento de horizonte finito como un problema de optimización en línea estacionario.

1. Objetivo de Arrepentimiento Cuadrático: En lugar de minimizar el arrepentimiento acumulado $R_T$ directamente o utilizar recompensas descontadas, los autores introducen la minimización del arrepentimiento cuadrático acumulado $R_2$. Establecen una cota $R_T \leq \sqrt{R_2 \cdot T}$. Minimizar la suma de horizonte infinito de los arrepentimientos cuadrados $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ garantiza que la política alcance la tasa óptima de arrepentimiento $O(\sqrt{T})$ mientras proporciona un objetivo estacionario.
2. Ecuación de Bellman Estacionaria: Este nuevo objetivo produce una ecuación de Bellman estacionaria para la función de valor $V(\pi_t)$ (el arrepentimiento cuadrado futuro mínimo):
   $$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$$
   A diferencia del índice de Gittins (que maximiza la recompensa descontada lineal), esta minimización es cuadrática en las probabilidades de acción, lo que conduce a una política óptima aleatorizada en lugar de una determinista.
3. Forma de Optimización en Línea: Mediante un cambio de variables centrado en la recompensa esperada de la siguiente ronda $x_t$, los autores derivan que la política óptima en $R_2$ ($Q_{R2}$) adopta la forma de un problema de optimización en línea:
   $$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$$
   Aquí, el primer término representa la explotación instantánea (codicia), y el segundo término es una regularización lineal que representa la exploración. El regularizador $\nu_{R2}(\pi_t)$ se deriva de la ecuación de Bellman y mide la tensión entre exploración y explotación (la diferencia en el valor futuro entre tirar los brazos).
4. Reinterpretación de Thompson Sampling: Los autores demuestran que Thompson Sampling admite la misma forma exacta de optimización en línea:
   $$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$$
   Sin embargo, su regularizador $\nu_{TS}(\pi_t)$ es la covarianza biserial entre la brecha de recompensa ($\theta_1 - \theta_2$) y la identidad del brazo óptimo ($\text{sign}(\theta_1 - \theta_2)$). Este regularizador mide la incertidumbre sobre qué brazo es mejor, en lugar de la tensión entre la recompensa inmediata y el valor futuro.

Contribuciones Clave

• Estacionarización Fiel: El artículo introduce una formulación estacionaria (minimización del arrepentimiento cuadrático) que preserva la esencia de la minimización de arrepentimiento de horizonte finito, cerrando la brecha entre el muestreo heurístico y la programación dinámica basada en principios.
• Unificación Estructural: Revela que tanto Thompson Sampling como la política óptima de Bellman ($Q_{R2}$) son instancias de algoritmos de optimización en línea que intercambian codicia contra un regularizador.
• Identificación del Mecanismo: El artículo identifica el mecanismo específico que impulsa a TS: regulariza la codicia basándose en la incertidumbre (covarianza biserial), mientras que la política óptima regulariza basándose en la tensión (diferencia de valor futuro).
• Mejora de la Política: Aprovechando el marco de Bellman, los autores proponen un paso estándar de mejora de política para TS. Al evaluar la función de valor de TS e insertarla nuevamente en la ecuación de Bellman, derivan una política mejorada ($Q_{TS'}$) que utiliza un regularizador basado en la tensión.

Resultados

• Brecha de Rendimiento: Los experimentos numéricos en bandas gaussianas y de Bernoulli muestran que la política óptima en $R_2$ ($Q_{R2}$) logra un arrepentimiento acumulado significativamente menor que Thompson Sampling. La brecha se atribuye a que el regularizador de TS es una medida de incertidumbre que falla en capturar la "tensión" cuando el brazo líder es incierto pero el brazo subóptimo está sobre-explotado.
• Muestreo Dirigido por Información (IDS): El artículo encuentra que IDS, otra heurística, comparte la misma estructura de regularizador basado en la tensión que $Q_{R2}$ y tiene un rendimiento casi idéntico a la política óptima de Bellman, cerrando las perspectivas de teoría de la información y programación dinámica.
• Mejora de Un Paso: Un solo paso de mejora de política aplicado a Thompson Sampling cierra aproximadamente el 90% de la brecha de rendimiento entre TS y la referencia óptima de Bellman. Esta mejora transforma efectivamente el regularizador de TS de una medida de incertidumbre a una medida de tensión.
• Propiedad Estructural en el Caso de K Brazos: En el escenario de $K$ brazos, la política óptima de Bellman (y la TS mejorada) asigna probabilidad positiva a lo sumo dos brazos en cualquier ronda, mientras que la TS estándar puede asignar probabilidad positiva a todos los brazos. El paso de mejora de política otorga a TS esta dispersión estructural.

Significado
El artículo afirma proporcionar una "visión más amplia" de Thompson Sampling al replantearlo como un algoritmo de optimización en línea. Esta lente:

1. Explica la Heurística: Aclara que TS equilibra exploración y explotación regularizando la codicia con una medida de incertidumbre residual.
2. Identifica Limitaciones: Señala que la dependencia de TS de la incertidumbre en lugar de la tensión conduce a un comportamiento subóptimo en regímenes específicos (por ejemplo, cuando el brazo óptimo es incierto pero el brazo subóptimo está claramente sobre-explotado).
3. Permite Mejora Basada en Principios: Ofrece un marco riguroso para mejorar los algoritmos de muestreo posterior. Al alinear el regularizador con la medida de tensión óptima de Bellman, los autores demuestran que TS puede mejorarse significativamente con una sobrecarga computacional mínima (un solo paso de iteración de política), acercándolo al óptimo teórico sin abandonar su naturaleza basada en muestreo.