SGS-Poisson在带误差的预言机下仍保1/e和1-1/e近似比，还直接给出全臂老虎机遗憾界，做组合优化和在线学习值得看。
论文给出SGS-Poisson算法的对抗鲁棒性定理：在不修改泊松强度、单元素交换规则和spiteful drop步骤的情况下，该算法对非单调目标保持极限近似比1/e，对单调目标保持1-1/e。对于任意满足|f̂(S)-f(S)|≤ξ的受控预言机，算法返回集合期望值至少为(1/e-ε)OPT-O(kξ)或(1-1/e-ε)OPT-O(kξ)，调用次数为O~(n k² ε⁻²)。离线到在线转化得到一般拟阵约束子模奖励的全臂老虎机CMAB算法，极限近似-遗憾因子为1/e和1-1/e，遗憾为O~(n^{1/5}k^{4/5}T^{4/5})。
Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning
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 ξ$ for every set $S$, our implementation returns a feasible set with expected value at least $(1/e-\varepsilon)\OPT-O(kξ)$ and $(1-1/e-\varepsilon)\OPT-O(kξ)$, respectively, using $\widetilde O(nk^2\varepsilon^{-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.