An Optimal Algorithm for Stochastic and Adversarial Bandits II: α-Tsallis-INF With Symmetric Regularization Has Anytime Adversarial Pseudo-Regret 2√(min{1/(α−α²), log K/α, log T/(1−α)}·KT) + 1Research Paper
In the adversarial multi-armed bandit problem a learner repeatedly picks one of arms and observes only the loss of the arm it picked, while an adversary chooses the losses, possibly reacting to the learner's past choices. The minimax pseudo-regret of this problem is of order after rounds, and the classical algorithm Exp3 achieves only …