Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization

We study adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. A learner commits each action before observing its objective and competes with the best fixed action in hindsight. We prove a comparator-uniform first-order inequality that gives coefficient 4/9, improving the online 0.401 benchmark, with one gradient query and one projection per round and O(√ T) expected approximate regret. If zeta bf 1 ∈ Ksubseteq[0,1]d, the coefficient improves to underlineα(zeta)=tfrac12-(1-2zeta)_+2/[2(3-2zeta)2]. The proof is a direct ordered-coordinate argument with an objective-independent rational action. Conversely, a three-group symmetry-gap construction yields an offline oracle upper bound β_*=0.470438681380894ldots at zeta=0, even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every zeta. The lower and upper bounds match at 1/2 for zeta≥1/2, and show that the optimal deficit from 1/2 is Theta((1/2-zeta)2) as zetauparrow1/2. For coefficient-revealed polynomials we obtain 1/2 for quadratics and a geometry-dependent cubic coefficient starting at 8/17, including 0.49 at zeta=1/5. A constant objective sequence yields an offline (4/9-varepsilon) approximation with polynomially many first-order queries on the cube and projections, without requiring a supplied positive lower bound on the optimum. We also give nonanticipating adaptive-adversary and value-feedback guarantees, including O(T3/4) regret with one noisy value per round.