Thompson Sampling pour l’exploration-exploitation dans les systèmes linéaires

Abstract

Cette thèse est dédiée à l’étude du Thompson Sampling (TS), une heuristique qui vise à surmonter le dilemme entre exploration et exploitation qui est inhérent à tout processus décisionnel face à l’incertain. Contrairement aux algorithmes issus de l’heuristique optimiste face à l’incertain (OFU), où l’exploration provient du choix du modèle le plus favorable possible au vu de la connaissance accumulée, les algorithmes TS introduisent de l’aléa dans le processus décisionnel en sélectionnant aléatoirement un modèle plausible, ce qui les rend bien moins coûteux numériquement. Cette étude se concentre sur les problèmes paramétriques linéaires, qui autorisent les espaces état-action continus (infinis), en particulier les problèmes de Bandits Linéaires (LB) et les problèmes de contrôle Linéaire et Quadratique (LQ). Nous proposons dans cette thèse de nouvelles analyses du regret des algorithmes TS pour chacun de ces deux problèmes. Bien que notre démonstration pour les LB garantisse une borne supérieure identique aux résultats préexistants, la structure de la preuve offre une nouvelle vision du fonctionnement de l’algorithme TS, et nous permet d’étendre cette analyse aux problèmes LQ. Nous démontrons la première borne supérieure pour le regret de l’algorithme TS dans les problèmes LQ, qui garantie dans le cadre fréquentiste un regret au plus d’ordre O(sqrt(T)). Enfin, nous proposons une application des méthodes d’exploration-exploitation pour les problèmes d’optimisation de portefeuille, et discutons dans ce cadre le besoin ou non d’explorer activement.