Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
It provides a unified algorithmic framework for distributed online submodular maximization, addressing the practical issue of sampling violations, which is relevant for multi-agent systems with limited feedback.
The paper tackles distributed online submodular maximization under partition matroid constraints, achieving sublinear (1-1/e)-regret guarantees for both full-information and bandit feedback models, with cumulative sampling violation sublinear in T.
We study distributed online submodular maximization under partition matroid constraints, in which multiple agents select a limited number of actions from their own subsets sequentially to maximize the cumulative value of a sequence of objective functions. We develop a unified algorithmic framework that accommodates full-information and bandit feedback models. For both feedback models, we prove that the proposed algorithms achieve sublinear $(1-1/e)$-regret guarantees, which are comparable to those achieved by existing centralized counterparts. Furthermore, to tackle the sampling violation issue caused by continuous relaxation and rounding, we develop a bounded stochastic pipage rounding scheme and show that the probability of sampling violation vanishes asymptotically. As a result, the cumulative sampling violation remains sublinear in $T$, which is further shown to be not improvable under certain conditions. Numerical results validate the theoretical findings in this paper.