Foundations and Trends® in Information Retrieval > Vol 13 > Issue 4

Bandit Algorithms in Information Retrieval

Dorota Glowacka, University of Helsinki, Finland, glowacka@cs.helsinki.fi
 
Suggested Citation
Dorota Glowacka (2019), "Bandit Algorithms in Information Retrieval", Foundations and Trends® in Information Retrieval: Vol. 13: No. 4, pp 299-424. http://dx.doi.org/10.1561/1500000067

Published: 23 May 2019
© 2019 D. Glowacka
 
Subjects
Information Retrieval,  Collaborative filtering and recommender systems,  Metasearch, rank aggregation and data fusion,  Performance issues for IR systems,  Usability, interactivity, and visualisation issues in IR,  User modelling and user studies for IR,  Web search
 

Free Preview:

Article Help

Share

Login to download a free copy

Free until: 21 September 2019

In this article:
1. Introduction
2. Reinforcement Learning and Bandit Algorithms
3. Click Models and Bandit Algorithms
4. Ranking and Optimization
5. Ranker Evaluation
6. Recommendation
7. Conclusions and Research Trends
8. Conclusions and Future Directions
Acknowledgements
References

Abstract

Bandit algorithms, named after casino slot machines sometimes known as “one-armed bandits”, fall into a broad category of stochastic scheduling problems. In the setting with multiple arms, each arm generates a reward with a given probability. The gambler’s aim is to find the arm producing the highest payoff and then continue playing in order to accumulate the maximum reward possible. However, having only a limited number of plays, the gambler is faced with a dilemma: should he play the arm currently known to produce the highest reward or should he keep on trying other arms in the hope of finding a better paying one? This problem formulation is easily applicable to many real-life scenarios, hence in recent years there has been an increased interest in developing bandit algorithms for a range of applications. In information retrieval and recommender systems, bandit algorithms, which are simple to implement and do not require any training data, have been particularly popular in online personalization, online ranker evaluation and search engine optimization. This survey provides a brief overview of bandit algorithms designed to tackle specific issues in information retrieval and recommendation and, where applicable, it describes how they were applied in practice.

DOI:10.1561/1500000067
ISBN: 978-1-68083-574-8
184 pp. $90.00
Buy book
 
ISBN: 978-1-68083-575-5
184 pp. $140.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Reinforcement Learning and Bandit Algorithms
3. Click Models and Bandit Algorithms
4. Ranking and Optimization
5. Ranker Evaluation
6. Recommendation
7. Conclusions and Research Trends
8. Conclusions and Future Directions
Acknowledgements
References

Bandit Algorithms in Information Retrieval

This monograph provides an overview of bandit algorithms inspired by various aspects of Information Retrieval (IR), such as click models, online ranker evaluation, personalization or the cold-start problem. Using a survey style, each chapter focuses on a specific IR problem and explains how it was addressed with various bandit approaches. Within each section, all the algorithms are presented in chronological order.

The monograph shows how specific concepts related to bandit algorithms. This comprehensive, chronological approach enables the author to explain the impact of IR on the development of new bandit algorithms as well as the impact of bandit algorithms on the development of new methods in IR.

The survey is primarily intended for two groups of readers: researchers in Information Retrieval or Machine Learning and practicing data scientists. It is accessible to anyone who has completed introductory to intermediate level courses in machine learning and/or statistics.

 
INR-067