Interactively optimizing information retrieval systems as a dueling bandits problem

ABSTRACT

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.

REFERENCES

• 1: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148177]
• 2: Carterette, B., Bennett, P., Chickering, D. M., & Dumais, S. (2008). Here or There: Preference Judgments for Relevance. European Conference on Information Retrieval (ECIR) (pp. 16--27).
• 3: Carterette, B., & Jones, R. (2007). Evaluating Search Engines by Modeling the Relationship Between Relevance and Clicks. Neural Information Processing Systems (NIPS) (pp. 217--224).
• 4: Soumen Chakrabarti , Rajiv Khanna , Uma Sawant , Chiru Bhattacharyya, Structured learning for non-smooth ranking losses, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401906]
• 5: Donmez, P., Svore, K., & Burges, C. (2009). On the Local Optimality of LambdaRank. ACM Conference on Information Retrieval (SIGIR).
• 6: Georges E. Dupret , Benjamin Piwowarski, A user browsing model to predict search engine click data from past observations., Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390392]
• 7: Abraham D. Flaxman , Adam Tauman Kalai , H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Filip Radlinski , Geri Gay, Evaluating the accuracy of implicit feedback from clicks and query reformulations in Web search, ACM Transactions on Information Systems (TOIS), v.25 n.2, p.7-es, April 2007 [doi>10.1145/1229179.1229181]
• 9: Kleinberg, R. (2004). Nearly tight bounds for the continuum-armed bandit problem. Neural Information Processing Systems (NIPS) (pp. 697--704).
• 10: Langford, J., & Zhang, T. (2007). The Epoch-Greedy Algorithm for Contextual Multi-armed Bandits. Neural Information Processing Systems (NIPS) (pp. 817--824).
• 11: Pandey, S., Agarwal, D., Chakrabarti, D., & Josifovski, V. (2007). Bandits for Taxonomies: A Model-based Approach. SIAM Conference on Data Mining (SDM) (pp. 216--227).
• 12: Filip Radlinski , Robert Kleinberg , Thorsten Joachims, Learning diverse rankings with multi-armed bandits, Proceedings of the 25th international conference on Machine learning, p.784-791, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390255]
• 13: Filip Radlinski , Madhu Kurup , Thorsten Joachims, How does clickthrough data reflect retrieval quality?, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458092]
• 14: Yue, Y., Broder, J., Kleinberg, R., & Joachims, T. (2009). The K-armed Dueling Bandits Problem. Conference on Learning Theory (COLT).
• 15: Yisong Yue , Thorsten Joachims, Predicting diverse subsets using structural SVMs, Proceedings of the 25th international conference on Machine learning, p.1224-1231, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390310]
• 16: Zinkevich, M. (2003). Online Convex Programming and Generalized Infinitesimal Gradient Ascent. International Conference on Machine Learning (ICML) (pp. 928--936).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies
      I.6.6 Simulation Output Analysis

General Terms:
Algorithms, Design, Performance, Theory