Déclinaisons de bandits et leurs applications

Cette thèse s’intéresse à différentes variantes du problème des bandits, une instance simplifiée d’un problème de reinforcement learning (RL) dont l’accent est mis sur le compromis entre l’exploration et l’exploitation. Plus spécifiquement, l’accent est mis sur trois variantes, soient les bandits contextuels, structurés et multi-objectifs. Dans la première, un agent recherche l’action optimale dépendant d’un contexte donné. Dans la seconde, un agent recherche l’action optimale dans un espace potentiellement grand et caractérisé par une métrique de similarité. Dans la dernière, un agent recherche le compromis optimal sur un front de Pareto selon une fonction d’articulation des préférences non observable directement. La thèse propose des algorithmes adaptés à chacune de ces variantes, dont les performances sont appuyées par des garanties théoriques ou des expériences empiriques. Ces variantes de bandits servent de cadre à deux applications réelles et à haut potentiel d’impact, soient l’allocation de traitements adaptative pour la découverte de stratégies de traitement du cancer personnalisées, et l’optimisation en-ligne de paramètres d’imagerie microscopique à grande résolution pour l’acquisition efficace d’images utilisables en neuroscience. La thèse apporte donc des contributions à la fois algorithmiques, théoriques et applicatives. Une adaptation de l’algorithme best empirical sampled average (BESA), GP BESA, est proposée pour le problème des bandits contextuels. Son potentiel est mis en lumière par des expériences en simulation, lesquelles ont motivé le déploiement de la stratégie dans une étude sur des animaux en laboratoire. Les résultats, prometteurs, montrent que GP BESA est en mesure d’étendre la longévité de souris atteintes du cancer et ainsi augmenter significativement la quantité de données recueillies sur les sujets. Une adaptation de l’algorithme Thompson sampling (TS), Kernel TS, est proposée pour le problème des bandits structurés en reproducing kernel Hilbert space (RKHS). Une analyse théorique permet d’obtenir des garanties de convergence sur le pseudo-regret cumulatif. Des résultats de concentration pour la régression à noyau avec régularisation variable ainsi qu’une procédure d’ajustement adaptative de la régularisation basée sur l’estimation empirique de la variance du bruit sont également introduits. Ces contributions permettent de lever l’hypothèse classique sur la connaissance a priori de la variance du bruit en régression à noyau en-ligne. Des résultats numériques illustrent le potentiel de ces outils. Des expériences empiriques illustrent également la performance de Kernel TS et permettent de soulever des questionnements intéressants relativement à l’optimalité des intuitions théoriques. Une nouvelle variante de bandits multi-objectifs généralisant la littérature est proposée. Plus spécifiquement, le nouveau cadre considère que l’articulation des préférences entre les objectifs provient d’une fonction non observable, typiquement d’un utilisateur (expert), et suggère d’intégrer cet expert à la boucle d’apprentissage. Le concept des rayons de préférence est ensuite introduit pour évaluer la robustesse de la fonction de préférences de l’expert à des erreurs dans l’estimation de l’environnement. Une variante de l’algorithme TS, TS-MVN, est proposée et analysée. Des expériences empiriques appuient ces résultats et constituent une investigation préliminaire des questionnements relatifs à la présence d’un expert dans la boucle d’apprentissage. La mise en commun des approches de bandits structurés et multi-objectifs permet de s’attaquer au problème d’optimisation des paramètres d’imagerie STED de manière en-ligne. Les résultats expérimentaux sur un vrai montage microscopique et avec de vrais échantillons neuronaux montrent que la technique proposée permet d’accélérer considérablement le processus de caractérisation des paramètres et facilitent l’obtention rapide d’images pertinentes pour des experts en neuroscience.This thesis deals with various variants of the bandits problem, wihch corresponds to a simplified instance of a RL problem with emphasis on the exploration-exploitation trade-off. More specifically, the focus is on three variants: contextual, structured, and multi-objective bandits. In the first, an agent searches for the optimal action depending on a given context. In the second, an agent searches for the optimal action in a potentially large space characterized by a similarity metric. In the latter, an agent searches for the optimal trade-off on a Pareto front according to a non-observable preference function. The thesis introduces algorithms adapted to each of these variants, whose performances are supported by theoretical guarantees and/or empirical experiments. These bandit variants provide a framework for two real-world applications with high potential impact: 1) adaptive treatment allocation for the discovery of personalized cancer treatment strategies; and 2) online optimization of microscopic imaging parameters for the efficient acquisition of useful images. The thesis therefore offers both algorithmic, theoretical, and applicative contributions. An adaptation of the BESA algorithm, GP BESA, is proposed for the problem of contextual bandits. Its potential is highlighted by simulation experiments, which motivated the deployment of the strategy in a wet lab experiment on real animals. Promising results show that GP BESA is able to extend the longevity of mice with cancer and thus significantly increase the amount of data collected on subjects. An adaptation of the TS algorithm, Kernel TS, is proposed for the problem of structured bandits in RKHS. A theoretical analysis allows to obtain convergence guarantees on the cumulative pseudo-regret. Concentration results for the regression with variable regularization as well as a procedure for adaptive tuning of the regularization based on the empirical estimation of the noise variance are also introduced. These contributions make it possible to lift the typical assumption on the a priori knowledge of the noise variance in streaming kernel regression. Numerical results illustrate the potential of these tools. Empirical experiments also illustrate the performance of Kernel TS and raise interesting questions about the optimality of theoretical intuitions. A new variant of multi-objective bandits, generalizing the literature, is also proposed. More specifically, the new framework considers that the preference articulation between the objectives comes from a nonobservable function, typically a user (expert), and suggests integrating this expert into the learning loop. The concept of preference radius is then introduced to evaluate the robustness of the expert’s preference function to errors in the estimation of the environment. A variant of the TS algorithm, TS-MVN, is introduced and analyzed. Empirical experiments support the theoreitcal results and provide a preliminary investigation of questions about the presence of an expert in the learning loop. Put together, structured and multi-objective bandits approaches are then used to tackle the online STED imaging parameters optimization problem. Experimental results on a real microscopy setting and with real neural samples show that the proposed technique makes it possible to significantly accelerate the process of parameters characterization and facilitate the acquisition of images relevant to experts in neuroscience