We investigate the optimality of perturbation based algorithms in the
stochastic and adversarial multi-armed bandit problems. For the stochastic
case, we provide a unified regret analysis for both sub-Weibull and bounded
perturbations when rewards are sub-Gaussian. Our bounds are instance optimal
for sub-Weibull perturbations with parameter 2 that also have a matching lower
tail bound, and all bounded support perturbations where there is sufficient
probability mass at the extremes of the support. For the adversarial setting,
we prove rigorous barriers against two natural solution approaches using tools
from discrete choice theory and extreme value theory. Our results suggest that
the optimal perturbation, if it exists, will be of Frechet-type.

本研究探讨了在随机和对抗多臂老虎机问题中，基于扰动的算法的最优性。我们提供了对于子 Weibull 和有界扰动的统一遗憾分析，当收益是次高斯分布时。我们的界限对于具有参数 2 的子 Weibull 扰动是实例最优的，并且具有匹配的下支界。对于对于在支持的极端点处有足够概率质量的所有有界扰动，我们都提供了实例最优边界。在对抗设置中，我们使用离散选择理论和极值理论的工具，证明了两种自然解决方法的严格障碍。我们的结果表明，如果最优扰动存在，则将是 Frechet 类型的。