First Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

Resumen Técnico: Primeros Límites de Arrepentimiento en el Peor Caso para el Muestreo de Thompson Combinatorio en Semi-Bandidos Dormidos

Definición del Problema
Este artículo aborda el problema del muestreo de Thompson combinatorio (CTS) en el contexto de semi-bandidos estocásticos con "brazos dormidos". En este escenario, un agente selecciona repetidamente un "super-brazo" (un subconjunto factible de a lo sumo $m$ brazos base) de un conjunto dinámicamente cambiante de brazos disponibles extraídos de un grupo de $N$ brazos base. La disponibilidad de los brazos puede variar de manera adversaria a lo largo del tiempo, un escenario motivado por aplicaciones de redes como el enrutamiento en mallas inalámbricas, donde la disponibilidad de los enlaces fluctúa debido a la congestión o fallos. El agente observa recompensas individuales para los brazos seleccionados (retroalimentación de semi-bandido) y busca maximizar la recompensa acumulada, o equivalentemente, minimizar el arrepentimiento frente a un oráculo que selecciona el subconjunto factible óptimo dada la disponibilidad actual.

Los autores identifican tres brechas críticas en la literatura existente sobre CTS para este problema:

1. Falta de Garantías en el Peor Caso: Los análisis previos de CTS en semi-bandidos fueron predominantemente dependientes del problema (escalando con los huecos de recompensa $\Delta$), fallando en proporcionar límites significativos de arrepentimiento en el peor caso.
2. Disponibilidad Adversaria: Las garantías teóricas existentes para el muestreo de Thompson generalmente asumieron una disponibilidad estocástica de los brazos, careciendo de análisis para una disponibilidad que varía de manera adversaria.
3. Suboptimalidad Empírica: El CTS con priores gaussianos (CTS-G), a pesar de su atractivo teórico, ha demostrado históricamente un rendimiento empírico más débil en comparación con los métodos de Límite Superior de Confianza (UCB) y el CTS con priores Beta (CTS-B).

Metodología y Algoritmos
El artículo propone dos enfoques algorítmicos principales:

1. Muestreo de Thompson Combinatorio con Priores Gaussianos (CTS-G):
   Esta es una adaptación directa del muestreo de Thompson estándar al escenario de semi-bandidos dormidos. En cada ronda, el algoritmo mantiene estimaciones de medias empíricas para cada brazo y extrae muestras de posteriores gaussianas independientes para cada brazo base. Luego selecciona el super-brazo que maximiza la suma de estas muestras dentro del conjunto factible actual.

2. Aprendizaje Combinatorio con una Semilla Gaussiana Única (CL-SG):
   Para abordar las limitaciones teóricas y empíricas del CTS-G, los autores proponen CL-SG. Esta variante introduce un mecanismo de coordinación: en lugar de extraer ruido independiente para cada brazo, se extrae una única semilla gaussiana compartida $w_t \sim \mathcal{N}(0, 1)$ por ronda. Esta semilla se utiliza para perturbar simultáneamente las estimaciones empíricas de todos los brazos base. Este diseño busca coordinar la exploración entre los brazos y reducir la inflación de varianza inherente al muestreo independiente.

Contribuciones Clave y Resultados Teóricos

• Primera Análisis en el Peor Caso de CTS-G:
  El artículo proporciona el primer análisis frecuentista de arrepentimiento en el peor caso para el CTS-G estándar en semi-bandidos dormidos.

  • Límite Superior: Los autores prueban un límite superior de $\tilde{O}(m\sqrt{NT})$.
  • Límite Inferior: Establecen un límite inferior coincidente de $\tilde{\Omega}(m\sqrt{NT})$, demostrando que el CTS-G es óptimo en el peor caso hasta factores logarítmicos.
  • Estrategia de Prueba: El análisis se aparta de los métodos tradicionales basados en huecos. Utiliza un argumento de "muestra fantasma" y un análisis refinado de anti-concentración para estimaciones gaussianas correlacionadas para manejar la no observabilidad del super-brazo óptimo y las restricciones de factibilidad dinámicas.

• Límites Mejorados mediante CL-SG:
  Los autores muestran que el CTS-G estándar sufre un factor extra de $\sqrt{m}$ en su límite de arrepentimiento debido a la inflación de varianza requerida para controlar la probabilidad de seleccionar el conjunto óptimo cuando los brazos se muestrean independientemente.

  • Límite Superior: Al utilizar una única semilla compartida, CL-SG logra un límite de arrepentimiento en el peor caso estrictamente mejorado de $\tilde{O}(\sqrt{mNT})$.
  • Límite Inferior: Se prueba un límite inferior coincidente de $\Omega(\sqrt{mNT})$, estableciendo que CL-SG alcanza la tasa minimax-óptima para esta clase de problemas.
  • Mecanismo: La semilla compartida evita la necesidad de que la varianza escale con $m$ para mantener una probabilidad de anti-concentración constante para la suma de errores, eliminando así el factor $\sqrt{m}$ extrínseco.

Resultados Experimentales
Los autores evalúan CL-SG frente a líneas base sólidas, incluyendo CTS-G, CTS-B, BG-CTS y CombUCB, utilizando dos configuraciones:

1. Red Sintética: Una malla inalámbrica de 16 nodos con recompensas Bernoulli.
2. Red del Mundo Real: Trazas del conjunto de datos UCSB MeshNet que involucran disponibilidad de enlaces variable en el tiempo.

Los resultados promediados sobre 100 ejecuciones demuestran que CL-SG supera consistentemente a CTS-G, CTS-B y CombUCB en términos de arrepentimiento acumulado. Los experimentos también indican que CL-SG es robusto al parámetro de exploración $\gamma$, logrando un bajo arrepentimiento incluso con valores de $\gamma$ más grandes donde CTS-G sufre de exploración excesiva.

Significado
El artículo afirma resolver un problema abierto de larga data al establecer las primeras garantías de arrepentimiento en el peor caso para el muestreo de Thompson en semi-bandidos combinatorios con brazos dormidos adversarios. Al cerrar la brecha entre la teoría y la práctica, el trabajo demuestra que una modificación simple al mecanismo de muestreo (utilizando una semilla compartida) puede producir tanto límites teóricos más ajustados como un rendimiento empírico superior. Los autores proporcionan implementaciones de código abierto para asegurar la reproducibilidad y sentar las bases para futuras investigaciones sobre el equilibrio óptimo entre aleatoriedad y exploración en la optimización combinatoria.