On the Optimality of Perturbations in Stochastic and
  Adversarial Multi-armed Bandit Problems

           Baekjin Kim                 Ambuj Tewari
         Department of Statistics          Department of Statistics
         University of Michigan           University of Michigan
         Ann Arbor, MI 48109             Ann Arbor, MI 48109
         baekjin@umich.edu              tewaria@umich.edu

                       Abstract
     We investigate the optimality of perturbation based algorithms ...