A simple multi-armed bandit algorithm with optimal variation-bounded regret

We pose the question of whether it is possible to design a simple, linear-time algorithm for the basic multi-armed bandit problem in the adversarial setting which has a regret bound of O(√Q logT), where Q is the total quadratic variation of all the arms. We are interested in the fundamental multi-armed bandit (MAB) problem: iteratively at times t = 1,2,..., T the decision maker has to choose (possibly randomly) one of n arms, it, and then receives the payoff of the arm, assumed to be in the range [0, 1]. The payoffs are constructed adversarially, as in (Auer et al., 2003), and we denote the payoff at time t for arm i by f_t{i) ∈ [0,1]. The decision maker can only see her own payoff, and does not have access to the entire payoff vector f_t (otherwise it would have been the usual "experts" problem"). The goal is to minimize regret: