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\mathrm{/}9$, improving the online $0.401$ benchmark, with one gradient query and one projection per round and $O(\sqrt{T})$ expected approximate regret. If $\zeta \mathbf{1}\in K\subseteq [0,1{]}^d$, the coefficient improves to $\underset{‾}{\alpha }(\zeta )=\frac{1}{2}-(1-2\zeta {)}_{+}^2\mathrm{/}[2(3-2\zeta {)}^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 ${\beta }_{\ast }=0.470438681380894\dots$ 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\mathrm{/}2$ for $\zeta \ge 1\mathrm{/}2$, and show that the optimal deficit from $1\mathrm{/}2$ is $\mathrm{\Theta }((1\mathrm{/}2-\zeta {)}^2)$ as $\zeta \uparrow 1\mathrm{/}2$. For coefficient-revealed polynomials we obtain $1\mathrm{/}2$ for quadratics and a geometry-dependent cubic coefficient starting at $8\mathrm{/}17$, including $0.49$ at $\zeta =1\mathrm{/}5$. A constant objective sequence yields an offline $(4\mathrm{/}9-\epsilon )$ 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(T^{3\mathrm{/}4})$ regret with one noisy value per round.