Cette thèse, à la croisée entre les domaines de l’intelligence artificielle, de la statistique séquentielle et de l’optimisation, s’intéresse au problème d’identification du meilleur bras (en espérance) dans les bandits non structurés à K bras. Ce problème possède deux approches dont les niveaux de compréhension sont très différents.
Le cadre le mieux compris est celui de la confiance fixée, pour lequel des stratégies asymptotiquement optimales sont connues. Nous introduisons dans un premier temps une nouvelle stratégie (asymptotiquement optimale), que nous analysons de manière non asymptotique, ce qui permet d’obtenir de nouvelles garanties théoriques dans ce cadre. Cette analyse est réalisée pour des bandits gaussiens grâce à l’obtention de résultats quantitatifs de régularité concernant les fréquences de tirages optimales des bras. Puis pour des modèles plus généraux (exponentiels), nous voyons ces fréquences optimales comme point fixe de transformations amenant naturellement à la définition
d’un algorithme de type Top Two adaptatif. Finalement nous montrons que certains algorithmes Top Two adaptatifs sont asymptotiquement optimaux pour tout modèle exponentiel.
Par ailleurs, dans le cadre à budget fixé, nous proposons des généralisations à des modèles nonparamétriques des bornes (supérieures et inférieures) connues jusqu’à présent pour des modèles très spécifiques. Les bornes obtenues font intervenir des quantités de théorie de l’information plus précises que les écarts entre les moyennes qui apparaissaient précédemment. Ces quantités pourraient être la clé pour mesurer la complexité de l’identification de meilleur bras à budget fixé, aujourd’hui encore inconnue.
Gratuit
Disciplines