Greedy algorithms for stochastic monotone k-submodular maximization under full-bandit feedback

In this paper, we theoretically study the Combinatorial Multi-Armed Bandit problem with stochastic monotone k-submodular reward function under full-bandit feedback. In this setting, the decision-maker is allowed to select a super arm composed of multiple base arms in each round and then receives its k-submodular reward. The k-submodularity enriches the application scenarios of the problem we consider in contexts characterized by diverse options. We present two simple greedy algorithms for two budget constraints (total size and individual size) and provide the theoretical analysis for upper bound of the regret value. For the total size budget, the proposed algorithm achieves a $$\frac{1}{2}$$ 1 2 -regret upper bound by $$\tilde{\mathcal {O}}\left( T^\frac{2}{3}(kn)^{\frac{1}{3}}B\right) $$ O ~ T 2 3 ( k n ) 1 3 B where T is the time horizon, n is the number of base arms and B denotes the budget. For the individual size budget, the proposed algorithm achieves a $$\frac{1}{3}$$ 1 3 -regret with the same upper bound. Moreover, we conduct numerical experiments on these two algorithms to empirically demonstrate the effectiveness.