Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

This paper addresses the challenge of maximizing a sequence of submodular objective functions in a distributed online setting. Specifically, it focuses on scenarios where multiple agents must make sequential decisions under partition matroid constraints without prior knowledge of future functions. The primary goal is to achieve near-optimal (1-1/e) regret while managing the computational complexity of gradient evaluation and the feasibility issues inherent in continuous relaxation and rounding.

The authors develop a unified algorithmic framework that integrates the Meta-Frank-Wolfe algorithm with a consensus-based coordination scheme. To handle the bandit feedback model, they utilize a one-point gradient estimator. A key innovation is the introduction of Bounded Stochastic Pipage Rounding (B-SPR), which generalizes standard pipage rounding to handle arbitrary fractional bounds. By embedding this into a Progressively Bounded Stochastic Pipage Rounding (PB-SPR) scheme, the algorithm forces iterates toward matroid vertices, effectively reducing the probability of generating infeasible (violating) samples over time.

The proposed algorithms achieve sublinear (1-1/e)-regret bounds of O(T^4/5) for full-information feedback and O(T^8/9) for bandit feedback, matching the performance of centralized counterparts. Crucially, the authors prove that the probability of sampling violation vanishes at a rate of O(T^-1/9), leading to a cumulative sampling violation of O(T^7/9). They further establish that this O(T^7/9) rate is not improvable under certain conditions, confirming the optimality of their approach in managing feasibility.

This work bridges the gap between distributed online optimization and combinatorial constraints. By resolving the conflict between unbiased gradient estimation and set-constraint feasibility, the framework provides a robust solution for large-scale, multi-agent decision-making systems—such as sensor selection or resource allocation—where agents must operate under strict local constraints while maximizing a global objective.