Sum-max Submodular Bandits
Stephen Pasteris Alberto Rumi Fabio Vitale Nicolò Cesa-Bianchi
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 facility location, $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 $\big(1 - \frac{1}{e}\big)$-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
$\widetilde{O}\big(T^{2/3}\big)$ regret bound for online monotone submodular
maximization with bandit feedback.