Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Contextual Linear Bandits with Delay as Payoff

ICML 2025 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Linear and generalized linear bandits · 0 citations (OpenAlex)

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.

Extends the delay-as-payoff bandit model (delay proportional to loss/reward) to contextual linear bandits via a phased volumetric-spanner arm elimination algorithm plus a contextual-to-non-contextual reduction, with regret overhead bounds and a small synthetic experiment versus LinUCB.

Problem

Stochastic linear bandits where the payoff (loss or reward) is revealed after a delay proportional to the payoff itself, with fixed or i.i.d. varying action sets; prior work only covered multi-armed bandits.

Approach

Replace ellipsoidal confidence sets with phased arm elimination over a volumetric spanner of the action set (3n actions), building UCB/LCB for each action from spanner estimates; the spanner-based LCB avoids the need for a confidence set on theta. Combined with a misspecification-robust variant and the contextual-to-non-contextual reduction of prior work.

Key results

• Delay overhead for delay-as-loss is O(min{n d* log(T/n) + D Delta_max, D Delta_max log(T/n)}), a separation from the delay-free regret of order min{n^2/Delta_min, n sqrt(T)} up to logs.
• Contextual extension gives the first regret guarantee for contextual linear bandits with delay-as-payoff, with an O(n sqrt(T log T)) standard term.
• On synthetic instances (T=16000, D=1000, n in {6,8,10}, 8 seeds), the proposed algorithm consistently outperforms LinUCB with only currently available feedback.

Measured effects reported in the paper

Limitations

• Standard regret term has worse dependence on dimension n in the contextual case.
• No matching regret lower bounds are proven.
• Experiments restricted to the non-contextual setting with synthetic data and ignoring the role of B.

Experimental setup

Benchmarks: synthetic linear bandit instances

Metrics: cumulative pseudo regret

Baselines: LinUCB with currently available feedback

Builds on: Schlisselberg et al. (2025) delay-as-payoff MAB LinUCB volumetric spanner (Hazan et al.) contextual-to-non-contextual reduction (Hao et al.)

Closest papers by meaning

• Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.93)
• Delay as Payoff in MAB (AAAI 2025 · similarity 0.92)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits (NeurIPS 2020 · similarity 0.90)
• Learning in Generalized Linear Contextual Bandits with Stochastic Delays (NeurIPS 2019 · similarity 0.90)
• Delay and Cooperation in Nonstochastic Linear Bandits (NeurIPS 2020 · similarity 0.90)
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.89)