Efficient bandit algorithms for online multiclass prediction

This paper introduces the Banditron, a vari-ant of the Perceptron [Rosenblatt, 1958], for the multiclass bandit setting. The multiclass bandit setting models a wide range of prac-tical supervised learning applications where the learner only receives partial feedback (re-ferred to as “bandit ” feedback, in the spirit of multi-armed bandit models) with respect to the true label (e.g. in many web applications users often only provide positive “click ” feed-back which does not necessarily fully disclose a true label). The Banditron has the abil-ity to learn in a multiclass classification set-ting with the “bandit ” feedback which only reveals whether or not the prediction made by the algorithm was correct or not (but does not necessarily reveal the true label). We pro-vide (relative) mistake bounds which show how the Banditron enjoys favorable perfor-mance, and our experiments demonstrate the practicality of the algorithm. Furthermore, this paper pays close attention to the impor-tant special case when the data is linearly separable — a problem which has been ex-haustively studied in the full information set-ting yet is novel in the bandit setting. 1