拟阵上泊松过程次模最大化的对抗鲁棒性：从鲁棒离线优化到全强盗学习
文章背景与核心概要
本文研究了在一般拟阵约束下的非负次模最大化问题，特别关注离线算法配备任意受控值谕言机（controlled value oracle）时的表现。作者针对“恶意贪婪交换泊松过程（SGS-Poisson）”算法建立了一个对抗鲁棒性定理，证明了该算法在无需修改核心参数（如泊松强度、单元素交换规则或恶意丢弃步骤）的情况下，仍能为单调和非单调目标函数保持强大的极限近似保证。
此外，通过离线到在线归约，本文成功推导出了适用于拟阵约束次模奖励的全强盗组合多臂强盗（CMAB）算法，实现了精确的极限近似-遗憾因子以及次线性的遗憾界。这一研究沟通了鲁棒离线优化与复杂在线强盗学习之间的理论桥梁。
摘要 (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.
我们研究了一般拟阵约束下的非负次模最大化问题，此时离线算法被赋予了一个任意的受控值谕言机。我们的主要结果是针对恶意贪婪交换泊松过程（Spiteful Greedy Swap Poisson Process, SGS-Poisson）的对抗鲁棒性定理：在不修改其泊松强度、单元素交换规则或恶意丢弃步骤的前提下，该算法对于非单调目标函数仍能保持 \(1/e\) 的极限近似因子，对于单调目标函数则保持 \(1-1/e\) 的近似因子。
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-\varepsilon)\text{OPT}-O(k\xi)\) for non-monotone objectives, and * \((1-1/e-\varepsilon)\text{OPT}-O(k\xi)\) for monotone objectives, 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.
更准确地说，对于满足任意集合 \(S\) 都有 \(|\widehat f(S)-f(S)|\le \xi\) 的每一个受控谕言机 \(\widehat f\)，我们的实现返回的可行集其期望值至少为： * 对于非单调目标函数，为 \((1/e-\varepsilon)\text{OPT}-O(k\xi)\)； * 对于单调目标函数，为 \((1-1/e-\varepsilon)\text{OPT}-O(k\xi)\)，
算法所需的谕言机调用次数为 \(\widetilde O(nk^2\varepsilon^{-2})\)。因此，离线到在线的归约成功为一般拟阵约束的次模奖励生成了全强盗 CMAB 算法，实现了精确的极限近似-遗憾因子（\(1/e\) 和 \(1-1/e\)）以及 \(\widetilde O(n^{1/5}k^{4/5}T^{4/5})\) 的遗憾界。