On Bayesian index policies for sequential resource allocation.

Résumé Cet article traite des politiques d'indexation visant à minimiser le regret (fréquentiste) dans un modèle stochastique de bandit à bras multiples, inspiré par une vision bayésienne du problème. Notre principale contribution est de prouver que l'algorithme Bayes-UCB, qui repose sur les quantiles des distributions postérieures, est asymptotiquement optimal lorsque les distributions de récompense appartiennent à une famille exponentielle unidimensionnelle, pour une grande classe de distributions antérieures. Nous montrons également que la littérature bayésienne donne un nouvel aperçu du type de taux d'exploration qui pourrait être utilisé dans les algorithmes fréquentistes de type UCB. En effet, les approximations de la solution optimale bayésienne ou des indices de Gittins à horizon fini fournissent une justification pour les algorithmes kl-UCB+ et kl-UCB-H+, dont l'optimalité asymptotique est également établie.