Analyse de stratégies bayésiennes et fréquentistes pour l'allocation séquentielle des ressources.

Résumé Dans cette thèse, nous étudions des stratégies d'allocation séquentielle de ressources, sous le modèle dit du bandit multi-bras stochastique. Dans ce modèle, lorsqu'un agent tire un bras, il reçoit comme récompense une réalisation issue d'une distribution de probabilité associée à ce bras. Dans ce document, nous considérons deux problèmes de bandit différents. Dans l'objectif de maximisation de la récompense, l'agent vise à maximiser la somme des récompenses obtenues lors de son interaction avec le bandit, tandis que dans l'objectif d'identification du meilleur bras, son but est de trouver l'ensemble des m meilleurs bras (i.e. les bras avec la récompense moyenne la plus élevée), sans subir de perte lors du tirage de "mauvais" bras. Pour ces deux objectifs, nous proposons des stratégies, également appelées algorithmes de bandit, qui sont optimales (ou proches de l'optimal), dans un sens précisé ci-dessous. Maximiser la somme des récompenses est équivalent à minimiser une quantité appelée regret. Grâce à une borne inférieure asymptotique sur le regret de tout algorithme uniformément efficace donnée par Lai et Robbins, on peut définir les algorithmes asymptotiquement optimaux comme des algorithmes dont le regret atteint cette borne inférieure. Dans cette thèse, nous proposons, pour deux algorithmes bayésiens, Bayes-UCB et Thompson Sampling, une analyse en temps fini, c'est-à-dire une borne supérieure non-asymptotique sur leur regret, dans le cas particulier de bandits à récompenses binaires. Cette borne supérieure permet d'établir l'optimalité asymptotique des deux algorithmes. Dans le cadre de l'identification des meilleures armes, un objectif possible est de déterminer le nombre d'échantillons d'armes nécessaires pour identifier, avec une forte probabilité, l'ensemble des m meilleures armes. Nous définissons une notion de complexité pour l'identification du meilleur bras dans deux contextes différents considérés dans la littérature : le contexte à budget fixe et le contexte à confiance fixe. Nous fournissons de nouvelles bornes inférieures sur ces termes de complexité et nous analysons de nouveaux algorithmes, dont certains atteignent la borne inférieure dans des cas particuliers de modèles de bandits à deux bras et sont donc optimaux. Dans cette thèse, nous étudions des stratégies d'allocation séquentielle de ressources.