Sparse online learning with bandit feedback

The bandit classification problem considers learning the labels of a time-indexed data stream under a mere " hit-or-miss " binary guiding. Adapting the OVA (" one-versus-all ") hinge loss setup, we develop a sparse and lightweight solution to this problem. The issued sequential norm-minimal update solves the classification problem in finite time in the separable case, provided enough redundancy is present in the data. An O(√ T) regret in moreover expected in the non-separable case. The algorithm shows effectiveness on both large scale text-mining and machine learning datasets, with (i) a favorable comparison with the more demanding confidence-based second-order bandits setups on large scale datasets and (ii) a good sparsity and efficacy when a kernel approach is applied to non-separable datasets