5 juil. 2015 Villeneuve d'Ascq (Lille) (France)
Un Algorithme pour le Problème des Bandits Manchots avec Stationnarité par Parties
Robin Allesiardo  1, 2@  , Raphaël Féraud  1@  
1 : Orange Labs - Lannion
France Télécom
Technopole Anticipa 2 avenue Pierre Marzin 22300 LANNION -  France
2 : TAO  (INRIA Saclay - Ile de France)  -  Site web
Université Paris XI - Paris Sud, CNRS : UMR8623, INRIA
DIGITEO Bat. Claude Shannon - Université de Paris-Sud, Bâtiment 660, 91190 Gif-sur-Yvette -  France

Dans le problème des bandits manchots, un joueur possède le choix entre plusieurs bras possédant des espérances de gain différentes. Son but est de maximiser la récompense obtenue après T essais. Il doit alors explorer pour estimer les récompenses de chaque machine tout en exploitant le bras qu'il estime le meilleur. C'est le dilemme exploration/exploitation. Dans le cas des bandits adverses, la séquence de récompenses d'une machine est choisie à l'avance par un adversaire. En pratique, la notion de meilleur bras sur le jeu complet est trop restrictive pour des applications comme l'optimisation publicitaire où la meilleure publicité peut changer au cours du temps. Dans ce papier, nous considérons une variante du problème adverse, où le jeu est divisé en un nombre inconnu de périodes à l'intérieur desquelles les récompenses sont tirées dans des distributions stochastiques. Entre chaque période, le meilleur bras peut changer. Nous présentons un algorithme utilisant l'exploration constante d'EXP3 pour détecter les changements de meilleur bras. Son analyse montre, que sur un jeu divisé en N segments où le meilleur bras change, l'algorithme proposé possède un regret en O(N sqrt(T log T)).


Personnes connectées : 2