Research map / Bandits and online learning / Multi-armed bandits
Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantile-based delayed-feedback Successive Elimination rather than the prior expectation-based delay bound | Stochastic MAB with reward-independent delays · Reward-independent delays | expected pseudo-regret upper bound: O(\min_{q}\{\mabregret/q + d(q)\}) vs. O(\mabregret + K\mathbb{E}[D]) | Helped |
| Use phased elimination to balance observed samples across arms | Successive Elimination · Arm-dependent packet loss | expected pseudo-regret upper bound: O(\sum_{i\ne i^{*}}\log(T)/\Delta_{i}\cdot(1/p_i+1/p_{i^{*}})) -> O(\sum_{i\ne i^{*}}\log T/(\Delta_{i}p_{i})) | Helped |
| Use round-robin Successive Elimination instead of UCB under fixed delays | Stochastic MAB · Fixed delay | expected pseudo-regret: O(\mabregret + Kd) -> O(\mabregret + d) | Helped |
| Use SE rather than PatientBandits | Stochastic MAB with reward-independent delays · α-Pareto delays | regret | Helped |
| Use OPSE's optimistic and pessimistic bounds to account for missing, potentially biased rewards | Stochastic MAB with reward-dependent delays · Reward-dependent delays | regret | Helped |
| Use standard SE without accounting for reward-dependent observation bias | Stochastic MAB · Reward-dependent delays | regret | Hurt |
| Use UCB with fixed delays instead of immediate-feedback UCB | UCB · Fixed delay | expected pseudo-regret: \Omega(Kd) | Hurt |
| Use Optimistic-UCB instead of OPSE | Reward-dependent delayed MAB · Reward-dependent delays | expected pseudo-regret upper bound: O(\sum_{i\ne i^{*}}\frac{\log T}{\Delta_{i}} + \sum_{i\ne i^{*}}d_{i}(1-\Delta_{i}/4)) | Mixed |
Closest papers by meaning
- Near-Optimal Stochastic Linear Bandits with Delay (NeurIPS 2026 · similarity 0.94)
- Delay as Payoff in MAB (AAAI 2025 · similarity 0.93)
- Stochastic bandits with arm-dependent delays (ICML 2020 · similarity 0.92)
- Bandits with Delayed, Aggregated Anonymous Feedback (ICML 2018 · similarity 0.91)
- A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delays (NeurIPS 2024 · similarity 0.90)
- Contextual Linear Bandits with Delay as Payoff (ICML 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.