Adaptive Submodular Maximization in Bandit Setting
Maximization of submodular functions has wide applications in machine learning and artificial intelligence. Adaptive submodular maximization has been traditionally studied under the assumption that the model of the world, the expected gain of choosing an item given previously selected items and their states, is known. In this paper, we study the setting where the expected gain is initially unknown, and it is learned by interacting repeatedly with the optimized function. We propose an efficient algorithm for solving our problem and prove that its expected cumulative regret increases logarithmically with time. Our regret bound captures the inherent property of submodular maximization, earlier mistakes are more costly than later ones. We refer to our approach as Optimistic Adaptive Submodular Maximization (OASM) because it trades off exploration and exploitation based on the optimism in the face of uncertainty principle. We evaluate our method on a preference elicitation problem and show that non-trivial K-step policies can be learned from just a few hundred interactions with the problem.
This paper extends the concept of adaptive 
      submodularity (Golovin & Krause, JAIR 2011) to the setting where 
      one wants to maximize an adaptive submodular function whose form is not 
      known, but where the necessary training episodes are provided. 
      What differentiates adaptive submodularity for submodularity is 
      that the set-valued function being optimized is stochastic: the reward 
      for selecting set A \subset L can vary with the state/context \phi \in 
      {0,1}^L. We assume that \phi is drawn from a distribution P(\Phi). Call 
      the reward f(A,\phi). A training episode is a sequence of steps, where the 
      forecaster selects a set of items according to a policy. The policy 
      accounts for the uncertainty in \phi. The key ideas in this paper, 
      which connect adaptive submodularity to multi-armed bandits are, in my 
      opinion K1. Learn the incremental gains, not the submodular 
      function The critical assumption made is that the reward of adding 
      an element to a set does not depend on the unknown state \phi, so one 
      can generalize the reward gained from adding an element to a set across 
      states \phi. K2. Optimism in the face of uncertainty Once 
      you assume the incremental gains do not depend on the context, learning 
      can be framed as a bandit problem where each element in the ground set 
      corresponds to an arm. Under K1, the authors can frame learning in terms 
      of the UCB1 algorithm on Bernoulli bandits, drawing heavily on the 
      original UCB1 paper. It is worth mentioning to the reader that the 
      no-regret result in this paper depends heavily on K1 and K2.If one looks 
      at the literature on learning monotone submodular functions in a more 
      general setting (Balcan & Harvey, STOC 2011), the picture is much more 
      dismal. The proof of Theorem 1 is quite elegant, but the paper is 
      definitely hampered by the tight page limitations of a NIPS submission. A 
      reader who has not read Golovin & Krause will have only the foggiest 
      idea of why this problem is interesting. One way of improving the clarity 
      of this submission, in its own right, is to strip the redundant first 
      paragraph in the conclusions, and use the space for exposition on how 
      submodularity fits into this problem from a MAB perspective. The 
      paper clearly builds on two established ideas: adaptive submodularity and 
      the UCB1 algorithm for multi-armed bandits. The clever bit is K1, which 
      connects the two ideas. The experiments (Section 4) are 
      perfunctory, and seem pretty contrived. The ground set is the 19 genres. 
      It's not at all clear what the training episodes are. It does seem though 
      that the independence of gains and contexts is the same as assuming that a 
      genres of a movie don't depend on the preferred genres of the users. But, 
      I'd expect that there are more movies in more popular genres. Is there 
      something that I am missing?