The Real Price of Bandit Information in Multiclass Classification

arXiv:2405.10027v1 Announce Type: new
Abstract: We revisit the classical problem of multiclass classification with bandit feedback (Kakade, Shalev-Shwartz and Tewari, 2008), where each input classifies to one of $K$ possible labels and feedback is restricted to whether the predicted label is correct or not. Our primary inquiry is with regard to the dependency on the number of labels $K$, and whether $T$-step regret bounds in this setting can be improved beyond the $\smash{\sqrt{KT}}$ dependence exhibited by existing algorithms. Our main …

abstract arxiv classification cs.ai cs.lg feedback information labels price regard stat.ml type