Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

1. Énoncé du problème

L'article aborde le problème de l'optimisation de bandit par processus gaussien (GP), spécifiquement dans un cadre non bayésien (où la fonction est fixe mais inconnue et réside dans un espace de Hilbert à noyau reproduisant, ou RKHS). L'objectif est de sélectionner séquentiellement des points $x_t$ pour maximiser une fonction boîte noire coûteuse $f(x)$ basée sur des observations bruitées $y_t = f(x_t) + \epsilon_t$.

La performance est mesurée par le regret cumulatif $R_T = \sum_{t=1}^T (f(x^*) - f(x_t^+))$, où $x^*$ est l'optimum global et $x_t^+$ est le meilleur point rapporté par l'algorithme jusqu'à l'itération $t$.

Le défi central :
Bien que l'algorithme Expected Improvement (EI) soit une heuristique populaire pour l'optimisation bayésienne en raison de sa simplicité, ses propriétés de convergence théoriques dans un cadre bruité sont restées une question ouverte.

• Dans des cadres sans bruit, le « incumbent » (la meilleure valeur actuelle) est simplement la valeur observée maximale, qui est monotone.
• Dans des cadres bruités, l'incumbent est généralement défini comme le maximum de la moyenne prédictive GP ($\mu_t^+$) ou le maximum des observations bruitées ($y_t^+$).
• Contrairement au cas sans bruit, la moyenne prédictive GP $\mu_t^+$ n'est pas monotone au fil du temps. Ce manque de monotonie rend l'analyse théorique standard (qui repose sur la borne du regret via la monotonie de l'incumbent) extrêmement difficile. Les travaux antérieurs exigeaient soit la connaissance de paramètres inconnus (comme la borne de norme RKHS $B$ et la sous-gaussianité du bruit $R$), soit utilisaient des incumbents non standards nécessitant des étapes d'optimisation globale coûteuses.

2. Méthodologie

Les auteurs proposent deux algorithmes principaux pour combler ces lacunes théoriques et pratiques.

A. GP-EI avec Incumbent Standard

La première contribution est une analyse rigoureuse d'un algorithme GP-EI standard où l'incumbent est défini comme le maximum de la moyenne prédictive GP sur les points observés :
$$\xi_t = \mu_t^+ = \max_{x_i \in D_{t-1}} \mu_{t-1}(x_i)$$

• Fonction d'acquisition : L'algorithme sélectionne le point suivant $x_t$ en maximisant l'Expected Improvement :
  $$\alpha_{EI}(x) = \mathbb{E}[\max\{0, f(x) - \mu_t^+\} | D_t]$$
  Ceci est calculé sous forme fermée en utilisant la fonction $\rho(u, v) = u\Phi(u/v) + v\phi(u/v)$.
• Échelle variant dans le temps : Pour gérer le bruit et assurer la convergence sans connaître la norme RKHS ($B$) ni le paramètre de bruit ($R$), l'algorithme utilise un paramètre d'échelle variant dans le temps $\omega_t = \sqrt{\gamma_{t-1} + 1 + \ln(1/\delta)}$, où $\gamma_t$ est le gain d'information maximal.
• Innovation théorique clé : Les auteurs surmontent la non-monotonie de $\mu_t^+$ en exploitant la monotonie de la fonction de variance ($\sigma_t(x)$ diminue à mesure que $t$ augmente). Ils décomposent le regret instantané et bornent la somme des « termes d'amélioration » en utilisant cette propriété de variance, une technique jamais appliquée auparavant à l'optimisation de bandit GP de cette manière.

B. Improved-GP-EI

Pour remédier aux limitations du GP-EI standard (notamment que la borne de regret n'est pas toujours sous-linéaire pour les noyaux Matérn et que le paramètre d'échelle $\omega_t$ croît trop vite, provoquant une exploration inutile), les auteurs proposent Improved-GP-EI.

• Inspiration : Adapté de l'algorithme $\pi$-GP-UCB (Janz et al., 2020).
• Stratégie de partitionnement : L'espace de recherche est partitionné en hypercubes (un recouvrement). Un GP indépendant est ajusté sur chaque hypercube en utilisant uniquement des données locales.
• Échelle globale : Au lieu d'un $\omega_t$ variant dans le temps, il utilise une échelle globale fixe $\omega_T = \sqrt{\ln(T)\ln\ln(T)}$ qui ne croît que de manière poly-logarithmique.
• Mécanisme : À chaque étape, l'algorithme sélectionne un point en maximisant l'EI au sein de l'hypercube spécifique contenant le meilleur candidat actuel, localisant ainsi efficacement l'optimisation.

3. Contributions clés

1. Premières garanties théoriques pour le GP-EI standard :
   L'article fournit la première preuve que le GP-EI avec un incumbent standard ($\xi = \mu_t^+$) converge dans un cadre bruité.

   • Borne de regret : Le regret cumulatif est borné par $O(\gamma_T \sqrt{T})$.
   • Indépendance aux paramètres : Crucialement, l'algorithme ne nécessite pas la connaissance de la borne de norme RKHS ($B$) ni du paramètre de sous-gaussianité du bruit ($R$), qui sont typiquement inconnus dans les applications réelles.

2. Algorithme Improved-GP-EI :
   Une nouvelle variante qui atteint des taux de convergence plus rapides pour les noyaux Matérn.

   • Borne de regret : Pour les noyaux Matérn avec une régularité $\nu > 1$, le regret est $\tilde{O}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$. Ceci est sous-linéaire pour tout $\nu > 1$ et $d \geq 1$, améliorant les limitations du GP-EI standard.
   • Efficacité : En utilisant une stratégie de partitionnement et un paramètre d'échelle poly-logarithmique, il évite la croissance rapide de l'échelle de variance observée dans les méthodes précédentes, réduisant ainsi l'exploration inutile.

3. Nouvelles techniques de preuve :
   Les auteurs introduisent une stratégie de preuve qui gère la non-monotonie de l'incumbent de moyenne prédictive GP en exploitant la monotonie décroissante de la fonction de variance GP pour borner la somme des termes d'amélioration.

4. Résultats

Résultats théoriques

• GP-EI standard : Atteint un regret de $O(\gamma_T \sqrt{T})$. Pour les noyaux exponentiels carrés (SE), ceci est sous-linéaire. Pour les noyaux Matérn, il nécessite $2\nu > d$ pour être sous-linéaire.
• Improved-GP-EI : Atteint une borne de regret plus serrée qui est sous-linéaire pour tout $\nu > 1$. Il correspond au taux de regret de $\pi$-GP-UCB mais supprime l'exigence de connaître $B$ et $R$.

Résultats empiriques

Les auteurs ont testé leurs algorithmes sur des fonctions synthétiques (Hartmann3, Shekel, Hartmann6, Ackley) et des fonctions générées à partir d'espaces RKHS.

• Performance : Improved-GP-EI a constamment surpassé le GP-EI standard, le Modified-GP-EI et le $\pi$-GP-UCB de l'état de l'art.
• Robustesse : Contrairement au $\pi$-GP-UCB, qui nécessite un réglage heuristique de paramètres inconnus ($B$ et $R$) et a mal performé lorsque ces derniers étaient mal estimés, Improved-GP-EI est sans paramètre concernant ces bornes et a montré une stabilité supérieure.
• Efficacité : La stratégie de partitionnement dans Improved-GP-EI a réduit la complexité computationnelle. Par exemple, sur Hartmann3, le temps d'exécution moyen par itération était de 1,21 minute pour Improved-GP-EI contre 1,37 minute pour le GP-EI standard, l'écart s'élargissant pour des horizons plus grands en raison de la taille réduite des inversions de matrices de noyau (inversion de matrices locales plus petites au lieu d'une matrice globale).

5. Importance

Cet article résout un problème ouvert de longue date dans l'analyse théorique de l'Expected Improvement pour les bandits à processus gaussiens.

• Pont entre théorie et pratique : Il prouve que l'heuristique la plus populaire (EI) est théoriquement solide dans des environnements bruités sans nécessiter de connaissance « oracle » de la régularité de la fonction ou des niveaux de bruit.
• Applicabilité pratique : En supprimant la dépendance aux paramètres inconnus ($B$ et $R$), les algorithmes proposés sont immédiatement applicables à des scénarios réels (par exemple, robotique, réglage d'hyperparamètres) où ces valeurs sont difficiles ou impossibles à estimer a priori.
• Avancement algorithmique : Le Improved-GP-EI offre une alternative robuste et sans paramètre aux méthodes basées sur UCB, démontrant que les stratégies basées sur EI peuvent atteindre des taux de regret optimaux tout en étant plus robustes au choix du noyau et à l'incertitude des paramètres.