Sum-max submodular bandits

Many online decision-making problems correspond to maximizing a sequence of submodular functions. In this work, we introduce sum-max functions, a subclass of monotone submodular functions capturing several interesting problems, including best-of-K-bandits, combinatorial bandits, and the bandit versions on M-medians and hitting sets. We show that all functions in this class satisfy a key property that we call pseudo-concavity. This allows us to prove (1-1/e)-regret bounds for bandit feedback in the nonstochastic setting of the order of sqrt(MKT) (ignoring log factors), where T is the time horizon and M is a cardinality constraint. This bound, attained by a simple and efficient algorithm, significantly improves on the O(T^2/3) regret bound for online monotone submodular maximization with bandit feedback. We also extend our results to a bandit version of the facility location problem.