Nearly Minimax Optimal Submodular Maximization with Bandit Feedback

We consider maximizing an unknown monotonic, submodular set function f: 2[n] rightarrow [0,1] with cardinality constraint under stochastic bandit feedback. At each time t=1,dots,T the learner chooses a set St subset [n] with |St| ≤ k and receives reward f(St) + ηt where ηt is mean-zero sub-Gaussian noise. The objective is to minimize the learner's regret with respect to an approximation of the maximum f(S_*) with |S_*| = k, obtained through robust greedy maximization of f. To date, the best regret bound in the literature scales as k n1/3 T2/3. And by trivially treating every set as a unique arm one deduces that √ n choose k T is also achievable using standard multi-armed bandit algorithms. In this work, we establish the first minimax lower bound for this setting that scales like tildeOmega(minL ≤ k(L1/3n1/3T2/3 + √n choose k - LT)). For a slightly restricted algorithm class, we prove a stronger regret lower bound of tildeOmega(minL ≤ k(Ln1/3T2/3 + √n choose k - LT)). Moreover, we propose an algorithm Sub-UCB that achieves regret tildeO(minL ≤ k(Ln1/3T2/3 + √n choose k - LT)) capable of matching the lower bound on regret for the restricted class up to logarithmic factors.