Analysis of bayesian and frequentist strategies for sequential resource allocation

Résumé : Dans cette thèse, nous étudions des stratégies d’allocation séquentielle de ressources. Le modèle statistique adopté dans ce cadre est celui du bandit stochastique à plusieurs bras. Dans ce modèle, lorsqu’un agent tire un bras du bandit, il reçoit pour récompense une réalisation d’une distribution de probabilité associée au bras. Nous nous intéressons à deux problèmes de bandit différents : la maximisation de la somme des récompenses et l’identification des meilleurs bras (où l’agent cherche à identifier le ou les bras conduisant à la meilleure récompense moyenne, sans subir de perte lorsqu’il tire un «mauvais» bras). Nous nous attachons à proposer pour ces deux objectifs des stratégies de tirage des bras, aussi appelées algorithmes de bandit, que l’on peut qualifier d’optimales. La maximisation des récompenses est équivalente à la minimisation d’une quantité appelée regret. Grâce à une borne inférieure asymptotique sur le regret d’une stratégie uniformément efficace établie par Lai et Robbins, on peut définir la notion d’algorithme asymptotiquement optimal comme un algorithme dont le regret atteint cette borne inférieure. Dans cette thèse, nous proposons pour deux algorithmes d’inspiration bayésienne, Bayes-UCB et Thompson Sampling, une analyse à temps fini dans le cadre des modèles de bandit à récompenses binaires, c’est-à-dire une majoration non asymptotique de leur regret. Cette majoration permetd’établir l’optimalité asymptotique des deux algorithmes. Dans le cadre de l’identification des meilleurs bras, on peut chercher à déterminer le nombre total d’échantillons des bras nécessaires pour identifier, avec forte probabilité, le ou les meilleurs bras, sans la contrainte de maximiser la somme des observations. Nous définissons deux termes de complexité pour l’identification des meilleurs bras dans deux cadres considérés dans la littérature, qui correspondent à un budget fixé ou à un niveau de confiance fixé. Nous proposons de nouvelles bornes inférieures sur ces complexités, et nous analysons de nouveaux algorithmes, dont certains atteignent les bornes inférieures dans des cas particuliers de modèles de bandit à deux bras, et peuvent donc être qualifiés d’optimaux.
Type de document :
Thèse
Machine Learning [cs.LG]. Télécom ParisTech, 2014. English. 〈NNT : 2014ENST0056〉
Liste complète des métadonnées

Littérature citée [110 références]  Voir  Masquer  Télécharger

https://pastel.archives-ouvertes.fr/tel-01413183
Contributeur : Abes Star <>
Soumis le : vendredi 9 décembre 2016 - 14:36:06
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39
Document(s) archivé(s) le : jeudi 23 mars 2017 - 10:16:25

Fichier

TheseKaufmann2.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01413183, version 1

Citation

Emilie Kaufmann. Analysis of bayesian and frequentist strategies for sequential resource allocation. Machine Learning [cs.LG]. Télécom ParisTech, 2014. English. 〈NNT : 2014ENST0056〉. 〈tel-01413183〉

Partager

Métriques

Consultations de la notice

435

Téléchargements de fichiers

278