Aller au contenu principal

Kimang KHUN

Indexability and learning algorithms for Markovian bandits

Jeudi 30 Mars 2023

Résumé :

Un bandit markovien est un problème de décision séquentielle dans lequel un sous-ensemble de bras doivent être activés à chaque instant, et les bras évoluent de manière markovienne. Il y a deux catégories de bandits markoviens. Si les bras qui ne sont pas activés restent figés, on entre alors dans la catégorie des bandits markoviens avec repos. S’ils évoluent de manière markovienne, on parle alors de bandit markovien sans repos. En général, les bandits markoviens souffrent de la malédiction de la dimension qui rend souvent la solution exacte prohibitive en terme de calculs. Il faut donc recourir à des heuristiques telles que les politiques d’indice. Deux indices célèbres sont l’indice de Gittins pour les bandits avec repos et l’indice de Whittle pour les bandits sans repos.

Cette thèse se concentre sur deux questions : (1) le calcul d’indices lorsque tous les paramètres du modèle sont connus et (2) les algorithmes d’apprentissage lorsque les paramètres sont inconnus.
Pour le calcul de l’indice, nous relevons les ambiguïtés de la définition classique de l’indexabilité et proposons une définition qui assure l’unicité de l’indice de Whittle quand ce dernier existe. Nous développons ensuite un algorithme testant l’indexabilité et calculant les indices de Whittle. La complexité théorique de notre algorithme est O(S2.5286), où S est le nombre d’états du bras.

Pour l’apprentissage dans les bandits avec repos, nous montrons que MB-PSRL et MB-UCBVI, des versions modifiées des algorithmes PSRL et UCBVI, peuvent tirer parti de la politique d’indice de Gittins pour avoir une garantie de regret et un temps d’exécution qui passent à l’échelle avec le nombre de bras. De plus, nous montrons que MB-UCRL2, une version modifiée de UCRL2, possède également une garantie de regret qui passe à l’échelle. Cependant, MB-UCRL2 a un temps d’exécution exponentiel dans le nombre de bras. Lors de l’apprentissage dans les bandits sans repos, la garantie de regret dépend fortement de la structure du bandit. Ainsi, nous étudions comment la structure des bras se traduit dans la structure du bandit. Nous exposons une sous-classe de bandits sans repos qui ne sont pas apprenables. Nous montrons également qu’il est difficile de construire des hypothèses sur les bras qui rendent les bandits sans repos apprenables efficacement.

Date et Lieu

Jeudi 30 Mars 2023 à 15h00
Salle de séminaire 1 du bâtiment IMAG
Lien Zoom

Composition du Jury

Konstantin AVRACHENKOV
Directeur de recherche, Inria Sophia Antipolis, France, rapporteur
Aditya MAHAJAN
Associate professor, McGill University, Canada, rapporteur
Ana BUSIC
Chargée de recherche, Inria, France, examinatrice
Franck IUTZELER
Maître de conférences, Université Grenoble-Alpes, France, examinateur
Aurélien GARIVIER
Professeur, Ecole Normale Supérieure de Lyon, France, examinateur
Bruno GAUJAL
Directeur de recherche, Inria de l'Université Grenoble-Alpes, France, directeur de thèse

Publié le 28 mars 2023

Mis à jour le 8 octobre 2024