Échantillonnage asymptotiquement optimal dirigé par l'information

Résumé

Nous présentons un algorithme simple et efficace pour les bandits linéaires stochastiques avec un nombre fini d'actions, qui est asymptotiquement optimal et optimal dans le pire des cas en temps fini. L'approche est basée sur le cadre frequentiste d'échantillonnage dirigé par l'information (IDS), avec un substitut pour le gain d'information qui est informé par le problème d'optimisation qui définit la limite inférieure asymptotique. Notre analyse met en lumière la manière dont l'IDS équilibre le compromis entre le regret et l'information. De plus, nous découvrons un lien surprenant entre les méthodes primales-duales récemment proposées et l'algorithme IDS bayésien. Nous démontrons empiriquement que l'IDS est compétitif par rapport à l'UCB en temps fini, et peut être significativement meilleur dans le régime asymptotique.