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

CardsList
  1. Near-Optimal Stochastic Linear Bandits with Delay

    Jun 15, 2026Ofir Schlisselberg, Mengxiao Zhang, Yishay MansourBandits with Delayed FeedbackContextual Bandits

  2. Lipschitz Bandits with Arbitrary Feedback Delays

    Aug 15, 2026Yuhao Liu, Yu Chen, Longbo HuangLipschitz BanditsMulti-Armed Bandits