Research map / Bandits and online learning / Online convex optimization and games
Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DBGD-NF and BDBGD-NF, bandit-feedback online nonsubmodular optimization algorithms with delayed feedback whose regret depends on the average delay, and a blocking variant that decouples delay and bandit effects, validated on structured sparse learning.
Problem
Online nonsubmodular optimization with delayed feedback under bandit feedback, where prior regret bounds O(n d^{1/3} T^{2/3}) depend on the maximum delay and multiply delay and bandit-estimation terms.
Approach
Use one-point gradient estimates from all received delayed feedback each round (DBGD-NF) for an average-delay regret bound, and a blocking update that aggregates gradients per block so delay and bandit variance effects add rather than multiply (BDBGD-NF).
Key results
- DBGD-NF achieves O(n d̄^{1/3} T^{2/3}) bandit regret relevant to average delay, improving on O(n d^{1/3} T^{2/3}) of DBAGD.
- BDBGD-NF achieves O(n(T^{2/3}+sqrt(dT))) regret, matching O(nT^{2/3}) when d=O(T^{1/3}).
- DOGD-NF achieves O(sqrt(n d̄ T)) full-information regret, improving on DOAGD's O(sqrt(ndT)).
- Experiments on synthetic structured sparse learning (T=8000, n=10) show BDBGD-NF yields lowest regret across delay settings d in {10,20,500}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the one-point gradient estimator and all available estimated gradients instead of only the oldest available gradient | DBGD-NF versus DBAGD · Bandit, delayed feedback | (α,β)-regret bound: $\mathcal{O}\left(nd^{1/3}T^{2/3}\right)$ -> $\mathcal{O}\left(n\bar{d}^{1/3}T^{2/3}\right)$ | Helped |
| Add a blocking update mechanism to DBGD-NF | BDBGD-NF · Bandit, delayed feedback | (α,β)-regret bound: $\mathcal{O}\left(n\Bar{d}^{1/3}T^{2/3}\right)$ -> $\mathcal{O}\left(n(T^{2/3}+\sqrt{dT})\right)$ | Helped |
| Use true gradients and all available gradients for updates | DOGD-NF versus DOAGD · Full-information, delayed feedback | (α,β)-regret bound: $\mathcal{O}(\sqrt{ndT})$ -> $\mathcal{O}(\sqrt{n\bar{d}T})$ | Helped |
| Use all available gradients rather than just the oldest one | DOGD-NF versus DOAGD · Structured sparse learning, full-information, delayed feedback | regret | Helped |
| Use the one-point gradient estimator and all available estimated gradients | DBGD-NF versus DBAGD · Structured sparse learning, bandit, delayed feedback | regret | Helped |
| Add a blocking update mechanism | BDBGD-NF versus DBGD-NF · Structured sparse learning, bandit, delayed feedback | regret | Helped |
Limitations
- DBGD-NF requires prior knowledge of average delay to set the learning rate (doubling trick mentioned as fix).
- BDBGD-NF regret depends on maximum delay d rather than average delay.
- Experiments are small-scale synthetic only.
Experimental setup
Datasets: synthetic linear regression data for structured sparse learning
Benchmarks: synthetic structured sparse learning regression
Metrics: (alpha,beta)-regret
Baselines: DOAGD DBAGD
Builds on: DBAGD DOAGD Lovász extension blocking update mechanism one-point gradient estimator
Closest papers by meaning
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.93)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.92)
- Bandit and Delayed Feedback in Online Structured Prediction (NeurIPS 2025 · similarity 0.92)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.91)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.90)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.