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

arXiv: https://arxiv.org/abs/2608.12134 · HTML: https://mlsanity.com/paper/2608.12134/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 12 Aug 2026.

## Builds on (most cited first, 12 of 12)

- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint](https://mlsanity.com/paper/2408.03583/) (2024)
- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [A Poisson Process for Submodular Maximization](https://mlsanity.com/paper/2605.03071/) (2026)
- [A Unified Approach to Submodular Maximization Under Noise](https://mlsanity.com/paper/2510.21128/) (2025)
- [If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization](https://mlsanity.com/paper/2608.05062/) (2026)

## Abstract (arXiv)

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.