LogoLogo

Ménard, Pierre. Sur la notion d'optimalité dans les problèmes de bandit stochastique

Ménard, Pierre (2018). Sur la notion d'optimalité dans les problèmes de bandit stochastique.

[img]PDF - nécessite un logiciel de visualisation PDF comme GSview, Xpdf or Adobe Acrobat Reader
3323Kb

Résumé en francais

Cette thèse s'inscrit dans les domaines de l'apprentissage statistique et de la statistique séquentielle. Le cadre principal est celui des problèmes de bandit stochastique à plusieurs bras. Dans une première partie, on commence par revisiter les bornes inférieures sur le regret. On obtient ainsi des bornes non-asymptotiques dépendantes de la distribution que l'on prouve de manière très simple en se limitant à quelques propriétés bien connues de la divergence de Kullback-Leibler. Puis, on propose des algorithmes pour la minimisation du regret dans les problèmes de bandit stochastique paramétrique dont les bras appartiennent à une certaine famille exponentielle ou non-paramétrique en supposant seulement que les bras sont à support dans l'intervalle unité, pour lesquels on prouve l'optimalité asymptotique (au sens de la borne inférieure de Lai et Robbins) et l'optimalité minimax. On analyse aussi la complexité pour l'échantillonnage séquentielle visant à identifier la distribution ayant la moyenne la plus proche d'un seuil fixé, avec ou sans l'hypothèse que les moyennes des bras forment une suite croissante. Ce travail est motivé par l'étude des essais cliniques de phase I, où l'hypothèse de croissance est naturelle. Finalement, on étend l'inégalité de Fano qui contrôle la probabilité d'évènements disjoints avec une moyenne de divergences de Kullback-leibler à des variables aléatoires arbitraires bornées sur l'intervalle unité. Plusieurs nouvelles applications en découlent, les plus importantes étant une borne inférieure sur la vitesse de concentration de l'a posteriori Bayésien et une borne inférieure sur le regret pour un problème de bandit non-stochastique.

Sous la direction du :
Directeur de thèse
Garivier, Aurélien
Stoltz, Gilles
Ecole doctorale:Mathématiques, informatique, télécommunications de Toulouse (MITT)
laboratoire/Unité de recherche :Institut de Mathématiques de Toulouse (IMT), UMR 5219
Mots-clés libres :Bandits stochastiques multi-bras - Théorie de l'information - Bornes inférieures non-asymptotiques - Analyse du regret - Optimalité asymptotique - Optimalité minimax - Borne supérieure de confiance - Bandits à seuil - Identification du meilleur bras - Régression unimodale - Test d'hypothèses multiples
Sujets :Mathématiques
Déposé le :14 Nov 2018 15:40