Statistics Department Seminar Series: Ambuj Tewari, Assistant Professor, Department of Statistics, University of Michigan

A lot of effort has gone into building ranking systems that can rank items (web pages, images, videos, news items, etc.) in response to user queries (say “election 2016”) in the order of their relevance to the query. A major practical issue in this area is the difficulty faced in obtaining relevance judgments about items from humans. In systems that interact with users and improve in real-time, it is especially important to not burden the user with the task of giving feedback on the entire ranked list. Instead, we might just ask the user about the quality of the top few, say 1 or 2, items. In this talk, I will describe some recent results we have obtained about the fundamental limits of learning from feedback only on the top few items. There are fascinating connections with a class of repeated games called partial monitoring games. I will also describe some important questions that are still open.

This talk is based on joint work with my Ph.D. student Dr. Sougata Chaudhuri (now Data Scientist at A9.com).