Évaluation par les données d'algorithmes de bandits contextuels avec applications à la recommandation dynamique

The context of this thesis work is dynamic recommendation. Recommendation is the action,for an intelligent system, to supply a user of an application with personalized content so as toenhance what is refered to as ”user experience” e.g. recommending a product on a merchantwebsite or even an article on a blog. Recommendation is considered dynamic when the contentto recommend or user tastes evolve rapidly e.g. news recommendation. Many applications thatare of interest to us generates a tremendous amount of data through the millions of online usersthey have. Nevertheless, using this data to evaluate a new recommendation technique or evencompare two dynamic recommendation algorithms is far from trivial. This is the problem weconsider here. Some approaches have already been proposed. Nonetheless they were not studiedvery thoroughly both from a theoretical point of view (unquantified bias, loose convergencebounds...) and from an empirical one (experiments on private data only). In this work we startby filling many blanks within the theoretical analysis. Then we comment on the result of anexperiment of unprecedented scale in this area: a public challenge we organized. This challengealong with a some complementary experiments revealed a unexpected source of a huge bias:time acceleration. The rest of this work tackles this issue. We show that a bootstrap-basedapproach allows to significantly reduce this bias and more importantly to control it.Ce travail de th`ese a ́et ́e r ́ealis ́e dans le contexte de la recommandation dynamique. La recom-mandation est l’action de fournir du contenu personnalis ́e `a un utilisateur utilisant une ap-plication, dans le but d’am ́eliorer son utilisation e.g. la recommandation d’un produit surun site marchant ou d’un article sur un blog. La recommandation est consid ́er ́ee commedynamique lorsque le contenu a ` recommander ou encore les goˆuts des utilisateurs ́evoluentrapidement e.g. la recommandation d’actualit ́es. Beaucoup d’applications auxquelles nousnous int ́eressons g ́en`erent d’ ́enormes quantit ́es de donn ́ees grˆace `a leurs millions d’utilisateurssur Internet. N ́eanmoins, l’utilisation de ces donn ́ees pour ́evaluer une nouvelle technique derecommandation ou encore comparer deux algorithmes de recommandation est loin d’ˆetre triv-iale. C’est cette probl ́ematique que nous consid ́erons ici. Certaines approches ont d ́ej`a ́et ́epropos ́ees. N ́eanmoins elles sont tr`es peu ́etudi ́ees autant th ́eoriquement (biais non quantifi ́e,borne de convergence assez large...) qu’empiriquement (exp ́eriences sur donn ́ees priv ́ees). Dansce travail nous commen ̧cons par combler de nombreuses lacunes de l’analyse th ́eorique. En-suite nous discutons les r ́esultats tr`es surprenants d’une exp ́erience `a tr`es grande ́echelle : unecomp ́etition ouverte au public que nous avons organis ́ee. Cette comp ́etition nous a permisde mettre en ́evidence une source de biais consid ́erable et constamment pr ́esente en pratique :l’acc ́el ́eration temporelle. La suite de ce travail s’attaque a ` ce probl`eme. Nous montrons qu’uneapproche `a base de bootstrap permet de r ́eduire mais surtout de contrˆoler ce biais