Interactively optimizing information retrieval systems as a dueling bandits problem

By Yisong Yue, Thorsten Joachims. 2009

400 citations recorded by the source corpus.

We present an on-line learning framework tailored towards real-time learning from observed user behavior in search engines and other information retrieval systems. In particular, we only require pairwise comparisons which were shown to be reliably inferred from implicit feedback (Joachims et al., 2007; Radlinski et al., 2008b). We will present an algorithm with theoretical guarantees as well as simulation results.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Information Retrieval & Search, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Information Retrieval & Search

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Yue and Joachims (2009, 2011); Saha and Krishnamurthy (2022); Ghoshal and Saha (2022); Saha and Gopalan (2018a) The setting is relevant in various realworld systems which aim to collect information from user preferences, including recommender systems, retail management, search engine optimization,…”
Contextual Dueling Bandits (2015, methodology): “The method that is the most closely related to our work is Dueling Bandit Gradient Descent (DBGD) (Yue and Joachims, 2009).”
DRN: A Deep Reinforcement Learning Framework for News Recommendation (2018, methodology): “Therefore, rather than doing random exploration, we apply a Dueling Bandit Gradient Descent algorithm [16, 17, 49] to do the exploration.”
Boosting Search Engines with Interactive Agents (2021, neutral): “Other work at the intersection of IR and RL concerns bandit methods for news recommendation (Li et al., 2010) and learning to rank (Yue & Joachims, 2009).”
Interactive machine learning for health informatics: when do we need the human-in-the-loop? (2016, methodology): “Meanwhile ILO has been applied mostly to information retrieval, for example Yue and Joachims [76] presented an online learning framework, tailored toward real-time learning from observed user behavior in search engines.”
Programming by Feedback (2014, background): “Two early ILO approaches focussing on information retrieval are (Yue & Joachims, 2009) and (Viappiani & Boutilier, 2010).”
Relative confidence sampling for efficient on-line ranker evaluation (2014, background): “Another important question is to design ranker evaluation algorithms that can deal with even larger (possibly inﬁnite) numbers of rankers, without requiring convexity assumptions such as those in [35].”
Unbiased Learning-to-Rank with Biased Feedback (2016, methodology): “Different from online learning via bandit algorithms and interleaving [30, 22], batch learning from bandit feedback (BLBF) [25] still uses randomization during feedback collection, and then performs offline learning.”
Introduction to Multi-Armed Bandits (2019, methodology): “In dueling bandits (Yue et al., 2012; Yue and Joachims, 2009), numeric reward is unavailable to the algorithm.”
Copeland Dueling Bandits (2015, methodology): “Given that both our algorithms utilize confidence bounds to make their choices, we anticipate that continuous-armed UCB-style algorithms like those proposed in [23–29] can be combined with our ideas to produce a solution to the continuous-armed Copeland bandit problem that does not rely on the conve”
A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits (2015, methodology): “The K-armed dueling bandit problem is a variation of the classical Multi-Armed Bandit (MAB) problem introduced by Yue and Joachims (2009) to formalize the exploration/exploitation dilemma in learning from preference feedback.”
Double Thompson Sampling for Dueling Bandits (2016, methodology): “This model can be applied in systems such as information retrieval (IR) [5, 6], where user preferences are easier to obtain and typically more stable.”
Coactive Learning (2015, methodology): “Most closely related to Coactive Learning is the dueling bandits setting (Yue, Broder, Kleinberg, & Joachims, 2009; Yue & Joachims, 2009).”
A Survey of Preference-Based Online Learning with Bandit Algorithms (2014, methodology): “An example of such a function is the logistic function, which was used in [45].”
MergeDTS (2018, methodology): “In practice, bandit algorithms are always deployed and evaluated within limited user iterations [34, 49].”
Beat the Mean Bandit (2011, methodology): “The K-armed Dueling Bandits Problem (Yue et al., 2009) is an iterative learning problem on a set of bandits B = {b 1 , . . . , b K } (also called arms or strategies).”
Refining Recency Search Results with User Click Feedback (2011, background): “The exploration/exploitation tradeoﬀ described above is a deﬁning characteristic of a class of problems known as bandit problems [27], which has received considerable attention recently for Internet-related applications [25, 29].”
Query Complexity of Derivative-Free Optimization (2012, background): “Yue and Joachims in [14] built off the work of Flaxman [19] and showed that a pairwise comparison oracle can achieve the same n/T 1/4 rate achieved by function evaluations.”