Bandits with Delayed Feedback

Follow this topic Ask about this topic

Bandits with delayed feedback study sequential decisions when the reward for an action is observed only after a delay, as in advertising, recommendations, and online experimentation. Researchers adapt methods such as UCB, online mirror descent, EXP3, and inverse-propensity weighting to stochastic, adversarial, contextual, and structured settings, sometimes using early signals to predict eventual rewards. Regret guarantees often retain the delay-free learning rate plus an additional cost tied to the amount of delay, but the cost can depend on whether delays are arbitrary, outcome-dependent, or constrained by capacity. A central open tension is how to obtain sharp guarantees when delay timing, changing contexts, safety requirements, or imperfect early signals affect which observations are available for learning.

Latest papers

12 papers1 paper in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Planned Restlessness: Delayed Meta Bandits with Budgets
Oct 28, 2026Sudipto GuhaMulti-Armed Bandits Bandits with Delayed Feedback
DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback
Oct 9, 2026He Sun, Junyuan Mao, Wenhao Jiang +2Online Resource Allocation Training Data Curation
University of Hong Kong · National University of Singapore · Guangming Laboratory +1
Pooling and Drift in Delayed Bandits
Sep 1, 2026Melika BaghiMulti-Armed Bandits Non-Stationary Bandits
Georgia Institute of Technology
Beyond Peak Backlog: Conditional Energy and Temporal Geometry in Capacity-Constrained Delayed Bandit Optimization
Aug 17, 2026Anling Xiang, Yuwen Yang, Yang ShenBandits with Delayed Feedback Bandit Convex Optimization
Department of Intelligent Communication, School of Journalism and Communication, Minzu University of China, Beijing, China · ZeeLin (Beijing) Technology Co., Ltd., Beijing, China · School of Journalism and Communication, Tsinghua University, Beijing, China +1
Lipschitz Bandits with Arbitrary Feedback Delays
Aug 15, 2026Yuhao Liu, Yu Chen, Longbo HuangLipschitz Bandits Multi-Armed Bandits
Institute for Interdisciplinary Information Sciences, Tsinghua University
When Offline Evaluation Misleads: A Diagnostic Protocol for Reward and Policy Selection in Delayed-Feedback Contextual Bandits
Aug 12, 2026Sang Su Lee, Vineeth Loganathan, Shishir Dash +1Multi-Armed Bandits Off-Policy Evaluation
Thumbtack, Inc. San Francisco, CA, USA
Sequential Hiring of Contingent Workers Through Learning-Based Optimization
Jun 16, 2026Chris Lee, Xiuli Chao, Izak DuenyasMulti-Armed Bandits Bandits with Delayed Feedback
Department of Industrial and Operations Engineering, University of Michigan · Ross School of Business, University of Michigan
Near-Optimal Stochastic Linear Bandits with Delay
Jun 15, 2026Ofir Schlisselberg, Mengxiao Zhang, Yishay MansourBandits with Delayed Feedback Contextual Bandits
Tel Aviv University · University of Iowa · Google Research
Linear and Neural Dueling Bandits with Delayed Feedback
May 26, 2026Xiangyi Wang, Pingchen Lu, Jie Mao +4Inverse Probability Weighting Multi-Armed Bandits
The Chinese University of Hong Kong, Shenzhen · The Chi- nese University of Hong Kong
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
May 22, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisMulti-Armed Bandits Minimax Regret
Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison
Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions
May 3, 2026Youngmin OhMulti-Armed Bandits Bandits with Delayed Feedback
InfiniTree, Republic of Korea
Impatient Bandits: Optimizing for the Long-Term Without Delay
Jan 14, 2025Kelly W. Zhang, Thomas Baldwin-McDonald, Kamil Ciosek +2Multi-Armed Bandits Sequential Recommendation
Imperial College London · University of Manchester · Spotify +2

Oct 28, 2026J/K move · Enter open · S save

Planned Restlessness: Delayed Meta Bandits with Budgets

Sudipto Guha

Multi-Armed Bandits Bandits with Delayed Feedback

Open paper AskPDF arXiv

We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets, bounded report lag and nonbinding budgets, posterior sampling over the recurring priors bounds the price of not knowing them by

O(\sqrt{N})

over

N

episodes, with other parameters fixed. For one undelayed

T

-step episode with arms capped at

T/X

plays each, we obtain the LP-relative approximation factor

1+(2πX)^{-1/2}+O(X^{-1})

, improving previous factors, with a matching lower bound for the leading term.