Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits

Nous proposons un algorithme de bandit multi-armé qui explore en se basant sur la randomisation de son histoire. L’idée principale est d’estimer la valeur du bras à partir de l’échantillon bootstrap de son historique, auquel nous ajoutons des pseudo-observations après chaque traction du bras. Les pseudo observations semblent nuisibles. Mais au contraire, ils garantissent que l’échantillon bootstrap est optimiste avec une probabilité élevée. Pour cette raison, nous appelons notre algorithme Giro, qui est une abréviation de garbage in, récompense. Nous analysons Giro chez un bandit de Bernoulli aux bras croisés et prouvons un O (KΔ-1logn) lié à son regret à n tour, où Δ indique la différence entre les récompenses attendues des meilleurs bras optimaux. Le principal avantage de notre stratégie d’exploration est qu’elle peut être appliquée à toute généralisation de fonction de récompense, telle que les réseaux de neurones. Nous évaluons Giro et sa variante contextuelle sur de multiples problèmes synthétiques et réels, et constatons que Giro est comparable ou supérieur aux algorithmes les plus avancés.