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

This paper investigates whether the Spiteful Greedy Swap (SGS-Poisson) algorithm—a discrete stochastic process for submodular maximization under matroid constraints—can maintain its theoretical approximation guarantees when the value oracle is subject to persistent, adversarial errors. This is a critical question for the 'offline-to-online' reduction framework, where offline optimization algorithms are used as black boxes to solve full-bandit combinatorial multi-armed bandit (CMAB) problems.

The author proves an adversarial resilience theorem for the SGS-Poisson process. Rather than modifying the algorithm's core components—such as its Poisson intensity, single-element exchange rules, or spiteful drop steps—the paper demonstrates that the existing process is robust to controlled oracle perturbations. The technical core of the proof involves an adaptive potential-preservation result, showing that even when the trajectory of the algorithm changes due to noisy oracle feedback, the 'exchange potential' satisfies a robust drift inequality. The author also incorporates a robust version of Residual Random Greedy (RRG) to provide a constant-factor estimate of the optimum, which is necessary for the algorithm's preprocessing phase.

The study establishes that for any target approximation loss, the SGS-Poisson algorithm returns a feasible set with an expected value within an additive $O(k\xi)$ term of the classical $1/e$ (non-monotone) and $1-1/e$ (monotone) approximation factors, where $\xi$ is the oracle error bound. By plugging this resilient offline algorithm into the offline-to-online reduction framework, the author derives new full-bandit CMAB algorithms for general matroids that achieve the optimal approximation factors with $\widetilde{O}(n^{1/5}k^{4/5}T^{4/5})$ regret. This improves upon previous general-matroid bandit results that were limited to lower approximation factors.