Résolution des bandits de Bernoulli Rank-One avec un échantillonnage Thompson unimodal.

Résumé Les bandits stochastiques de rang un (Katarya et al, (2017a,b)) sont un cadre simple pour les problèmes de minimisation du regret sur les matrices de rang un d'armes. Les algorithmes initialement proposés sont prouvés avoir un regret logarithmique, mais ne correspondent pas à la borne inférieure existante pour ce problème. Nous comblons cette lacune en prouvant d'abord que les bandits rank-one sont une instance particulière des bandits unimodaux, puis en fournissant une nouvelle analyse de l'échantillonnage Thompson unimodal (UTS), initialement proposé par Paladino et al (2017). Nous prouvons une limite de regret asymptotiquement optimale sur le regret fréquentiste de l'UTS et nous soutenons nos affirmations avec des simulations montrant l'amélioration significative de notre méthode par rapport à l'état de l'art.