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

Summary

This paper studies the problem of nonnegative submodular maximization subject to a general matroid constraint when the offline algorithm is given an arbitrary controlled value oracle. The 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 fb satisfying fb(S) − f (S) ≤ ξ for every set S, the implementation returns a feasible set with expected value at least (1/e − ε)OPT − O(kξ) and (1 − 1/e − ε)OPT − O(kξ), respectively, using O(nk2ε−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 O(n 1/5 k 4/5 T 4/5) regret.

The paper addresses the canonical problem of submodular maximization under matroid constraints, with applications including influence maximization, sensor placement, experimental design, and data summarization. The ground set has n items, the matroid has rank k, and the objective f is nonnegative and submodular. For monotone objectives, continuous greedy gives the classical 1 − 1/e approximation, and for non-monotone objectives, measured continuous greedy gives the classical 1/e factor. A recent line of work introduced a Poisson-process approach, with the SGS-Poisson process maintaining feasibility and evolving through single-element exchanges.

The paper asks whether the same SGS-Poisson process is resilient to controlled oracle error. This question is important for full-bandit combinatorial multi-armed bandits (CMAB), where empirical estimates of super-arm rewards naturally enter an offline optimization routine. Existing full-bandit results cover general matroid constraints but obtain only 1/2 for monotone and 1/3 for non-monotone objectives. The goal is to establish the controlled-oracle resilience required to place SGS-Poisson inside the offline-to-online framework and thereby recover the classical 1 − 1/e and 1/e approximation factors for general matroids.

The main technical novelty is an adaptive potential-preservation result: Controlled-oracle adaptive preprocessing preserves the exact structural certificate needed by SGS-Poisson. The preprocessing process is driven by a controlled-oracle estimate of the maximum sum of residual marginals and stops at a controlled-oracle threshold. The paper first robustifies Residual Random Greedy (RRG) to obtain a realized constant-factor estimate Vb of OPT. Then it runs the exact preprocessing process with fb. Although the chosen bases and stopping time can be completely different from their exact-oracle counterparts, the exchange potential Mt = f(Qt ∪ Ot) + (1/2)f(Qt) satisfies the robust drift inequality E[Mt+1 − Mt Ft] ≥ (8OPT − kξ)/(k − t). This is the key lemma of the paper, simultaneously handling noisy maximum-base selection, a noisy adaptive stopping rule, and the evolving matroid exchange set.

A second technical ingredient is a robust almost-above-average swap lemma. The exact SGS-Poisson implementation estimates, for every candidate element, a multilinear marginal using random sets. Under controlled oracle error, the base-sum concentration argument remains valid and incurs only an additional O(kξ) term. Thus a swap at every Poisson event is η-almost-above-average with η ≤ C1εOPT + C2kξ. The original SGS-Poisson process and its drop rule are unchanged.

The paper uses the offline-to-online reduction proposed in prior work as a black box, converting the resilience parameters into exact limiting approximation-regret factors 1/e and 1 − 1/e with O(n 1/5 k 4/5 T 4/5) regret for general matroids. The paper emphasizes this is not claimed to dominate specialized cardinality-bandit rates; the point is that the general-matroid resilient offline guarantee survives the full-bandit reduction.

The problem setup defines a matroid M = (U, I) of rank k and n = U. A set function f: 2 U → [0, 1] is submodular if f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B) for all A, B ⊆ U. For the online full-bandit application, at round t the learner chooses a feasible super-arm At ∈ I and observes only an aggregate reward Yt ∈ [0, 1] with E[Yt At = S] = f(S). For α ∈ (0, 1], the cumulative α-regret is defined by Rα(T):= αT OPT − E[Σ t=1 T Yt]. Only the aggregate reward is observed; no component-wise or semi-bandit feedback is assumed.

A ξ-controlled oracle is a function fb: 2 U → R satisfying fb(S) − f(S) ≤ ξ for all S ⊆ U. The perturbation is deterministic and may be adversarial; no stochastic or independence assumption is imposed. Because fb is a fixed function, the same set always receives the same oracle value, so the adversarial perturbation is persistent throughout the execution. The paper projects fb onto [0, 1] without increasing its error, so 0 ≤ fb(S) ≤ 1, and then fb(i S) − f(i S) ≤ 2ξ.

The paper uses the (α, β, γ, ψ, δ) resilience parameterization, which extends the robust-approximation notion by recording the accuracy-dependent oracle complexity. An offline algorithm A(ε) is (α, β, γ, ψ, δ)-resilient if, for every ξ ≥ 0, under a ξ-controlled oracle it outputs a feasible Θ satisfying E[f(Θ)] ≥ (α − ε)OPT − δξ, and has expected oracle complexity at most ψ ε-β log γ(1/ε) for ε > 0.

The exact algorithmic object is the SGS-Poisson algorithm used as a black-box base process. Its Poisson rate, valid-swap conditions, and spiteful drop step are unchanged. The algorithm starts at time ε0 > 0 with A = ∅, and while t < 1, samples the next event time τ(t) of a Poisson process with rate k/t, then performs a swap (I, J) ← Swap(t, A), updates A ← A − I + J, and if I = J, with probability t sets A ← A − I. The expected number of swap calls is k log(1/ε0).

The paper uses the Poisson-process guarantee from prior work: if Algorithm 1 uses a right-continuous η-almost-above-average valid swap, then E[f(A)] ≥ (1 − ε0)e-1OPT + e-1f(∅) − η for non-monotone f, and E[f(A)] ≥ (1 − ε0)(1 − e-1)OPT + e-1f(∅) − η for monotone f.

The paper adds a set D of k dummy elements and forms the rank-k augmentation U+:= U ∪ D, I+:= S ⊆ U+: S ∩ U ∈ I, S ≤ k. Equivalently, M+ is the rank-k truncation of the direct sum of M and the free matroid on D. Every independent set of M can be completed to a base of M+ by adding dummy elements. The objective and controlled oracle are extended by f+(S):= f(S D), fb+(S):= fb(S D). Hence every dummy element has identically zero true and estimated marginal, and an optimal solution of the original instance can be extended to an optimal base of M+ without changing its value.

Residual Random Greedy (RRG) is run for r = ⌈k/2⌉ iterations. At iteration i, let Si−1 be the current set and ri = k − i + 1 the residual rank. In the contraction M/Si−1, compute a maximum-weight base Mi with weights wbi(u) = fb(u Si−1), and choose ui uniformly from Mi. The paper proves a robust maximum-base comparison lemma: at iteration i, for every base B of the residual matroid, Σ u∈Mi f(u Si−1) ≥ Σ u∈B f(u Si−1) − 4riξ. This follows from optimality under fb and the error bound of 2riξ on either side.

The RRG exchange coupling lemma shows that for the augmented matroid M+ and an optimal base O+ containing an optimal solution, the coupling can be chosen so that for 0 ≤ i ≤ k − 1, E[f+(Si ∪ Oi)] ≥ ((k − i)(k − i − 1))/(k(k − 1)) OPT. The proof uses the strong basis-exchange property to construct a bijection hi: Mi → Oi−1 such that Si−1 ∪ Oi−1 − hi(u) + u ∈ I(M+) for all u ∈ Mi, with hi(u) = u whenever u ∈ Mi ∩ Oi−1. After drawing ui uniformly from Mi, set Oi:= Oi−1 hi(ui).

The paper proves a robust RRG lemma: for 1 ≤ i ≤ ⌈k/2⌉, E[f+(Si)] ≥ (i(k − i))/(k(k − 1)) OPT − 4iξ. In particular, for r = ⌈k/2⌉, E[f(Sr)] ≥ (1/4)OPT − 4kξ. The proof uses the exchange coupling and the robust maximum-base comparison, with an induction on i starting from S0 = ∅.

For the high-probability optimum certificate, the paper runs Algorithm 2 independently R = 15 log(1/ρ) times and lets G⋆ be the set with largest fb value. If OPT ≥ 32kξ, then E[f(Sr)] ≥ (1/8)OPT, and since 0 ≤ f(Sr) ≤ OPT, P(f(Sr) ≥ OPT/16) ≥ 1/15. Thus, with probability at least 1 − ρ, one run has value at least OPT/16. Define Vb:= max 32kξ, 16fb(G⋆) + 64ξ. On the good event, OPT ≤ Vb. Moreover, because G⋆ is feasible, fb(G⋆) ≤ OPT + ξ, and hence OPT ≤ Vb ≤ 16OPT + 96kξ with probability at least 1 − ρ. If OPT < 32kξ, the first term in Vb already gives Vb ≥ OPT.

For the robust adaptive preprocessing, the paper proves a marginal-mass perturbation lemma: for every Q ∈ I, Marfb(Q) − Marf(Q) ≤ 2kξ. This follows because every feasible T contains at most k elements, and the difference between its estimated and true marginal sum is at most 2kξ. Starting from Q0 = ∅, define the stopping time τ:= inf t: Marfb(Qt) ≤ 20Vb. For t < τ, choose a maximum-weight residual base Zt under the estimated marginals and draw jt uniformly from Zt. Set Qt+1 = Qt + jt. Because of the dummy elements, every residual independent set can be extended to a base, so this process has at most k iterations.

The residual marginal bound lemma shows that on the event in (26), Marf(S̄) ≤ 320OPT + 1922kξ, where S̄ = Qτ. At stopping, Marfb(S̄) ≤ 20Vb, and by the marginal-mass perturbation lemma and the bound on Vb, Marf(S̄) ≤ 20(16OPT + 96kξ) + 2kξ.

The crucial resilient adaptive-preprocessing drift lemma is proved as follows. Let O0 = O be an optimal base, construct Ot ⊆ O so that Qt ∪ Ot is a base at every time, and define Mt = f(Qt ∪ Ot) + (1/2)f(Qt). On the event Vb ≥ OPT, for every t < τ, E[Mt+1 − Mt Ft] ≥ (8OPT − kξ)/(k − t). The proof fixes t < τ and writes rt = k − t. Because the stopping condition has not fired, Σ j∈Zt fb(j Qt) > 20Vb ≥ 20OPT. The base Zt has rt elements, so by the error bound, Σ j∈Zt f(j Qt) ≥ 20OPT − 2rtξ. Since jt is uniform in Zt, E[f(Qt+1) − f(Qt) Ft] ≥ (20OPT − 2rtξ)/rt. The exchange argument uses the strong basis-exchange property to construct a bijection ht: Zt → Ot such that Qt ∪ Ot − ht(j) + j ∈ I for all j ∈ Zt, with ht(j) = j on Zt ∩ Ot. After drawing jt uniformly from Zt, set Ot+1:= Ot ht(jt). Every element of Qt ∪ Ot is removed from the next base with probability at most 1/rt, while every element outside Qt ∪ Ot is inserted with probability at most 1/rt. Applying the submodularity inequality with p = 1 − 1/rt and q = 1/rt gives E[f(Qt+1 ∪ Ot+1) Ft] ≥ (1 − 2/rt)f(Qt ∪ Ot). Combining the two inequalities gives E[Mt+1 − Mt Ft] ≥ (10OPT − rtξ − 2f(Qt ∪ Ot))/rt. Since Qt ∪ Ot is feasible, f(Qt ∪ Ot) ≤ OPT, giving the claimed bound.

The resilient preprocessing certificate theorem states that on any event E measurable with respect to the initial RRG randomness such that E ⊆ Vb ≥ OPT, the output S̄ of Advanced Preprocessing satisfies E[max T:T∪S̄∈I f(T ∪ S̄) + (1/2)f(S̄) E] ≥ OPT − C0kξ. The proof conditions on any such event E, defines Mt∧τ as a submartingale under the conditional probability given E, and uses the bounded optional-stopping theorem since τ ≤ k and 0 ≤ Mt ≤ 3/2.

The paper emphasizes why this lemma is the technical centerpiece: "The proof does not compare the controlled-oracle trajectory to the exact trajectory. The two trajectories may diverge completely. Instead, the potential is shown to retain positive drift on the controlled-oracle trajectory itself. This is the reason the result is not a routine Lipschitz perturbation argument."

After preprocessing, the matroid is contracted at S̄: M′:= M/S̄, g(T):= f(T ∪ S̄). Then g is nonnegative and submodular. Let Og maximize g in M′. By the preprocessing certificate, on the event E, E[(1/2)g(Og) + g(∅) E] ≥ OPT − C0kξ. By the residual marginal bound, Mar(g, M′) ≤ 320OPT + 1922kξ.

For the robust almost-above-average swaps, at time t, current set A ∈ I(M′), and candidate element i, define wi = F(t1A ∨ 1i) − F(t1A). Sample R1,..., Rm ∼ t1A independently and estimate wei = (1/m)Σ l=1 m [g(Rl ∪ i) − g(Rl)]. The exact SGS-Poisson implementation chooses a maximum-weight base under wei, constructs a matroid exchange map, and samples uniformly from that base. The paper uses exactly this implementation, replacing exact function values by the controlled oracle induced on the contracted instance, gb(T):= fb(T ∪ S̄). Then gb(T) − g(T) ≤ ξ and gb(i T) − g(i T) ≤ 2ξ.

The robust swap concentration lemma fixes δs ∈ (0, 1/2) and uses the same value-oracle sampling, maximum-weight-base selection, exchange-map construction, and fixed tie-breaking convention as the exact SGS-Poisson implementation, but evaluates every set through the controlled oracle gb. If m = O((k log n + log(1/δs))/δs2), then the resulting swap is valid and right-continuous and satisfies η ≤ C1δs(Mar(g, M′) + g(Og)) + C2kξ. The proof establishes a uniform concentration event for the true marginals, showing that with high probability, sup Z∈I(M′) Wg(Z) − Wg(Z) ≤ (δs/5)L where L:= Mar(g, M′) + g(Og). The controlled oracle contributes only O(kξ) to a base comparison, while the sampling term is proportional to the residual marginal scale. This yields η ≤ C1εOPT + C2kξ.

The paper notes the important relative form of the first term: We do not replace it by O(ε): doing so would lose the desired (α − ε)OPT resilience statement when OPT is small.

The controlled-oracle complexity lemma shows that with ρ = Θ(ε), δs = Θ(ε), and ε0 = Θ(ε), the expected number of controlled-oracle evaluations used by the unchanged SGS-Poisson value-oracle implementation is N(ε) = O(nk log(1/ε) + nk + (nk2 log n log(1/ε))/ε2 + (nk log2(1/ε))/ε2) = O(nk2ε−2). Each RRG run has ⌈k/2⌉ iterations, and each iteration requires O(n) marginal-value queries. The amplified certificate uses R = O(log(1/ρ)) = O(log(1/ε)) independent runs, hence O(nk log(1/ε)) queries. Advanced Preprocessing performs at most k iterations, each requiring O(n) marginal queries, hence O(nk) additional queries. For a swap, m = O((k log n + log(1/ε))/ε2), and there are n candidate entering elements, so one Poisson event requires O(nm) controlled-oracle evaluations. The non-homogeneous Poisson process on [ε0, 1] has expected number of events k log(1/ε0).

The main resilience theorem states that there exists a universal constant C such that for every ε ∈ (0, 1/2], for k = 0 return ∅, for k = 1 query fb on every feasible singleton and on ∅ and return the best queried feasible set (giving E[f(Aout)] ≥ OPT − 2ξ), and for k ≥ 2, given any persistent ξ-controlled oracle, the SGS-Poisson value-oracle implementation outputs Aout ∈ I satisfying E[f(Aout)] ≥ (1/e − ε)OPT − Ckξ for non-monotone f and E[f(Aout)] ≥ (1 − 1/e − ε)OPT − Ckξ for monotone f. The proof chooses the RRG amplification failure probability ρ = ε/100, defines the event E:= OPT ≤ Vb ≤ 16OPT + 96kξ, and uses the preprocessing certificate and swap bounds. After conditioning on E, the paper runs SGS-Poisson on the contracted instance with starting time ε0 = ε/100, applies Proposition 4.2, and then removes the conditioning using P(E) ≥ 1 − ρ and the fact that f(Aout) ≥ 0.

The resilience parameters corollary states that in the resilience parameterization, SGS-Poisson is (1/e, 2, 2, O(nk2), O(k)) for non-monotone submodular maximization and (1 − 1/e, 2, 2, O(nk2), O(k)) for monotone submodular maximization.

For the offline-to-online CMAB application, the paper uses the offline-to-online reduction as a black box. The theorem states that if δ > 0 and an offline algorithm A(ε) is (α, β, γ, ψ, δ)-resilient with oracle complexity N(ε) = O(ψε-β log γ(1/ε)), then for stochastic single-agent CMAB with full-bandit feedback, whenever T ≥ max ψ, 2ψ/δ β+1, the reduction achieves Rα(T) = O(δ 2/(3+β) ψ 1/(3+β) T(2+β)/(3+β)). The theorem eliminates the offline ε-approximation loss and gives α-regret.

The full-bandit CMAB corollary states that for stochastic full-bandit CMAB with a general rank-k matroid and a nonnegative submodular mean reward, there exist algorithms satisfying, for all horizons T ≥ max ψ, 2ψ/δ3, R 1/e(T) = O(n 1/5 k 4/5 T 4/5) for non-monotone rewards and R 1−1/e(T) = O(n 1/5 k 4/5 T 4/5) for monotone rewards, where one may take ψ = O(nk2) and δ = O(k). The proof applies Theorem 6.1 with β = 2, γ = 2, ψ = O(nk2), δ = O(k), and α = 1/e or α = 1 − 1/e. After enlarging δ by a universal constant if necessary, δ ≥ 1, so a sufficient condition is T ≥ 2ψ = O(nk2). Applying Theorem 6.1 with β = 2 yields Rα(T) = O((k) 2/5 (nk2) 1/5 T 4/5) = O(n 1/5 k 4/5 T 4/5).

The paper separates imported ingredients from new technical statements. Imported ingredients include: (i) the exact SGS-Poisson process and its Poisson differential analysis; (ii) the standard Residual Random Greedy exchange lemma; and (iii) the single-agent offline-to-online CMAB conversion. New technical statements include: (i) robust RRG under an arbitrary adversarially controlled oracle; (ii) a realized constant-factor optimum certificate that can drive an adaptive controlled-oracle stopping rule; (iii) the resilient adaptive-preprocessing drift inequality E[Mt+1 − Mt Ft] ≥ (8OPT − kξ)/(k − t); (iv) the robust almost-above-average swap guarantee with error O(εOPT + kξ); and (v) the resulting adversarial resilience parameters.

The paper details why the adaptive-preprocessing lemma is not routine perturbation: "A pointwise perturbation argument would attempt to compare the noisy execution with the exact execution. This is impossible in general: an arbitrarily small change in marginal weights can switch the maximum-weight base, which can switch the exchange map, which can switch the stopping time and every subsequent state of the process. Moreover, fb need not be submodular. Our proof instead evaluates the true objective along the controlled-oracle trajectory and constructs the exchange potential Mt = f(Qt ∪ Ot) + (1/2)f(Qt). The key drift inequality uses the residual rank k − t: E[∆Mt Ft] ≥ (8OPT − kξ)/(k − t). Thus the proof never needs the controlled-oracle trajectory to remain close to the exact trajectory. This is the central structural reason that the oracle error is absorbed as O(kξ) rather than multiplied by the number of adaptive decisions."

The paper also details why the swap lemma is nontrivial: "The SGS-Poisson implementation does not merely need a good estimate of one marginal. It needs a base whose sum of multilinear marginals satisfies the almost-above-average condition while the resulting exchange map satisfies the validity and right-continuity conditions. We therefore concentrate the base-sum random variable directly. The controlled oracle contributes only O(kξ) to a base comparison, while the sampling term is proportional to the residual marginal scale. This yields η ≤ C1εOPT + C2kξ. The relative form εOPT is essential: replacing it by an absolute O(ε) term would not imply the desired (α − ε)OPT − O(kξ) resilience statement."

The conclusion states: "We established adversarial resilience of the SGS-Poisson paradigm for nonnegative submodular maximization over general matroids. The Poisson process, single-element exchange mechanism, and spiteful drop rule are unchanged. The key technical result is a resilient adaptive-preprocessing theorem: despite controlled-oracle maximum-base decisions and a noisy stopping time, a matroid-exchange potential retains positive drift. This produces the residual marginal certificate required by SGS-Poisson, after which robust almost-above-average swaps preserve its Poisson differential inequality. The resulting offline algorithms have limiting approximation factors 1/e and 1 − 1/e, additive sensitivity O(kξ), and O(nk2ε−2) controlled-oracle complexity. Through the single-agent offline-to-online CMAB reduction, our resilience parameters yield exact limiting approximation-regret factors 1/e and 1 − 1/e with O(n 1/5 k 4/5 T 4/5) regret."

Based on this paper, here are the specific improvements you can make to AI systems:

• Improvement: Implement the controlled-oracle resilience framework so AI systems can maintain performance guarantees even when their evaluation functions are persistently corrupted by adversarial noise (up to ξ error per query).

• What the improved system can do: An AI that performs submodular optimization (e.g., sensor placement, data summarization, influence maximization) will still achieve near-optimal results (1/e or 1−1/e approximation) even if its value oracle is systematically biased, without needing to detect or correct the bias.

• Improvement: Use the resilient adaptive-preprocessing drift lemma to design AI systems that can adaptively select initial solution components (e.g., seed sets, feature subsets) using noisy estimates, while guaranteeing the potential function retains positive drift.

• What the improved system can do: An AI can perform multi-stage greedy selection (like choosing an initial subset before refinement) even when each marginal gain estimate is noisy, and still converge to a high-quality solution without requiring the noisy trajectory to stay close to the true trajectory.

• Improvement: Adopt the Spiteful Greedy Swap Poisson Process (SGS-Poisson) as a search algorithm that maintains feasibility and explores via single-element exchanges, even when marginal estimates are noisy.

• What the improved system can do: An AI can perform continuous-time-like stochastic search over combinatorial spaces (e.g., selecting a subset of items under matroid constraints) with noisy feedback, achieving the same approximation guarantees as with perfect feedback, while using only O(nk2ε−2) oracle calls.

• Improvement: Integrate the offline-to-online reduction to build AI systems that learn optimal combinatorial decisions (e.g., which sensors to activate, which items to recommend) from only aggregate reward feedback (no per-item feedback).

• What the improved system can do: An AI can achieve exact limiting approximation-regret factors of 1/e (non-monotone) and 1−1/e (monotone) with regret O(n 1/5k 4/5T 4/5) over time horizon T, even when it only observes the total reward of its chosen set, not individual component rewards.

• Improvement: Use the robust maximum-base comparison lemma to make AI systems that select the best base (e.g., a maximal feasible set) under noisy edge weights or marginal values, with error bounded by O(kξ) rather than amplified by the number of selection steps.

• What the improved system can do: An AI can perform greedy selection of a maximal feasible set (e.g., spanning tree, matching) with noisy weight estimates and still guarantee that the selected set's true weight is within O(kξ) of the optimal, avoiding error accumulation across iterations.

• Improvement: Implement the realized constant-factor optimum certificate to let AI systems estimate the optimal value (OPT) with high confidence even when oracle values are noisy, by running multiple independent noisy greedy runs and taking the best.

• What the improved system can do: An AI can reliably estimate the upper bound of the optimal solution value (within a constant factor) even under adversarial noise, enabling it to set appropriate stopping thresholds and allocate computational resources.

• Improvement: Use the paper's proof technique (which does not require the noisy oracle to be submodular) to make AI systems robust to arbitrary non-submodular perturbations of their objective function.

• What the improved system can do: An AI can optimize a submodular objective even when its evaluation function is corrupted by an arbitrary (possibly non-submodular) function, as long as the corruption is bounded pointwise, and still achieve the classical approximation guarantees.

• Improvement: Adopt the relative form of error bounds (ε·OPT + O(kξ)) to ensure AI systems scale gracefully when the optimal value is small.

• What the improved system can do: An AI can maintain its approximation guarantee even when OPT is small (e.g., when the best achievable solution has low value), because the error term scales with OPT rather than being an absolute constant, preventing the guarantee from becoming vacuous.

• Improvement: Apply the resilience framework to AI systems that must make sequential decisions under matroid constraints (e.g., selecting a portfolio of projects, allocating resources) where the feedback function has a fixed, unknown bias.

• What the improved system can do: An AI can make a sequence of feasible decisions (each respecting the matroid constraint) and still achieve near-optimal cumulative performance, even if the same biased oracle is used throughout, because the bias is absorbed as O(kξ) rather than multiplied by the number of decisions.

• Improvement: Use the resilient submodular maximization as a subroutine in larger AI systems (e.g., feature selection for machine learning, active learning, recommender systems) to make them robust to noisy data or model mis-specification.

• What the improved system can do: An AI pipeline that uses submodular maximization (e.g., for diverse subset selection) will maintain its performance guarantees even when the underlying data or reward model is corrupted, making the entire pipeline more reliable in real-world adversarial settings.