Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

Robustness of stochastic bandit policies

Antoine Salomon 1 Jean-Yves Audibert 1, 2
2 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : This paper studies the deviations of the regret in a stochastic multi-armed bandit problem. When the total number of plays n is known beforehand by the agent, Audibert et al. [2] exhibit a policy such that with probability at least 1-1/n, the regret of the policy is of order log n. They have also shown that such a property is not shared by the popular ucb1 policy of Auer et al. [3]. This work first answers an open question: it extends this negative result to any anytime policy (i.e. any policy that does not take the number of plays n into account). Another contribution of this paper is to design robust anytime policies for specific multi-armed bandit problems in which some restrictions are put on the set of possible distributions of the different arms. We also show that, for any policy (i.e. even when the number of plays n is known), the regret is of order log n with probability at least 1-1/n, so that the policy of Audibert et al. has the best possible deviation properties.
Liste complète des métadonnées

https://hal-enpc.archives-ouvertes.fr/hal-01801056
Contributeur : Renaud Marlet <>
Soumis le : lundi 28 mai 2018 - 10:29:44
Dernière modification le : mardi 22 septembre 2020 - 03:47:49

Lien texte intégral

Identifiants

Citation

Antoine Salomon, Jean-Yves Audibert. Robustness of stochastic bandit policies. Theoretical Computer Science, Elsevier, 2014, 519, pp.46 - 67. ⟨10.1016/j.tcs.2013.09.019⟩. ⟨hal-01801056⟩

Partager

Métriques

Consultations de la notice

168