Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning

arXiv:2608.12134v1 Announce Type: cross Abstract: We study nonnegative submodular maximization subject to a general matroid 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, 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-arepsilon)OPT-O(kxi) and (1-1/e-arepsilon)OPT-O(kxi), respectively, using widetilde O(nk^2arepsilon^{-2}) oracle calls. As a consequence, the offline-to-online reduction yields full-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.

Source: arXiv cs.AI | 2026-08-13