Sum-max Submodular Bandits

2023/11/10 by Pasteris, Stephen, Rumi, Alberto, Vitale, Fabio +1
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2311.05975

Abstract

Many online decision-making problems correspond to maximizing a sequence of submodular functions. In this work, we introduce sum-max functions, a subclass of monotone submodular functions capturing several interesting problems, including best-of-K-bandits, combinatorial bandits, and the bandit versions on facility location, M-medians, and hitting sets. We show that all functions in this class satisfy a key property that we call pseudo-concavity. This allows us to prove (1 - (1)/(e))-regret bounds for bandit feedback in the nonstochastic setting of the order of √(MKT) (ignoring log factors), where T is the time horizon and M is a cardinality constraint. This bound, attained by a simple and efficient algorithm, significantly improves on the \widetildeO(T^2/3) regret bound for online monotone submodular maximization with bandit feedback.

Related

• Stochastic k-Submodular Bandits with Full Bandit Feedback
• Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
• Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits
• Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedback
• Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit