Improving offline evaluation of contextual bandit algorithms via bootstrapping techniques - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Improving offline evaluation of contextual bandit algorithms via bootstrapping techniques

Résumé

In many recommendation applications such as news recommendation, the items that can be rec- ommended come and go at a very fast pace. This is a challenge for recommender systems (RS) to face this setting. Online learning algorithms seem to be the most straight forward solution. The contextual bandit framework was introduced for that very purpose. In general the evaluation of a RS is a critical issue. Live evaluation is of- ten avoided due to the potential loss of revenue, hence the need for offline evaluation methods. Two options are available. Model based meth- ods are biased by nature and are thus difficult to trust when used alone. Data driven methods are therefore what we consider here. Evaluat- ing online learning algorithms with past data is not simple but some methods exist in the litera- ture. Nonetheless their accuracy is not satisfac- tory mainly due to their mechanism of data re- jection that only allow the exploitation of a small fraction of the data. We precisely address this issue in this paper. After highlighting the limita- tions of the previous methods, we present a new method, based on bootstrapping techniques. This new method comes with two important improve- ments: it is much more accurate and it provides a measure of quality of its estimation. The latter is a highly desirable property in order to minimize the risks entailed by putting online a RS for the first time. We provide both theoretical and ex- perimental proofs of its superiority compared to state-of-the-art methods, as well as an analysis of the convergence of the measure of quality.
Nous nous intéressons au problème de recommendation dans le contexte où l'ensemble d'items recommendables évolue à un rythme élevé. Les algorithmes d'apprentissage en-ligne constituent une solution à ce problème. Les bandits contextuels ont été introduits à cet effet. D'une manière générale, l'évaluation des systèmes de recommendaiton est un problème critique. L'évaluation en-ligne est rarement possible. Reste alors l'évaluation face à un modèle ou l'évaluation basée sur des historiques d'interaction utilisateurs/système de recommendation. Dans cet article, nous considérons cette seconde alternative. La précision des solutions existants dans la littérature n'est pas satisfaisante. C'est ce point que nous étudions ici. Après avoir montré les limites des méthodes existantes, nous présentons une nouvelle approche basée sur la technique de bootstrap. Cette méthode apporte deux avantages : sa précision est plus grande que celle proposée jusqu'à maintenant et il est possible d'estimer sa qualité. Ce dernier point est particulièrement important pour minimiser les risques lors de la mise en ligne de l'algorithme de recommendation. Nous proposons des arguments théoriques et expérimentaux quant à la supériorité de cette méthode par rapport à l'état de l'art. Nous étudions également formellement la convergence de l'estimateur.
Fichier principal
Vignette du fichier
Improving-offline-evaluation-of-contextual-bandit-algorithms-via-bootstrapping-techniques.pdf (277.78 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00990840 , version 1 (14-05-2014)

Identifiants

Citer

Olivier Nicol, Jérémie Mary, Philippe Preux. Improving offline evaluation of contextual bandit algorithms via bootstrapping techniques. International Conference on Machine Learning, Jun 2014, Beijing, China. ⟨hal-00990840⟩
308 Consultations
502 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More