Multiclass Online Learnability under Bandit Feedback
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914646552739840 |
|---|---|
| author | Raman, Ananth Raman, Vinod Subedi, Unique Mehalel, Idan Tewari, Ambuj |
| author_facet | Raman, Ananth Raman, Vinod Subedi, Unique Mehalel, Idan Tewari, Ambuj |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_04620 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Multiclass Online Learnability under Bandit Feedback Raman, Ananth Raman, Vinod Subedi, Unique Mehalel, Idan Tewari, Ambuj Machine Learning 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. |
| title | Multiclass Online Learnability under Bandit Feedback |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2308.04620 |