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


Elad Hazan, Satyen Kale ;
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:817-820, 2011.


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(\sqrtQ \log T), where Q is the total quadratic variation of all the arms.

Related Material