Algorithms for Markovian bandits : Indexability and Learning

Des algorithmes pour les bandits markoviens : indexabilité et apprentissage 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 banditsmarkoviens. Si les bras qui ne sont pas activés restent figés, on entre alors dans la catégorie des banditsmarkoviens 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 solutionexacte 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 banditssans repos.Cette thèse se concentre sur deux questions : (1) le calcul d’indices lorsque tous les paramètres du modèle sontconnus 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 proposonsune définition qui assure l’unicité de l’indice de Whittle quand ce dernier existe. Nous développons ensuiteun algorithme testant l’indexabilité et calculant les indices de Whittle. La complexité théorique de notrealgorithme 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 versionsmodifiées des algorithmes PSRL et UCBVI, peuvent tirer parti de la politique d’indice de Gittins pour avoirune garantie de regret et un temps d’exécution qui passent à l’échelle avec le nombre de bras. De plus, nousmontrons que MB-UCRL2, une version modifiée de UCRL2, possède également une garantie de regret quipasse à l’échelle. Cependant, MB-UCRL2 a un temps d’exécution exponentiel dans le nombre de bras. Lors del’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 unesous-classe de bandits sans repos qui ne sont pas apprenables. Nous montrons également qu’il est difficile deconstruire des hypothèses sur les bras qui rendent les bandits sans repos apprenables efficacement.