In our universal setting, this approach does not work immediately since it may be the case that the multiclass Littlestone tree is not infinite but the associated class has infinite multiclass Littlestone dimension. To this end, we have to introduce the ordinal multiclass Littlestone dimension, which quantifies “how infinite” the multiclass Littlestone dimension is. Hence, the learner's strategy will be to play according to the ordinal Standard Optimal Algorithm. The intuition is similar as in the classical setting, but the proof becomes more involved. To establish the result, we follow the approach of [1]} and define a more general infinite game \(\mathcal {G}\)  between the learner and the adversary and prove that it belongs to the family of the so-called Gale-Stewart games. Then, we leverage results from the theory of Gale-Stewart games and [1]} in order to show that the ordinal SOA makes a finite number of mistakes whenever \(\mathcal {H}\)  does not have an infinite multiclass Littlestone tree. Let us continue with the proof.
[Proof of thm:adversarial]
We first introduce a two-player game \(\mathcal {G}\)  that is played in discrete timesteps \(t=1,2,\ldots \)  between the adversary and the learner.
<FIGURE>