标题： 带重尾的强盗问题 显示英文标题

标题： Bandits with heavy tail

摘要： 当奖励分布为次高斯分布时，随机多臂老虎机问题已经被很好地理解了。 本文在较弱的假设下研究了老虎机问题，即假设分布具有 \(1+\)\epsilon 阶矩，其中 $\epsilon \in (0,1]$是某个值。 令人惊讶的是，二阶矩（即有限方差）就足以获得与次高斯奖励分布下相同阶数的遗憾界。 为了实现这种遗憾界，我们定义了基于改进均值估计器的采样策略，例如截断经验均值、Catoni 的 M 估计器和中位数均值估计器。 我们还推导了匹配的下界，这些下界也表明当 \epsilon <1 时，最佳可达到的遗憾会恶化。 显示英文摘要

摘要： The stochastic multi-armed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper we examine the bandit problem under the weaker assumption that the distributions have moments of order 1+\epsilon, for some $\epsilon \in (0,1]$. Surprisingly, moments of order 2 (i.e., finite variance) are sufficient to obtain regret bounds of the same order as under sub-Gaussian reward distributions. In order to achieve such regret, we define sampling strategies based on refined estimators of the mean such as the truncated empirical mean, Catoni's M-estimator, and the median-of-means estimator. We also derive matching lower bounds that also show that the best achievable regret deteriorates when \epsilon <1.