Efficient Bandit Algorithms for Online Multiclass Prediction

This paper introduces the Banditron, a variant of the Perceptron, for the multiclass bandit setting. The multiclass bandit setting models a wide range of practical supervised learning applications whe