# Multiclass Online Learnability under Bandit Feedback

arXiv: https://arxiv.org/abs/2308.04620 · HTML: https://mlsanity.com/paper/2308.04620/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 8 Aug 2023.

## Builds on (most cited first, 9 of 9)

- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [The price of bandit information in multiclass online classification](https://mlsanity.com/paper/1302.1043/) (2013)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [A note on the price of bandit feedback for mistake-bounded online learning](https://mlsanity.com/paper/2101.06891/) (2021)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)

## Built on by (most cited first, 12 of 12)

- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification](https://mlsanity.com/paper/2407.11619/) (2024)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [Fast Rates for Bandit PAC Multiclass Classification](https://mlsanity.com/paper/2406.12406/) (2024)
- [Apple Tasting: Combinatorial Dimensions and Minimax Rates](https://mlsanity.com/paper/2310.19064/) (2023)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Partial Feedback Online Learning](https://mlsanity.com/paper/2601.21462/) (2026)
- [Faster Rates for Private Adversarial Bandits](https://mlsanity.com/paper/2505.21790/) (2025)
- [A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advice](https://mlsanity.com/paper/2511.00257/) (2025)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [Robust Online Learning](https://mlsanity.com/paper/2602.06775/) (2026)
- [Closing the loop in learning with missing data](https://mlsanity.com/paper/2608.09030/) (2026)

## Abstract (arXiv)

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.