cs.LGNov 8, 2026

Regret without Optimal-Arm Feedback under Reward-Dependent Delays

Authors: Zhong Han

Organizations: Department of Biomedical Engineering, College of Design and Engineering, National University of Singapore

Abstract

We study stochastic bandits with reward-dependent delays, possibly infinite, whose reports omit the originating round. For each c∈[0,1)c\in[0,1), Balanced Historical Optimism (BHO) has a delay term controlled by the largest suboptimal-arm quantile at level 1−cΔi1-cΔ_i, without requiring optimal-arm reports. Lower bounds give an inverse-square slack cost in the logarithmic statistical regime and linear minimax regret at c=1c=1. A family with growing KK forces worst-case regret Ω(Glog⁡K)Ω(G\log K) for every learner, where G=max⁡iΔihiG=\max_iΔ_i h_i is the largest gap-weighted suboptimal cutoff. Pending-triggered balance preserves BHO's weighted-cutoff bound for c<1c<1 and attains the historical-greedy exploration coefficient with deterministic rewards, a unique optimum and fixed bounded delays. Gap-weighted comparisons and experiments show when shared waiting helps and what balanced exploration costs.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jun 15, 2026

Near-Optimal Stochastic Linear Bandits with Delay

We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB), and when the linear structure creates fundamentally new challenges. Specifically, (1) for loss-independent delays, where the delay does not depend on the realized loss (but potentially depends on the arm), we show that delays incur only an additive regret penalty. Under stochastic delays, this penalty scales with the expected delay, while under adversarial delays, it scales with the maximum number of outstanding observations. Notably, both delay penalties are dimension-free, improving upon the state-of-the-art results; (2) for loss-dependent delays, we show that linear bandits are substantially harder than MAB: unlike in MAB, we prove matching (up to log factors) upper and lower bounds in linear bandits, whose delay penalty depends on the square root of the dimension. (3) for the delay-as-payoff model, a special case of loss-dependent delay, we show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits. Together, these results provide a sharp characterization of how delayed feedback interacts with linear generalization.
Aug 15, 2026

Lipschitz Bandits with Arbitrary Feedback Delays

The Lipschitz bandit problem extends the traditional multi-armed bandit framework to continuous action spaces by assuming that the reward functions satisfy a Lipschitz condition. This work investigates Lipschitz bandits under arbitrary feedback delays, where reward signals are not received immediately upon taking an action but after an arbitrarily chosen delay. We consider both stochastic and adversarial reward settings, proposing an elimination-based algorithm and an EXP3-based algorithm, respectively. For both settings, our algorithms achieve a regret bound of O~(Tdz+1dz+2+D)\tilde{O}\left(T^{\frac{d_z+1}{d_z+2}}+\sqrt{D}\right) over a time horizon TT with total delay DD, where the main difference between settings lies in the definition of the zooming dimension dzd_z. Our bounds match existing delay-free regret guarantees for Lipschitz bandits and characterize the additional O~(D)\tilde{O}(\sqrt{D}) impact introduced by feedback delays.
Oct 28, 2026

Planned Restlessness: Delayed Meta Bandits with Budgets

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(N)O(\sqrt{N}) over NN episodes, with other parameters fixed. For one undelayed TT-step episode with arms capped at T/XT/X plays each, we obtain the LP-relative approximation factor 1+(2πX)−1/2+O(X−1)1+(2πX)^{-1/2}+O(X^{-1}), improving previous factors, with a matching lower bound for the leading term.