Visible Tails：刻画重尾多臂老虎机中对未知矩的适应性
Visible Tails: Characterizing Adaptation to Unknown Moments in Heavy-Tailed Bandits
AI 导读
arXiv 论文《Visible Tails》刻画了重尾多臂老虎机学习中区分劣臂与有利奖励尚未出现的臂这一障碍。论文通过最优奖励分布的单侧可见性条件刻度来描述该问题，并提出一种给定可见性常数的分位数截断 UCB 策略，可在各指数下达到臂特定的矩速率，且指数无下界。该策略在奖励可积时期望遗憾为对数级，而固定探索预算的策略在违反相应条件的分布上只能获得多项式遗憾。
正文 · 原文
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