Algorithmes asymptotiquement optimaux pour les bandits à jeux multiples budgétisés.

Résumé Nous étudions une généralisation du problème du bandit à plusieurs bras avec des jeux multiples où il y a un coût associé à la traction de chaque bras et l'agent a un budget à chaque moment qui dicte combien il peut s'attendre à dépenser. Nous dérivons une borne inférieure de regret asymptotique pour tout algorithme uniformément efficace dans notre cadre. Nous étudions ensuite une variante de l'échantillonnage de Thompson pour les récompenses de Bernoulli et une variante de KL-UCB pour les familles exponentielles à un paramètre et les récompenses bornées à support fini. Nous montrons que ces algorithmes sont asymptotiquement optimaux, à la fois en termes de taux et de constantes dépendantes du problème, y compris dans le cadre de la marge épaisse où plusieurs bras tombent sur la limite de décision.