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.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include 多臂老虎机, BHO, arXiv, 在线学习.
Source attribution: curated from arXiv cs.LG (@Zhong Han).