# Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

arXiv: https://arxiv.org/abs/2607.00680 · HTML: https://mlsanity.com/paper/2607.00680/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 1 Jul 2026.

## Builds on (most cited first, 22 of 22)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments](https://mlsanity.com/paper/1407.1082/) (2014)
- [Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings](https://mlsanity.com/paper/1802.03825/) (2018)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Distributed Submodular Maximization with Limited Information](https://mlsanity.com/paper/1706.04082/) (2017)
- [Black Box Submodular Maximization: Discrete and Continuous Settings](https://mlsanity.com/paper/1901.09515/) (2019)
- [Optimal Algorithms for Submodular Maximization with Distributed Constraints](https://mlsanity.com/paper/1909.13676/) (2019)
- [Distributed Strategy Selection: A Submodular Set Function Maximization Approach](https://mlsanity.com/paper/2107.14371/) (2021)
- [Risk-Aware Submodular Optimization for Multi-Robot Coordination](https://mlsanity.com/paper/2003.10492/) (2020)
- [Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization](https://mlsanity.com/paper/2208.08681/) (2022)
- [Jacobi-Style Iteration for Distributed Submodular Maximization](https://mlsanity.com/paper/2010.14082/) (2020)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [A Performance Bound for the Greedy Algorithm in a Generalized Class of String Optimization Problems](https://mlsanity.com/paper/2409.05020/) (2024)
- [Approximate Supermodularity of Kalman Filter Sensor Selection](https://mlsanity.com/paper/1912.03799/) (2019)
- [Optimality Gap of Decentralized Submodular Maximization under Probabilistic Communication](https://mlsanity.com/paper/2409.09979/) (2024)

## Abstract (arXiv)

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.