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 \ge 0$, under every controlled oracle $\hat{f}$ satisfying $|\hat{f}(S)-f(S)|\le \xi$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\epsilon )OPT-O(k\xi )$ and $(1-1/e-\epsilon )OPT-O(k\xi )$, respectively, where $OPT$ is the feasible optimum. The implementation uses a \emph{deterministically bounded} budget of $O(n{k}^2{\epsilon }^{-2}\log n{\log }^2(1/\epsilon ))$ 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 $\tilde{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 $\tilde{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.