Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling

Este trabajo propone dos algoritmos basados en Thompson sampling (PE-GP-TS y HP-GP-TS) para la selección adaptativa de priores en banditos de procesos gaussianos, estableciendo límites teóricos de arrepentimiento y demostrando su eficacia mediante experimentos sintéticos y del mundo real.

Lo esencial

Imagina que eres un chef intentando crear el plato más delicioso del mundo, pero no tienes una receta. Solo tienes una lista de posibles estilos de cocina (prioris): italiano, japonés, mexicano, etc. Cada vez que pruebas un ingrediente (un "brazo" en el lenguaje de la inteligencia artificial), recibes una retroalimentación (el sabor), pero el sabor es un poco impredecible porque hay ruido en tu paladar.

El problema es que no sabes cuál es el estilo de cocina correcto (el "prior" verdadero). Si te equivocas de estilo, desperdiciarás muchos ingredientes antes de encontrar el plato perfecto.

Este paper presenta dos nuevas formas inteligentes de navegar este caos para encontrar el mejor plato lo más rápido posible, sin desperdiciar ingredientes.

El Problema: La Adivinanza del Chef

En el mundo de la inteligencia artificial, esto se llama optimización de funciones de caja negra. Quieres encontrar el punto máximo (el plato más sabroso) sin saber cómo funciona la cocina.

• El Prior (La Hipótesis): Es tu suposición inicial. "Creo que el plato será picante" o "Creo que será suave".
• El Dilema: La mayoría de los métodos anteriores asumían que el chef ya sabía la receta exacta. Pero en la vida real, ¡nadie sabe la receta! Los chefs suelen adivinar los ingredientes basándose en lo que han probado antes (estimación de máxima verosimilitud), pero esto no tiene garantías matemáticas de que funcione.

Las Dos Soluciones Propuestas

Los autores proponen dos algoritmos (dos estrategias de chef) para resolver esto usando una técnica llamada Muestreo de Thompson (que es como probar un poco de todo con un toque de suerte controlada).

1. PE-GP-TS: "El Chef Eliminador"

Imagina que tienes 10 chefs diferentes en tu cocina, cada uno con un estilo de cocina distinto (un "prior").

• Cómo funciona: El algoritmo les da un turno a todos para cocinar. Si un chef propone un plato que sabe terriblemente mal (muy diferente a lo que el algoritmo esperaba), ¡se le quita el delantal!
• La analogía: Es como un concurso de talentos donde eliminas a los concursantes que fallan demasiado.
• La ventaja: Elimina las opciones obvias y malas rápidamente. Sin embargo, a veces es un poco "optimista" (cree que un plato malo podría ser bueno por pura suerte) y puede tardar un poco más en descartar a los chefs que son simplemente "pesimistas" (nunca se les da la oportunidad de cocinar).

2. HP-GP-TS: "El Chef Probabilista"

Esta es la estrategia más sofisticada. En lugar de eliminar a los chefs, el algoritmo mantiene una lista de confianza para cada uno.

• Cómo funciona: Imagina que tienes una pizarra con porcentajes. Al principio, todos los estilos de cocina tienen un 10% de probabilidad de ser el correcto.
  • Si el estilo japonés funciona bien, su porcentaje sube al 20%.
  • Si el estilo italiano falla, su porcentaje baja al 5%.
  • El algoritmo elige qué estilo usar basándose en estos porcentajes, pero también se da la oportunidad de probar los menos probables solo para estar seguro.
• La ventaja: Es como tener un "cerebro colectivo". Aprende continuamente cuál es el estilo correcto sin descartar a nadie bruscamente. Es más eficiente y comete menos errores a largo plazo.

¿Por qué es importante? (Los Resultados)

Los autores probaron sus métodos en dos tipos de escenarios:

1. Datos Sintéticos: Como un laboratorio de cocina donde controlan todo.
2. Datos del Mundo Real: Como medir la temperatura en sensores de Intel, el tráfico en autopistas de California o la lluvia en el noroeste del Pacífico.

Los hallazgos clave:

• Menos desperdicio: Sus métodos (especialmente el "Chef Probabilista" o HP-GP-TS) encontraron el plato perfecto (el punto óptimo) con mucha menos "prueba y error" que los métodos anteriores.
• No importa cuántas opciones tengas: Lo más sorprendente es que, a diferencia de otros métodos que se vuelven lentos y torpes cuando hay muchas opciones de cocina (muchos "priors"), el método HP-GP-TS mantiene su velocidad y eficiencia incluso si tienes 100 estilos de cocina diferentes.
• Aprendizaje real: El algoritmo no solo encuentra el plato, sino que realmente aprende cuál es el estilo de cocina correcto. En los experimentos, acertó en el estilo correcto más del 60% de las veces, mientras que otros métodos apenas llegaban al 17%.

En Resumen

Este paper nos dice que, cuando no sabemos las reglas del juego (la función desconocida), no debemos adivinar ciegamente ni eliminar opciones de forma brusca.

En su lugar, debemos usar un enfoque probabilístico y adaptativo: mantener una lista de posibilidades, actualizarla con cada nueva prueba y dejar que la inteligencia artificial "sienta" poco a poco cuál es la dirección correcta. Es como aprender a cocinar no siguiendo una receta fija, sino ajustando la sal y el fuego en tiempo real hasta que el plato sea perfecto.

Resumen técnico

Resumen Técnico: Selección Adaptativa de Priors en Bandits de Procesos Gaussianos con Muestreo de Thompson

1. Planteamiento del Problema

El problema se centra en la optimización de funciones de caja negra mediante Bandits de Procesos Gaussianos (GP-Bandits). En este marco, un agente selecciona secuencialmente "brazos" (puntos de entrada) para maximizar la recompensa acumulada, asumiendo que la función de recompensa subyacente se distribuye según un Proceso Gaussiano (GP).

• El Desafío Principal: La mayoría de los resultados teóricos asumen que el prior del GP (definido por su función de media y su kernel) es conocido. Sin embargo, en aplicaciones prácticas, este prior es desconocido.
• Limitaciones de Métodos Actuales:
  • Los practicantes suelen usar Estimación de Máxima Verosimilitud (MLE) para seleccionar hiperparámetros, lo cual carece de garantías teóricas en entornos de toma de decisiones secuenciales.
  • Métodos existentes como PE-GP-UCB (Prior-Elimination GP-UCB) utilizan la eliminación de priors basada en cotas de confianza superiores (UCB). Sin embargo, estos métodos son "doble optimistas" (optimismo en la selección del brazo y en la selección del prior), lo que puede llevar a una sobre-exploración costosa.
  • Trabajos previos con Muestreo de Thompson (TS) y priors mixtos (MixTS) presentan problemas técnicos en sus demostraciones de límites de arrepentimiento (regret) en configuraciones lineales.

2. Metodología Propuesta

Los autores proponen dos algoritmos basados en Muestreo de Thompson (GP-TS) para realizar la selección conjunta de priors y la minimización del arrepentimiento, eliminando la necesidad de un prior conocido.

A. PE-GP-TS (Prior-Elimination GP-TS)

• Concepto: Es una extensión del algoritmo PE-GP-UCB que reemplaza la regla de selección doblemente optimista (maximización de UCB sobre brazos y priors) por muestreo posterior.
• Mecanismo:
  1. Para cada prior activo $p \in P_t$, se muestrea una función $\tilde{f}_{t,p}$ del GP posterior.
  2. Se selecciona el brazo y el prior que maximizan esta función muestreada: $(x_t, p_t) = \arg\max_{x, p} \tilde{f}_{t,p}(x)$.
  3. Eliminación: Se calcula el error de predicción $\eta_t = y_t - \mu_{t, p_t}(x_t)$. Si la suma acumulada de errores de un prior supera un umbral estadístico ($V_t$), ese prior se elimina del conjunto activo.
• Ventaja: Reduce una capa de optimismo en comparación con PE-GP-UCB, mitigando la sobre-exploración.

B. HP-GP-TS (HyperPrior GP-TS)

• Concepto: Un enfoque totalmente bayesiano que utiliza un esquema de muestreo de dos niveles (bi-level).
• Mecanismo:
  1. Se mantiene una hiper-posterior $P_t$ sobre el conjunto de priors.
  2. En cada paso, se muestrea un prior $p_t$ de la hiper-posterior.
  3. Luego, se muestrea una función $\tilde{f}_t$ del GP condicional a $p_t$.
  4. Se selecciona el brazo $x_t$ maximizando $\tilde{f}_t$.
  5. Se actualiza la hiper-posterior $P_{t+1}$ calculando la verosimilitud de la observación $y_t$ bajo cada prior posible.
• Ventaja: Evita la exploración costosa al seleccionar priors probables en lugar de priors "optimistas". Es computacionalmente más eficiente que métodos que promedian sobre la hiper-posterior (como SCoreBO), ya que solo requiere una muestra.

3. Contribuciones Clave

1. Algoritmos Nuevos: Propuesta de PE-GP-TS y HP-GP-TS para GP-Bandits con priors desconocidos.
2. Análisis Teórico:
   • Se establecen límites superiores de arrepentimiento (regret bounds) para ambos algoritmos.
   • PE-GP-TS: El límite es del orden $O(\sqrt{T \log T |P| \hat{\gamma}_T})$, donde $\hat{\gamma}_T$ es la ganancia de información máxima en el peor caso. Incluye un término adicional no acotado relacionado con la incertidumbre del brazo óptimo bajo el prior correcto.
   • HP-GP-TS: El límite es del orden $O(\sqrt{T \log T \bar{\gamma}_T})$, donde $\bar{\gamma}_T$ es la ganancia de información promedio. Esto es teóricamente superior si los priors tienen complejidades diferentes y el hiper-prior favorece priors simples.
3. Crítica a la Literatura: Se identifica y detalla un error técnico en la demostración del límite de arrepentimiento del algoritmo MixTS (Hong et al., 2022b) en el caso lineal, específicamente en la manipulación de eventos condicionales que invalidan la igualdad en distribución necesaria para el muestreo de Thompson.
4. Evaluación Experimental: Validación exhaustiva con datos sintéticos y del mundo real.

4. Resultados Experimentales

Los algoritmos se evaluaron en tres configuraciones sintéticas (diferentes kernels, diferentes longitudes de escala y subespacios) y tres conjuntos de datos reales (Intel Berkeley, PeMS, PNW Precipitation).

• Rendimiento de Regret:
  • HP-GP-TS y EEI (Expected Improvement Bayesiano) mostraron consistentemente el menor arrepentimiento, acercándose al rendimiento de un "oráculo" que conoce el prior verdadero.
  • PE-GP-TS superó a PE-GP-UCB en todos los experimentos, confirmando que reducir el optimismo mejora el rendimiento.
  • SCoreBO tuvo un regret significativamente más alto en la mayoría de los casos, a pesar de reducir la incertidumbre del prior rápidamente.
• Selección de Prior:
  • HP-GP-TS selecciona el prior correcto con mayor frecuencia (ej. ~63% de precisión en experimentos de kernels) en comparación con métodos de eliminación (PE-GP-TS ~17%).
  • Los métodos de eliminación (PE) a menudo eliminan priors incorrectos pero también fallan en distinguir entre kernels similares (RBF, Matérn, RQ), mostrando sesgos hacia kernels menos suaves (Matérn 3/2) debido a la sobre-exploración.
• Escalabilidad con $|P|$ (Número de Priors):
  • El regret de HP-GP-TS no aumenta significativamente con el número de priors $|P|$ en los experimentos, manteniéndose cerca del oráculo.
  • En contraste, los métodos de eliminación (PE-GP-TS/UCB) muestran un aumento en el regret proporcional a $\sqrt{|P|}$ en experimentos de subespacios, debido a la dificultad de eliminar priors incorrectos cuando hay muchos candidatos similares.

5. Significado e Impacto

Este trabajo es significativo porque cierra la brecha entre la teoría de optimización bayesiana y la práctica, donde el prior nunca se conoce con certeza.

• Eficiencia: Demuestra que el Muestreo de Thompson es superior a los métodos UCB (como PE-GP-UCB) en escenarios de selección de priors, al evitar la sobre-exploración innecesaria.
• Robustez Teórica: Proporciona los primeros límites de regret rigurosos para GP-TS con selección adaptativa de priors, corrigiendo suposiciones erróneas en trabajos previos.
• Aplicabilidad: Los resultados en datos reales (sensores de temperatura, tráfico, precipitación) confirman que estos algoritmos son viables para problemas del mundo real donde la distribución de los datos puede variar y el modelo subyacente debe adaptarse dinámicamente.

En conclusión, HP-GP-TS se presenta como el método más robusto y eficiente, logrando un equilibrio óptimo entre la exploración del espacio de priors y la explotación de la función objetivo, sin depender de la suposición de un prior conocido.