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 St C 2 V where C is a feasible family of sets. An adversary then reveals a submodular function ft. 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.