Combinatorial Stochastic-Greedy Bandit
Fares Fourati Christopher John Quinn Mohamed-Slim Alouini Vaneet Aggarwal
We propose a novel combinatorial stochastic-greedy bandit (SGB) algorithm for
combinatorial multi-armed bandit problems when no extra information other than
the joint reward of the selected set of $n$ arms at each time step $t\in [T]$
is observed. SGB adopts an optimized stochastic-explore-then-commit approach
and is specifically designed for scenarios with a large set of base arms.
Unlike existing methods that explore the entire set of unselected base arms
during each selection step, our SGB algorithm samples only an optimized
proportion of unselected arms and selects actions from this subset. We prove
that our algorithm achieves a $(1-1/e)$-regret bound of
$\mathcal{O}(n^{\frac{1}{3}} k^{\frac{2}{3}} T^{\frac{2}{3}}
\log(T)^{\frac{2}{3}})$ for monotone stochastic submodular rewards, which
outperforms the state-of-the-art in terms of the cardinality constraint $k$.
Furthermore, we empirically evaluate the performance of our algorithm in the
context of online constrained social influence maximization. Our results
demonstrate that our proposed approach consistently outperforms the other
algorithms, increasing the performance gap as $k$ grows.