Research map / Bandits and online learning / Online convex optimization and games
Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and 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.
Gives delay-robust regret algorithms for adversarial contextual bandits with delayed bandit feedback: an EXP4-style policy-class method and a FIFO-based function-approximation method using a stable Hedge-based Vovk aggregating forecaster as the least-squares oracle.
Problem
Adversarial contextual multi-armed bandits where loss observations arrive with adversarially chosen delays, under policy-class learning and general function approximation with online least-squares oracles.
Approach
Delay-adapted importance-weighted loss estimators for EXP4 yield an O(sqrt(KT log|Pi|)+sqrt(D log|Pi|)) bound; for function approximation, a DA-FA algorithm feeds delayed observations to a stable online regression oracle, and a stability analysis of Hedge-based Vovk's aggregating forecaster shows beta = O(log|F|).
Key results
- Policy-class EXP4-DALE attains E[R_T] <= log N/eta + eta KT + 2 eta D, giving O(sqrt(KT log N)+sqrt(D log N)), matched by a lower bound.
- DA-FA attains O(sqrt(KT R_T) + sqrt(d_max D beta)) under FIFO delays, and with Hedge-based Vovk forecaster beta = 2 log|F| gives O(sqrt(KT log|F|)+sqrt(d_max D log|F|)).
- Without an oracle stability assumption, any algorithm suffers Omega(T) regret with delay d=1 and a zero-regret oracle.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EXP4-DALE for policy-class learning with adversarial delays | Adversarial CMAB over a finite policy class · Adversarial CMAB, policy class learning | expected regret: O (\sqrt{KT \log N} + \sqrt{D \log N}) | Helped |
| Use DA-FA with a stable online least-squares regression oracle under FIFO delays | Adversarial CMAB with function approximation · Online function approximation with FIFO delays | expected regret: O\brk*{\sqrt{KT \mathcal{R}_{T}(\OLSR^{\mathcal{F},\beta})} + \sqrt{d_{\max} D \beta}} | Helped |
| Use the Hedge-based Vovk forecaster as the regression oracle | DA-FA with a finite realizable function class · Adversarial CMAB, finite realizable function class with FIFO delays | expected regret: O\brk{\sqrt{KT\log(\abs{\mathcal{F}})} + \sqrt { d_{\max} D \log \abs{\mathcal{F}} }} | Helped |
| Remove the oracle stability assumption | Adversarial CMAB with realizable function approximation · Fixed delay d=1 | regret: \Omega(T) | Hurt |
| Use Hedge-based Vovk's forecaster for finite realizable square-loss regression | Online least-squares regression · Finite realizable function class | expected square-loss regret: \frac{2\log \abs{\mathcal{F}}}{\eta} | Helped |
| Use Hedge-based Vovk's forecaster for finite realizable square-loss regression | Online least-squares regression · Finite realizable function class | cumulative stability: \log \abs{\mathcal{F}} | Helped |
| Use FIFO-ordered feedback | DA-FA · Adversarial CMAB with function approximation | expected regret | Helped |
Surprising findings
- Without an additional oracle stability assumption, no algorithm can achieve sublinear regret under delays even with zero oracle regret and fixed delay 1.
- The Hedge-based Vovk forecaster has stability parameter independent of T, bounded by log|F|.
Limitations
- Function-approximation bound carries an extra sqrt(d_max) factor relative to the lower bound.
- Requires FIFO delay order and realizability for the stability analysis.
- Purely theoretical; no experiments.
Experimental setup
Metrics: expected regret
Baselines: EXP4 SquareCB
Builds on: EXP4 SquareCB Vovk's aggregating forecaster
Closest papers by meaning
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.92)
- Improved Regret for Bandit Convex Optimization with Delayed Feedback (NeurIPS 2024 · similarity 0.91)
- Second Order Bounds for Contextual Bandits with Function Approximation (ICLR 2025 · similarity 0.91)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.91)
- An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction (NeurIPS 2025 · similarity 0.91)
- Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays (NeurIPS 2026 · 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.