mlsanityData to 7 Oct 2026

Multiclass Online Learnability under Bandit Feedback

arXiv 2308.04620 ↗First posted 8 Aug 2023cs.LG stat.MLcited by 12

Not on the map. Why?

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.

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

Builds on

9 of 21 references.

References · 9

  1. 2019VC Classes are Adversarially Robustly Learnable, but Only Improperlycited by 83
  2. 2022A Characterization of Multiclass Learnabilitycited by 66
  3. 2014Optimal Learners for Multiclass Problemscited by 65
  4. 2021Adversarial Laws of Large Numbers and Optimal Regret in Online Classificationcited by 39
  5. 2013The price of bandit information in multiclass online classificationcited by 24
  6. 2023Multiclass Online Learning and Uniform Convergencecited by 19
  7. 2023Optimal Prediction Using Expert Advice and Randomized Littlestone Dimensioncited by 18
  8. 2021A note on the price of bandit feedback for mistake-bounded online learningcited by 9
  9. 2023Online Learning with Set-Valued Feedbackcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 3; 2026: 4.

12 papers.

  1. 2024Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffscited by 9
  2. 2024Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classificationcited by 8
  3. 2024The Real Price of Bandit Information in Multiclass Classificationcited by 7
  4. 2024Fast Rates for Bandit PAC Multiclass Classificationcited by 6
  5. 2023Apple Tasting: Combinatorial Dimensions and Minimax Ratescited by 4
  6. 2025From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewardscited by 4
  7. 2026Partial Feedback Online Learningcited by 2
  8. 2025Faster Rates for Private Adversarial Banditscited by 1
  9. 2025A Tight Lower Bound for Non-stochastic Multi-armed Bandits with Expert Advicecited by 1
  10. 2026The Sample Complexity of Multiclass and Sparse Contextual Banditscited by 1
  11. 2026Robust Online Learningcited by 0
  12. 2026Closing the loop in learning with missing datacited by 0