We investigate the problem of unconstrained combinatorial multi-armed bandits with full-bandit feedback and stochastic rewards for submodular maximization. Previous works investigate the same problem assuming a submodular and monotone reward function. In this work, we study a more general problem, i.e., when the reward function is not necessarily monotone, and the submodularity is assumed only in expectation. We propose Randomized Greedy Learning (RGL) algorithm and theoretically prove that it achieves a $\frac{1}{2}$-regret upper bound of $\tilde{\mathcal{O}}(n T^{\frac{2}{3}})$ for horizon $T$ and number of arms $n$. We also show in experiments that RGL empirically outperforms other full-bandit variants in submodular and non-submodular settings.

我们研究了无约束组合多臂强盗问题 具有全强盗反馈和子模最大化的随机奖励。 以前的工作在假设子模和单调的情况下研究了相同的问题 奖励功能。在这项工作中，我们研究了一个更一般的问题，即当 奖励函数不一定是单调的，并且假定为子模 只是在期待中。提出了随机贪婪学习(RGL)算法，并对RGL算法进行了改进 从理论上证明了它达到了$\FRAC{1}{2}$-遗憾上界 $\tilde{\mathcal{O}}(n T^{\frac{2}{3}})$表示地平线$T$和臂数 $n$。我们还在实验中表明，RGL在经验上优于其他 子模块和非子模块设置中的全盗版变体。