arXiv 新论文：BHO 算法处理奖励依赖延迟的多臂老虎机问题
Regret without Optimal-Arm Feedback under Reward-Dependent Delays
搞在线学习或多臂老虎机的值得看这篇：延迟反馈但不知道奖励来自哪一轮的场景很常见，论文提出的 BHO 算法不依赖最优臂报告也能控住遗憾，还给了配套下界，理论上把可行边界画清楚了，做算法研究或推荐系统延迟归因的可以拿来对照自己的设定。
arXiv 论文 2611.11494 研究带奖励依赖延迟的随机多臂老虎机问题，延迟可能为无穷大，且反馈不标注奖励 originating round，即无需最优臂报告即可学习。
论文提出 Balanced Historical Optimism（BHO）算法，其延迟项由次优臂在水平 1-cΔᵢ 处的最大分位数控制，覆盖参数 c∈[0,1) 的情形。下界结果表明：在对数统计机制下存在逆平方松弛代价，当 c=1 时遗憾退化为线性；
当臂总数 K 增长时，任何学习器的最坏情况遗憾都达到 Ω(G log K)，其中 G 为最大的 gap-weighted 次优 cutoff。机制上，BHO 通过 pending-triggered balance 维持加权 cutoff 界（c<1），并在确定奖励、唯一最优臂和固定有界延迟的情形下实现 historical-greedy 探索系数。
论文还通过 gap-weighted 比较与实验分析了共享等待何时有利以及平衡探索的代价，对延迟反馈环境下的在线学习算法设计具有参考价值。
Regret without Optimal-Arm Feedback under Reward-Dependent Delays
We 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. Lower bounds give an inverse-square slack cost in the logarithmic statistical regime and linear minimax regret at $c=1$. A family with growing $K$ forces worst-case regret $Ω(G\log K)$ for every learner, where $G=\max_iΔ_i h_i$ is the largest gap-weighted suboptimal cutoff. Pending-triggered balance preserves BHO's weighted-cutoff bound for $c<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.
本条情报归属 AITOP「论文」核心追踪栏目。涉及核心实体与技术议题包括：多臂老虎机、BHO、arXiv、在线学习，读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明：本文原始线索采编自「arXiv cs.LG」（@Zhong Han），经 AITOP 多维评分管线结构化提炼。