Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Is O(log N) practical? Near-Equivalence Between Delay Robustness and Bounded Regret in Bandits and RL
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.
Shows that under unknown anonymous reward delays, consistent algorithms can be epsilon-delay-robust only if the Graves-Lai constant is zero, and that for linear contextual bandits and linear MDPs zero Graves-Lai constant is also sufficient for bounded regret with delay robustness.
Problem
Achieving consistent (sub-polynomial) and bounded regret in interactive decision making with stochastic, unknown, anonymous reward delays when the delay model may be misspecified by epsilon-contamination.
Approach
Links the Graves-Lai constant being zero to delay robustness: necessity for any consistent algorithm to be epsilon-delay-robust for general DMSO, and sufficiency for linear DMSO problems via a test-to-commit algorithm (ST2C) that needs no delay model knowledge and attains bounded regret under cross-informativeness.
Key results
- Theorem 4.1: for general DMSO, a consistent algorithm can be epsilon-delay-robust (for any epsilon>0) only if the Graves-Lai constant C(f*)=0.
- Theorem 4.11: ST2C achieves bounded expected regret, without delay-model knowledge, under cross-informativeness (Assumption 4.7) and bounded log-likelihood ratios (Assumption 4.8).
- Corollary 5.3: for contextual linear bandits, bounded regret is a priori achievable under anonymous delays if and only if the arm feature vectors span R^d for all theta.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow any positive ϵ-contamination of the delay model | Consistent DMSO algorithms · DMSO with anonymous delayed rewards | regret consistency under delay misspecification | Hurt |
| Use ST2C without knowledge of the delay distribution model under Assumptions 4.7 and 4.8 | DMSO · Unknown delay models | regret: bounded regret ∆(1+5 4c4e−2/W(2c2)2 ) π2/6 | Helped |
| Require optimal feature vectors to span Rd for all θ ∈ Θ | ST2C for contextual linear bandits · Contextual linear bandits with anonymous delayed rewards | regret | Helped |
| Require optimal-policy feature vectors to span Rd at every h | ST2C for Linear MDPs with Bellman closure · Episodic Linear MDP with anonymous delayed rewards | regret | Helped |
Surprising findings
- Even an arbitrarily small epsilon-contamination of the delay model precludes consistency unless the Graves-Lai constant is zero.
Limitations
- Positive (sufficiency) result is restricted to linear problems (contextual linear bandits and linear MDPs with Bellman closure).
- Relies on technical assumptions such as cross-informativeness (Assumption 4.7) and bounded log-likelihood ratios (Assumption 4.8).
- Purely theoretical; no experiments.
Experimental setup
Metrics: regret Graves-Lai constant
Baselines: DAAF algorithm of Dong et al. (2021) Vernade et al. (2020) delayed anonymous feedback algorithm
Builds on: Dong and Ma (2022) DMSO lower bound Wagenmaker and Foster (2023) instance-optimal DMSO Hao, Lattimore, Szepesvari contextual linear bandit characterization Papini et al. linear MDP characterization
Closest papers by meaning
- How Does Variance Shape the Regret in Contextual Bandits? (NeurIPS 2024 · similarity 0.89)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.88)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.88)
- Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.88)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.87)
- Catoni Contextual Bandits are Robust to Heavy-tailed Rewards (ICML 2025 · similarity 0.87)
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.