Adaptive Prior Selection in Gaussian Process Bandits with Thompson Sampling

Each language version is independently generated for its own context, not a direct translation.

Voici une explication de ce papier de recherche, imagée et simplifiée, comme si vous racontiez une histoire à un ami autour d'un café.

Le Problème : Le Chef et ses Recettes Mystérieuses

Imaginez que vous êtes un chef cuisinier (l'algorithme) dans un restaurant très spécial. Votre but est de trouver le plat le plus délicieux (l'optimisation) parmi des milliers de possibilités, mais vous ne pouvez goûter qu'un seul plat à la fois. De plus, chaque fois que vous goûtez, le serveur vous donne un avis un peu flou à cause du bruit ambiant (le "bruit" des données).

C'est ce qu'on appelle un problème de bandit (comme un joueur de machine à sous qui doit choisir le meilleur bras).

Mais il y a un gros hic : pour prédire quel plat sera bon, vous utilisez un livre de recettes générique appelé Gaussian Process (GP). Ce livre vous dit : "Si ce plat ressemble à celui-ci, il sera probablement bon".

Le vrai problème ? Vous ne savez pas quelle version de ce livre de recettes est la bonne !

Est-ce que les plats changent doucement (comme une soupe) ?
Est-ce qu'ils changent brutalement (comme une éruption volcanique) ?
Est-ce qu'ils sont périodiques (comme les saisons) ?

Dans la vraie vie, on ne connaît pas la "vraie recette" (le prior). Les chefs habituels essaient de deviner la recette en regardant les notes passées (Maximum Likelihood Estimation), mais c'est souvent une mauvaise méthode qui peut les piéger.

La Solution : Deux Nouvelles Stratégies

Les auteurs de ce papier, Jack et Morteza, ont inventé deux nouvelles façons de jouer à ce jeu pour trouver le meilleur plat et identifier la bonne recette en même temps, sans se tromper trop souvent. Ils utilisent une technique intelligente appelée Thompson Sampling (qui consiste à jouer à la loterie basée sur ce qu'on croit être vrai, plutôt que d'être trop optimiste).

1. La Méthode "Élimination" (PE-GP-TS) : Le Tri des Candidats

Imaginez que vous avez un tas de 10 livres de recettes suspects.

L'approche ancienne (UCB) : Elle essaie d'être trop optimiste. Elle dit : "Peut-être que le livre A est le bon, et peut-être que le plat X est le meilleur, alors on va essayer ça !" Cela la pousse à tester des choses inutiles.
La nouvelle approche (PE-GP-TS) : C'est plus direct.
1. On prend un livre de recettes au hasard dans le tas.
2. On imagine un plat selon ce livre.
3. On le goûte.
4. Le verdict : Si le goût réel est très différent de ce que le livre prédisait, on dit : "Ce livre est faux !" et on le jette à la poubelle.
5. On recommence avec les livres restants.

C'est comme un jeu de "Qui est l'imposteur ?". On élimine progressivement les mauvaises recettes jusqu'à ne garder que les plus probables.

2. La Méthode "Super-Recette" (HP-GP-TS) : Le Chef Omniscient

Cette méthode est encore plus subtile. Au lieu de jeter les livres, le chef imagine qu'il possède un livre maître qui contient toutes les recettes possibles, avec une probabilité pour chacune.

À chaque tour, le chef regarde ce livre maître et dit : "Aujourd'hui, j'ai 60% de chances que la recette A soit la bonne, et 30% pour la recette B."
Il choisit une recette au hasard (selon ces chances), imagine un plat, et le goûte.
Ensuite, il met à jour son livre maître : "Tiens, ce plat goûté correspondait mieux à la recette A. Je vais donc augmenter la probabilité de la recette A pour demain."

C'est comme si le chef apprenait en temps réel quelle est la "vraie" nature des plats, sans jamais être trop confiant ni trop pessimiste.

Les Résultats : Qui gagne ?

Les auteurs ont testé ces méthodes sur des données synthétiques (des jeux vidéo) et réelles (températures, trafic routier, pluie).

Moins d'erreurs, plus vite : Leurs méthodes (surtout la "Super-Recette") trouvent le meilleur plat beaucoup plus vite que les anciennes méthodes. Elles font moins d'erreurs (ce qu'on appelle le "regret" en mathématiques).
Pas de panique avec le nombre de recettes : Si vous avez 100 livres de recettes au lieu de 10, les anciennes méthodes s'effondrent et perdent beaucoup de temps. La méthode "Super-Recette" continue de fonctionner aussi bien, comme si le nombre de livres n'avait pas d'importance.
Elles savent ce qu'elles font : À la fin, la méthode "Super-Recette" sait exactement quel livre de recettes est le bon dans la grande majorité des cas.

En Résumé

Ce papier nous dit : "Arrêtez de deviner la recette parfaite d'un coup. Utilisez l'intelligence pour éliminer les mauvaises options ou pour ajuster vos croyances en temps réel."

C'est une avancée majeure pour l'intelligence artificielle qui doit prendre des décisions dans l'incertitude, que ce soit pour régler les paramètres d'un modèle d'IA, découvrir de nouveaux médicaments ou optimiser la circulation dans une ville. Au lieu d'essayer de tout deviner, l'IA apprend à apprendre, et elle le fait très efficacement.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique

Le problème traité concerne l'optimisation de fonctions boîte noire bruitées dans le cadre des bandits à processus gaussien (GP Bandits). Dans ce contexte, un agent doit sélectionner séquentiellement des actions (bras) pour maximiser la récompense cumulative, en supposant que la fonction de récompense inconnue $f$ est un échantillon d'un processus gaussien (GP).

Le défi central identifié par les auteurs est l'incertitude sur l'a priori (prior). La plupart des travaux théoriques supposent que les hyperparamètres du GP (comme la longueur d'échelle ou le type de noyau) sont connus. En pratique, cela est rarement le cas. Les praticiens utilisent souvent l'estimation du maximum de vraisemblance (MLE), qui ne garantit pas théoriquement la récupération des paramètres corrects dans un cadre de décision séquentielle.

L'objectif est donc de concevoir des algorithmes capables de :

Sélectionner dynamiquement le bon a priori parmi un ensemble fini de candidats $\mathcal{P}$ .
Minimiser le regret (la perte de récompense par rapport à l'optimum) sans connaître l'a priori vrai $p^*$ .

2. Méthodologie

Les auteurs proposent deux algorithmes basés sur l'Échantillonnage de Thompson (Thompson Sampling - TS), une approche probabiliste qui tend à surperformer les méthodes basées sur la borne de confiance supérieure (UCB) dans les problèmes où la construction de bornes de confiance serrées est difficile.

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

C'est une extension de l'algorithme Prior-Elimination GP-UCB (Ziomek et al., 2025), adapté au TS.

Principe : Au lieu de maximiser une borne de confiance (comme en UCB), l'algorithme échantillonne une fonction $\tilde{f}_{t,p}$ à partir de l'a posteriori de chaque a priori actif $p \in \mathcal{P}_t$ . Il sélectionne ensuite le bras $x_t$ et l'a priori $p_t$ qui maximisent cette fonction échantillonnée.
Mécanisme d'élimination : L'algorithme surveille l'erreur de prédiction cumulative de l'a priori sélectionné. Si la somme des erreurs de prédiction dépasse un seuil de confiance $V_t$ , l'a priori est éliminé de l'ensemble actif.
Avantage : Contrairement à PE-GP-UCB qui est "doublement optimiste" (optimisme sur le bras et sur l'a priori via la borne supérieure), PE-GP-TS n'a qu'un seul niveau d'optimisme (via l'échantillonnage), réduisant ainsi l'exploration excessive.

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

C'est un algorithme entièrement bayésien utilisant un schéma d'échantillonnage à deux niveaux (bi-level).

Principe : À chaque étape, l'algorithme échantillonne d'abord un a priori $p_t$ à partir d'une hyper-postérieur (la distribution sur les a priori mise à jour avec les données), puis échantillonne une fonction $\tilde{f}_t$ à partir du GP conditionné à cet $p_t$ .
Mise à jour : Après observation de la récompense, l'hyper-postérieur est mis à jour en calculant la vraisemblance des données sous chaque a priori possible.
Différence clé : Contrairement aux méthodes bayésiennes complètes qui intègrent sur l'hyper-postérieur (coûteux en calcul), HP-GP-TS ne nécessite qu'un seul échantillon, réduisant la complexité computationnelle.

3. Contributions Clés

Proposition de deux nouveaux algorithmes : PE-GP-TS et HP-GP-TS pour la sélection adaptative d'a priori dans les bandits GP.
Analyse théorique du regret :
- Pour PE-GP-TS, les auteurs établissent une borne de regret de l'ordre de $O(\sqrt{T \log T |P| \hat{\gamma}_T})$ , où $\hat{\gamma}_T$ est le gain d'information maximal dans le pire des cas. Cette borne correspond à celle de PE-GP-UCB, mais avec un terme supplémentaire lié à l'incertitude du bras optimal sous l'a priori correct.
- Pour HP-GP-TS, la borne de regret bayésien est de l'ordre de $O(\sqrt{T \log T \bar{\gamma}_T})$ , où $\bar{\gamma}_T$ est le gain d'information moyen. Cela signifie que si l'hyper-a priori favorise des a priori simples, le regret est théoriquement meilleur que pour les méthodes d'élimination qui doivent se prémunir contre le pire des cas.
Critique de travaux antérieurs : Les auteurs identifient des problèmes techniques dans la preuve de la borne de regret de l'algorithme MixTS (Hong et al., 2022b) pour les bandits linéaires, remettant en question sa validité dans ce cadre spécifique.
Validation expérimentale rigoureuse : Tests sur des données synthétiques et réelles, comparant les méthodes proposées à des baselines (PE-GP-UCB, SCoreBO, EEI, MAP GP-TS).

4. Résultats Expérimentaux

Les expériences ont été menées sur trois scénarios synthétiques (différents noyaux, différentes longueurs d'échelle, sous-espaces) et trois jeux de données réels (température Intel, trafic PeMS, précipitations PNW).

Performance du regret :
- HP-GP-TS et EEI (Expected Improvement entièrement bayésien) obtiennent systématiquement les regrets les plus faibles, se rapprochant de la performance de l'oracle (qui connaît le vrai a priori).
- PE-GP-TS surpasse PE-GP-UCB, confirmant que la réduction de l'optimisme (passage de UCB à TS) améliore l'efficacité.
- SCoreBO montre un regret significativement plus élevé, bien qu'il réduise bien l'incertitude sur l'a priori.
Impact du nombre d'a priori ( $|P|$ ) :
- Le regret de HP-GP-TS ne semble pas augmenter avec le nombre d'a priori $|P|$ dans les expériences, contrairement aux méthodes d'élimination dont le regret croît approximativement comme $\sqrt{|P|}$ .
- HP-GP-TS identifie le bon a priori plus souvent (plus de 60% de précision dans les tests noyaux) que les méthodes d'élimination (~17%).
Convergence de l'hyper-postérieur : HP-GP-TS concentre rapidement la masse de probabilité sur un seul a priori (entropie faible), indiquant une identification efficace du modèle, tout en maintenant un regret faible.

5. Signification et Conclusion

Ce travail est significatif car il comble un fossé important entre la théorie des bandits GP (qui suppose souvent un a priori connu) et la pratique (où l'a priori est inconnu).

Efficacité de l'exploration : En remplaçant l'optimisme déterministe (UCB) par l'échantillonnage de Thompson, les auteurs parviennent à réduire l'exploration excessive souvent observée dans les méthodes d'élimination, tout en conservant des garanties théoriques solides.
Robustesse : HP-GP-TS démontre une robustesse remarquable face à la complexité croissante de l'ensemble des a priori, ce qui est crucial pour les applications réelles où le choix du modèle est incertain.
Apport pratique : Les résultats sur des données réelles (trafic, météo, capteurs) confirment que ces méthodes sont applicables et supérieures aux approches existantes pour l'optimisation de fonctions complexes avec des modèles incertains.

En résumé, l'article propose une approche théoriquement fondée et empiriquement validée pour l'optimisation bayésienne lorsque la structure du modèle (l'a priori) doit être apprise en ligne, offrant une alternative supérieure aux méthodes UCB et aux approches bayésiennes complètes coûteuses.