pipette
ESEspañol

Regret without Optimal-Arm Feedback under Reward-Dependent Delays

Zhong Han

Preprint

In the authors' words

We study stochastic bandits with reward-dependent delays, possibly infinite, whose reports omit the originating round. For each , Balanced Historical Optimism (BHO) has a delay term controlled by the largest suboptimal-arm quantile at level , without requiring optimal-arm reports. Lower bounds give an inverse-square slack cost in the logarithmic statistical regime and linear minimax regret at . A family with growing forces worst-case regret for every learner, where is the largest gap-weighted suboptimal cutoff. Pending-triggered balance preserves BHO's weighted-cutoff bound for 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.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 45 pages, 3 figures. Code and data are included as ancillary files