Paper bounds bandit regret when delayed rewards omit the round
Original title: Regret without Optimal-Arm Feedback under Reward-Dependent Delays
Balanced Historical Optimism controls delay cost without optimal-arm reports; minimax regret is linear at c=1.
The paper studies stochastic bandits with reward-dependent delays, possibly infinite, when reports omit the originating round. For each c in [0,1), Balanced Historical Optimism has a delay term set by the largest suboptimal-arm quantile at level 1-cΔ_i. Lower bounds give an inverse-square slack cost in the logarithmic regime and linear minimax regret at c=1. A growing-K family forces worst-case regret Ω(G log K) for every learner.
- G is defined as the largest gap-weighted suboptimal cutoff, max_i Δ_i h_i.
- Pending-triggered balance preserves the weighted-cutoff bound for c<1.
- With deterministic rewards, a unique optimum and fixed bounded delays, it matches the historical-greedy coefficient.
From the original article
1 min read at arxiv.orgWe study stochastic bandits with reward-dependent delays, possibly infinite, whose reports omit the originating round. For each $c\in[0,1)$, Balanced Historical Optimism (BHO) has a delay term controlled by the largest suboptimal-arm quantile at level $1-cΔ_i$, without requiring optimal-arm reports.
By Zhong Han · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.