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

The standard model and the bandit model are two generalizations of the\nmistake-bound model to online multiclass classification. In both models the\nlearner guesses a classification in each round, but in the standard model the\nlearner recieves the correct classification after each guess, while in the\nbandit model the learner is only told whether or not their guess is correct in\neach round. For any set $F$ of multiclass classifiers, define $opt_{std}(F)$\nand $opt_{bandit}(F)$ to be the optimal worst-case number of prediction\nmistakes in the standard and bandit models respectively.\n Long (Theoretical Computer Science, 2020) claimed that for all $M > 2$ and\ninfinitely many $k$, there exists a set $F$ of functions from a set $X$ to a\nset $Y$ of size $k$ such that $opt_{std}(F) = M$ and $opt_{bandit}(F) \\ge (1 -\no(1))(|Y|\\ln{|Y|})opt_{std}(F)$. The proof of this result depended on the\nfollowing lemma, which is false e.g. for all prime $p \\ge 5$, $s = \\mathbf{1}$\n(the all $1$ vector), $t = \\mathbf{2}$ (the all $2$ vector), and all $z$.\n Lemma: Fix $n \\ge 2$ and prime $p$, and let $u$ be chosen uniformly at random\nfrom $\\left\\{0, \\dots, p-1\\right\\}^n$. For any $s, t \\in \\left\\{1, \\dots,\np-1\\right\\}^n$ with $s \\neq t$ and for any $z \\in \\left\\{0, \\dots,\np-1\\right\\}$, we have $\\Pr(t \\cdot u = z \\mod p \\text{ } | \\text{ } s \\cdot u =\nz \\mod p) = \\frac{1}{p}$.\n We show that this lemma is false precisely when $s$ and $t$ are multiples of\neach other mod $p$. Then using a new lemma, we fix Long's proof.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC