The Real Price of Bandit Information in Multiclass Classification
<|reference_start|>The Real Price of Bandit Information in Multiclass Classification: 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 contribution is in showing that the minimax regret of bandit multiclass is in fact more nuanced, and is of the form $\smash{\widetilde{\Theta}\left(\min \left\{|H| + \sqrt{T}, \sqrt{KT \log |H|} \right\} \right) }$, where $H$ is the underlying (finite) hypothesis class. In particular, we present a new bandit classification algorithm that guarantees regret $\smash{\widetilde{O}(|H|+\sqrt{T})}$, improving over classical algorithms for moderately-sized hypothesis classes, and give a matching lower bound establishing tightness of the upper bounds (up to log-factors) in all parameter regimes.<|reference_end|>
@article{erez2024the,
    title={The Real Price of Bandit Information in Multiclass Classification},
    author={Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran},
    journal={arXiv preprint arXiv:2405.10027},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.10027},
    primaryClass={cs.LG cs.AI stat.ML}
}