mlsanityData to 7 Oct 2026

The Real Price of Bandit Information in Multiclass Classification

arXiv 2405.10027 ↗First posted 16 May 2024cs.LG cs.AI stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

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√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 smashwidetildeThetaleft(min left|H| + √T, √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 smashwidetildeO(|H|+√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.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 20 of its 36 references that are in the map. First posted on arXiv 16 May 2024.

Builds on

20 of 36 references.

References · 20

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Introduction to Multi-Armed Banditscited by 475
  3. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  4. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 200
  5. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  6. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  7. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  8. 2021Adapting to Misspecification in Contextual Banditscited by 81
  9. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  10. 2014Minimax Analysis of Active Learningcited by 61
  11. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  12. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
8 more
  1. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  2. 2013The price of bandit information in multiclass online classificationcited by 24
  3. 2017Sparsity, variance and curvature in multi-armed banditscited by 24
  4. 2023Multiclass Online Learnability under Bandit Feedbackcited by 12
  5. 2015Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Casecited by 9
  6. 2021A note on the price of bandit feedback for mistake-bounded online learningcited by 9
  7. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  8. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 5.

7 papers.

  1. 2024Fast Rates for Bandit PAC Multiclass Classificationcited by 6
  2. 2025From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewardscited by 4
  3. 2026PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Settingcited by 1
  4. 2026The Sample Complexity of Multiclass and Sparse Contextual Banditscited by 1
  5. 2026On Randomized Algorithms in Online Strategic Classificationcited by 0
  6. 2026Policy Gradient with Adaptive Entropy Annealing for Continual Fine-Tuningcited by 0
  7. 2026Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenoncited by 0