Online Submodular Set Cover, Ranking, and Repeated Active Learning

Online Ranking: At each round, the learner produces an ordered list of items, then suffers loss or receives reward. In this paper, loss is: the number of items needed to achieve some coverage objective Example: The cost at each round is the number of pages the user needs to view to deduce the complete information they desire. Repeated Active Learning is an interesting special case where the list consists of questions to ask or tests to perform. Here a reasonable loss is the number of the tests we need to perform before we can make a accurate diagnosis. For these applications we propose a new online learning problem we call online submodular set cover.