Pas de regrets pour avoir appris le Prieur dans Bandits

Résumé :

Nous proposons 𝙰𝚍𝚊𝚃𝚂, un algorithme d'échantillonnage de Thompson qui s'adapte séquentiellement aux tâches de bandit avec lesquelles il interagit. L'idée clé de 𝙰𝚍𝚊𝚃𝚂 est de s'adapter à une distribution préalable de tâche inconnue en maintenant une distribution sur ses paramètres. Lors de la résolution d'une tâche de bandit, cette incertitude est marginalisée et correctement prise en compte. 𝙰𝚍𝚊𝚃𝚂 est un algorithme entièrement bayésien qui peut être implémenté efficacement dans plusieurs classes de problèmes de bandits. Nous dérivons des bornes supérieures sur son regret de Bayes qui quantifient la perte due à l'ignorance de l'antériorité de la tâche, et nous montrons qu'elle est faible. Notre théorie est soutenue par des expériences, où 𝙰𝚍𝚊𝚃𝚂 surpasse les algorithmes antérieurs et fonctionne bien même dans des problèmes difficiles du monde réel.