Un algorithme pratique pour les bandits multijoueurs lorsque les moyens d'armement varient entre les joueurs.

Résumé Nous étudions un problème de bandit stochastique multijoueur à plusieurs bras dans lequel les joueurs ne peuvent pas communiquer, et si deux joueurs ou plus tirent le même bras, une collision se produit et les joueurs impliqués reçoivent une récompense nulle. Nous considérons le cadre hétérogène difficile, dans lequel différents bras peuvent avoir des moyens différents pour différents joueurs, et nous proposons un nouvel algorithme efficace qui combine l'idée de tirer parti des collisions forcées pour une communication implicite et celle d'effectuer des éliminations de correspondance. Nous donnons une analyse en temps fini de notre algorithme, en limitant son regret par O((log T)^{1+\kappa}) pour tout \kappa>0 fixe. Si l'affectation optimale des joueurs aux armes est unique, nous montrons en outre qu'elle atteint le regret optimal O(log(T)), résolvant ainsi une question ouverte soulevée à NeurIPS 2018.