# A note on the price of bandit feedback for mistake-bounded online learning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 11 references that are in the map.
- First posted on arXiv 18 Jan 2021.

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

- [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)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [Sharp bounds on the price of bandit feedback for several models of mistake-bounded online learning](https://mlsanity.com/paper/2209.01366/) (2022)
- [Bounds on the price of feedback for mistake-bounded online learning](https://mlsanity.com/paper/2401.05794/) (2024)
- [Mistake-bounded online learning with operation caps](https://mlsanity.com/paper/2509.03892/) (2025)
- [Learning from Equivalence Queries, Revisited](https://mlsanity.com/paper/2604.04535/) (2026)
- [Online learning of smooth functions on ℝ](https://mlsanity.com/paper/2604.03525/) (2026)

## Abstract (arXiv)

The standard model and the bandit model are two generalizations of the mistake-bound model to online multiclass classification. In both models the learner guesses a classification in each round, but in the standard model the learner recieves the correct classification after each guess, while in the bandit model the learner is only told whether or not their guess is correct in each round. For any set F of multiclass classifiers, define optstd(F) and optbandit(F) to be the optimal worst-case number of prediction mistakes in the standard and bandit models respectively. Long (Theoretical Computer Science, 2020) claimed that for all M > 2 and infinitely many k, there exists a set F of functions from a set X to a set Y of size k such that optstd(F) = M and optbandit(F) ≥ (1 - o(1))(|Y|ln|Y|)optstd(F). The proof of this result depended on the following lemma, which is false e.g. for all prime p ≥ 5, s = 1 (the all 1 vector), t = 2 (the all 2 vector), and all z. Lemma: Fix n ≥ 2 and prime p, and let u be chosen uniformly at random from left0, dots, p-1rightn. For any s, t ∈ left1, dots, p-1rightn with s neq t and for any z ∈ left0, dots, p-1right, we have Pr(t · u = z mod p   |   s · u = z mod p) = frac1p. We show that this lemma is false precisely when s and t are multiples of each other mod p. Then using a new lemma, we fix Long's proof.