Show simple item record

dc.contributor.authorSalomon, Antoine
dc.contributor.authorAudibert, Jean-Yves
dc.date.accessioned2013-11-19T09:34:51Z
dc.date.available2013-11-19T09:34:51Z
dc.date.issued2014
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12095
dc.language.isoenen
dc.subjectExploration–exploitation tradeoffen
dc.subjectMulti-armed stochastic banditen
dc.subjectRegret deviations/risken
dc.subject.ddc338.5en
dc.subject.classificationjelC73en
dc.subject.classificationjelD81en
dc.titleRobustness of stochastic bandit policiesen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherÉcole des Ponts ParisTech, Université Paris Est;France
dc.description.abstractenThis 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.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol519
dc.relation.isversionofjnldate2014
dc.relation.isversionofjnlpages46-67
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.tcs.2013.09.019en
dc.identifier.urlsitehttp://hal.inria.fr/hal-00821670en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelMicroéconomieen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record