Research map / Bandits and online learning / Multi-armed bandits
Delay as Payoff in MAB
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.
Studies stochastic multi-armed bandits where the payoff equals the delay, proving tight regret bounds for both cost (minimal expected delay d*) and reward (second-maximal expected delay) settings, improving on prior delay-dependent results.
Problem
Stochastic multi-armed bandits where each arm's payoff (cost or reward) is delayed and equals the magnitude of that delay; prior delay-dependent regret bounds are loose, especially for the cost case which was unstudied.
Approach
Exploits partial information from missing feedback (a pending payoff implies delay at least the elapsed time) via successive elimination with a threshold B estimated by doubling (cost) or halving (reward), yielding regret additive terms d* (cost) and second-max delay (reward) instead of the maximum delay D.
Key results
- Reward setting: BHSE outperforms OPSE and CensoredUCB on both truncated Normal and Bernoulli delay distributions in synthetic experiments (averaged over 10 runs).
- Cost setting: theoretical regret sum log T/Delta_i + min{d*, D Delta_max}, with matching lower bound Omega(d*) for d* <= D/2.
- Reward setting regret improves additive term from D sum Delta_i (prior) to min{second-max delay, D Delta_max}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BDSE for delay-as-cost payoff | Stochastic MAB with delay as cost · Delay-as-cost MAB | pseudo regret | Helped |
| use BHSE for delay-as-reward payoff | Stochastic MAB with delay as reward · Delay-as-reward MAB | pseudo regret | Helped |
| use BHSE instead of OPSE and CensoredUCB | Delay-as-reward MAB · Truncated Normal and Bernoulli | cumulative regret | Helped |
| use BDSE instead of OPSE | Delay-as-cost MAB · Synthetic cost experiments | cumulative regret | Helped |
| use Bernoulli rather than Truncated Normal delays | Synthetic reward experiments · Bernoulli versus Truncated Normal | cumulative regret | Hurt |
Surprising findings
- In the cost setting, the optimal regret depends on the minimal expected delay, while in the reward setting it depends on the second-maximal expected delay, so cost can be much cheaper than reward on the same instance.
- BDSE shows high variance in the Bernoulli cost experiments because small mean changes alter the number of doubling calls.
Limitations
- Assumes bounded delays with support in [0, D]; unbounded delays left open.
- Analysis is for non-contextual stochastic bandits; contextual and linear variants not covered.
- Experiments are synthetic only, with limited algorithm comparison.
Experimental setup
Datasets: synthetic bandit instances (truncated Normal, Bernoulli delays)
Benchmarks: synthetic bandit instances with T=150000, K=30, D=5000
Metrics: cumulative pseudo regret
Baselines: OPSE CensoredUCB
Builds on: Successive Elimination Censored UCB OPSE
Closest papers by meaning
- Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions (ICML 2021 · similarity 0.93)
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.92)
- Contextual Linear Bandits with Delay as Payoff (ICML 2025 · similarity 0.92)
- Nonstochastic Multiarmed Bandits with Unrestricted Delays (NeurIPS 2019 · similarity 0.90)
- Individual Regret in Cooperative Stochastic Multi-Armed Bandits (NeurIPS 2025 · similarity 0.89)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.89)
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.