 |
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)).
