Title: A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis,
Abstract: Existing strategies for finite-armed stochastic bandits mostly depend on a
parameter of scale that must be known in advance. Sometimes this is in the form
of a bound on the payoffs, or the knowledge of a variance or subgaussian
parameter. The notable exceptions are the analysis of Gaussian bandits with
unknown mean and variance by Cowan and Katehakis [2015] and of uniform
distributions with unknown support [Cowan and Katehakis, 2015]. The results
derived in these specialised cases are generalised here to the non-parametric
setup, where the learner knows only a bound on the kurtosis of the noise, which
is a scale free measure of the extremity of outliers.