Minimax Optimal Submodular Optimization with Bandit Feedback
Artin Tajdini Lalit Jain Kevin Jamieson
We consider maximizing a monotonic, submodular set function $f: 2^{[n]}
\rightarrow [0,1]$ under stochastic bandit feedback. Specifically, $f$ is
unknown to the learner but at each time $t=1,\dots,T$ the learner chooses a set
$S_t \subset [n]$ with $|S_t| \leq k$ and receives reward $f(S_t) + \eta_t$
where $\eta_t$ is mean-zero sub-Gaussian noise. The objective is to minimize
the learner's regret over $T$ times with respect to ($1-e^{-1}$)-approximation
of maximum $f(S_*)$ with $|S_*| = k$, obtained through greedy maximization of
$f$. To date, the best regret bound in the literature scales as $k n^{1/3}
T^{2/3}$. And by trivially treating every set as a unique arm one deduces that
$\sqrt{ {n \choose k} T }$ is also achievable. In this work, we establish the
first minimax lower bound for this setting that scales like
$\mathcal{O}(\min_{i \le k}(in^{1/3}T^{2/3} + \sqrt{n^{k-i}T}))$. Moreover, we
propose an algorithm that is capable of matching the lower bound regret.