Improved Algorithms for Online Submodular Maximization via First-order Regret Bounds

We consider the problem of nonnegative submodular maximization in the online setting. At time step t, an algorithm selects a set S t. The goal is to design an efficient algorithm for minimizing the expected approximate regret. In this work, we give a general approach for improving regret bounds in online submodular maximization by exploiting "first-order" regret bounds for online linear optimization.