Bandit multiclass linear classification: Efficient algorithms for the separable case

We study the problem of efficient online multi-class linear classification with bandit feedback, where all examples belong to one of K classes and lie in the (¿-dimensional Euclidean space. Previous works have left open the challenge of designing efficient algorithms with finite mistake bounds when the data is linearly separable by a margin 7. In this work, we take a first step towards this problem. We consider two notions of linear separability, strong and weak. 1. Under the strong linear separability condition, we design an efficient algorithm that achieves a near-optimal mistake bound of o(K/γ²). 2. Under the more challenging weak linear separability condition, we design an efficient algorithm with a mistake bound of min(2^õ(K log ²(1/γ)),2^õ(√1/γ log K)).¹ Our algorithm is based on kernel Perceptron and is inspired by the work of Klivans & Serve-dio (2008) on improperly learning intersection of halfspaces.