Batched Kernelized Bandits: Refinements and Extensions

1. Planteamiento del Problema

El artículo aborda el problema de la optimización de funciones de caja negra con retroalimentación ruidosa, donde las observaciones no se revelan de inmediato, sino en lotes (batches). Este escenario es común en aplicaciones prácticas como la sintonización de hiperparámetros, pruebas A/B y aprendizaje por refuerzo, donde la recolección de muestras en paralelo es beneficiosa o esencial.

• Contexto: Se asume un enfoque no bayesiano donde la función desconocida $f$ reside en un Espacio de Hilbert de Núcleo Reproductor (RKHS) con una norma acotada ($\|f\|_k \le \Psi$).
• Configuración:
  • Horizonte de tiempo $T$.
  • Número de lotes $B$.
  • Lotes Fijos: Los tamaños de los lotes se determinan de antemano.
  • Lotes Adaptativos: El tamaño del siguiente lote se decide basándose en las observaciones de los lotes anteriores.
• Objetivo: Minimizar el arrepentimiento acumulado ($R_T$), definido como la diferencia entre el valor óptimo de la función y la suma de los valores obtenidos en cada paso. También se considera un escenario robusto, donde el objetivo es encontrar puntos que mantengan un valor alto incluso bajo perturbaciones adversarias.

2. Metodología

Los autores refinan y extienden el algoritmo BPE (Batched Pure Exploration) propuesto previamente por Li y Scarlett (2022). La metodología se centra en tres pilares:

A. Refinamiento de los Límites Superiores (Upper Bounds)

El algoritmo BPE mantiene un conjunto de candidatos potenciales ($X_i$) y, en cada lote, explora puntos con máxima varianza posterior. Al final del lote, elimina puntos subóptimos utilizando cotas de confianza.

• Innovación en el tamaño de los lotes: En lugar de usar la secuencia fija original, los autores proponen una generalización parametrizada por $a \in (0, 1)$:
  $$N_i = \min \left\{ \lceil T^{1-ai} \rceil, T - \sum_{j=1}^{i-1} N_j \right\}$$
  Donde $N_i$ es el tamaño del $i$-ésimo lote.
• Selección de $a$:
  • Para el núcleo SE (Exponencial Cuadrático), se elige $a \in (1/2, 1)$.
  • Para el núcleo Matérn, se permite $a \in (\frac{\nu}{2\nu+d}, 1/2]$.
• Resultado: Esta elección permite eliminar un factor de $B$ innecesario en el límite de arrepentimiento y ajustar el número de lotes de manera óptima.

B. Límites Inferiores Independientes del Algoritmo (Lower Bounds)

El trabajo presenta una contribución teórica significativa al derivar límites inferiores para lotes adaptativos.

• Desafío: Los límites anteriores solo aplicaban a lotes fijos. Para lotes adaptativos, es difícil predecir qué lote será "malo" (ineficiente) antes de tiempo.
• Solución: Utilizan una técnica de "cambio de medida" (change of measure). Construyen familias de funciones difíciles de distinguir y demuestran que, incluso con adaptividad, el algoritmo no puede evitar incurrir en un arrepentimiento significativo en al menos un lote "malo".
• Hallazgo clave: Demuestran que los lotes adaptativos no ofrecen una ventaja sustancial en el sentido minimax sobre los lotes fijos; ambos escalan de manera similar.

C. Escenario Robusto (Robust-BPE)

Extienden el problema al entorno robusto, donde un adversario perturba la entrada $x$ dentro de un radio $\xi$.

• Algoritmo: Proponen Robust-BPE, que explora un conjunto ampliado $X_{\xi, i}$ (incluyendo todas las perturbaciones posibles de los puntos candidatos) y elimina puntos basándose en cotas de confianza robustas (LCB/UCB minimax).
• Métrica: Utilizan un arrepentimiento acumulado $\xi$ ($R_{\xi, T}$) que mide el rendimiento bajo la peor perturbación.

3. Contribuciones Clave

1. Optimización del Número de Lotes ($B$):

   • Identifican el número óptimo de lotes necesario para alcanzar un arrepentimiento casi óptimo $O^*(\sqrt{T\gamma_T})$.
   • Refinan el resultado anterior de $B = O(\log \log T)$ para incluir factores constantes precisos (hasta $1 + o(1)$).
   • Demuestran que para problemas más difíciles (núcleo Matérn con bajo $\nu/d$), se requieren menos lotes para lograr el mismo rendimiento, lo cual no se capturaba en trabajos anteriores.

2. Mejora en el Límite de Arrepentimiento:

   • Eliminan un factor de $B$ (número de lotes) del límite de arrepentimiento acumulado, logrando un límite más estricto:
     $$R_T = O\left( (\Lambda + \sqrt{\log \log \log T}) \sqrt{T \gamma_T} \right)$$
     donde $\Lambda$ depende de la norma del RKHS y el tamaño del dominio.

3. Límites Inferiores para Lotes Adaptativos:

   • Proporcionan los primeros límites inferiores para lotes adaptativos en el contexto de banditos de kernel.
   • Establecen que la adaptividad no mejora la escala minimax del arrepentimiento, validando la eficacia de las estrategias de lotes fijos bien diseñadas.

4. Avances en Optimización Robusta:

   • Presentan el algoritmo Robust-BPE.
   • Logran un límite de arrepentimiento acumulado robusto que coincide con el caso no robusto.
   • Mejoran significativamente el límite de arrepentimiento simple (simple regret) respecto al estado del arte (Bogunovic et al., 2018), eliminando un factor $\sqrt{\gamma_T}$ innecesario.

4. Resultados Principales

• Teorema 1 (Límites Superiores): Para kernels SE y Matérn, con tamaños de lote definidos por el parámetro $a$, el algoritmo BPE alcanza un arrepentimiento de orden $O^*(\sqrt{T\gamma_T})$ con $B \approx \log_{1/a} \log_2 T$ lotes.
• Teorema 2 (Límites Inferiores): Para cualquier algoritmo con lotes adaptativos, el arrepentimiento esperado está acotado inferiormente por términos que dependen de $B$ y $T$, mostrando que la adaptividad no reduce la complejidad fundamental del problema.
• Teorema 3 (Robustez): Robust-BPE alcanza el mismo orden de arrepentimiento acumulado que el caso estándar, y mejora el límite de arrepentimiento simple a $O^*(\sqrt{\gamma_T/T})$.
• Experimentos: Las simulaciones en funciones sintéticas 2D (kernels SE y Matérn) confirman que ajustar el parámetro $a$ (especialmente valores cercanos a los límites inferiores teóricos) puede reducir el arrepentimiento acumulado, a veces incluso con menos lotes que la configuración original.

5. Significado e Impacto

Este trabajo es fundamental para la teoría de la optimización bayesiana y los banditos de kernel por varias razones:

• Precisión Teórica: Cierra la brecha entre los límites superiores e inferiores al refinar los factores constantes en el número de lotes y eliminar términos logarítmicos innecesarios en el arrepentimiento.
• Generalidad: Al abordar los lotes adaptativos, responde a una pregunta abierta importante sobre si la flexibilidad en la decisión de cuándo terminar un lote ofrece ventajas teóricas reales (la respuesta es que no, en términos de escalado minimax).
• Aplicabilidad Práctica: La demostración de que se pueden lograr rendimientos óptimos con un número muy pequeño de lotes ($O(\log \log T)$) es crucial para aplicaciones del mundo real donde la comunicación o la sincronización es costosa (ej. ensayos clínicos, experimentos físicos).
• Robustez: Extiende el marco teórico a entornos adversarios, proporcionando garantías de rendimiento más fuertes para sistemas que deben operar bajo incertidumbre o ataques.

En resumen, el artículo establece un nuevo estándar teórico para la optimización de funciones de caja negra en entornos por lotes, ofreciendo algoritmos más eficientes y una comprensión más profunda de las limitaciones fundamentales de la adaptividad en este contexto.