Search papers, labs, and topics across Lattice.
This paper investigates distributed online submodular maximization with partition matroid constraints, where multiple agents sequentially select actions to optimize cumulative objectives. The authors introduce a unified algorithmic framework that effectively handles both full-information and bandit feedback models, achieving sublinear $(1-1/e)$-regret guarantees that match centralized methods. Additionally, they address sampling violations through a bounded stochastic pipage rounding scheme, ensuring the cumulative sampling violation remains sublinear over time, with empirical results supporting their theoretical claims.
Achieving sublinear regret in distributed online submodular maximization while effectively managing sampling violations could redefine multi-agent decision-making strategies.
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.
