• Langue : Anglais
• Discipline : Informatique et applications
• Identifiant : 2025ULILB046
• Type de thèse : Doctorat
• Date de soutenance : 09/12/2025

Résumé en langue originale

Cette thèse porte sur l'exploration pure multiobjectif dans le cadre des bandits stochastiques. L'objectif est de concevoir des algorithmes capables d'identifier l'ensemble des bras Pareto-optimaux; ceux qu'il est impossible d'améliorer sur un objectif sans en détériorer un autre, tout en minimisant le nombre d'échantillons nécessaires pour atteindre un niveau de confiance donné.Après une revue de la littérature sur les bandits classiques et multiobjectifs, nous introduisons le problème d'Identification de l'Ensemble de Pareto (IEP) et les outils théoriques qui le sous-tendent. Nous progressons des méthodes basées sur des intervalles de confiance offrant des garanties en temps fini vers des approches asymptotiquement optimales, tout en préservant l'efficacité computationnelle. Les algorithmes proposés sont évalués de manière systématique sur des jeux de données synthétiques et réels, afin d'analyser finement leurs performances empiriques. La première partie traite l'IEP dans le cas non structuré et présente l'algorithme EGE, qui identifie efficacement l'ensemble de Pareto lorsque le budget d'échantillons est fixé. Revisitant les travaux sur l'IEP à confiance fixée, nous introduisons APE, une procédure adaptative [dollar]delta[dollar]-correcte reposant sur des intervalles de confiance. APE fournit de fortes garanties en nombre fini d'échantillons et de très bonnes performances pratiques. Des applications à des jeux de données issus d'essais vaccinaux multicritères illustrent EGE et APE peuvent guider la sélection de stratégies thérapeutiques optimisant simultanément plusieurs marqueurs immunologiques. Nous étendons ensuite l'IEP au cas structuré, où les moyennes des bras dépendent linéairement de descripteurs connus via une matrice de régression inconnue. L'algorithme GEGE exploite cette structure pour réduire la complexité d'échantillonnage et atteint des bornes inférieures dépendantes de l'instance. Le chapitre suivant identifie les limites de ces approches et introduit PSIPS, premier algorithme à la fois asymptotiquement optimal et sans projection pour l'IEP avec objectifs corrélés. Basé sur un échantillonnage a posteriori pour le choix des bras et la règle d'arrêt, PSIPS élimine la nécessité de fixer à l'avance le paramètre de confiance [dollar]delta[dollar].Il atteint la borne inférieure théorique sur la complexité d'échantillonnage et se montre très compétitif, y compris sur des données réelles comme COV-BOOST, tout en étant bien plus rapide que les méthodes à base de gradient.Enfin, le dernier chapitre traite du cas contraint, où seuls les bras respectant certains critères doivent être considérés pour le calcul de l'ensemble de Pareto. Un algorithme doit donc apprendre simultanément les bras viables et déterminer leur optimalité. Nous proposons cAPE, un algorithme qui généralise celui du chapitre 3 et établit des bornes théoriques pour l'IEP sous contraintes. Dans l'ensemble, cette thèse fait progresser les fondements théoriques et algorithmiques de l'exploration pure multiobjectif. En combinant les outils issus de statistiques, conception expérimentale optimale et principes bayésiens, elle montre qu'il est possible de concilier optimalité théorique et efficacité pratique. Les idées développées ouvrent la voie à une théorie générale de l'apprentissage séquentiel multiobjectif, avec des applications aux essais cliniques adaptatifs, à l'apprentissage par renforcement et plus globalement à la décision multicritère sous incertitude.

Résumé traduit

In this dissertation, we study a class of emph{multi-objective pure exploration problems} in stochastic bandits.Our goal is to design algorithms that identify the set of emph{Pareto-optimal} arms, i.e., those that cannot be improved in one objective without deteriorating another, while minimizing the number of samples required to achieve a prescribed level of confidence.We begin by reviewing the literature on classical and multi-objective bandits, outlining the key theoretical tools that motivate the study of emph{Pareto Set Identification} (PSI).Throughout the thesis, we progressively move from simple algorithms based on confidence sequences with finite-time guarantees to more advanced approaches that achieve asymptotic optimality, while maintaining computational tractability.All proposed methods are systematically evaluated on synthetic and real-world-inspired datasets to provide a comprehensive understanding of their empirical performance.The first part of the thesis introduces PSI in the emph{unstructured} setting and proposes two algorithms.In the fixed-budget regime, we develop {EGE} (emph{Empirical Gap Elimination}), the first algorithm for PSI in this setting.In the fixed-confidence regime, we introduce {APE}, a [dollar]delta[dollar]-correct procedure based on adaptive confidence intervals.{APE} offers strong finite-sample guarantees and excellent empirical performance, making it one of the first effective and interpretable algorithms for PSI.Applications to multi-endpoint vaccine trials illustrate how PSI can guide early-stage clinical decision-making by identifying treatment strategies that jointly optimize multiple immunological indicators.Chapter~4 extends PSI to the emph{structured} case, where arm means are linearly related through an unknown parameter matrix~[dollar] heta[dollar] and known feature representations.We derive problem-dependent lower bounds on the sample complexity and propose efficient algorithms that exploit this structure to significantly reduce the number of required samples.Chapter~5 focuses on algorithms that achieve the emph{information-theoretic lower bounds}.We introduce {PSIPS} (emph{PSI with Posterior Sampling}), the first computationally efficient and asymptotically optimal algorithm for PSI with correlated objectives.{PSIPS} uses posterior sampling for both the sampling and stopping rules, eliminating the need to predefine the confidence parameter~[dollar]delta[dollar].It achieves theoretical optimality and demonstrates excellent empirical performance in extensive experiments, including on the emph{COV-BOOST} vaccine dataset, while being several orders of magnitude faster than gradient-based approaches.Finally, Chapter~6 explores PSI under emph{linear constraints}, where the goal is to identify the set of Pareto-optimal arms among those that satisfy feasibility conditions.We propose {cAPE}, an extension of {APE}, and characterize the information-theoretic complexity of constrained PSI.Overall, this work advances the theoretical and algorithmic foundations of emph{multi-objective pure exploration}.By bridging information theory, optimal experimental design, and Bayesian decision principles, it demonstrates that one can achieve both theoretical optimality and computational efficiency.Beyond bandits, the insights and methods developed here open promising avenues toward a general theory of emph{multi-objective sequential learning}, with applications to adaptive clinical trials, reinforcement learning, and multi-criteria decision-making under uncertainty.