Méthode de décomposition-coordination pour les problèmes de bandit à horizon fini.

Résumé La résolution optimale d'un problème de bandit à bras multiples souffre de la malédiction de la dimensionnalité. En effet, le recours à la programmation dynamique conduit à une croissance exponentielle du temps de calcul, à mesure que le nombre de bras et l'horizon augmentent. Nous introduisons une heuristique de décomposition-coordination, DeCo, qui transforme le problème initial en problèmes de bandit à un bras coordonnés en parallèle. En conséquence, nous obtenons un temps de calcul qui est essentiellement linéaire dans le nombre de bras. En outre, la décomposition fournit une limite inférieure théorique sur le regret. Pour le cas du bandit à deux bras, la programmation dynamique fournit la solution exacte, qui est presque égalée par l'heuristique DeCo. De plus, dans les simulations numériques avec jusqu'à 100 tours et 20 armes, DeCo surpasse les algorithmes classiques (échantillonnage de Thompson et limite supérieure de confiance de Kullback-Leibler) et correspond presque à la limite inférieure théorique du regret pour 20 armes.