arXiv cs.AI· Tuan Ngoc Do, Hai Duc Nguyen·· 1 天前AI 评分18
可见尾部：重尾赌博机中未知时刻自适应性的刻画
Visible Tails: Characterizing Adaptation to Unknown Moments in Heavy-Tailed Bandits
AI 导读
研究提出用最优奖励律上的单侧可见性条件刻画重尾赌博机中"好臂的有利奖励尚未出现"这一障碍：均值隐藏在稀有事件中时，至多不超过保留中心矩的常数倍。给定可见性常数的分位数截断 UCB 索引在每个指数上都达到臂级矩速率，且指数无下界；反之，任何固定探索预算的策略在违反对应条件的律上都有多项式 regret。对方差基准，确定了可见性水平下两个预算常数的阶，且所得类别严格嵌套。
正文 · 原文
Abstract:Heavy-tailed bandit learners must tell a poor arm from an arm whose favorable rewards have not yet appeared. We characterize this obstruction through a scale of one-sided visibility conditions on the optimal reward law: the mean hidden in a rare event is at most a constant multiple of a retained central moment. A quantile-trimmed UCB index that is given the visibility constants attains arm-specific moment rates at every exponent, with no lower bound on the exponent. Conversely, every strategy with a fixed exploration budget has polynomial regret on each law that violates the corresponding condition. For the variance benchmark we determine the order of both budget constants in the visibility level. The frontier depends on the largest exponent the benchmark promises, and the resulting classes are strictly nested. The same index has logarithmic expected regret when rewards are integrable, with a coefficient that can be exponential in the inverse gap.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.12140 [cs.LG] |
| (or arXiv:2611.12140v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.12140 arXiv-issued DOI via DataCite |
Submission history
From: Tuan Do [view email]
[v1]
Mon, 9 Nov 2026 09:53:14 UTC (133 KB)
[v2]
Wed, 11 Nov 2026 17:03:18 UTC (142 KB)
来源：arXiv cs.AI · arxiv.org