Research map / Bandits and online learning / Online convex optimization and games
Bandit and Delayed Feedback in Online Structured Prediction
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.
Develops online structured prediction algorithms under bandit and delayed feedback, bounding surrogate regret via inverse-weighted and pseudo-inverse gradient estimators with randomized decoding under uniform exploration.
Problem
Online structured prediction is usually studied under full-information feedback, which is unrealistic for complex outputs; the paper asks how to get finite surrogate regret under bandit and delayed feedback when the output set is large.
Approach
Uses randomized decoding with uniform exploration (RDUE) so that the bandit gradient estimator can be built from the observed target loss. An inverse-weighted estimator gives O(sqrt(KT)); a pseudo-inverse matrix estimator removes explicit dependence on K at the cost of O(T^{2/3}). Delayed variants combine these with ODAFTRL or BOLD.
Key results
- Bandit feedback with inverse-weighted estimator achieves O(sqrt(KT)) surrogate regret.
- Pseudo-inverse matrix estimator achieves K-independent O(T^{2/3}) surrogate regret, e.g. O(d^{2/3}T^{2/3}) for multiclass with 0-1 loss.
- Full-information delayed feedback achieves O(D+1) surrogate regret, matched by an Omega(D+1) lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an inverse-weighted gradient estimator with RDUE under bandit feedback | OSP with SELF loss · Bandit feedback | surrogate regret bound: O(\sqrt{KT}) vs. O(K\sqrt{T}) | Helped |
| Use a pseudo-inverse matrix estimator instead of an inverse-weighted gradient estimator | OSP with SELF* loss · Bandit feedback | surrogate regret bound: O(\sqrt{KT}) -> O(T^{2/3}) | Mixed |
| Use ODAFTRL for fixed-delay full-information feedback | OSP · Fixed-delay full-information feedback | surrogate regret bound: O(\sqrt{(D + 1)T}) -> O(\min\{D^2 + 1, (D + 1)^{2/3}T^{1/3}\}) | Helped |
| Use BOLD with OGD for fixed-delay full-information feedback | OSP · Fixed-delay full-information feedback | surrogate regret bound: O(\sqrt{(D + 1)T}) -> O(D + 1) | Helped |
| Add fixed delay to inverse-weighted bandit feedback using ODAFTRL | OSP with SELF loss · Fixed-delay bandit feedback | surrogate regret bound: O(\sqrt{KT}) -> O(\sqrt{(K+D)T}) | Hurt |
| Add fixed delay to pseudo-inverse bandit feedback using ODAFTRL | OSP with SELF* loss · Fixed-delay bandit feedback | surrogate regret bound: O(T^{2/3}) -> O(D^{1/3} T^{2/3}) | Hurt |
| Use ODAFTRL instead of BOLD under delayed bandit feedback | OSP with inverse-weighted or pseudo-inverse gradient estimation · Fixed-delay bandit feedback | surrogate regret bound: O(\sqrt{KDT}) -> O(\sqrt{(K+D)T}); O(D^{1/3}T^{2/3}) -> O(D^{1/3} T^{2/3}) | Helped |
Surprising findings
- The surrogate regret under full-information delayed feedback is independent of T (O(D+1)), with a matching lower bound.
- The inverse-weighted bandit bound improves the existing O(K sqrt(T)) bound by a factor of sqrt(K), though the comparison is not direct due to different surrogate losses.
Limitations
- Lower bound for bandit feedback is open; the O(sqrt(T)) and O(T^{2/3}) rates may not be tight.
- The pseudo-inverse estimator requires assumptions on V, b, c and the output structure, and gives a worse dependence on T.
- Results are restricted to base-2 logistic surrogate for the bandit inverse-weighted bound, not directly comparable to prior K sqrt(T) bounds.
Experimental setup
Metrics: surrogate regret
Baselines: Hoeven et al. 2020 bandit multiclass Hoeven et al. 2021 graph bandit inverse-weighted estimator
Builds on: Fenchel-Young loss structured encoding loss function (SELF) randomized decoding online gradient descent ODAFTRL BOLD
Closest papers by meaning
- Non-Stationary Online Structured Prediction with Surrogate Losses (ICML 2026 · similarity 0.92)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.92)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.89)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.89)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.88)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.88)
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.