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.

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.