Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits - Wan, Zongqi; Zhang, Jialin; Chen, Wei; Sun, Xiaoming; Zhang, Zhijie (Proceedings of the 40th International Conference on Machine Learning (ICML), 2023)
We investigate the online bandit learning of the monotone multi-linear DR-submodular functions, designing the algorithm that attains of -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 of -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 -regret upper bound. For the bandit sequential submodular maximization, the existing work proves an regret with a suboptimal approximation ratio (Niazadeh et al. 2021).