This algorithm drives the game in a win-win phenomenon for the learner in every round: If the adversary forces the learner to a mistake, then she will “prune” the tree and set the learner closer to winning the game. Otherwise, the learner will be correct and will not incur any loss.
In order to show that the ordinal SOA makes a finite number of mistakes, we couple the online game with a Gale-Stewart game.
The idea is that every time the learner makes a mistake in the online game on point \(x_t\) , we advance the Gale-Stewart game by one round where we pretend that \(\xi _{\tau } = x_t, y^{(0)}_{\tau } = \widehat{y}_t, y^{(1)}_{\tau } = y_t, \eta _{\tau } = y_t\) . Notice that if the learner makes an infinite number of mistakes in the online game using the ordinal SOA, then the Gale-Stewart game can proceed infinitely. Hence, to conclude the proof, we need to show that in this coupled game, there is some finite point \(\tau ^*\)  such that \(\mathcal {H}_{\xi _1, y_1^{(\eta _1)}, \ldots , \xi _{\tau ^{\star }}, y_{\tau ^{\star }}^{(\eta _{\tau ^{\star }})}} = \emptyset \) . The following result helps us establish that. In fact, the next lemma follows from [1]}(Proposition B.8) by choosing the value of the game being the ordinal multiclass Littlestone dimension.
