Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor

Online challenge

• The online method cannot directly run the offline Box-Maximization step because current-function feedback arrives only after the action is committed under adversarial variation.Past or averaged box solutions do not control the current reward, so standard offline-to-online wrappers fail.Source: §1 · pp. 3–4

Online composition

• The new composition replaces the unavailable per-round box optimum with weighted online unconstrained maximization whose cumulative certificate amortizes delayed-trajectory debts, while an outer learner controls the remaining linear term.Randomized selection between the inner and outer candidates yields the reward guarantee without relying on invalid concavity arguments.Source: §1 · pp. 4, 6, 7

Feedback extensions

• Batching yields O(T^δ) calls per round and O(T^(4/5−δ/5)) regret for δ ∈ [0, 1/4], while randomized blocking gives O(T^5/6) one-point bandit regret under the positive-anchor condition.These weaker-feedback extensions change additive learning terms and oracle budgets, not the 0.401 approximation factor.Source: §1 · pp. 3, 6

Main result

• 0.401 approximation with sublinear regret matches the best known constructive offline factor, without claiming optimality; the related hardness benchmark is 0.478 [12].The comparison concerns the approximation coefficient under the corresponding constructive assumptions, not identical oracle models.Source: §1 · pp. 2, 6

Weighted balance

• The exact weighted balance theorem gives approachable constant 2√cXcY, preserving the offline asymmetric coefficients and making the online and offline factor-revealing programs agree at the certified delay.The theorem includes an explicit polynomial-time Blackwell approachability strategy and applies to estimated marginals under noisy feedback.Source: §1 · pp. 5, 7

Implementation

• O(T^3/4) regret and O(dT^1/4) oracle calls per round hold for the direct post-decision full-information implementation under conditionally unbiased bounded noisy feedback.For every fixed noise level σ, the approximation factor, regret exponents, and call budgets remain unchanged.Source: §1 · pp. 6–7

Offline DR-submodular maximization

• The offline benchmark improved from 1/e to 0.401 through asymmetric Box-Maximization, while related hardness results limit polynomial-query guarantees to 0.478 [10] [12].Continuous Double-Greedy provides the optimal 1/2 guarantee on unconstrained boxes and motivates the inner primitive [18].Source: §2 · p. 7

Online submodular maximization

• Online submodular work developed no-regret and resource-allocation methods, but this paper requires an exact weighted asymmetric balance game to preserve the offline constant [17].Earlier online DR-submodular results covered approximate regret over convex sets, whereas the present focus is the asymmetric box layer for the 0.401 down-closed benchmark [19, 22, 26, 27, 30, 28].Source: §2 · pp. 7–8

Value-query and bandit feedback

• Existing value-feedback methods retained factor 1/e, including O(T^3/4) post-decision and O(T^4/5) bandit rates, leaving the online approximation barrier open [29] [30].These approaches use smoothing, finite differences, stochastic gradients, projection-free methods, or upper-linearizability to obtain feedback conversions [23] [25] [26].Source: §2 · p. 8
• This paper resolves the open barrier under its studied feedback models, trading a larger O(T^5/6) bandit additive term for the stronger 0.401 approximation factor.Its construction exploits nonadaptivity of within-round queries to estimate a block-average objective from one observation per physical round.Source: §2 · p. 8

• The feasible region K is nonempty, compact, convex, and down-closed within [0,1]^d, with diameter D and 0 ∈ K.The learner has a polynomial-time Euclidean projection oracle for K, and D is known for parameter tuning.Source: §3 · p. 8
• An oblivious adversary fixes differentiable, nonnegative, L-smooth DR-submodular rewards f_1,...,f_T valued in [0,M].DR-submodularity is characterized by an antitone gradient, and the parameters T, d, M, B, and L are fixed throughout.Source: §3 · p. 8
• At each round, the learner commits to a history-measurable feasible point p_t before receiving information about f_t, and earns the true value f_t(p_t).The objective is to achieve a constant approximation coefficient with regret o(T), assuming the horizon is known for parameter tuning.Source: §3 · pp. 9–10
• The noisy value oracle returns conditionally unbiased values with independent, bounded errors of magnitude σ, so observations lie in [−σ,M+σ] and repeated calls are informative.Every repeated occurrence requires a separate oracle call; exact feedback is the special case σ = 0.Source: §3 · p. 9
• The model includes post-decision full-information queries at arbitrary points and one-point bandit feedback restricted to the noisy value of the played point.Conditional unbiasedness is essential: systematic bias propagates through the algorithm and cannot be removed by repetition.Source: §3 · pp. 9–10
• The claimed factor is asymptotic: it is the benchmark coefficient α, while finite-horizon guarantees may have a deficit and provide no constant factor when OPT_T is sublinear.For linear OPT_T, the stated deficits are O(T^-1/4) for the direct algorithm and O(T^-1/6) for the bandit algorithm.Source: §3 · p. 10

4 Post-decision full-information value-oracle result

• 0.401 approximation is achieved online against an oblivious adversary under noisy post-decision value-oracle feedback, using Algorithm 1 with certified structural parameters.The construction composes delayed endpoint certification, asymmetric offline box coefficients, online Double-Greedy, and projected stochastic online gradient ascent.Source: §4 · pp. 11–12
• O(T^3/4) regret with O(dT^1/4) oracle calls per round follows from the balanced choice m = ⌈T^1/4⌉ and ε = T^-1/4.For σ = 0 this is the exact-oracle guarantee; with fixed noise, noise changes constants through Mσ = M + σ but not the approximation factor or exponents.Source: §4 · p. 12
• O(T^δ) calls per round and O(T^(4/5-δ/5)) regret are obtained for every δ ∈ [0, 1/4], including one call with O(T^4/5) regret.The endpoint δ = 1/4 recovers the direct T-exponents, while decreasing δ trades a smaller query budget for a worse regret rate and batching can incur dimension-dependent regret costs.Source: §4 · p. 13

4.1 Structural certificate

• The structural certificate gives a comparator-uniform endpoint inequality for every nonnegative differentiable DR-submodular f and arbitrary x, o ∈ K.Trajectory feasibility ensures Yτ(x) ∈ K and supports the early- and late-phase comparisons; the resulting two-coefficient form leaves only f(x ⊙ o), f(x), and a linear residual.Source: §4.1 · pp. 14–16
• The two-coefficient endpoint form absorbs the lattice-step residue ζs⟨∇f(x), o − x⟩ into outer online linear optimization, replacing the offline approximate local maximum.The transformed objective exposes the remaining nonlinear comparator terms through f(x ⊙ a) at a = o and a = 1, preserving the offline asymmetry-optimized value.Source: §4.1 · p. 16

4.2 Weighted online unconstrained submodular maximization (USM)

• The weighted online USM subproblem models Double-Greedy as a binary balance game whose target cone requires reward R to dominate both missed-opportunity piles.The adversary may depend on history and the announced mixture but not the learner’s fresh binary draw; conditionally unbiased noisy observations preserve the balance guarantee up to a constant factor.Source: §4.2 · p. 17
• Theorem 4.8 gives the exact approachable-balance condition a ≤ 2√c_Xc_Y, with impossibility for every larger a.The converse constructs an admissible fixed adversary whose cone violation remains bounded away from zero and grows linearly with T.Source: §4.2 · pp. 18–19
• At weights (c_X,c_Y)=(1/r,r), the maximum balance constant is 2, so asymmetric weighting preserves the offline Double-Greedy coefficients.These coefficients transfer to the comparator, all-ones, and all-zeros values; Theorem 4.18 and Proposition 4.26 preserve their offline composition online.Source: §4.2 · pp. 19–20
• The efficient Blackwell balancer uses a constant-dimensional quadratic program and achieves expected weighted balance regret O(M√T) whenever a ≤ 2√c_Xc_Y.Its per-round computational cost is polynomial in the input size and independent of d and m.Source: §4.2 · pp. 20–21
• The noisy-marginal extension remains valid when estimates are observed only after all round decisions, provided they are conditionally unbiased and bounded.The estimation errors form martingale differences, while true marginals—not noisy estimates—must satisfy admissibility.Source: §4.2 · p. 21
• Count lifting converts a continuous nonnegative DR-submodular box problem into a nonnegative submodular set function while losing at most B_G√d/m per rounded comparator per round.The count representation preserves every grid point exactly; max-level lifting can fail submodularity for non-monotone objectives.Source: §4.2 · pp. 22–23
• The online Double-Greedy reduction uses the asymmetric balance game while retaining both endpoint terms under a nonanticipating, post-decision noisy-feedback model.The current submodular function is fixed before fresh binary draws, and learner probabilities depend only on prior observations.Source: §4.2 · pp. 23–24
• The weighted Double-Greedy reduction converts per-learner weighted balance regret into a global guarantee by telescoping hybrid potentials, despite acyclic within-round dependence among learners.Each learner faces an admissible nonanticipating move, while the hybrid argument handles negative non-monotone marginals without discarding rounds.Source: §4.2 · pp. 24–25
• The weighted online USM theorem preserves the asymmetric offline Box-Maximization coefficient triple online, up to additive balance-regret and grid-discretization losses.The result is polynomial-time and applies to differentiable DR-submodular round objectives with conditionally fresh inner randomization and post-commitment noisy feedback.Source: §4.2 · p. 26
• The lifted Double-Greedy implementation uses 4dm noisy-oracle calls per round, with remaining work limited to combinatorial operations and constant-dimensional convex computations.The noisy estimates are conditionally unbiased and bounded, and the exact-feedback case is recovered when σ = 0.Source: §4.2 · p. 26
• The composition with G_t(a) = f_t(x_t ⊙ a) yields a certified comparator coefficient exceeding 0.401 through the explicit sequence a_max = 2√(c_Xc_Y), a = 2, and the final mixing coefficient.The inner coefficients align with the outer certificate’s cumulative quantities and debts, so the mixture pays both debts under the certified parameters.Source: §4.2 · pp. 26–27

4.3.1 Noisy post-decision value-oracle implementation

• Un-clipped noisy field estimates are handled by projected stochastic online gradient ascent with a second-moment step-size bound, charging estimator bias rather than fluctuation linearly in T.Conditional unbiasedness makes the martingale term vanish, while the iterate remains projected onto K after every update.Source: §4.3 · pp. 27–28, §4.3.1 · pp. 29–30

4.3 Algorithm and factor-revealing composition

• The online composition balances outer and inner learners through an asymmetric randomized mixture, yielding the central factor-revealing expression.The play coin is excluded from state updates and surrogate construction, while the two candidate points are selected independently and need not be comparable.Source: §4.3 · pp. 28–29

4.3.1 Noisy post-decision value-oracle implementation

• 4dQ oracle calls reconstruct the noisy gradient field, giving O(d/ε) calls when h = ε/2 and Q = ⌈ε−1⌉.The estimator uses fresh, nonadaptive finite-difference calls and averages Q repetitions at the current point to control oracle noise.Source: §4.3.1 · pp. 30–32

4.3.2 The approximation factor

• 0.401 is certified using rational parameters, with λ0 ≈0.8038 and α(s0, r0) ≈0.40102.The formal theorem uses the headline factor 0.401, while interval arithmetic certifies the rounded parameters.Source: §4.3.2 · p. 33

4.3.3 Equality with the offline coefficient program

• The online and offline constructions repay the f(x ⊕o) debt differently but attain the same optimized value at the balanced asymmetry associated with the certified delay.Offline uses an approximate local maximum and Box-Maximization, whereas online uses a lattice inequality and absorbs the resulting linear residue through the outer learner.Source: §4.3.3 · pp. 33–34

The common branch underlying the comparison is the identity

• For every admissible delay, the online and offline minima share the same branch switch, and their coefficients agree throughout the interval up to that switch.When the switch satisfies rs ≥ 2, both expressions are maximized at the common switch.Source: The common branch underlying the… · p. 34
• At the certified delay, both coefficient programs switch and optimize at the same asymmetry, attaining the same value strictly above 0.401.This equality concerns only the optimized approximation coefficient, not identical global behavior or algorithms.Source: The common branch underlying the… · pp. 34–35

4.3.4 Proof of the post-decision value-oracle theorem

• The post-decision algorithm remains feasible and unbiased because actions and lifted decisions precede fresh oracle calls, so current objectives affect only later rounds.This ordering permits separate learner analysis despite within-round dependence.Source: §4.3.4 · pp. 35–36
• O(T^3/4) regret and O(dT^1/4) oracle calls follow by choosing m = ⌈T^1/4⌉ and ε = T^-1/4.The proof obtains the regret guarantee from Proposition 4.24 and counts 4dm inner calls plus O(d/ε) outer calls; doubling epochs handle unknown horizons with constant-factor overhead.Source: §4.3.4 · p. 36

4.4.1 Why the offline factor survives online

• Cumulative online learning controls the transformed residuals, and Proposition 4.26 shows the optimized asymmetric coefficient equals the corresponding offline coefficient.The residuals are amortized over time rather than eliminated pointwise, preserving the offline factor.Source: §4.4.1 · p. 36

4.4.2 Oracle complexity and timing

• The direct implementation achieves O(T^3/4) regret with O(dT^1/4) oracle calls per round, while batching reduces the budget to O(T^δ).The online replacement is not a black-box reduction: it tracks changing transformed objectives with decisions made before observing them, while preserving the offline geometry.Source: §4.4.2 · p. 37

4.4.3 Relation to the offline frontier

• A polynomial-rate online regret guarantee on repeated objectives would imply the same offline factor up to arbitrarily small error, but exceeding 0.401 would improve the offline record.Value-oracle inapproximability beyond 0.478 for a related multilinear-extension problem limits what such improvements could achieve.Source: §4.4.3 · p. 38
• The architecture is modular: improvements to either the outer endpoint inequality or the inner box frontier propagate through the factor-revealing program when cumulative online guarantees are available.Within the current architecture, Theorem 4.8 makes the balance constant extremal, so reweighting cannot improve the stated coefficients.Source: §4.4.3 · p. 38

4.4.4 Where the noise is paid for

• The approximation factor remains exactly α⋆ at every noise level, with no restriction on how σ depends on T; oracle noise affects only additive terms.Noise changes inner regret constants, adds outer fluctuation terms, and doubles calls because caching is forbidden, while leaving structural coefficients unchanged.Source: §4.4.4 · p. 38

5 Secondary extension to one-point bandit feedback

• Block simulation replaces unavailable same-function queries by randomly injected feasible probes, while independent oracle noise affects second moments but leaves the bias unchanged.The query list is fixed before each block, and the learner observes only the noisy value of the assigned played point.Source: §5 · p. 39, §5.2 · p. 40

5.1 Interior geometry and feasible finite differences

• A known anchor x̄_i ≥ ρ enables contraction and finite-difference steps whose inner and outer query points all remain feasible in the down-closed set.The contraction provides uniform coordinate room, with h ≤ γρ/2 ensuring every required probe lies in K.Source: §5.1 · p. 39

5.2 Bandit algorithm

• Algorithm 2 batches labeled feasible query points, assigns them uniformly across each block, and updates the online learners from unbiased marginal and finite-difference estimates.The block-level construction uses past-block feedback and fresh pre-block randomness, then plays the assigned query or exploitation point.Source: §5.2 · p. 40

5.3 Bandit guarantee and parameter tradeoff

• The guarantee relies on obliviousness: pre-block randomness fixes the query schedule before feedback, making each injected label an unbiased sample of the block average.Sequential coupling among inner learners depends on decisions rather than current feedback, so it does not violate nonadaptivity.Source: §5.3 · p. 41
• The bandit guarantee is materially weaker than the post-decision one, with the coefficient BD/ρ identified as the relevant difference in Remark 5.3.Source: Algorithm 2 satisfies · p. 43

• 0.401 is achieved online in an adversarial setting with sublinear regret, matching the best known constructive offline approximation factor.An exact weighted balance theorem and amortized online composition preserve the asymmetric offline coefficients.Source: §6 · p. 43
• O(T^3/4) regret with O(dT^1/4) calls per round is obtained by the direct post-decision value-oracle implementation.Batching provides the limited-query tradeoff.Source: §6 · p. 43
• O(T^5/6) one-point bandit regret is obtained through randomized blocking under the positive-anchor condition.Source: §6 · p. 43
• Conditionally unbiased bounded oracle noise changes only additive terms, not the 0.401 approximation factor.Source: §6 · p. 43

A Block simulation of the query list

• A complete query list is fixed before observations and assigned by a uniform random injection, preserving nonanticipation despite noisy oracle feedback.The schedule issues labeled queries on assigned rounds and plays the exploitation point on all remaining rounds.Source: A Block simulation of the query list · pp. 45–46
• Post-decision queries incur no exploration loss, whereas bandit queries must themselves be played and therefore require feasibility.This is the sole difference between the two applications of the shared blocking machinery.Source: A Block simulation of the query list · p. 46
• The injected schedule preserves unbiased block averages and finite-difference estimates; smoothness and quadrature contribute O(Lh) and O((B + L)/Q) bias.The injection averages observations over the block, while centered oracle noise does not affect the estimator’s bias.Source: A Block simulation of the query list · p. 47
• The block estimator’s fluctuations combine injection and oracle noise with the same 1/Q damping, so noise does not change the exponent when σ ≤M.In that common regime, M^2σ ≤4M^2, limiting the constant increase to at most a factor of four.Source: A Block simulation of the query list · pp. 47–48
• Sampled inner marginals remain conditionally unbiased for true submodular marginals, enabling the inner learner with an O(dmMσN) learning term.Observed marginal estimates need not be nonnegative; admissibility is required only for the true marginals manipulated by the analysis.Source: A Block simulation of the query list · p. 48

Block construction

• Before current-objective feedback, the algorithm fixes all oracle locations, holds its state over each block, and plays the same reward-bearing action throughout.Unlike bandit conversion, oracle calls do not replace the played action, so block reward is exactly Hfb(pb) and probes need not be feasible.Source: B Proof of the limited-query frontier · pp. 48–49

Query scheduling

• Each update uses a nonadaptive list of J=O(dT^ξ) value labels, partitioned across blocks to require at most k oracle calls per round.The parameter relation δ+ℓ=ξ and the choice of Cq ensure the labels fit within the block capacity.Source: B Proof of the limited-query frontier · pp. 48–49

Unbiased feedback

• Uniform random assignment of labels to rounds makes every observed oracle value conditionally unbiased, combining round-assignment randomness with centered oracle noise.The proof then forms Double-Greedy marginals and the outer finite-difference estimator from these sampled values.Source: B Proof of the limited-query frontier · p. 49

Limited-query frontier

• O(T^(4−δ)/5) regret holds for the batched frontier, with δ≤1/4 and fixed noise leaving the exponent unchanged.The stochastic-field and incomplete-block exponents are both smaller than (4−δ)/5, while noise appears only through Mσ in the constant.Source: B Proof of the limited-query frontier · p. 49

Constant-sequence implication

• Sublinear regret on a constant sequence makes the expected approximation converge to α for every fixed instance.If R(T)=o(T), then R(T)/T vanishes.Source: C Offline implications of constant… · p. 50
• If R(T)≤CT^κ for κ<1 and max_o∈K f(o)≥v>0 is known, a sufficiently large polynomial horizon gives an expected (α−ε)-approximation.The explicit regret rate and optimum normalization determine the required horizon.Source: C Offline implications of constant… · p. 50

Online factors imply offline factors

• An online algorithm with Reg_α(T)≤CT^κ, polynomial per-round costs, and polynomially bounded C and v^-1 yields a polynomial-time offline (α−ε)-approximation by constant-sequence simulation.The guarantee applies in either feedback model of Section 3.Source: C Offline implications of constant… · p. 50
• The simulator returns a uniformly random played point because selecting the best point is unavailable under noisy values and bandit feedback.With exact values, returning the best played point is also valid and can only improve the guarantee.Source: C Offline implications of constant… · p. 50

Limitations

• The known lower bound v is essential for a quantitative polynomial-time implication, and the reduction does not show that 0.401 is optimal.Without optimum normalization, additive sublinear regret need not become relatively negligible in polynomially many rounds.Source: C Offline implications of constant… · p. 50

D Proof of the endpoint comparison inequalities

• The appendix proves inequalities (22)–(23), which are used in Lemma 4.6.These inequalities specialize Lemmas 5.7 and 5.9 of [10] to z = x and the constant direction x(τ) ≡ x.Source: D Proof of the endpoint comparison… · p. 51
• The proofs replace an optimizer with an arbitrary comparator o, making the inequalities quantitatively comparator-uniform.The imported inequalities are nonstandard offline ingredients of the outer certificate.Source: D Proof of the endpoint comparison… · p. 51
• The results assume differentiable, nonnegative, DR-submodular f on [0, 1]^d and use general-purpose lemmas stated in dimension n, including n = 2d for a doubled ground set.The second general-purpose lemma is applied by Lemma D.4 on the doubled ground set.Source: D Proof of the endpoint comparison… · p. 51

• DR-submodularity implies that ∇f is antitone coordinatewise, providing the central structural fact behind the toolbox’s inequalities.If u ≤ w, then ∇f(u) ≥ ∇f(w) coordinatewise.Source: §D.1 · p. 51
• Along nonnegative coordinate segments, f is concave, yielding the stated interpolation property and supporting-gradient inequalities for forward and backward displacements.The toolbox gives ⟨∇f(u), ∆⟩ ≥ f(u + ∆) − f(u) and ⟨∇f(u), ∆⟩ ≤ f(u) − f(u − ∆) under the corresponding feasibility conditions.Source: §D.1 · p. 51
• For every y ∈ [0, 1]^n, the maps a ↦ f(a ⊙ y) and a ↦ f(a ⊕ y) remain nonnegative and DR-submodular.This follows because each transformation is an order-preserving affine map with nonnegative diagonal scaling, which preserves antitonicity of the gradient.Source: §D.1 · p. 51

Basic exponential bound

• Lemma D.3 gives the basic exponential bound for any differentiable, nonnegative DR-submodular F, integrable trajectory ξ, and vector a.The proof establishes finite truncations by induction and passes to the infinite sum using monotone convergence.Source: §D.2 · p. 52
• The induction proof differentiates an auxiliary function g(t), applies the hypothesis to a transformed vector, and compares it with a truncated right-hand side.The chain rule, symmetry and associativity of ⊕, and nonnegativity yield the required almost-everywhere derivative inequality and matching initial values.Source: §D.2 · pp. 52–53

Two-block exponential bound

• Lemma D.4 derives a two-block exponential bound for f by lifting it to a 2d-dimensional function F and applying Lemma D.3 blockwise.The lifting remains DR-submodular because its argument is coordinatewise nondecreasing while ∇f is antitone, so the resulting gradient is antitone.Source: §D.2 · p. 53

D.3 A comparison lemma

• For x ∈ [0,1]^d, Δ ≤ 1 − o, and o′ ≤ o, the lemma establishes f(o) + f(0) − f(x ⊕ o) − f(o − o′) ≥ f(o) − f(x ⊕ o) − f(o − o′).The assumptions include Δ,o,o′ ∈ [0,1]^d, with o′ ≤ o.Source: §D.3 · p. 53
• The proof first applies (P1) at base o − o′ with increment o′ + (1 − x) ⊙ Δ, whose resulting point is feasible because it is at most 1.The feasibility check uses (o − o′) + o′ + (1 − x) ⊙ Δ = o + (1 − x) ⊙ Δ ≤ 1.Source: §D.3 · p. 54
• It then applies (P1) at base o with increment (1 − x) ⊙ Δ, using 1 − (x ⊕ o) ≥ (1 − x) ⊙ Δ, and combines the inequalities.Nonnegativity of f gives the second inequality after adding the two displays and using f(0) ≥ 0.Source: §D.3 · p. 54

D.4 The two comparisons

• Lemma D.6 gives the early comparison for every x,o ∈ [0,1]^d and every τ ∈ [0,s).Its proof represents the early-phase residual and applies the auxiliary comparison lemmas to obtain the required bound.Source: §D.4 · p. 54
• Lemma D.7 gives the late comparison for every x,o ∈ [0,1]^d and every τ ∈ [s,1].The proof separates integration cases according to whether coordinates fall before or after s, using exact equality in the one-coordinate late case and nonnegativity otherwise.Source: §D.4 · p. 55
• Together, Lemmas D.6 and D.7 establish (22) and (23), using only nonnegativity and DR-submodularity, with no optimality assumption on o or property of K beyond x,o ∈ [0,1]^d.This comparator-uniformity is the basis for the online argument.Source: §D.4 · p. 55