Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits
This work addresses optimization problems in adversarial online settings, such as ad placement or resource allocation, with incremental improvements in regret bounds for specific constraints.
The paper tackles online bandit learning for monotone multi-linear DR-submodular functions, achieving an O(T^{2/3} log T) (1-1/e)-regret algorithm, and applies it to improve existing results in submodular bandit with partition matroid constraint and bandit sequential monotone maximization.
We investigate the online bandit learning of the monotone multi-linear DR-submodular functions, designing the algorithm $\mathtt{BanditMLSM}$ that attains $O(T^{2/3}\log T)$ of $(1-1/e)$-regret. Then we reduce submodular bandit with partition matroid constraint and bandit sequential monotone maximization to the online bandit learning of the monotone multi-linear DR-submodular functions, attaining $O(T^{2/3}\log T)$ of $(1-1/e)$-regret in both problems, which improve the existing results. To the best of our knowledge, we are the first to give a sublinear regret algorithm for the submodular bandit with partition matroid constraint. A special case of this problem is studied by Streeter et al.(2009). They prove a $O(T^{4/5})$ $(1-1/e)$-regret upper bound. For the bandit sequential submodular maximization, the existing work proves an $O(T^{2/3})$ regret with a suboptimal $1/2$ approximation ratio (Niazadeh et al. 2021).