Résumé Technique : Identification de l'Ensemble de Pareto par Approche Bayésienne de Type « Anytime » pour les Bandits Multi-Objectifs Multi-Bras

Définition du Problème

L'article traite du problème des Bandits Multi-Objectifs Multi-Bras (MOMAB), en se concentrant spécifiquement sur l'Identification de l'Ensemble de Pareto (PSI). Contra-rément aux problèmes de bandits à objectif unique classiques qui visent à maximiser la récompense cumulée (minimisation du regret) ou à identifier un seul meilleur bras, le MOMAB implique l'optimisation simultanée de plusieurs objectifs potentiellement conflictuels. Dans ce contexte, aucun bras n'est optimal pour tous les critères ; il existe plutôt un ensemble de bras Pareto optimaux ($P^\star$) représentant les compromis optimaux.

Le défi spécifique abordé est la formulation PSI « Anytime » (en tout temps). Alors que la littérature existante couvre largement les contextes à budget fixe (minimisation de l'erreur après un nombre déterminé d'échantillons) et à confiance fixe (minimisation des échantillons pour atteindre une précision cible), il existe une lacune concernant les algorithmes capables de fournir une estimation valide et continuellement mise à jour de l'ensemble de Pareto après chaque observation, sans règle d'arrêt prédéfinie. Cela est crucial pour les applications réelles où les décideurs doivent surveiller la progression et potentiellement interrompre les expériences de manière dynamique en fonction des niveaux de confiance plutôt que sur des contraintes de ressources rigides.

Méthodologie : Top-Two Pareto Front Thompson Sampling (TTPFTS)

Les auteurs introduisent le Top-Two Pareto Front Thompson Sampling (TTPFTS), le premier algorithme bayésien de type « anytime » conçu pour le problème de PSI MOMAB. L'algorithme étend les principes du Top-Two Thompson Sampling (TTTS) du meilleur bras à objectif unique vers le domaine multi-objectif.

Mécanisme Central

Au lieu de scalariser les objectifs avec un vecteur de préférence (ce qui reviendrait à réduire le problème à un objectif unique), le TTPFTS opère directement sur les fronts de Pareto. À chaque étape $t$ :

1. Échantillonnage de l'A posteriori : L'algorithme échantillonne des vecteurs de récompenses moyennes $\tilde{\theta}^{(t)}_a$ pour tous les $K$ bras à partir de leurs distributions a posteriori respectives conditionnées par l'historique $H(t-1)$.
2. Identification du Front : Sur la base de ces échantillons, il identifie le Premier Front de Pareto ($F^\star_1$), composé des bras qui ne sont dominés par aucun autre bras échantillonné.
3. Sélection Stochastique : Un essai de Bernoulli avec une probabilité $\rho$ détermine quel front explorer :
   • Avec une probabilité $\rho$ : Un bras est sélectionné uniformément au hasard dans le Premier Front ($F^\star_1$). Cela se concentre sur la vérification des bras actuellement considérés comme optimaux.
   • Avec une probabilité $1-\rho$ : L'algorithme retire $F^\star_1$ et identifie le Second Front de Pareto ($F^\star_2$) parmi les bras restants. Un bras est ensuite sélectionné uniformément au hasard dans $F^\star_2$. Cela favorise l'exploration des bras sous-optimaux les plus prometteurs (challengers) pour tester s'ils ont été sous-estimés ou pour consolider leur statut de sous-optimalité.
4. Mise à jour : Le bras sélectionné est tiré, la récompense est observée, et l'historique est mis à jour. L'algorithme maintient un ensemble de recommandation $\hat{P}^\star_t$ (l'ensemble de Pareto des moyennes a posteriori) à tout moment.

Garanties Théoriques

L'article fournit une preuve de correction asymptotique (Théorème 1). Sous des hypothèses standards (bras finis, a posteriori cohérents, écarts de Pareto stricts et exploration suffisante), l'estimation $\hat{P}^\star_t$ de l'algorithme converge vers le véritable ensemble de Pareto $P^\star$ avec une probabilité de 1 quand $t \to \infty$. La preuve repose sur le Lemme 1, qui établit que le TTPFTS garantit une exploration infinie de tous les bras presque sûrement, empêchant ainsi qu'un bras ne soit définitivement exclu du processus d'échantillonnage.

Principales Contributions

1. Premier Algorithme Bayésien « Anytime » pour le MOMAB PSI : Le TTPFTS comble la lacune de la littérature concernant les algorithmes « anytime » pour l'identification de l'ensemble de Pareto, offrant une alternative flexible aux approches à budget ou confiance fixes.
2. Nouvelle Métrique de Quantification de l'Incertitude (UQ) : Les auteurs introduisent une métrique indépendante de la vérité terrain pour estimer la confiance de l'algorithme dans sa prédiction actuelle du Pareto. Cette métrique calcule le chevauchement de Bhattacharyya entre les densités a posteriori des bras du front estimé ($\hat{P}^\star_1$) et du second front ($\hat{P}^\star_2$).
   • Un chevauchement élevé indique une incertitude élevée (difficulté à distinguer les bras optimaux des sous-optimaux).
   • Un faible chevauchement indique une confiance élevée (séparation claire entre les fronts).
   • Cette métrique sert de substitut en temps réel de la performance d'identification, permettant des critères d'arrêt dynamiques.
3. Application Réelle dans la Découverte Moléculaire : L'algorithme est validé dans un cadre complexe de bibliothèque de synthèse à la demande de 94 millions de candidats, démontrant son utilité pour identifier des molécules optimisant des propriétés conflictuelles (Similarité Structurelle et LogP).

Résultats Empiriques

Benchmarks Synthétiques

Le TTPFTS a été évalué contre des algorithmes à budget fixe de pointe (variantes de Successive Rejects et Successive Halving de l'Empirical Gap Elimination, EGE) à travers huit environnements synthétiques avec des géométries et des dimensions de front de Pareto variables.

• Performance : Le TTPFTS surpasse systématiquement l'échantillonnage uniforme et l'algorithme EGE-SH. Il atteint une performance comparable à l'EGE-SR (la base la plus forte à budget fixe) dans tous les environnements, malgré la contrainte plus stricte du mode « anytime ».
• Scalabilité : Dans des environnements avec de grands espaces d'action (ex: $K=200$), le TTPFTS surpasse significativement les variantes d'EGE, suggérant que son allocation pilotée par l'a posteriori est plus efficace que l'élimination rigide basée sur les écarts dans les problèmes à grande échelle.
• Robustesse : L'algorithme fonctionne bien même avec des hypothèses a priori faibles (priors uniformes).

Étude de Cas : Découverte Moléculaire

Dans l'exploration d'une bibliothèque de 94 millions de composés :

• Efficacité : Le TTPFTS a identifié des molécules coïncidant parfaitement avec le front de Pareto réel (52 molécules) en n'évaluant que 0,05 % de la base de données.
• Comparaison : Il surpasse de manière significative tant la recherche aléatoire (qui n'a trouvé aucune molécule optimale) que la méthode d'apprentissage actif de pointe MolPAL.
• Corrélation de l'Incertitude : La métrique d'UQ proposée montre une forte corrélation négative avec la métrique de Jaccard (précision). À mesure que l'algorithme améliore son estimation de l'ensemble de Pareto, la métrique d'incertitude diminue, validant son utilisation comme indicateur fiable de convergence indépendant de la vérité terrain.

Signification et Revendications

L'article affirme que le TTPFTS fournit une méthodologie robuste pour surveiller la progression de l'apprentissage dans des contextes complexes à objectifs multiples sans nécessiter la connaissance du véritable front de Pareto. En combinant une stratégie d'exploration « anytime » avec une nouvelle métrique de quantification de l'incertitude, ce travail transforme le problème d'identification de l'ensemble de Pareto d'une tâche d'échantillonnage statique en un système dynamique d'aide à la décision.

Les auteurs soulignent que cette approche permet aux décideurs de :

• Déterminer dynamiquement quand le front de Pareto est suffisamment résolu pour interrompre une expérience.
• Optimiser le compromis entre les ressources computationnelles et la confiance de la découverte.
• Appliquer ces avantages à des scénarios réels comme la découverte de médicaments, où le criblage exhaustif est irréalisable et où les préférences ne sont pas connues a priori.

L'article reste modeste concernant les bornes d'erreur en temps fini, reconnaissant que si la correction asymptotique est prouvée, dériver des taux explicites en temps fini reste un défi similaire à celui rencontré par le Thompson Sampling standard par le passé. Cependant, les auteurs soutiennent que la combinaison de la solidité asymptotique, de la forte performance empirique et de l'utilité pratique de la métrique d'incertitude établit le TTPFTS comme une avancée significative dans la prise de décision multi-objectif.