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

Beginning with the seminal work of Hannan [1957], researchers have been interested in algorithms that use random perturbations to generate a distribution over available actions. Kalai and Vempala [2005] showed that the perturbation idealeads to efficient algorithms for many online learning problems with large action sets. Due to the Gumbel lemma [Hazan et al., 2017], the well known exponential weights algorithm [Freund and Schapire, 1997] also has an interpretation as a perturbation based algorithm that uses Gumbel distributed perturbations. There have been several attempts to analyze the regret of perturbation based algorithms with specific distributions such as Uniform, Double-exponential, dropout and random walk (see, e.g., [Kalai and Vempala, 2005, Kujala and Elomaa, 2005, Devroye et al., 2013, Van Erven et al., 2014]). These works provided rigorous guarantees but the techniques they used did not generalize to general perturbations.