Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

1. Planteamiento del Problema

El artículo aborda el problema de la Optimización de Bandidos con Procesos Gaussianos (GP), específicamente en un entorno no bayesiano (donde la función es fija pero desconocida y reside en un Espacio de Hilbert de Núcleo Reproductor, o RKHS). El objetivo es seleccionar secuencialmente puntos $x_t$ para maximizar una función costosa de caja negra $f(x)$ basándose en observaciones ruidosas $y_t = f(x_t) + \epsilon_t$.

El rendimiento se mide mediante el arrepentimiento acumulado $R_T = \sum_{t=1}^T (f(x^*) - f(x_t^+))$, donde $x^*$ es el óptimo global y $x_t^+$ es el mejor punto reportado por el algoritmo hasta la iteración $t$.

El Desafío Central:
Si bien el algoritmo de Mejora Esperada (EI) es una heurística popular para la Optimización Bayesiana debido a su simplicidad, sus propiedades teóricas de convergencia en el entorno ruidoso han permanecido como una pregunta abierta.

• En entornos sin ruido, el "actual" (el mejor valor actual) es simplemente el valor máximo observado, que es monótono.
• En entornos ruidosos, el actual se define típicamente como el máximo de la media predictiva del GP ($\mu_t^+$) o el máximo de la observación ruidosa ($y_t^+$).
• A diferencia del caso sin ruido, la media predictiva del GP $\mu_t^+$ no es monótona a lo largo del tiempo. Esta falta de monotonía hace que el análisis teórico estándar (que depende de acotar el arrepentimiento mediante la monotonía del actual) sea extremadamente difícil. Trabajos anteriores o requerían conocer parámetros desconocidos (como el límite de la norma del RKHS $B$ y la sub-Gaussianidad del ruido $R$) o utilizaban actuales no estándar que requerían pasos costosos de optimización global.

2. Metodología

Los autores proponen dos algoritmos principales para abordar estas brechas teóricas y prácticas.

A. GP-EI con Actual Estándar

La primera contribución es un análisis riguroso de un algoritmo estándar GP-EI donde el actual se define como el máximo de la media predictiva del GP sobre los puntos observados:
$$\xi_t = \mu_t^+ = \max_{x_i \in D_{t-1}} \mu_{t-1}(x_i)$$

• Función de Adquisición: El algoritmo selecciona el siguiente punto $x_t$ maximizando la Mejora Esperada:
  $$\alpha_{EI}(x) = \mathbb{E}[\max\{0, f(x) - \mu_t^+\} | D_t]$$
  Esto se calcula en forma cerrada utilizando la función $\rho(u, v) = u\Phi(u/v) + v\phi(u/v)$.
• Escala Variable en el Tiempo: Para manejar el ruido y asegurar la convergencia sin conocer la norma del RKHS ($B$) ni el parámetro de ruido ($R$), el algoritmo utiliza un parámetro de escala variable en el tiempo $\omega_t = \sqrt{\gamma_{t-1} + 1 + \ln(1/\delta)}$, donde $\gamma_t$ es la ganancia máxima de información.
• Innovación Teórica Clave: Los autores superan la no monotonía de $\mu_t^+$ explotando la monotonía de la función de varianza ($\sigma_t(x)$ disminuye a medida que $t$ aumenta). Descomponen el arrepentimiento instantáneo y acotan la suma de los "términos de mejora" utilizando esta propiedad de varianza, una técnica no aplicada previamente a la optimización de bandidos GP de esta manera.

B. Improved-GP-EI

Para abordar las limitaciones del GP-EI estándar (específicamente, que el límite de arrepentimiento no es siempre sublineal para núcleos Matérn y que el parámetro de escala $\omega_t$ crece demasiado rápido, causando exploración innecesaria), los autores proponen Improved-GP-EI.

• Inspiración: Adaptado del algoritmo $\pi$-GP-UCB (Janz et al., 2020).
• Estrategia de Partición: El espacio de búsqueda se partitiona en hipercubos (una cobertura). Se ajusta un GP independiente en cada hipercubo utilizando solo datos locales.
• Escala Global: En lugar de un $\omega_t$ variable en el tiempo, utiliza una escala global fija $\omega_T = \sqrt{\ln(T)\ln\ln(T)}$ que crece solo polilogarítmicamente.
• Mecanismo: En cada paso, el algoritmo selecciona un punto maximizando la EI dentro del hipercubo específico que contiene al mejor candidato actual, localizando efectivamente la optimización.

3. Contribuciones Clave

1. Primeras Garantías Teóricas para GP-EI Estándar:
   El artículo proporciona la primera prueba de que GP-EI con un actual estándar ($\xi = \mu_t^+$) converge en el entorno ruidoso.

   • Límite de Arrepentimiento: El arrepentimiento acumulado está acotado por $O(\gamma_T \sqrt{T})$.
   • Independencia de Parámetros: Crucialmente, el algoritmo no requiere conocimiento del límite de la norma del RKHS ($B$) ni del parámetro de sub-Gaussianidad del ruido ($R$), que típicamente son desconocidos en aplicaciones del mundo real.

2. Algoritmo Improved-GP-EI:
   Una nueva variante que logra tasas de convergencia más rápidas para núcleos Matérn.

   • Límite de Arrepentimiento: Para núcleos Matérn con suavidad $\nu > 1$, el arrepentimiento es $\tilde{O}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$. Esto es sublineal para todo $\nu > 1$ y $d \geq 1$, mejorando las limitaciones del GP-EI estándar.
   • Eficiencia: Al utilizar una estrategia de partición y un parámetro de escala polilogarítmico, evita el crecimiento rápido de la escala de varianza observado en métodos anteriores, reduciendo la exploración innecesaria.

3. Técnicas de Prueba Novedosas:
   Los autores introducen una estrategia de prueba que maneja la no monotonía del actual de media predictiva del GP aprovechando la monotonía decreciente de la función de varianza del GP para acotar la suma de los términos de mejora.

4. Resultados

Resultados Teóricos

• GP-EI Estándar: Logra un arrepentimiento de $O(\gamma_T \sqrt{T})$. Para núcleos Exponenciales Cuadráticos (SE), esto es sublineal. Para núcleos Matérn, requiere $2\nu > d$ para ser sublineal.
• Improved-GP-EI: Logra un límite de arrepentimiento más ajustado que es sublineal para todo $\nu > 1$. Coincide con la tasa de arrepentimiento de $\pi$-GP-UCB pero elimina la necesidad de conocer $B$ y $R$.

Resultados Empíricos

Los autores probaron sus algoritmos en funciones sintéticas (Hartmann3, Shekel, Hartmann6, Ackley) y funciones generadas a partir de espacios RKHS.

• Rendimiento: Improved-GP-EI superó consistentemente al GP-EI estándar, Modified-GP-EI y al estado del arte $\pi$-GP-UCB.
• Robustez: A diferencia de $\pi$-GP-UCB, que requiere ajuste heurístico de parámetros desconocidos ($B$ y $R$) y funcionó mal cuando estos se adivinaron incorrectamente, Improved-GP-EI es libre de parámetros respecto a estos límites y mostró una estabilidad superior.
• Eficiencia: La estrategia de partición en Improved-GP-EI redujo la complejidad computacional. Por ejemplo, en Hartmann3, el tiempo de ejecución promedio por iteración fue de 1.21 minutos para Improved-GP-EI frente a 1.37 minutos para GP-EI estándar, ampliándose la brecha para horizontes más grandes debido al tamaño reducido de las inversiones de matrices de núcleo (inviertiendo matrices locales más pequeñas en lugar de una matriz global).

5. Significado

Este artículo resuelve un problema abierto de larga data en el análisis teórico de la Mejora Esperada para bandidos de Procesos Gaussianos.

• Puente entre Teoría y Práctica: Demuestra que la heurística más popular (EI) es teóricamente sólida en entornos ruidosos sin requerir conocimiento de "oráculo" sobre la suavidad de la función o los niveles de ruido.
• Aplicabilidad Práctica: Al eliminar la dependencia de parámetros desconocidos ($B$ y $R$), los algoritmos propuestos son inmediatamente aplicables a escenarios del mundo real (por ejemplo, robótica, ajuste de hiperparámetros) donde estos valores son difíciles o imposibles de estimar a priori.
• Avance Algorítmico: El Improved-GP-EI ofrece una alternativa robusta y libre de parámetros a los métodos basados en UCB, demostrando que las estrategias basadas en EI pueden lograr tasas de arrepentimiento óptimas mientras son más robustas ante la elección del núcleo y la incertidumbre de parámetros.