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 ξ≥0, under every controlled oracle f̂ satisfying |f̂(S)−f(S)|≤ ξ for every set S, our implementation returns a feasible set with expected value at least (1/e−ε)OPT−O(kξ) and (1−1/e−ε)OPT−O(kξ), respectively, where OPT is the feasible optimum. The implementation uses a \emph{deterministically bounded} budget of O(nk2ε−2log nlog2(1/ε)) 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 Õ(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 Õ(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.
Related
- An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
- A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
- Online Submodular Welfare Maximization: Computation is not the Bottleneck
BibTeX
@misc{aggarwal2026adversarial,
title = {{Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning}},
author = {Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.12134},
eprint = {2608.12134},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.12134},
}
RIS
TY - UNPB
TI - Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2608.12134
UR - https://arxiv.org/abs/2608.12134
AB - 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 ξ≥0, under every controlled oracle f̂ satisfying |f̂(S)−f(S)|≤ ξ for every set S, our implementation returns a feasible set with expected value at least (1/e−ε)OPT−O(kξ) and (1−1/e−ε)OPT−O(kξ), respectively, where OPT is the feasible optimum. The implementation uses a \emph{deterministically bounded} budget of O(nk^2ε^−2log nlog^2(1/ε)) 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 Õ(n^1/5k^4/5T^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 Õ(n^1/5k^3/5T^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.
ER -