Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
Abstract
We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the d-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at 1/e. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has O(T3/4) regret and uses O(dT1/4) oracle calls per round. More generally, for every δ∈[0,1/4], batching gives O(Tδ) calls per round and O(T4/5−δ/5) regret, including a one-call O(T4/5) endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with O(T5/6) one-point bandit regret.
Related
- An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
- A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization
- Online Submodular Welfare Maximization: Computation is not the Bottleneck
BibTeX
@misc{aggarwal2026online,
title = {{Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor}},
author = {Vaneet Aggarwal and Yiyang Lu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02145},
eprint = {2609.02145},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02145},
}
RIS
TY - UNPB
TI - Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
AU - Vaneet Aggarwal
AU - Yiyang Lu
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02145
UR - https://arxiv.org/abs/2609.02145
AB - We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the d-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at 1/e. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The online algorithm does not run the offline construction on a changing objective. Instead, it replaces the offline objective-dependent box step by a weighted online learner that controls the required residual terms cumulatively. An exact asymmetric balance theorem preserves the offline coefficients despite adversarial variation. The direct implementation has O(T^3/4) regret and uses O(dT^1/4) oracle calls per round. More generally, for every δ∈[0,1/4], batching gives O(T^δ) calls per round and O(T^4/5−δ/5) regret, including a one-call O(T^4/5) endpoint. Under a positive-anchor condition, randomized blocking retains factor $0.401$ with O(T^5/6) one-point bandit regret.
ER -