{"ID":5551787,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T09:21:41.829188432Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00680","arxiv_id":"2607.00680","title":"Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations","abstract":"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.","short_abstract":"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 ful...","url_abs":"https://arxiv.org/abs/2607.00680","url_pdf":"https://arxiv.org/pdf/2607.00680v1","authors":"[\"Bin Du\",\"Chang Liu\",\"Dingqi Zhu\",\"Lintao Ye\",\"Dengfeng Sun\"]","published":"2026-07-01T09:22:18Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}