# The price of bandit information in multiclass online classification

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2013.

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

- [Multiclass Online Learnability under Bandit Feedback](https://mlsanity.com/paper/2308.04620/) (2023)
- [Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs](https://mlsanity.com/paper/2402.07453/) (2024)
- [Multiclass Transductive Online Learning](https://mlsanity.com/paper/2411.01634/) (2024)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [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)
- [Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learning](https://mlsanity.com/paper/2209.01366/) (2022)
- [Apple Tasting: Combinatorial Dimensions and Minimax Rates](https://mlsanity.com/paper/2310.19064/) (2023)
- [Bounds on the price of feedback for mistake-bounded online learning](https://mlsanity.com/paper/2401.05794/) (2024)
- [Deterministic Apple Tasting](https://mlsanity.com/paper/2410.10404/) (2024)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Quantum Learning Theory Beyond Batch Binary Classification](https://mlsanity.com/paper/2302.07409/) (2023)
- [Improved Regret Bounds for Bandits with Expert Advice](https://mlsanity.com/paper/2406.16802/) (2024)
- [Post-Training with Policy Gradients: Optimality and the Base Model Barrier](https://mlsanity.com/paper/2603.06957/) (2026)
- [A Characterization of Multioutput Learnability](https://mlsanity.com/paper/2301.02729/) (2023)
- [Partial Feedback Online Learning](https://mlsanity.com/paper/2601.21462/) (2026)
- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)
- [Neural Active Learning Meets the Partial Monitoring Framework](https://mlsanity.com/paper/2405.08921/) (2024)
- [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)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [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)
- [Thompson Sampling Is 2-Competitive for Mistakes](https://mlsanity.com/paper/2607.12389/) (2026)

## Abstract (arXiv)

We consider two scenarios of multiclass online learning of a hypothesis class Hsubseteq YX. In the em full information scenario, the learner is exposed to instances together with their labels. In the em bandit scenario, the true label is not exposed, but rather an indication whether the learner's prediction is correct or not. We show that the ratio between the error rates in the two scenarios is at most 8·|Y|· log(|Y|) in the realizable case, and tildeO(√|Y|) in the agnostic case. The results are tight up to a logarithmic factor and essentially answer an open question from (Daniely et. al. - Multiclass learnability and the erm principle). We apply these results to the class of γ-margin multiclass linear classifiers in realsd. We show that the bandit error rate of this class is tildeTheta(frac|Y|γ2) in the realizable case and tildeTheta(frac1γ√|Y|T) in the agnostic case. This resolves an open question from (Kakade et. al. - Efficient bandit algorithms for online multiclass prediction).