Before the formal proof, we provide a proof sketch. The adversary's strategy is clear. Whenever the learner predicts a label, she must choose a different label that will cause the learner to make a mistake in that round; an infinite Littlestone tree is exactly the combinatorial structure the adversary is looking for. On the other hand, since there is no infinite multiclass Littlestone tree, the learner's predictions should lead her to a leaf of the Littlestone tree that is defined by her interaction with the learner. This is established by a variant of the (multiclass) Standard Optimal Algorithm (SOA) [1]}, [2]}, which works whenever \(\mathcal {H}\)  has a finite multiclass Littlestone dimension \(d\) . To gain some intuition, it is instructive to consider the first step of her algorithm. The learner is presented with a point \(x_1\)  and she picks the label \(y_1 = \operatornamewithlimits{argmax}_{y\in [k]} \mathrm {Ldim}_k(\mathcal {H}_{x_1,y})\) . It is easy to see that there is at most one \(y\)  such that \(\mathrm {Ldim}_k(\mathcal {H}_{x_1,y}) = d\) ; if there were two of them then \(\mathrm {Ldim}_k(\mathcal {H}) = d+1\) . Thus, by picking the one that induces the subset of the hypothesis class with the largest Littlestone dimension, the learner either does not make a mistake or gets closer to a leaf of the tree.
