Étude du regret associé aux algorithmes de bandit de type Narendra-Shapiro

Carte non disponible

Date/heure
Date(s) - 27/03/2017
14 h 00 min - 15 h 00 min

Catégories Pas de Catégories


Les algorithmes de bandit de types N-S ont été introduits dans les années 60 en vue d’applications aux tests cliniques notamment. Le principe d’un algorithme de bandit peut être défini de la manière suivante : on dispose de 2 sources A et B (ayant respectivement une probabilité pA et pB d’être satisfaisante lorsque qu’elle est utilisée) et on souhaite déterminer laquelle des deux est la plus performante. Récemment, Lamberton et Pagès ont introduit une version dite “pénalisée” de cet algorithme pour laquelle divers résultats de convergence ont été démontrés. Nous nous intéressons dans ce travail à la question suivante : ces algorithmes sont-ils performants d’un point de vue de regret ? Le regret étant la différence entre la meilleure performance possible (i.e celle obtenue en choisissant toujours la meilleur source) et celle obtenue par l’algorithme. Dans cette présentation, nous verrons qu’une légère modification de cette algorithme conduit à des bornes de regret de l’ordre de \sqrt{n} uniformément en pA et pB. Nous étendrons aussi les résultats de Lamberton et Pagès à une version multidimensionnelle de l’algorithme. Nous établirons une convergence en loi vers la mesure invariante d’un PDMP pour lequel nous étudierons sa convergence à l’équilibre par méthode de couplage.

https://www.tse-fr.eu/people/sofiane-saadane

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange