To prove this result, we invoke the theory of Gale-Stewart games. We introduce a novel two-player game, the Exponential GS Game outlined in algorithms:universal1. The structure of this game looks like the standard multiclass online learning game but has some evident differences; the adversary not only reveals a point \(\xi _t\)  but also two colors for it. Then, the learner should choose between these two.
The structure of this game (while unaccustomed) is crucial and generalizes the game of [1]}.
The learner wins if the class of consistent hypotheses \(\mathcal {H}_{\kappa _1,\eta _1,...,\kappa _t,\eta _t} = \lbrace  h \in \mathcal {H}: h(\xi _\ell ) = y_\ell ^{(\eta _\ell )} ~ \forall \ell \in [1..t] \rbrace \)  becomes empty after a finite number of rounds. If the game continues indefinitely, the adversary wins.
The intuition behind the definition of the class in algorithms:universal1 is that the adversary wins as long as there is always a hypothesis in \(\mathcal {H}\)  that is consistent with the examples (this is in parallel with the definition of an infinite path in the multiclass Littlestone tree). Using tools from Gale-Stewart games (thm:gale-stewart winning strategies), we manage to show that the learning player \(\texttt {P}_L\)  has a winning strategy if and only if \(\mathcal {H}\)  does not have an infinite multiclass Littlestone tree. This winning strategy is in fact the ordinal Standard Optimal Algorithm. Recall that it is possible to have unbounded multiclass Littlestone dimension while not having an infinite multiclass Littlestone tree.
