Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning

Abstract:We study nonnegative submodular maximization on $n$ elements subject to a general matroid of rank $k$, when the offline algorithm is given an arbitrary controlled value oracle. Our main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors $1/e$ for non-monotone objectives and $1-1/e$ for monotone objectives. More precisely, given an error bound $\xi\ge0$, under every controlled oracle $\widehat f$ satisfying $|\widehat f(S)-f(S)|\le \xi$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)OPT-O(k\xi)$ and $(1-1/e-\varepsilon)OPT-O(k\xi)$, respectively, where $OPT$ is the feasible optimum. The implementation uses a \emph{deterministically bounded} budget of $O(nk^{2}\varepsilon^{-2}\log n\log^{2}(1/\varepsilon))$ oracle calls. As a consequence, an offline-to-online reduction yields full-bandit combinatorial multi-armed bandit (CMAB) algorithms for general matroid-constrained submodular rewards with exact limiting approximation-regret factors $1/e$ and $1-1/e$ and $\widetilde O(n^{1/5}k^{4/5}T^{4/5})$ regret over $T$ rounds. These online guarantees allow exploration to play sets that become independent after deleting at most one element; exploitation and the benchmark remain matroid-feasible. For unit-capacity partition matroids we obtain $\widetilde O(n^{1/5}k^{3/5}T^{4/5})$ under the same exploration relaxation. We establish a deterministic query budget by truncating the Poisson process and identify the enlarged action set needed to answer its offline queries.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Optimization and Control (math.OC)

arXiv:2608.12134 [cs.LG]

(or arXiv:2608.12134v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2608.12134 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.