New bounds on the price of bandit feedback
for mistake-bounded online multiclass learning
Philip M. LongGoogle, 1600 Amphitheatre Parkway, Mountain View, CA 94043 USA. Email: plong@google.com.

Abstract
This paper is about two generalizations of the mistake bound model to online multiclassclassification. In the standard model, the learner receives the correct classification at
the end of each round, and in the bandit model, the learner only finds out whether its
prediction was correct or not. For a set F of multiclass classifiers, let optstd (F) andoptbandit (F) be the optimal bounds for learning F according to these two models. We
show that anoptbandit (F) ≤ (1 + o(1))(|Y| ln |Y|)optstd (F)bound is the best possible up to the leading constant, closing a Θ(log |Y|) factor gap.
Keywords: online learning, bandit feedback, mistake-bound model, learning theory
68T05

1. Introduction
There are two natural ways to generalize the mistake-bound model [17] to multiclass classification [5].
In the standard model, for a set F of functions from some set X to a finite set Y, foran arbitrary f ∈ F that is unknown to the algorithm, learning proceeds in rounds, andin round t, the algorithm• receives xt ∈ X,
• predicts ŷt ∈ Y, and• gets f (xt ).
The goal is to bound the number of prediction mistakes in the worst case, over all
possible f ∈ F and x1 , x2 , ... ∈ X.
The bandit model [12, 11, 14] (called “weak reinforcement” in [5, 4]) is like thestandard model, except that, at the end of each round, the algorithm only finds out
whether ŷt = f (xt ) or not.
Obviously, optstd (F) ≤ optbandit (F). It is known [4] that, for all F,optbandit (F) ≤ (2.01 + o(1)) (|Y| ln |Y|) optstd (F),
Preprint submitted to Theoretical Computer Science(1)

February 11, 2019and that, for any k and M, there is a set F of functions from a set X to a set Y of size ksuch that optstd (F) = M andoptbandit (F) ≥ (|Y| − 1) optstd (F),so that (1) cannot be improved by more than a log factor.
This note shows that, for all M > 1 and infinitely many k, there is a set F offunctions from a set X to a set Y of size k such that optstd (F) = M andoptbandit (F) ≥ (1 − o(1)) (|Y| ln |Y|) optstd (F),(2)optbandit (F) ≤ (1 + o(1)) (|Y| ln |Y|) optstd (F)(3)

and that an
bound holds for all F.
Previous work. In addition to the bounds described above, on-line learning withbandit feedback, side-information and adversarially chosen examples has been heavily
studied (see [15, 3, 1, 2, 16, 10, 8, 11]). Daniely and Halbertal [13] studied the priceof bandit feedback in the agnostic on-line model, where there is not necessarily anf ∈ F that always provides the correct classification, and the online learning algorithm
is evaluated by comparing its number of mistakes with the best mistake count possible
in hindsight obtained by repeatedly applying a classifier in F. The proof of (2) uses
analytical tools that were previously used for experimental design [21, 22], and hashing, derandomization and cryptography [9, 19]. The proof of (3) uses tools based on
the Weighted Majority algorithm [18, 4].
2. Preliminaries and main results
2.1. Definitions
Define optbs (k, M) to be the best possible bound on optbandit (F) in terms of M =optstd (F) and k = |Y|. In other words, optbs (k, M) is the maximum, over sets X and sets
F of functions from X to {0, ..., k − 1} such that optstd (F) = M, of optbandit (F).
We denote the limit supremum by lim.
2.2. Result
The following is our main result.
Theorem 1.
lim M→∞ limk→∞

optbs (k, M)= 1.
kM ln k2.3. The extremal case
For any prime p, let F L (p, n) be the set of all linear functions from {0, ..., p − 1}n to{0, ..., p − 1}, where operations are done with respect the finite field GF(p).
In other words, for each a ∈ {0, ..., p − 1}n , let fa : {0, ..., p − 1}n → {0, ..., p − 1} bedefined byfa (x) = (a · x) mod p2

and let F L (p, n) = { fa : a ∈ {0, ..., p − 1}n }.
The fact thatoptstd (F L (p, n)) = n(4)for all primes p ≥ 2 is essentially known (see [23, 5, 6]). (An algorithm can achieve amistake bound of n by exploiting the linearity of the target function to always predict
correctly whenever xt is in the span of previously seen examples. An adversary canforce mistakes on any linearly independent set of the domain by answering whicheverof 0 or 1 is different from the algorithm’s prediction.)
3. Lower bounds
Our lower bound proof will use an adversary that maintains a version space [20],a subset of F L (p, n) that could still be the target. To keep the version space large nomatter what the algorithm predicts, the adversary chooses a xt for round t that divides
it evenly. The first lemma analyzes its ability to do this.
Lemma 1. For any S ⊆ {1, ..., p − 1}n , there is a u such that for all z ∈ {0, ..., p − 1},p|{s ∈ S : s · u = z mod p}| ≤ |S |/p + 2 |S |.
Lemma 1 is similar to analyses of hashing (see [7]).
Lemma 1 is proved using the probabilistic method. The next two lemmas about
the distribution of splits for random domain elements may already be known; see e.g.
[19, 7] for proofs of some closely related statements. We included proofs in appendicesbecause we do not know a reference with proofs for exactly the statements needed here.
Lemma 2. Assume n ≥ 1. For u chosen uniformly at random from {0, ..., p − 1}n , forany s ∈ {0, ..., p − 1}n − {0} for any z ∈ {0, ..., p − 1}, we havePr(s · u = z mod p) = 1/p.
Proof: See Appendix A.

Lemma 3. Assume n ≥ 2. For u chosen uniformly at random from {0, ..., p − 1}n , forany s, t ∈ {1, ..., p − 1}n such that s , t, and for any z ∈ {0, ..., p − 1}, we havePr(t · u = z mod p | s · u = z mod p) = 1/p.
Proof. See Appendix B.
Armed with Lemmas 2 and 3, we are ready for the proof of Lemma 1.

Proof (of Lemma 1): Let S be an arbitrary subset of {1, ..., p − 1}n . Choose u
uniformly at random from {0, ..., p − 1}n . For each z ∈ {0, ..., p − 1}, let S z be the(random) set of s ∈ S such that s · u = z mod p. Lemma 2 implies that, for all z,
E(|S z |) = |S |/p3

and, since Lemmas 2 and 3 imply that the events that s · u = z are pairwise independent,Var(|S z |) = Var(1s·u=z )|S | = (1/p)(1 − 1/p)|S | < |S |/p.
Using Chebyshev’s inequality,p1
Pr(|S z | ≥ |S |/p + 2 |S |) ≤.
4p
Applying a union bound, with probability at least 3/4,√∀z, |S z | ≤ |S |/p + 2 S ,completing the proof.
Now we are ready for the learning lower bound.
Lemma 4.
limn→∞ lim p→∞

optbandit (F L (p, n))≥ 1.
pn ln p(5)Proof: Choose n ≥ 3 and p ≥ 5. Consider an adversary that maintains a list Ft ofmembers of{ fa : a ∈ {1, ..., p − 1}n } ⊆ F L (p, n)that are consistent with its previous answers, always answers “no”, and picks xt for
round t that splits Ft as evenly as possible; that is, xt minimizes the maximum, overpotential values of ŷt , of |Ft ∩ { f : f (xt ) = ŷt }|. As long as |Ft | ≥ p2 ln p, Lemma 1
implies that,p|Ft |− 2 |Ft |p|Ft |2|Ft |≥ |Ft | −− ppp ln p
p

 1 + 2/ ln p = 1 −  |Ft |.
p|Ft+1 | ≥ |Ft | −Thus, by induction, we havet−1p 1 + 2/ ln p 
 (p − 1)n .
|Ft | ≥ 1 − p
The adversary can force m mistakes before |Ft | < p2 ln p if

m−1p

1 + 2/ ln p 1 −
(p − 1)n ≥ p2 ln pp
which is true for m = (1 − o(1))np ln p, proving (5).
4

4. Upper boundThe upper bound proof closely follows the arguments in [18, 4].
Lemma 5. For any set F of functions from some set X to {0, ..., k − 1},
optbandit (F) ≤ (1 + o(1))(k ln k)optstd (F).
Proof: Consider an algorithm Ab for the bandit model, which uses an algorithm A s forthe standard model as a subroutine, defined as follows. Algorithm Ab maintains a listof copies of algorithm A s that have been given different inputs. For α = k ln1 k , each copyof A s is given a weight: if it has made m mistakes, its weight is αm . In each round, Abuses these weights to make its prediction by taking a weighted vote over the predictions
made by the copies of A s .
Algorithm Ab starts with a single copy. Whenever it makes a mistake, all copies
of A s that made a prediction that was not used by Ab “forget” the round – their stateis rewound as if the round did not happen. Each copy of A s that voted for the winneris cloned, including its state, to make k − 1 copies, and each copy is given a different“guess” of f (xt ).
Let Wt be the total weight of all of the copies of A s before round t. Since one copyof A s always gets correct information, for all t, we have
Wt ≥ αoptstd (F) .

(6)

On the other hand, after each round t in which Ab makes a mistake, copies of A s
whose total weight is at least Wt /k are cloned to make k − 1 copies, each with weightα < 1/(k − 1) times its old weight. Thus
Wt+1 ≤ (1 − 1/k)Wt + (1/k)(α(k − 1)Wt ) < (1 − 1/k)Wt + αWt
and, after Ab has made m mistakes,
Wt < (1 − 1/k + α)m < e−(1/k−α)m .
Combining with (6) yieldse−(1/k−α)m > αoptstd (F)which implies m ≤ln(1/α)optstd (F)and substituting the value of α completes the proof. 1/k−α

5. Putting it together
Theorem 1 follows from (4), Lemma 4, and Lemma 5.
6. Two open problems
Can the analysis of F L (p, n) improve our understanding of the cost of bandit feedback in the agnostic case?
It is not hard to see that optbs (k, 1) = k − 1 = Θ(k), and the proofs of Lemmas 4 and5 imply that optbs (k, 3) = Θ(k log k). What about optbs (k, 2)?
5

Acknowledgements
We thank anonymous reviewers for helpful comments, and Yoram Singer for avaluable conversation.
Appendix A. Proof of Lemma 2
Pick i such that si , 0. We havePr(u · s = z mod p) = Pr(ui si = z −Xujsjmod p)j,i Xu j s j  s−1= Pr(ui = z −imod p)j,i= 1/p,completing the proof.
Appendix B. Proof of Lemma 3
Let i be one component such that si , ti . Let s0 , t0 and u0 be the projections of s, tand u onto the indices other than i.
Lemma 2 implies that s0 · u0 mod p is distributed uniformly on {0, ..., p − 1}. Thus,
after conditioning on the event that s · u = z mod p, ui is uniform over {0, ..., p − 1},which implies
Pr(t · u = z mod p | s · u = z mod p)= Pr(ui (ti − si ) = (s0 − t0 ) · u0mod p | s · u = z mod p)= 1/p,
completing the proof.
References[1] N. Abe, A. W. Biermann, and P. M. Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263–293, 2003.
[2] P. Auer. Using confidence bounds for exploitation-exploration trade-offs. Journalof Machine Learning Research, 3(Nov):397–422, 2002.
[3] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic
multiarmed bandit problem. SIAM J. Comput., 32(1):48–77, 2002.
[4] P. Auer and P. M. Long. Structural results about on-line learning models with andwithout queries. Machine Learning, 36(3):147–181, 1999.
[5] P. Auer, P. M. Long, W. Maass, and G. J. Woeginger. On the complexity offunction learning. Machine Learning, 18(2-3):187–230, 1995.
6

[6] A. Blum. On-line algorithms in machine learning. In Online algorithms, pages
306–325. Springer, 1998.
[7] A. Blum. https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf,
2011. Accessed on Nov 20, 2016.
[8] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic
multi-armed bandit problems. Foundations and Trends in Machine Learning,
5(1):1–122, 2012.
[9] J. L. Carter and M. N. Wegman. Universal classes of hash functions. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages
106–112. ACM, 1977.
[10] W. Chu, L. Li, L. Reyzin, and R. E. Schapire. Contextual bandits with linear
payoff functions. In AISTATS, volume 15, pages 208–214, 2011.
[11] K. Crammer and C. Gentile. Multiclass classification with bandit feedback using
adaptive regularization. Machine learning, 90(3):347–383, 2013.
[12] V. Dani, T. P. Hayes, and S. M. Kakade. Stochastic linear optimization underbandit feedback. In COLT, pages 355–366, 2008.
[13] A. Daniely and T. Halbertal. The price of bandit information in multiclass online
classification. In Conference on Learning Theory, pages 93–104, 2013.
[14] E. Hazan and S. Kale. Newtron: an efficient bandit algorithm for online multiclassprediction. In Advances in Neural Information Processing Systems, pages 891–899, 2011.
[15] D. P. Helmbold, N. Littlestone, and P. M. Long. Apple tasting. Information andComputation, 161(2):85–139, 2000. Preliminary version in FOCS’92.
[16] S. M. Kakade, S. Shalev-Shwartz, and A. Tewari. Efficient bandit algorithms foronline multiclass prediction. In Proceedings of the 25th international conference
on Machine learning, pages 440–447. ACM, 2008.
[17] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linearthreshold algorithm. Machine learning, 2(4):285–318, 1988.
[18] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 256–261.
IEEE, 1989.
[19] M. G. Luby and A. Wigderson. Pairwise independence and derandomization,
volume 4. Now Publishers Inc, 2006.
[20] T. M. Mitchell. Version spaces: A candidate elimination approach to rulelearning. In Proceedings of the 5th international joint conference on Artificial
intelligence-Volume 1, pages 305–310. Morgan Kaufmann Publishers Inc., 1977.

7

[21] C. R. Rao. Hypercubes of strength d leading to confounded designs in factorialexperiments. Bulletin of the Calcutta Mathematical Society, 38:67–78, 1946.
[22] C. R. Rao. Factorial experiments derivable from combinatorial arrangements ofarrays. Supplement to the Journal of the Royal Statistical Society, pages 128–139,
1947.
[23] H. Shvaytser. Linear manifolds are learnable from positive examples, 1988. Unpublished manuscript.

8