On the Optimality of Perturbations in Stochastic and Adversarial
  Multi-armed Bandit Problems
  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.
