Combinatorial Stochastic-Greedy Bandit
This work addresses efficient exploration in combinatorial bandits for applications like social influence maximization, representing an incremental improvement over existing methods.
The paper tackles combinatorial multi-armed bandit problems with large sets of base arms by proposing a stochastic-greedy bandit algorithm that samples only a subset of arms, achieving a (1-1/e)-regret bound of O(n^{1/3} k^{2/3} T^{2/3} log(T)^{2/3}) for monotone stochastic submodular rewards, which outperforms state-of-the-art methods in terms of the cardinality constraint k.
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.