# Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting

arXiv: https://arxiv.org/abs/2508.00523 · HTML: https://mlsanity.com/paper/2508.00523/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 1 Aug 2025.

## Builds on (most cited first, 15 of 15)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Batch Bayesian Optimization via Local Penalization](https://mlsanity.com/paper/1505.08052/) (2015)
- [Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback](https://mlsanity.com/paper/1910.12424/) (2019)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [On learning to localize objects with minimal supervision](https://mlsanity.com/paper/1403.1024/) (2014)
- [Improved Regret Bounds for Projection-free Bandit Convex Optimization](https://mlsanity.com/paper/1910.03374/) (2019)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Optimal approximation for unconstrained non-submodular minimization](https://mlsanity.com/paper/1905.12145/) (2019)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Improved Projection-free Online Continuous Submodular Maximization](https://mlsanity.com/paper/2305.18442/) (2023)
- [A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation](https://mlsanity.com/paper/1407.2697/) (2014)
- [Structured Sparsity: Discrete and Convex approaches](https://mlsanity.com/paper/1507.05367/) (2015)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [A totally unimodular view of structured sparsity](https://mlsanity.com/paper/1411.1990/) (2014)
- [Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2205.07217/) (2022)

## Built on by (most cited first, 1 of 1)

- [Bandit Guided Submodular Curriculum for Adaptive Subset Selection](https://mlsanity.com/paper/2511.22944/) (2025)

## Abstract (arXiv)

We investigate the online nonsubmodular optimization with delayed feedback in the bandit setting, where the loss function is α-weakly DR-submodular and β-weakly DR-supermodular. Previous work has established an (α,β)-regret bound of O(nd1/3T2/3), where n is the dimensionality and d is the maximum delay. However, its regret bound relies on the maximum delay and is thus sensitive to irregular delays. Additionally, it couples the effects of delays and bandit feedback as its bound is the product of the delay term and the O(nT2/3) regret bound in the bandit setting without delayed feedback. In this paper, we develop two algorithms to address these limitations, respectively. Firstly, we propose a novel method, namely DBGD-NF, which employs the one-point gradient estimator and utilizes all the available estimated gradients in each round to update the decision. It achieves a better O(nbard1/3T2/3) regret bound, which is relevant to the average delay bard = frac1Tsumt=1T dt≤ d. Secondly, we extend DBGD-NF by employing a blocking update mechanism to decouple the joint effect of the delays and bandit feedback, which enjoys an O(n(T2/3 + √dT)) regret bound. When d = O(T1/3), our regret bound matches the O(nT2/3) bound in the bandit setting without delayed feedback. Compared to our first O(nbard1/3T2/3) bound, it is more advantageous when the maximum delay d = o(bard2/3T1/3). Finally, we conduct experiments on structured sparse learning to demonstrate the superiority of our methods.