Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

Resumen Técnico: Límites de Arrepentimiento más Estrechos para Bandidos de Procesos Gaussianos con Variación Temporal y Exploración Constante

Configuración del Problema
El artículo aborda la optimización bayesiana en entornos no estacionarios donde la función de recompensa desconocida $f_t: S \to \mathbb{R}$ evoluciona a lo largo del tiempo. Específicamente, los autores consideran el modelo de Procesos Gaussianos con Variación Temporal (TV-GP) introducido por Bogunovic et al. [2016]. En este entorno, la función latente evoluciona según una recursión de Markov impulsada por innovaciones de GP:
$$f_{t+1}(x) = \sqrt{1-\epsilon} f_t(x) + \sqrt{\epsilon} g_{t+1}(x)$$
donde $g_t$ son extracciones i.i.d. de un proceso gaussiano espacial con núcleo $k_S$, y $\epsilon \in (0, 1]$ es un parámetro de deriva que controla la tasa de cambio temporal. El objetivo es minimizar el arrepentimiento acumulado $R_T = \sum_{t=1}^T (f_t(x_t^*) - f_t(x_t))$. A diferencia de los entornos estáticos, el arrepentimiento acumulado sublineal generalmente no es alcanzable aquí; el objetivo es acotar el arrepentimiento promedio $R_T/T$ como una función de la tasa de deriva $\epsilon$.

Metodología
Los autores revisan el algoritmo de Límite Superior de Confianza de Procesos Gaussianos (GP-UCB) en este entorno dinámico. Los análisis estándar para bandidos TV-GP suelen requerir que el parámetro de exploración $\beta_t$ crezca con el tiempo $t$ para mantener límites de confianza uniformes sobre todo el horizonte. Este artículo propone un enfoque analítico diferente:

1. Eventos de Confianza Locales: En lugar de depender de un único evento de confianza global que se mantenga uniformemente durante el horizonte (lo que requiere un $\beta_t$ que aumenta con el tiempo), el análisis construye eventos de confianza locales $E_t$ para cada ronda $t$.
2. Parámetro de Exploración Constante: Al utilizar estos eventos locales, los autores demuestran que el GP-UCB puede ejecutarse con un parámetro de exploración constante $\beta_t \equiv \beta$.
3. Discretización y Límites de Cola: La demostración combina un límite de arrepentimiento de UCB por ronda en un evento de confianza local con un límite agnóstico al algoritmo sobre el evento complementario poco frecuente. Esto implica:
   • Una discretización de la rejilla espacial de tamaño $\tau^d$.
   • Límites de cola de la derivada (Supuesto 1) para controlar el error de discretización.
   • Concentración subgaussiana de la amplitud de la función $W_t = \sup f_t - \inf f_t$.
4. Ganancia de Información con Decaimiento Temporal: Los autores derivan un límite más estrecho para la ganancia de información máxima variable en el tiempo $\tilde{\gamma}_T$, que controla la suma de las varianzas posteriores. Utilizan una técnica de descomposición por bloques para relacionar $\tilde{\gamma}_T$ con la ganancia de información estática $\gamma_N$ y el parámetro de deriva $\epsilon$.

Contribuciones Clave y Resultados

• Límite de Arrepentimiento con Exploración Constante: El principal resultado teórico (Teorema 1) establece un límite de arrepentimiento esperado para el TV-GP-UCB de $\beta$ constante:
  $$E[R_T] \le \sqrt{C_1 T \beta \tilde{\gamma}_T} + T C_2 + T \delta C_3$$
  donde $\tilde{\gamma}_T$ es la ganancia de información máxima variable en el tiempo. Este límite se mantiene para cualquier tasa de deriva fija $\epsilon > 0$ sin requerir que $\beta$ escale con $T$.
• Escalamiento de Ganancia de Información más Estrecho: El artículo deriva un nuevo límite para la ganancia de información variable en el tiempo. Si la ganancia de información estática satisface $\gamma_N = \tilde{O}(N^q)$, entonces en el régimen de deriva persistente (donde el horizonte $T$ excede la longitud de bloque efectiva), la ganancia de información promedio escala como:
  $$\frac{\tilde{\gamma}_T}{T} = \tilde{O}\left(\epsilon^{\frac{2(1-q)}{4-q}}\right)$$
  Consecuentemente, el arrepentimiento promedio esperado escala como:
  $$\frac{E[R_T]}{T} = \tilde{O}\left(\epsilon^{\frac{1-q}{4-q}}\right)$$
  Para el núcleo exponencial cuadrático ($q=0$), esto produce un arrepentimiento promedio de $\tilde{O}(\epsilon^{1/4})$.
• Parámetro de Exploración Sugerido por el Límite: El análisis revela que el $\beta$ constante óptimo (denotado $\beta_{opt}$) sugerido al balancear los términos del límite de arrepentimiento depende logarítmicamente del inverso de la tasa de deriva:
  $$\beta_{opt} \propto \log(1/\epsilon)$$
  Esto contrasta con los esquemas previos donde $\beta_t$ era independiente de $\epsilon$. El artículo argumenta que, a medida que la deriva se ralentiza ($\epsilon \to 0$), las observaciones pasadas siguen siendo informativas por más tiempo, reduciendo la varianza posterior; un $\beta$ mayor compensa esto otorgando un mayor valor a la reducción de la incertidumbre restante.
• Garantías de Arrepentimiento Realizado: El artículo proporciona garantías tanto post-hoc como de confianza prescrita para el arrepentimiento realizado. En el caso de la confianza prescrita, el algoritmo puede ejecutarse con un $\beta$ constante mientras alcanza un límite de arrepentimiento de alta probabilidad con dependencia logarítmica en la probabilidad de fallo $\omega$.
• Adaptación de la Frecuencia de Muestreo: El marco proporciona un heurístico para ajustar $\beta$ cuando la frecuencia de muestreo cambia. Si las observaciones se recolectan cada $\Delta$ unidades de tiempo, la deriva efectiva se convierte en $\epsilon_\Delta = 1 - (1-\epsilon)^\Delta$, y el $\beta$ sugerido escala con $\log(1/\epsilon_\Delta)$.

Significancia y Reivindicaciones
El artículo afirma que su análisis resuelve una limitación recurrente en la literatura de bandidos GP variables en el tiempo: la necesidad de esquemas de exploración que aumentan con el tiempo, lo que conduce a un desempeño deteriorado en horizontes largos y requiere un ajuste difícil. Al cambiar de eventos de confianza globales a locales, los autores muestran que se pueden mantener garantías de desempeño rigurosas con un parámetro de exploración constante.

La significancia radica en:

1. Mejor Escalamiento en Horizontes Largos: Eliminar el factor $\sqrt{\log T}$ que a menudo se introduce por la unión de conjuntos (union bounds) sobre el tiempo en el término de arrepentimiento principal.
2. Dependencia Explícita de la Deriva: Proporcionar una base teórica para cómo el parámetro de exploración debe escalar con la tasa de deriva $\epsilon$ del entorno, en lugar de solo con el tiempo $t$.
3. Límites más Estrechos: Ofrecer tasas más ajustadas para la ganancia de información variable en el tiempo en comparación con trabajos previos (por ejemplo, Bogunovic et al. [2016], Imamura et al. [2020]).

Validación Empírica
Los autores respaldan sus hallazgos teóricos con un estudio de simulación en un dominio 2D utilizando un núcleo exponencial cuadrático. Simulan $T=10,000$ rondas utilizando una implementación de filtro de Kalman para manejar la posterior variable en el tiempo de manera eficiente. Los resultados confirman que:

• Un amplio rango de valores constantes de $\beta$ supera a los heurísticos logarítmicos que crecen con el tiempo.
• El $\hat{\beta}_{opt}$ constante empíricamente óptimo aumenta linealmente con $-\log(\epsilon)$, validando la predicción teórica $\beta_{opt} \propto \log(1/\epsilon)$.

Limitaciones y Direcciones Futuras
Los autores señarian que su análisis depende del núcleo temporal geométrico específico inducido por el modelo de deriva de Markov. Extender estas garantías a núcleos temporales más generales sigue siendo un problema abierto. Además, el análisis actual asume que el parámetro de deriva $\epsilon$ es conocido; adaptar $\beta$ de forma online cuando $\epsilon$ es desconocido es una dirección sugerida para trabajos futuros. El artículo también reconoce que el resultado de exploración constante es un resultado de "deriva positiva" y no recupera la garantía estándar de arrepentimiento sublineal estático en $\epsilon=0$, lo cual requiere un análisis separado.