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

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≥0, under every controlled oracle widehat f satisfying |widehat f(S)-f(S)|≤ xi for every set S, our implementation returns a feasible set with expected value at least (1/e-varepsilon)OPT-O(kxi) and (1-1/e-varepsilon)OPT-O(kxi), respectively, where OPT is the feasible optimum. The implementation uses a deterministically bounded budget of O(nk2varepsilon-2log nlog2(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(n1/5k4/5T4/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(n1/5k3/5T4/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.