Multiclass Online Learnability under Bandit Feedback
Authors:
- Ananth RamanARAnanth Raman
- Vinod RamanVRVinod Raman
- Unique SubediUSUnique Subedi
- Idan MehalelIMIdan Mehalel
- Ambuj TewariATAmbuj Tewari
Preprint
Abstract
We study online multiclass classification under bandit feedback. We extend the results of Daniely and Helbertal [2013] by showing that the finiteness of the Bandit Littlestone dimension is necessary and sufficient for bandit online learnability even when the label space is unbounded. Moreover, we show that, unlike the full-information setting, sequential uniform convergence is necessary but not sufficient for bandit online learnability. Our result complements the recent work by Hanneke, Moran, Raman, Subedi, and Tewari [2023] who show that the Littlestone dimension characterizes online multiclass learnability in the full-information setting even when the label space is unbounded.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Optimal Prediction Using Expert Advice and Randomized Littlestone DimensionSIAM Journal on Computing, 2025
- A note on the price of bandit feedback for mistake-bounded online learningTheoretical Computer Science, 2021
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- Structural Results About On-line Learning Models With and Without QueriesMachine Learning, 1999
- On Learning Sets and FunctionsMachine Learning, 1989