Research map / Bandits and online learning / Online convex optimization and games
Improved Regret for Bandit Convex Optimization with Delayed Feedback
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 D-FTBL, a follow-the-regularized-leader bandit method with blocking updates for bandit convex optimization under arbitrary delayed loss-value feedback, improving the delay-dependent regret to O(sqrt(dT)) and matching lower bounds in the worst case.
Problem
Bandit convex optimization where only the loss value is revealed after an arbitrary delay; prior bounds O(sqrt(n)T^{3/4}+(n·dbar)^{1/3}T^{2/3}) have a large gap to the Omega(sqrt(dbar T)) lower bound.
Approach
Combine one-point gradient estimation with a blocking update mechanism (updates only at block ends, block size K ~ n^2/delta^2), so block-level gradient variance scales with block size alone and the block-level delay shrinks as block size grows; this decouples delay and bandit-feedback effects within an FTRL-style update using all received feedback.
Key results
- D-FTBL achieves E[Regret] = O(sqrt(n)T^{3/4} + sqrt(dT)) for convex functions, improving the delay-dependent term over the prior O((n dbar)^{1/3}T^{2/3}) whenever d = O((n dbar)^{2/3} T^{1/3}), and matching the Omega(sqrt(dbar T)) lower bound in the worst case.
- For alpha-strongly convex functions, D-FTBL achieves O((nT)^{2/3} log^{1/3} T + d log T), with a delay term matching the Omega(d log T) lower bound.
- For unconstrained strongly convex and smooth functions, the extension achieves O(n sqrt(T log T) + d log T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use blocking updates with delayed bandit feedback | D-FTBL for delayed BCO with convex functions · Delayed BCO, convex functions | regret bound: O(\sqrt{n}T^{3/4}+\sqrt{dT}) versus O(\sqrt{n}T^{3/4}+(n\bar{d})^{1/3}T^{2/3}) | Helped |
| use blocking updates with delayed bandit feedback | D-FTBL for delayed BCO with convex functions · Delayed BCO, convex functions | regret bound: O(\sqrt{n}T^{3/4}+\sqrt{dT}) versus O(\sqrt{n}d^{1/4}T^{3/4}) | Helped |
| exploit strong convexity | D-FTBL for delayed BCO · Delayed BCO, strongly convex functions | regret bound: O((nT)^{2/3}\log^{1/3} T+d\log T) versus O(\sqrt{n}T^{3/4}+\sqrt{dT}) | Helped |
| extend D-FTBL to unconstrained action sets and use smoothness | D-FTBL for delayed BCO · Unconstrained, strongly convex and smooth functions | regret bound: O(n\sqrt{T\log T}+d\log T) versus O((nT)^{2/3}\log^{1/3} T+d\log T) | Helped |
Limitations
- All bounds depend on the maximum delay d rather than the average delay dbar.
- The blocking mechanism enlarges each delay to at least the block size.
- Assumes an oblivious adversary and requires step size tuning with knowledge of d for the convex case (handled via doubling trick).
Experimental setup
Metrics: expected regret
Baselines: BGD GOLD improved GOLD (block-box/refined bound)
Builds on: bandit gradient descent GOLD follow-the-regularized-leader one-point gradient estimator
Closest papers by meaning
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.93)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.93)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.92)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.91)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.91)
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.