Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
2026-07-01 • Machine Learning
Machine Learning
AI summaryⓘ
The authors look at a problem where multiple agents pick actions one after another to maximize some value while following certain rules. They create a general method that works whether agents get full feedback or limited feedback about their choices. Their method performs nearly as well as existing centralized methods and keeps errors from rounding decisions small over time. They also support their findings with experiments.
distributed optimizationonline learningsubmodular maximizationpartition matroidbandit feedbackregret analysispipage roundingstochastic algorithms
Authors
Bin Du, Chang Liu, Dingqi Zhu, Lintao Ye, Dengfeng Sun
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.